John Gustafson and the Argument That Bigger Problems Can Scale
John Gustafson's 1988 reevaluation of Amdahl's law argued that parallel machines are often used to solve larger problems in roughly fixed time, changing how speedup should be interpreted.
Amdahl’s law became the classic warning against unlimited parallel speedup
Gene Amdahl’s 1967 argument emphasized that the serial portion of a computation constrains the benefit of adding processors when the total workload is fixed.[2] If a program contains work that cannot be parallelized, reducing the parallel part toward zero eventually leaves the serial portion as the dominant runtime. This fixed-size perspective became one of the most frequently cited limits in parallel computing and a useful antidote to naive claims that doubling processors must halve execution time.
The assumption is hidden in the phrase speedup
Amdahl’s familiar formula compares how long the same problem takes on one processor and on many processors. It does not ask whether a larger machine encourages the scientist to solve a larger problem.
John Gustafson argued that real supercomputer users often scale the workload instead
In 1988 John Gustafson published “Reevaluating Amdahl’s Law,” based on experience with large scientific computations at Sandia.[1] His central observation was practical: users of powerful parallel machines rarely buy hundreds of processors merely to finish yesterday’s fixed problem sooner. They increase spatial resolution, simulate longer intervals, use more particles, or add physical detail while trying to keep elapsed time within a useful bound.
Scaled speedup holds time roughly constant while problem size grows
Gustafson’s formulation starts from a parallel run and asks how much longer the scaled workload would have taken sequentially. If the serial fraction observed on the parallel machine is small, the effective speedup can grow approximately as P – α(P-1), where P is the processor count and α is the serial fraction.[1] The formula became known as Gustafson’s law or scaled speedup. It does not repeal Amdahl’s law; it changes the experimental question from fixed size to fixed time.
Both laws can be correct under different workload assumptions
Amdahl asks how fast one fixed job can become. Gustafson asks how much more work can be completed in a similar amount of wall-clock time as resources grow.
Sandia’s 1024-processor experiments gave the argument empirical force
Gustafson, Gary Montry, and Robert Benner reported large parallel scientific calculations on a 1024-processor hypercube, including wave mechanics, fluid dynamics, and structural analysis.[3] Their results showed very high speedups when the problem was allowed to scale with processor count. The work received the Gordon Bell Award and became evidence that large parallel systems could be useful despite pessimistic interpretations of Amdahl’s bound.
The scaled-workload view changed how researchers discussed parallel efficiency
The important shift was from asking only how much serial code exists to asking what resource limits define a useful problem. Xian-He Sun and Lionel Ni later distinguished fixed-size, fixed-time, and memory-bounded speedup models, showing that Amdahl’s and Gustafson’s formulas occupy different points in a broader space of scaling assumptions.[4] Memory capacity can itself grow with a parallel machine, enabling datasets or meshes that could not fit on the baseline system.
Scaling is constrained by more than processors
Communication, synchronization, memory capacity, I/O, algorithmic complexity, and the physics of the modeled problem all determine whether adding resources can be converted into a meaningfully larger computation.
Gustafson’s argument did not make serial work irrelevant
The serial fraction still matters. A large fixed coordination phase, centralized data structure, or sequential I/O step can dominate as processor counts rise. Gustafson’s point was that the fraction itself may shrink when the scalable parallel portion grows with problem size. Amdahl’s law remains essential for components that truly stay fixed, while scaled speedup helps describe scientific workloads where the valuable output improves as more work is performed.
The debate remained relevant when multicore processors moved parallelism onto ordinary chips
Mark Hill and Michael Marty revisited Amdahl’s law for multicore processors and showed that chip designers still face tradeoffs between resources devoted to sequential performance and resources devoted to parallel cores.[5] Their work demonstrates why neither Amdahl nor Gustafson is a universal slogan. Performance depends on workload scaling, hardware resource allocation, and the fraction of computation that benefits from additional parallel units.
Scaling laws are models for asking better questions
The value of a law is not that every application must obey one formula exactly, but that the assumptions make researchers explicit about what stays fixed as hardware changes.
Why Gustafson’s law belongs in high-performance computing history
Gustafson’s contribution belongs in HPC history because it corrected a common interpretation of parallel limits without denying the mathematics behind Amdahl’s result. His 1988 paper reframed speedup around how supercomputers were actually used: to increase the ambition of a computation as well as to reduce time.[1][3]
The distinction became central to weak scaling and strong scaling experiments. Strong scaling resembles the fixed-size question; weak or scaled experiments increase workload as resources grow. Modern HPC performance reports routinely need both perspectives.
The enduring lesson is that “how well does this scale?” is incomplete without saying what is being held constant. Processor count, problem size, elapsed time, memory per processor, and desired scientific fidelity define different experiments. Gustafson made that hidden choice visible and gave massively parallel computing a more realistic way to describe its purpose.
Works Cited
- 01
- 02
- 03
- 04
- 05Hill and Marty — Amdahl's Law in the Multicore Era research.google
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead