How Does Gustafson's Law Scale Parallel Speedup?
Gustafson's law explains how parallel computing achieves near-linear speedup when the problem size grows alongside the number of processors. Rather than treating a workload as fixed, it models how practitioners actually use larger systems to solve bigger problems within the same amount of time. By scaling the parallelizable portion of a task with processor count, the serial bottleneck shrinks in relative importance, allowing classical parallel systems to scale effectively.
Fixed Problem Size vs. Scaled Problem Size
To understand Gustafson's argument, it helps to contrast it with Amdahl's law. Amdahl's law assumes a fixed total workload: as you add processors, the parallel portion runs faster, but the strictly serial portion remains constant and eventually dominates execution time.
Gustafson's law, formulated by John L. Gustafson in 1988, takes the opposite perspective. In practice, when researchers gain access to a machine with more processors, they do not simply run the same small problem faster. Instead, they increase the resolution, dataset size, or simulation complexity so that the job still finishes in a practical, roughly constant wall-clock time.
The Mathematics of Gustafson's Law
Let \(P\) be the number of processors, and let \(s\) be the fraction of total execution time spent on the strictly serial part of the program on the parallel machine. The remaining fraction, \(1 - s\), is the time spent on the parallelizable part.
If the parallel system takes \(1\) unit of time to complete the scaled workload, then a single processor would need \(s\) time for the serial part plus \(P(1 - s)\) time for the parallel part. The scaled speedup \(S(P)\) is the ratio of single-processor time to parallel time:
\[S(P) = s + P(1 - s)\]
This can also be written as:
\[S(P) = P - s(P - 1)\]
Because \(s\) is typically small and \(P\) can be large, \(S(P)\) grows linearly with \(P\). For example, if \(s = 0.05\) and \(P = 100\), the scaled speedup is:
\[S(100) = 100 - 0.05(99) = 95.05\]
Under Amdahl's law with a fixed problem size and a \(5\%\) serial fraction, speedup would be capped at \(20\) regardless of how many processors were added.
Why Scaling Works in Classical Computing
Gustafson's law reflects how classical high-performance computing workloads behave in fields such as weather modeling, computational fluid dynamics, and molecular dynamics. In these domains, the serial overhead—such as initialization, reading configuration files, or final aggregation—often grows slowly or stays constant as the problem size increases.
Meanwhile, the parallel workload—such as updating grid cells or computing particle interactions—grows rapidly with problem size. When you double the number of processors and double the parallel work, each processor handles the same amount of computation as before, while the serial fraction remains a small, bounded part of the total runtime.
Practical Limits to Scaled Speedup
While Gustafson's law demonstrates strong theoretical scaling, real classical architectures still face physical constraints:
- Communication overhead: Processors must exchange data over interconnects, and synchronization costs can grow with \(P\).
- Memory bandwidth and contention: Multiple cores competing for shared memory or cache can slow down individual execution rates.
- I/O bottlenecks: Reading and writing larger datasets can increase serial or poorly parallelized I/O time.
Despite these hardware realities, Gustafson's law provides the foundational justification for building massively parallel classical systems: as long as problem sizes scale with processor counts and communication remains manageable, parallel speedup continues to grow effectively.