When one running time is no longer enough: work and span, the two numbers that describe how much an algorithm does and how fast it could possibly go.
Clock speeds stopped rising; core counts did not. An algorithm that cannot be decomposed leaves most of a modern machine idle. Chapter 26 develops task-parallel algorithms, where you express the available parallelism and a runtime scheduler assigns it to processors. The analysis changes shape: instead of one running time you compute two quantities, work and span, and their ratio tells you how many processors the algorithm can usefully absorb.
CLRS uses three keywords layered on ordinary serial pseudocode.
| Keyword | Meaning |
|---|---|
spawn | The named subroutine may run in parallel with the caller. The caller continues immediately rather than waiting. |
sync | Wait here until all children spawned by this procedure have finished. |
parallel for | All iterations of the loop may run concurrently. |
An execution is modelled as a computation dag: vertices are strands of serial execution, edges are dependencies. spawn creates a fork, sync creates a join.
T₁ is the total time on one processor — the number of vertices in the dag.T∞ is the time on infinitely many processors — the longest path through the dag, also called the critical path.T₁/T∞: the maximum possible speedup, and therefore the largest processor count worth using.Two laws bound the time Tᴵ on P processors:
Work law: Tᴵ ≥ T₁ / P // P processors do at most P units per step
Span law: Tᴵ ≥ T∞ // cannot beat the critical path, everComposing the measures is simple:
| Composition | Work | Span |
|---|---|---|
| Series (A then B) | T₁(A) + T₁(B) | T∞(A) + T∞(B) |
| Parallel (A alongside B) | T₁(A) + T₁(B) | max(T∞(A), T∞(B)) |
max instead of +.CLRS assumes a greedy scheduler: at every step, if at least P strands are ready, run P of them; otherwise run all that are ready.
P processors, a greedy scheduler executes a computation in timeTᴵ ≤ T₁/P + T∞Since the two lower bounds are T₁/P and T∞, this is within a factor of 2 of optimal. The practical reading: when the parallelism T₁/T∞ substantially exceeds P, the T₁/P term dominates and you get near-linear speedup. This condition is called having ample parallel slackness.
s of an algorithm is inherently serial, the span is at least s·T₁, so parallelism is at most 1/s however many processors you buy. A 5% serial fraction caps speedup at 20×. This is why span, not work, is the number to attack.P-FIB(n)
1 if n ≤ 1
2 return n
3 x = spawn P-FIB(n-1) // may run in parallel
4 y = P-FIB(n-2) // caller continues immediately
5 sync // wait for x
6 return x + yT₁(n) = Θ(φⁿ) — exponential, exactly as in the serial version.T∞(n) = T∞(n-1) + Θ(1) = Θ(n), since the two branches run in parallel and only the deeper one counts.Θ(φⁿ/n) — enormous.P-FIB has spectacular parallelism and is still an exponential-work disaster. A linear-time serial loop beats it at every input size. Optimise work first, span second — parallelism cannot rescue a bad asymptotic.MAT-VEC(A, x, n)
1 parallel for i = 1 to n
2 yᵢ = 0
3 parallel for i = 1 to n
4 for j = 1 to n
5 yᵢ = yᵢ + aᵢⱼxⱼ
6 return yA parallel for is implemented by recursive halving: split the range in two, spawn one half, recurse on the other. That produces a balanced binary spawn tree of depth lg n, so loop control contributes Θ(lg n) to the span rather than Θ(n).
For MAT-VEC: work is Θ(n²), span is Θ(n) because the inner serial loop dominates, so parallelism is Θ(n).
Parallelising the divide-and-conquer version from Chapter 4 gives an outstanding result.
P-MATRIX-MULTIPLY-RECURSIVE:
Work: T₁(n) = 8T₁(n/2) + Θ(1) = Θ(n³)
Span: T∞(n) = T∞(n/2) + Θ(lg n) = Θ(lg² n)
Parallelism: Θ(n³ / lg² n)Θ(n³) — the same total computation — but the critical path collapses to polylogarithmic. Parallelism of n³/lg² n is roughly a billion for n = 1000, far more than any real machine can use, which is exactly what you want.The naive attempt spawns the two recursive sorts but leaves MERGE serial:
Work: Θ(n lg n) Span: T∞(n) = T∞(n/2) + Θ(n) = Θ(n)
Parallelism: Θ(lg n) // poor — the serial merge is the bottleneckThe fix is a parallel merge. To merge two sorted arrays, take the median of the larger one, binary search for its position in the smaller, and recursively merge the two resulting pairs of pieces in parallel.
P-MERGE: Work Θ(n), Span Θ(lg² n)
P-MERGE-SORT: Work Θ(n lg n), Span Θ(lg³ n)
Parallelism Θ(n / lg² n)Θ(n lg n); all the effort went into reducing the span from Θ(n) to Θ(lg³ n), taking parallelism from a useless lg n to a useful n/lg² n. Find the serial bottleneck and parallelise it.RACE-EXAMPLE()
1 x = 0
2 parallel for i = 1 to 2
3 x = x + 1 // read, add, write — not atomic
4 print x // prints 2, or sometimes 1Both strands may read x = 0 before either writes, so one increment is lost. The algorithms in this chapter are written to be determinate: parallel strands touch disjoint memory, so the result is identical to the serialization on every run. That discipline is what makes them testable.
spawn and sync, then run a race detector.spawn, sync, and parallel for express logical parallelism. Deleting them gives the serialization, a correct serial program.T₁ is total computation; span T∞ is the critical path; parallelism is T₁/T∞, the most processors worth using.Tᴵ ≥ T₁/P and span law Tᴵ ≥ T∞. A greedy scheduler achieves Tᴵ ≤ T₁/P + T∞, within 2× of optimal.max. That max is where all the benefit lives.s caps parallelism at 1/s.P-FIB has enormous parallelism and exponential work, and is useless. Parallel matrix multiply achieves Θ(n³) work with Θ(lg² n) span.Θ(n) to Θ(lg³ n). Beware determinacy races: keep parallel strands on disjoint memory.Chapter 27 changes the model again, in a different direction. An online algorithm receives its input one piece at a time and must commit to a decision on each before seeing the rest — and is measured by its competitive ratio against the offline optimum that saw everything in advance.