CS329 Efficient Parallel Algorithms
This module is not running 2011/12
Academic Aims
To study parallel computation models and fundamental techniques in the design and analysis of parallel algorithms.
Learning Outcomes
Upon successful completion of the module students should be able to
- Understand the role of computation models in parallel computation;
- Understand the circuit and comparison network models;
- Understand the basics of merging and sorting networks;
- Understand the PRAM and BSP models and their theoretical foundations;
- Understand and analyse a number of fundamental parallel algorithms from various application domains.
Content
- Basic parallel computation models: circuits, comparison networks. Parallel merging and sorting by comparison networks.
- Advanced parallel computation models: PRAM, BSP.
- Fundamental parallel algortihms: total exchange, broadcast/combine, prefix sums, butterfly, grid.
- Further parallel algorithms: list and tree contraction, sorting, convex hull.
- Parallel matrix algorithms: matrix-vector multiplication, matrix multiplication, triangular system solution, Gaussian elimination.
- Parallel graph algorithms: algebraic paths, all-pairs shortest paths, minimum spanning tree.
