Parallel Algorithms and Data Parallelism
Reason about parallel algorithms with work and span, choose the right decomposition and schedule, and know the hardware effects (bandwidth, caches, SIMD/SIMT) that decide whether parallel code actually runs faster.
Key points
- 1
Work T₁ is total operations and span T∞ is the critical path; parallelism T₁/T∞ caps speedup, and Brent's bound gives Tₚ ≤ T₁/p + T∞.
- 2
Parallel reductions and scans need an associative operator. Floating-point addition is not associative in practice, so parallel float sums can differ from sequential ones and between thread counts.
- 3
Blelloch's scan is work-efficient (O(n) work, O(log n) span); Hillis-Steele has a shorter span but O(n log n) work.
- 4
Use a sequential cutoff in fork-join code, and prefer dynamic scheduling or work stealing when iteration costs vary.
- 5
Memory-bound kernels stop scaling once DRAM bandwidth saturates; the roofline model (min of peak compute and bandwidth × arithmetic intensity) predicts this.
- 6
On GPUs, branch divergence within a warp serializes paths, and uncoalesced memory access wastes bandwidth.
- 7
Hot keys, stragglers and barriers make the slowest worker set the pace; salting, combiners and over-decomposition spread the load.
Common traps
Assuming more threads always help: oversubscription, false sharing and bandwidth limits can make 32 threads slower than 8.
Expecting bit-identical float sums from a parallel reduction whose grouping depends on thread count or arrival order.
Giving every worker the same random seed, which turns independent Monte Carlo samples into copies of one run.
Read the source
Test yourself on Parallel Algorithms and Data Parallelism
Ten questions, with the answer and explanation after each one.