The Work And Span Model
To reason about a parallel algorithm independently of how many processors run it, we use two numbers: work and span.
Two key quantities
- Work is the total number of operations, equal to the running time on a single processor.
- Span is the length of the longest chain of dependent operations, equal to the running time on unlimited processors.
The ratio of work to span is the parallelism, the average speedup the algorithm could reach with enough processors.
Brent bound
A scheduler running on a fixed number of processors achieves a running time near the work divided by the processor count plus the span. This is the Brent style bound:
- More processors help only down to the span.
- The span is a hard floor no processor count can beat.
So a good parallel algorithm keeps work close to the best serial cost while shrinking the span as much as possible.
Key idea
Work is the serial cost and span is the unavoidable critical path, and their ratio bounds how much speedup parallelism can ever deliver.