Parallel Computation¶
Parallel speedup is limited by dependencies, coordination, memory bandwidth, and the sequential fraction of a program.
Work and span¶
- Work
T₁is time on one processor. - Span
T∞is the longest dependency chain with unlimited processors. - Parallelism is bounded by
T₁ / T∞.
A parallel algorithm should minimize both total work and the critical path. An algorithm with extra work can lose even if its theoretical span is smaller.
Amdahl's law¶
If fraction s is inherently sequential and the rest scales perfectly on p
processors, ideal speedup is bounded by:
As p grows, speedup approaches 1/s. The model is simplified but exposes why
small sequential bottlenecks matter.
Fork/Join¶
Divide work until tasks are large enough to amortize scheduling overhead, then compute directly. Thresholds depend on workload and hardware and should be measured. Work-stealing helps balance irregular tasks but cannot repair a fundamentally sequential dependency.
Hazards¶
- oversubscription and excessive task creation;
- contention or false sharing between nearby mutable fields;
- memory bandwidth saturation;
- non-associative reductions producing different rounding;
- nested parallelism using the same constrained resources;
- blocking in a pool designed for compute work.
Use representative end-to-end measurements, not only microbenchmarks, when the goal is application throughput or latency.