The question this answers
How much parallelism does this computation actually contain, before I go looking for a machine to run it on?
Two computations over the same 100-million-element array: summing it with a binary tree of additions, and sorting it with a merge sort whose merges are sequential.
Nothing mutable in either computation — both are pure task graphs over disjoint data. That is deliberate: work and span are properties of the *dependency structure*, and they impose a ceiling even when there is no contention, no lock and no shared state at all.
For every schedule on P workers, the completion time T_P satisfies T_P ≥ max(W/P, S): you can never do the work faster than P workers allow, and you can never finish before the longest dependency chain has run end to end.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
Two numbers, and the ratio between them
Work (W) is the total number of elementary operations the parallel computation performs — equivalently, how long it takes on one worker. Span (S), also called depth or critical-path length, is the number of operations on the longest chain of dependencies — equivalently, how long it takes on infinitely many workers. Both are properties of the algorithm and its dependency graph, measurable on paper before any hardware exists.
Their ratio W/S is the parallelism: the average amount of work available to be done simultaneously, and therefore the maximum useful worker count. Above it, extra workers have nothing to do — not because of overhead, not because of contention, but because the graph does not contain enough independent work. This is the cleanest ceiling in the whole domain and the one people most often skip past on their way to buying cores.
The two lower bounds are worth stating separately because they bind in different regimes. Work law: T_P ≥ W/P — P workers cannot do W operations faster than that. Span law: T_P ≥ S — the chain has to run. Below the parallelism, the work law binds and adding workers helps roughly linearly. Above it, the span law binds and adding workers does nothing at all. And Brent's bound gives the other side: a greedy scheduler achieves T_P ≤ W/P + S, so a decent runtime gets within a factor of two of the best possible schedule. That is a strong statement: if your computation has parallelism, an ordinary work-stealing scheduler will find it — so a disappointing speedup is usually a span problem, not a scheduler problem.
- W = 4+10+6+6+4+8+6+4 = 48 ticks of work in total.
- Two chains tie for longest: A→B→F→G→H and A→D→E→F→G→H, both 32 ticks. So S = 32 and parallelism is 48/32 = 1.5.
- Parallelism of 1.5 means this pipeline cannot usefully occupy two workers, let alone eight — and that is a fact about the graph, discoverable before any code runs.
- B is on the critical path and takes 10 ticks; C is not on it at all. Halving B shortens the span; halving C changes nothing. That is the practical use of span, and the biggest task is often not the one that matters.
The same input, two algorithms, two completely different ceilings
Summing 100 million numbers with a balanced tree has W = 100M additions and S = log₂(100M) ≈ 27 levels. Parallelism is roughly 3.7 million — for any machine you can buy, this computation is effectively unlimited, and speedup will be capped by memory bandwidth and overhead rather than by structure.
Merge-sorting the same array has W ≈ n log n ≈ 2.7 billion comparisons, but if the merges are sequential the span is dominated by the final merge of two 50-million-element runs, giving S ≈ 2n = 200 million. Parallelism is about 13. Thirteen. On a 64-core machine, 51 cores have nothing to do, and no amount of scheduler tuning changes that, because the graph itself has no more independent work in it.
This is the analysis that explains why library parallel sorts parallelise the merge step: doing so drops the span from O(n) to O(log² n) and raises parallelism from ~13 to something in the tens of thousands. The algorithmic change is entirely a span change — W barely moves — and it converts a computation that cannot use a big machine into one that can. Recognising "this is span-limited, so I need a different algorithm, not more cores" is the whole point of learning these two numbers.
W (work) S (span) W/S (parallelism) sum, binary tree n = 1.0e8 log2 n = 27 ~3,700,000 -> structurally unlimited; real limit is memory bandwidth map, independent per element n = 1.0e8 1 ~100,000,000 -> the most parallel shape there is merge sort, SEQUENTIAL merge n log n = 2.7e9 2n = 2.0e8 ~13 -> 13 useful workers. A 64-core machine is 80% idle by construction. merge sort, PARALLEL merge n log n = 2.7e9 log^2 n = ~729 ~3,700,000 -> same work, different span. This is why library sorts are complicated. prefix scan, naive left-to-right n = 1.0e8 n = 1.0e8 1 -> no parallelism at all prefix scan, two-pass ~2n = 2.0e8 ~log n + n/P ... -> more work, far less span: the standard parallel trade READING IT W/P is what you hope for. S is what you are stuck with. T_P >= max(W/P, S) T_P <= W/P + S (greedy scheduler, Brent) So a greedy scheduler is within 2x of optimal ALWAYS. If speedup is poor and the scheduler is sane, the span is the problem -- change the algorithm.
What the ceiling looks like when you hit it
The signature of a span-limited computation is a speedup curve that climbs cleanly and then goes completely flat — not a decline (that is overhead or contention, see Parallel Overhead and More Threads Is Not More Speed), and not a gentle bend (that is a serial fraction, see Amdahl's Law). Flat, at exactly the parallelism value, with workers visibly idle and no lock in sight.
The curve below is for a cleaner decomposition than the pipeline above: W = 48 and S = 12 — say a 3-tick prologue, 42 ticks of finely divisible independent work, and a 3-tick epilogue — so parallelism is exactly 4. Up to 4 workers speedup is linear because the work law binds. At 8, 16 and 32 workers it is unchanged, because the span law binds and the graph has no more independent work in it. The idle workers are not a bug; there is genuinely nothing for them to do.
Distinguishing span-limited from serial-fraction-limited matters because the remedies differ. A serial fraction is removed by parallelising more of the code or shrinking a critical section. A span limit is removed only by restructuring the dependency graph — parallelising the merge, replacing a linear fold with a tree, breaking a long chain into independent pieces. That is an algorithm change, and it is why span belongs in design discussions rather than in performance tuning.
- Flat curve at a fixed multiple = span limit. Change the algorithm.
- Gradually bending curve = serial fraction. Shrink the serial part (Amdahl's Law).
- Declining curve = overhead or contention. Coarsen tasks or reduce sharing.
- Idle workers with no blocked threads and no lock waits is the tell: the graph, not the runtime, is the constraint.
Key points
- Work W is total operations (time on one worker); span S is the longest dependency chain (time on infinite workers).
- Parallelism is W/S — the maximum number of workers that can be usefully employed, decided by the algorithm, not the machine.
- T_P ≥ max(W/P, S): the work law binds below the parallelism, the span law binds above it.
- Brent's bound T_P ≤ W/P + S means a greedy scheduler is within 2× of optimal, so poor speedup is usually a span problem rather than a scheduler problem.
- Merge sort with a sequential merge has parallelism ~13 at n = 100M; parallelising the merge raises it by five orders of magnitude with barely any change in work.
- A flat speedup curve at a fixed multiple is the signature of a span limit, and it is fixed by restructuring the graph, not by adding cores.
- Span tells you which task to optimise: only tasks on the critical path matter, and the biggest task is often not one of them.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Model the computation as a directed acyclic graph of tasks, with an edge wherever one task's output is another's input.
- • Work is the sum of all task costs; span is the maximum total cost along any path from a source to a sink.
- • Parallelism W/S estimates how many workers can be busy on average across the whole execution.
- • A greedy scheduler runs any ready task on any free worker; Brent's analysis shows this achieves at most W/P + S.
- • Identify the critical path; optimising anything off it cannot reduce the span and therefore cannot raise the ceiling.
- • If parallelism is too low for the target machine, restructure: replace linear chains with trees, parallelise the combine, or split long tasks.
- • On 4 workers with W = 48 and S = 12: every worker is busy the whole time, T = 12, and the schedule is optimal — the work law is exactly tight.
- • On 8 workers with the same graph: at each moment at most 4 tasks are ready, so 4 workers idle continuously and T is still 12. No schedule does better, and no interleaving helps.
- • Merge sort with sequential merges: at the last level exactly one task exists — the root merge — so all workers but one are idle for the final 2n operations, which is most of the span.
- • A greedy scheduler makes a locally poor choice (running a short off-critical-path task before a long critical-path one): Brent's bound says the damage is limited to an additive S, which is why greedy scheduling is good enough in practice.
- • A task on the critical path blocks on I/O: its cost inflates and the span inflates with it, which is why blocking inside a task graph is far more damaging than blocking in an independent task.
- • Guaranteed: no schedule, on any machine, finishes before S.
- • Guaranteed: no schedule on P workers finishes before W/P.
- • Guaranteed: a greedy scheduler achieves at most W/P + S, hence within a factor of 2 of the optimal schedule.
- • NOT guaranteed: that you reach W/P. Overhead, contention, bandwidth and imbalance all sit on top of these bounds.
- • NOT guaranteed: that W and S are constant. Both are input-dependent — quicksort's span depends on pivot quality, and a graph's critical path can change with data.
- • NOT guaranteed: that high parallelism means good performance. A computation can have enormous parallelism and still be memory-bandwidth-bound.
- • NOT guaranteed: that the model captures communication. Classic work/span assumes free data movement, which distributed and NUMA systems violate badly.
- • The model deliberately excludes contention: work and span are ceilings imposed by structure even in a perfect machine, and real results sit below them.
- • A lock inside a task effectively lengthens that task and, if it is on the critical path, lengthens the span.
- • When the span law binds, idle workers may look like a contention problem in dashboards — they are not, and lock-wait metrics will be flat.
- • Communication and data movement are outside the model, and on distributed or NUMA hardware they can dominate everything the model predicts.
- • Buying or provisioning far more workers than W/S, so most of them are structurally idle.
- • Optimising a task that is not on the critical path — real work, zero effect on the ceiling.
- • Choosing an algorithm with acceptable work and terrible span (sequential merge, linear fold, naive scan) and then blaming the runtime.
- • Mistaking a span limit for a serial fraction and trying to shrink a critical section that is not the constraint.
- • Blocking on I/O inside a critical-path task, inflating the span for every schedule.
- • Assuming the model's prediction is achievable — it is a ceiling, and overhead makes real results strictly worse.
- • At design time: comparing two algorithms' span tells you which one can use a big machine, before either is written.
- • When speedup plateaus and nothing looks contended — span is usually the explanation and the metrics will not show it.
- • For deciding where to optimise: only critical-path tasks can raise the ceiling.
- • For sizing: W/S is a principled maximum worker count, unlike a guess.
- • When treated as a performance prediction rather than a bound — real systems fall short of both laws.
- • When communication cost matters (distributed, NUMA, GPU transfers), because the classic model assumes data movement is free.
- • When W and S vary strongly with input, so a single pair of numbers describes no actual run.
- • When the analysis becomes a substitute for measurement on a computation that is bandwidth-bound rather than structure-bound.
- • Speedup versus workers: a clean flat plateau at a fixed multiple is a span limit, and that multiple is your measured parallelism.
- • Compare the plateau against the calculated W/S — agreement confirms the analysis and disagreement points at overhead or imbalance.
- • Idle-worker time with flat lock-wait metrics, which distinguishes structural idleness from contention.
- • Critical-path length from a task-graph profile where the runtime provides one, or by instrumenting task start and end times and finding the longest chain.
- • Per-task duration along the critical path, to find which task to attack.
- • Recompute W and S across input classes, since both are input-dependent for anything data-driven.
- • You have to be able to describe your computation as a dependency graph, which forces explicitness that most code does not have.
- • Estimating span requires knowing task costs, which for data-dependent work means a distribution rather than a number.
- • Reducing span usually means a structurally different algorithm — a parallel merge, a tree reduce, a two-pass scan — each more complex than the version it replaces.
- • The model omits communication, so on distributed hardware you need a second analysis layered on top of it.
- • Amdahl's serial-fraction analysis, when the structure is "one serial phase plus one parallel phase" and a full graph is overkill (Amdahl's Law).
- • Direct measurement of a speedup curve, when the code exists — it captures overhead and bandwidth that the model ignores.
- • Critical-path analysis on a trace, which gives the same insight empirically for systems whose graph is not known statically (Dependency Graphs).
- • Ignoring the analysis entirely for small P: if you have 4 cores and any reasonable decomposition, the span is unlikely to be the binding constraint.
Work, span and the speedup ceiling
critical path A → D → F → G = 90 ms work 20 + 30 + 25 + 40 + 15 + 20 + 10 = 160 ms ceiling T₁ / T∞ = 160 / 90 = 1.78× no extra edges — toggle one above
Scheduling a task graph
Why is 8 cores only 4.5×?
| workers | ideal | Amdahl only | realistic | limited by |
|---|---|---|---|---|
| 1 | 1.0× | 1.00× | 1.00× | none |
| 2 | 2.0× | 1.90× | 1.85× | serial |
| 4 | 4.0× | 3.48× | 3.19× | serial |
| 6 | 6.0× | 4.80× | 4.17× | serial |
| 8 | 8.0× | 5.93× | 4.17× | bandwidth |
| 10 | 10.0× | 6.90× | 4.17× | bandwidth |
| 12 | 12.0× | 7.74× | 4.17× | bandwidth |
| 14 | 14.0× | 8.48× | 4.17× | bandwidth |
| 16 | 16.0× | 9.14× | 4.17× | bandwidth |
What people believe, and what is true
More cores will help if the algorithm is parallel.
Only up to W/S. Merge sort with a sequential merge has parallelism around 13 at n = 100M, so a 64-core machine is mostly idle no matter what the runtime does.
The speedup plateaued, so the scheduler or the runtime is at fault.
Brent's bound puts a greedy scheduler within 2× of optimal. A clean plateau is the graph running out of independent work, and the fix is a different algorithm.
Optimising the most expensive task is the best use of effort.
Only if it is on the critical path. Halving an off-path task changes the span by nothing at all.
Span is just Amdahl's serial fraction under another name.
Amdahl models one indivisible serial region; span is the longest chain through the whole dependency graph, which can be long even when no single region is serial.
Go deeper
Overview
Work is how much there is to do. Span is the longest chain of steps that must happen in order. Divide them and you get the most workers that can ever be busy.
Practical
A speedup curve that goes flat at a fixed multiple with idle workers and no lock waits is a span limit. Fix it by changing the algorithm, not the machine.
Advanced
Only critical-path tasks matter for the ceiling. Parallelising a merge, replacing a linear fold with a tree, or converting a scan to two passes are all span reductions that leave work roughly unchanged.
Internals
Brent's bound is why greedy work-stealing schedulers are good enough: at every step either every worker is busy (spending work) or some worker runs a critical-path task (spending span), giving T_P ≤ W/P + S.