main page — CS 566 Efficient Algorithms
Unit 10: Parallel Algorithms
This is an archived version of this module from Winter 2024-25.
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
- Know and apply parallelization strategies for embarrassingly parallel problems.
- Identify limits of parallel speedups.
- Understand and use the parallel random-access-machine model in its different variants.
- Be able to analyze and compare simple shared-memory parallel algorithms by determining parallel time and work.
- Understand efficient parallel prefix sum algorithms.
- Be able to devise high-level description of parallel quicksort and mergesort methods.
Material
- slides
- Video 10-1 (2024-12-17):
§10.1 Parallel computation, PRAM
- Video 10-2 (2025-01-13):
§10.2 Parallel string matching
- Video 10-3 (2025-01-13):
§10.3 Parallel primitives, prefix sum, compaction
- Video 10-4 (2025-01-13):
§10.4 Parallel sorting
Further reading and sources
The presentation of parallel algorithms takes some inspiration from Uzi Vishkin’s class notes:
Further background on parallel algorithms (using the fork-join model of computation instead of full PRAM) can be found in here: