Algorithms · Cluster
Parallel Algorithms
Work, span, and concurrency in algorithm design.
- 01 Work, Span, and the Bound on Parallel Execution Time How a computation DAG yields two numbers, work and span, and why their ratio rather than the processor count sets the achievable speedup.
- 02 Reduction Trees and What Associativity Buys Why a reduction needs an associative operator to be reordered, how tree shape changes floating-point results, and what error bounds the shapes imply.
- 03 Work Stealing: Per-Processor Deques and Why Thieves Take the Oldest Task How a work-stealing scheduler keeps locality by pushing and popping on one end of a deque while idle processors take from the other, and where the contention lands.
- 04 Parallel Prefix Scan: Hillis-Steele Versus Blelloch Two scan algorithms with the same span class and different work, the up-sweep and down-sweep that make Blelloch work-optimal, and the arithmetic that decides between them.
- 05 Merge-Path Partitioning: Splitting Two Sorted Runs Without Sampling How binary search over the merge path cuts two sorted arrays into equal-sized pieces at the correct values, and why the split is exact rather than statistical.
- 06 Granularity and the Sequential Cut-Off How to size parallel tasks so that scheduling overhead stays below the work they contain, and how the optimum shifts with span, memory behaviour, and the runtime.
- 07 Amdahl, Gustafson, and the Fixed-Problem Fallacy Why the two scaling laws disagree, which quantity each holds constant, and how the choice of fixed time versus fixed problem size changes the predicted ceiling.
- 08 PRAM Variants and the Cost of Ignoring Memory What the EREW, CREW, and CRCW models permit, how work and depth carry over from the DAG, and why a model with free memory access mispredicts real parallel time.
- 09 Data Races, Memory Models, and Where Parallel Algorithms Lose Determinism How relaxed memory ordering breaks the intuitive interleaving model, what the C and C++ memory model guarantees, and why race-free parallel code can still be non-deterministic.
- 10 Supersteps and Message Bounds: Why Distributed Parallelism Costs More How the BSP model charges for latency and bandwidth per round, what the h-relation says about all-to-all traffic, and why matrix multiplication needs more memory per processor to avoid moving data.