main page — COMP 526 Applied Algorithmics
Unit 7: 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
- 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 7-1 (2023-11-17):
§7.1 Parallel computation, PRAM
- Video 7-2 (2023-11-23):
§7.1 Brent’s Theorem
- Video 7-3 (2023-11-23):
§7.2 Parallel string matching
- Video 7-4 (2023-11-23):
§7.3 Parallel primitives, prefix sum, compaction
- Video 7-5 (2023-11-23):
§7.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: