Unit 10: Parallel Algorithms

This unit covers machine models and some algorithms for parallel computation:

• parallel RAM (PRAM) model
• exploiting embarrassingly parallel problems
• parallel string matching
• parallel prefix sums
• parallel mergesort and quicksort

Learning outcomes

1. Know and apply parallelization strategies for embarrassingly parallel problems.
2. Identify limits of parallel speedups.
3. Understand and use the parallel random-access-machine model in its different variants.
4. Be able to analyze and compare simple shared-memory parallel algorithms by determining parallel time and work.
5. Understand efficient parallel prefix sum algorithms.
6. Be able to devise high-level description of parallel quicksort and mergesort methods.

Material

• slides (preliminary)

---

Further reading and sources

The presentation of parallel algorithms takes some inspiration from Uzi Vishkin’s class notes:

• Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques

Further background on parallel algorithms (using the fork-join model of computation instead of full PRAM) can be found in here:

• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms 3rd ed (2009), MIT Press

---

Unit 9  ⋅  Syllabus  ⋅  Unit 11