Scaled-workload parallel speedup model
Gustafson's Law
If a larger machine is used to solve a proportionally larger problem in roughly the same elapsed time, useful scaled speedup can grow almost linearly despite a nonparallel fraction.
S_G(N) = N - alpha(N - 1)
N is processor count and alpha is the serial fraction measured on the parallel execution. The model scales the problem with available resources; it answers a different question from fixed-workload Amdahl speedup.
The race holds elapsed time constant and expands the parallel workload. Change the measured serial fraction to see how much useful work the machine completes in that window.
(x)
The plot, diagram, and calculated result share the same state. Animation runs only when it adds explanatory value.
- CHANGE
- Processors
- WATCH
- scaled work in fixed time
- MEANING
- The race holds elapsed time constant and expands the parallel workload. Change the measured serial fraction to see how much useful work the machine completes in that window.
More processors can mean a larger solved problem, not merely a shorter wait.
Fixed-size and scaled-size curves share the same processor axis but answer different operational questions.
What it actually says
Gustafson's law reframes scalability. Amdahl asks how quickly a fixed job can finish as processors are added; Gustafson asks how much larger a job can be completed in the original time. Scientific simulations often use the extra capacity for finer resolution, more particles, more scenarios, or a larger domain.
The serial fraction alpha is an observed share of runtime, not an immutable property of the source code. Communication, synchronization, memory bandwidth, I/O, load imbalance, algorithm choice, and problem geometry all change as both machine and workload scale.
"A useful law compresses a pattern. It does not erase the conditions that make the pattern true."
How the idea developed
The modern form emerged through observation, argument, and later refinement. The timeline separates the first insight from the version now used in textbooks and practice.[1]
Amdahl formalizes the fixed-workload serial bottleneck.
John Gustafson publishes Reevaluating Amdahl's Law.
Karp and Flatt propose a metric for experimentally observed serial fraction.
Strong and weak scaling studies report different workload assumptions explicitly.
How the pattern works
The relation becomes useful only when its mechanism, measurement process, and operating range are visible.
Parallel work increases with processor count while elapsed time is held near constant.
Only the measured serial portion fails to expand across processors.
Work per processor remains roughly fixed as the system grows.
Communication and coordination can make alpha increase rather than stay fixed.
N is processor count and alpha is the serial fraction measured on the parallel execution. The model scales the problem with available resources; it answers a different question from fixed-workload Amdahl speedup.
Where it earns its keep
Applications are strongest when the law changes a decision, measurement, model, or experiment rather than merely providing an analogy.
Plan larger simulations
ApplicationTeams can translate added nodes into resolution or ensemble size.
Report memory, network, and I/O scaling.
Size distributed workloads
ApplicationThroughput can grow while per-item latency stays similar.
Skew, shuffles, and coordination can dominate.
Separate strong from weak scaling
ApplicationTwo curves prevent incompatible speedup claims.
State the baseline, workload, elapsed-time rule, and processor topology.
Where it stops working
The formula assumes a stable serial fraction under the chosen scaling path. It does not model communication complexity, contention, energy, cost, reliability, or algorithmic changes.
A large scaled speedup does not mean a single fixed task becomes equally faster, nor that user-perceived latency improves.
"Gustafson disproves Amdahl"
Better: They answer different workload questions and can both be correct."Weak scaling is free speed"
Better: The amount of solved work grows; resource use grows too."alpha is a constant of the program"
Better: It depends on implementation, input, machine, and measurement."Near-linear speedup proves efficiency"
Better: It may hide excess work, lower accuracy, or a changed output definition.Sources and further reading
Original publications and serious secondary scholarship are prioritized over summaries.
- Gustafson - Reevaluating Amdahl's LawThe original 1988 scaled-speedup argument.https://doi.org/10.1145/42411.42415
- Amdahl - Validity of the Single Processor ApproachThe fixed-workload comparison.https://doi.org/10.1145/1465482.1465560
- Karp and Flatt - Measuring Parallel Processor PerformanceExperimental serial-fraction metric.https://doi.org/10.1016/0167-8191(90)90023-I
- NERSC - Performance and ScalingOperational HPC examples and scaling context.https://docs.nersc.gov/jobs/examples/