Amdahl, Gustafson, and the Fixed-Problem Fallacy

The work-span model says a computation with parallelism W/D cannot use more than W/D processors usefully. Amdahl’s law says something stronger and more pessimistic: if a fraction of the work is irreducibly serial, the speedup is bounded by the reciprocal of that fraction regardless of processor count. Gustafson’s law says the bound is an artefact of holding the problem size fixed. Both are correct, and the difference between them is a statement about what is being measured rather than about the machine.

Amdahl’s derivation, and what f means

Let f be the fraction of the sequential execution time that cannot be parallelised. On P processors, the remaining fraction, 1−f, is divided by P:

$$S(P) = \frac{1}{f + \frac{1-f}{P}}$$

As P → ∞, S → 1/f. With f = 0.05 the ceiling is 20, and it is nearly reached at P = 100, where S ≈ 16.8; with f = 0.01 the ceiling is 100. The law is usually quoted with these numbers because they are uncomfortable: five percent serial work caps speedup at twenty, no matter the machine.

The definition of f is where most misapplications occur. It is the serial fraction of the sequential run time, not of the parallel run time and not of the instruction count. A part of the program that is executed in parallel but whose cost grows with P — a barrier, a reduction over per-processor partial results, a shared counter — is not part of f in the naive formulation, yet it limits scaling. That term is properly a function of P, and the law becomes

$$S(P) = \frac{1}{f + \frac{1-f}{P} + c(P)}$$

where c(P) captures overhead that grows with the processor count. Barriers, cache-coherence traffic, and scheduler contention all contribute, and c(P) is what makes real speedup curves bend downward before they flatten at 1/f. A measured curve that peaks and then declines is showing c(P) dominating; the Amdahl ceiling is only the asymptote of the idealised version.

A second subtlety: f is not a property of the source code. It is a property of the execution on a particular input. A program with a 5 percent serial phase on a small input may have a 0.5 percent serial phase on a large one, if the serial phase is a fixed setup cost and the parallel phase grows with n. This is the crack that Gustafson widens.

Gustafson’s reframing

Gustafson’s argument starts from the observation that in practice the problem size grows with the machine. The question is not “how much faster does the same problem run on more processors” but “how much larger a problem can be solved in the same time”. Define s as the serial fraction of the parallel execution time and p = 1−s as the parallel fraction, both measured on the P-processor run. Scaled speedup is

$$S_{scaled}(P) = s + P,(1 - s) = P - (P-1),s$$

which grows linearly in P with slope 1−s. At s = 0.05 and P = 1024, scaled speedup is about 973, against Amdahl’s ceiling of 20. The two numbers describe the same program; they differ in whether the problem is allowed to grow.

The relationship between the two fractions is a change of variable. If f is the serial fraction at the small size and the parallel work grows by a factor P while the serial work stays constant, then the serial fraction of the larger problem’s sequential time is f′ = f/(f + (1−f)P), which shrinks as P grows. Substituting f′ into Amdahl’s formula returns exactly the scaled speedup, so the two laws are the same equation evaluated on different problems and neither is a refutation of the other.

The practical content is about which regime a workload occupies. A weather simulation with a grid that is refined as cores become available is in Gustafson’s regime, and its speedup is close to linear. A compiler pass over a fixed 10 MB source file is in Amdahl’s regime, and its speedup is capped by the serial fraction of that file. Most workloads are somewhere between, and the diagnostic question is whether the work per processor stays constant as P grows.

Strong and weak scaling as measurements

The two laws correspond to two scaling experiments:

Strong scaling holds n fixed and varies P, reporting T(1)/T(P). This measures Amdahl behaviour. Efficiency E(P) = S(P)/P falls as P grows, and the point where it drops below, say, 0.5 is the practical processor limit for that problem size. For a computation with span D and work W, strong scaling is limited by the span: T(P) ≥ D, so efficiency falls below 0.5 once P > 2W/D roughly.

Weak scaling holds work per processor fixed — n grows proportionally to P — and reports T(P)/T(1) with the problem size growing. This measures Gustafson behaviour. Efficiency stays near 1 if the serial fraction does not grow, which requires that the extra work parallelises and that any global structure (a barrier, a reduction over all P, an all-to-all) grows slower than linearly. A global reduction at every step grows as log P, so weak scaling degrades slowly; an all-to-all grows as P, so it degrades fast.

Neither experiment is more honest; they answer different questions. A paper reporting only strong scaling at a small fixed n will show poor speedup for a computation that scales well in the weak sense, and a paper reporting only weak scaling can hide a fixed overhead that makes the code unusable at the sizes it was tested at.

Where the models meet the DAG

The connection to work and span is direct. In the DAG model with W work and D span, the running time is at least max(W/P, D), so speedup is at most

$$S(P) \le \frac{W}{\max(W/P,, D)} = \min\left(P,; \frac{W}{D}\right)$$

The quantity D/W is exactly the serial fraction in the limit: the critical path is the part of the computation that cannot be shortened, and W/D is the parallelism. Amdahl’s f is therefore the reciprocal of the parallelism for a computation whose span is the whole serial part, with the caveat that real computations have a serial fraction that is not one contiguous chain but a sum of many small dependencies. Those add along the span, which is why the span is often larger than the sum of the obviously serial phases.

This gives a better diagnostic than measuring f. Compute the span analytically for the algorithm and compare W/D to the processor count. If W/D is 8 and the machine has 64 cores, no amount of tuning will help; the algorithm needs restructuring, and the restructuring is always “reduce the span” — parallelise the merge, replace a linear chain of dependencies with a tree, or remove a global serialisation point. That is the recurring theme of the reduction article and of the scan article, both of which exist to turn a linear-span operation into a logarithmic-span one.

Overheads that scale the wrong way

The c(P) term deserves its own accounting because it is what makes the difference between the idealised laws and a real machine.

Synchronisation. A barrier among P processors costs at least the time to reach it plus the time for the last arrival to propagate; with a tree barrier it is O(log P) but the constant includes a cache-line transfer per level. A computation that barriers once per unit of work has a cost that grows as log P per unit, which is a weak-scaling penalty.

Coherence and false sharing. Two processors writing distinct variables in the same 64-byte line serialise on the line. The cost is not proportional to P but to the number of conflicting accesses, and it can dominate a fine-grained computation entirely. Padding to a cache line is the fix, at the cost of memory.

Memory bandwidth. Bandwidth per core does not grow with core count. A computation that is bandwidth-bound at one core cannot be sped up by adding cores, because the shared memory system is already saturated. This is the one overhead that looks exactly like a large serial fraction and is not one: the sequential phase is fast because it uses the full bandwidth, and the parallel phase is slow because P cores contend for the same bandwidth. Distinguishing the two requires measuring bandwidth, not just time.

Task overhead. Covered by the granularity calculation in the cut-off article: the per-task cost times the number of tasks is a term that grows with P if the task size is held fixed.

Reporting a speedup honestly

Given the above, a speedup number is meaningless without four pieces of context: the processor count and its meaning (cores, hardware threads, nodes), the problem size and whether it was held fixed, the baseline (best sequential implementation, not the parallel code run on one thread), and the efficiency at each point. A curve that reports only the best point hides the shape, which is the part that tells a reader where the algorithm stops scaling.

The honest summary for most algorithms of this kind is a sentence of the form: work Θ(f(n)), span Θ(g(n)), so efficiency stays above one half up to P ≈ 2f(n)/g(n) for problem size n, after which the span or a global overhead dominates. That statement is derivable from the algorithm without running it, and it is what the two scaling laws are approximating.