Gustafson's Law and Scaled Speedup

Both Gustafson's Law and Amdahl's Law start from the same decomposition of a program's execution time into a sequential portion and a parallelizable portion. Let a program require total time $T$ on one processor, split into a fraction $s$ that is inherently serial and a fraction $1-s$ that parallelizes perfectly across $p$ processors. Amdahl's Law asks: if I run this exact same fixed-size program on $p$ processors, how much faster does it finish? The answer is

which is bounded above by $1/s$ no matter how large $p$ grows — because the sequential part's time is fixed and un-shrinkable. Gustafson's Law, introduced by John Gustafson and Edwin Barsis in 1988, asks a different question: if I have a <strong>fixed time budget</strong> $T$ and a machine with $p$ processors, how much <strong>larger</strong> a problem can I solve in that budget, compared to what one processor could solve, and what is the resulting speedup? Here the measurement is taken on the parallel run as the reference point. Suppose on the $p$-processor machine the observed execution consumes fraction $s$ of time doing serial work and $1-s$ doing parallel work (this $1-s$ portion, by construction, is now $p$ times larger in work done than it would be on one processor, since $p$ processors did it in the same wall time). The scaled speedup — how much work a single processor would have needed to redo the same total job — is:

This is linear in $p$, with slope $(1-s)$, rather than asymptotically flat. The crucial conceptual move is that $s$ here is the serial fraction of the parallel run, not the serial fraction of some fixed sequential program — these are related but numerically distinct quantities, and confusing them is a classic error (see the pitfalls table below). The umbrella term for these two philosophies is strong scaling (Amdahl: fixed total problem, more processors, goal = shorter time) versus weak scaling (Gustafson: fixed problem-per-processor, more processors, goal = bigger problem in the same time). Real workloads often exhibit a mixture: some subroutines strong-scale (fixed matrix, more cores factor it faster), while the overall application weak-scales (finer mesh resolution as more nodes become available). Both laws are exact under their respective idealized assumptions; both ignore secondary costs like communication overhead, memory bandwidth contention, and load imbalance, which real systems must additionally account for.

The mechanism behind Gustafson's Law is best understood by tracking where time goes under the two different experimental protocols.

Amdahl's protocol. Fix the total work $W = W_{\text{serial}} + W_{\text{par}}$. Time on 1 processor is $T_1 = W_{\text{serial}} + W_{\text{par}}$. Time on $p$ processors is $T_p = W_{\text{serial}} + W_{\text{par}}/p$. Speedup is $T_1/T_p$. As $p \to \infty$, $T_p \to W_{\text{serial}}$, a floor — this is why speedup saturates.

Gustafson's protocol. Fix the time budget $T$ (the time you're willing to wait, e.g., one simulated day of compute). Run on $p$ processors: the machine spends time $s\cdot T$ on serial work and $(1-s)\cdot T$ on parallel work, but because there are $p$ processors, the parallel work accomplished in that $(1-s)T$ window is $p$ times what one processor could do in the same window. So the total work accomplished by the $p$-processor run, measured in "single-processor-equivalent time units," is

Dividing by the reference $T$ (what one processor alone would have accomplished in that same budget, which is just $T$ itself, i.e., $s\cdot T + (1-s)\cdot T$), gives the scaled speedup formula $s + p(1-s)$ directly — it is literally "how many times more work got done," not "how much time got saved." ``` ALGORITHM: EstimateScaledSpeedup INPUT: p // number of processors available s // serial fraction OBSERVED on the p-processor parallel run // (fraction of wall-clock time spent in non-parallel code) OUTPUT: speedup // Gustafson scaled speedup estimate function GustafsonSpeedup(p, s): assert 0 <= s <= 1 assert p >= 1 parallel_fraction = 1 - s speedup = s + p * parallel_fraction return speedup

# Contrast: Amdahl's Law answers a DIFFERENT question with the SAME s-notation

# but s there must be measured on the SEQUENTIAL (1-processor) run. function AmdahlSpeedup(p, s_seq): assert 0 <= s_seq <= 1 assert p >= 1 denom = s_seq + (1 - s_seq) / p return 1.0 / denom

# WORKFLOW for weak-scaling an actual experiment (how Gustafson numbers

# are produced in practice, e.g. in HPC benchmarking): function WeakScalingExperiment(base_problem_size, p_list, time_budget): results = [] for p in p_list: problem_size = base_problem_size * p // grow problem WITH p run_time = ExecuteParallel(problem_size, p)

# Ideally run_time ≈ time_budget for all p (that is the goal

# of weak scaling: keep wall time roughly flat as p and size grow) s_observed = MeasureSerialFraction(problem_size, p) speedup = GustafsonSpeedup(p, s_observed) results.append((p, run_time, s_observed, speedup)) return results ``` The pseudocode makes explicit the one thing that trips up almost every student encountering this the first time: the $s$ in Gustafson's formula is measured on the parallel execution, not derived from timing a sequential-only run. This is why the two laws, applied to the same system with the same letter $s$, give different-looking numbers that are not contradictory — they are answers to different experiments.

Complexity of the formula itself. Evaluating $\text{Speedup} = s + p(1-s)$ is $O(1)$ time and $O(1)$ space — it is a closed-form arithmetic expression, not an algorithm over a data structure. The "complexity" content of this topic is really about the asymptotic behavior of speedup as a function of $p$, which is the substantive claim to verify.

Correctness argument — why the formula is linear in $p$. By construction of the weak-scaling experiment, the wall-clock time is held fixed at $T$ across all values of $p$ (this is the defining invariant of Gustafson's protocol, not an assumption to be proven — it is how the experiment is run). Within that fixed time $T$:

• Serial time consumed: $sT$ (unchanged by $p$, by definition of "serial").
• Parallel time consumed: $(1-s)T$, but during this window all $p$ processors work simultaneously on independent pieces of a problem that has been scaled up to exactly fill them. The amount of work completed in this window equals $p$ times the work one processor would complete in the same window (perfect parallel efficiency assumption, identical to Amdahl's idealization for the parallel portion).

So total work completed, expressed in "one-processor-equivalent time units," is $sT + p(1-s)T$. Normalizing by $T$ (the work one processor alone accomplishes in that budget) yields exactly

a first-degree polynomial in $p$ with slope $(1-s) \geq 0$. This is manifestly unbounded as $p\to\infty$, in stark contrast to Amdahl's Law's asymptote at $1/s$. The derivative with respect to $p$ is constant, $\partial \text{Speedup}/\partial p = 1-s > 0$ whenever $s<1$, so speedup strictly increases with every additional processor — there is no saturation point in the idealized model.

Reconciling the two laws (they are not in conflict). It is a common misconception that Gustafson's Law "refutes" Amdahl's Law. It does not — both are algebraically exact under their own fixed quantity. One can show they are two different slices through the same underlying $(p, \text{size}, \text{time})$ surface: if you take a Gustafson-scaled experiment and instead ask "how much faster would the original small problem finish," you recover something Amdahl-like; if you take an Amdahl experiment and ask "how much more work fits in the shrunk time," you can derive a Gustafson-like bound. The formulas diverge because $s$ is not the same number in the two experiments — the serial fraction of a small fixed problem run in parallel is typically larger (relatively) than the serial fraction of a scaled-up problem, because many serial costs (I/O setup, initialization, a control loop) do not grow with problem size, so they shrink as a fraction of a larger total.

Honest tradeoffs and hidden assumptions. Both laws assume: 1. Perfect parallel efficiency — the $(1-s)$ portion divides evenly across $p$ processors with zero communication or synchronization overhead. Real systems lose efficiency to network latency, cache contention, and load imbalance; scaled speedup in practice is sublinear, and the honest bound is $\text{Speedup}(p) \le s + p(1-s)$, with equality only in the idealized case. 2. The serial fraction is measured, not assumed constant. In many real applications, as problem size grows, $s$ actually shrinks (I/O and setup overhead amortize over more work), which makes real weak-scaling curves sometimes better than the idealized formula predicts for a fixed $s$ — but if $s$ instead grows with problem size (e.g., a global reduction step that gets more expensive with more processors), scaled speedup can be considerably worse than linear. 3. Memory and bandwidth are assumed unconstrained. Growing the problem size with $p$ requires proportionally more memory and I/O bandwidth; if the machine's memory or network cannot keep pace, weak scaling degrades regardless of what the compute-only formula predicts.

Consider a climate simulation whose single-processor serial bookkeeping (I/O, boundary setup, a final reduction) is a small, roughly fixed cost, while its main grid-update computation parallelizes almost perfectly.

Setup for a strong-scaling (Amdahl) trace. Fix the grid at $N = 10^6$ cells. On 1 processor this takes $T_1 = 1000$s total, of which $50$s (5%) is irreducibly serial ($s_{\text{seq}} = 0.05$) and $950$s is parallelizable.

The ceiling of $1/0.05 = 20\times$ is visible clearly by $p=1024$: adding a thousand-fold more processors barely moves speedup from $19.6$ to $20$.

Setup for a weak-scaling (Gustafson) trace. Now the lab does what it actually does: with $p$ processors available, it runs a grid $p$ times larger (finer resolution), keeping wall time fixed near $T = 1000$s. Measuring the observed serial fraction on each run (the $50$s bookkeeping cost stays roughly fixed regardless of grid size, since it does not depend on cell count — think of it as reading one config file and writing one summary):

Here, even with the same nominal $s = 0.05$, speedup at $p=1024$ is $972.65\times$ — a night-and-day difference from Amdahl's ceiling of $20\times$, because the two tables answer different questions. The Amdahl table asks "how much faster is the fixed 1-million-cell grid?" The Gustafson table asks "how much more total simulated science got done in the same 1000 seconds?" Both are true, simultaneously, about the same underlying machine.

A less rosy variant — s growing with p. Suppose instead that the serial part includes a global synchronization ("gather all subdomain boundaries onto one node before writing output") that grows like $\sqrt{p}$ because more subdomains must be merged. Then $s(p) = 0.05\sqrt{p}/\sqrt{p_0}$ for some reference $p_0$; plugging into $s(p) + p(1-s(p))$ shows scaled speedup grows sublinearly and eventually can even decrease with $p$ once $s(p)$ approaches 1 — a cautionary case that shows why "scaled speedup is always linear" is only true under the idealized constant-$s$ assumption, and real system designers must measure $s(p)$ empirically at each scale rather than trust a single measurement extrapolated arbitrarily far.

John Gustafson worked at Sandia National Laboratories during the late 1980s, a period when massively parallel processors (the era's hypercube and mesh machines) were being evaluated against the pessimistic ceiling implied by Amdahl's Law and Speedup. Running actual production physics codes on a 1024-processor hypercube, Gustafson and his collaborators (including Edwin Barsis, along with Robert Montry and colleagues on related benchmark work) observed near-linear speedups that flatly contradicted the Amdahl-based expectation that such large processor counts should be nearly wasted on any program with even a small serial fraction. The resolution was not that Amdahl's algebra was wrong, but that the experiment being run was different: scientists were not solving the same fixed problem faster — they were solving proportionally larger, higher-fidelity problems in the same allotted machine time. Gustafson formalized this observation as what is now called Gustafson's Law (also known as the Gustafson–Barsis Law), published in the widely cited 1988 paper "Reevaluating Amdahl's Law." The paper reframed how the parallel-computing community justified investment in large machines: not by promising to make small jobs instantaneous, but by promising to make ambitious jobs tractable within a fixed patience budget — precisely the model that later underwrote climate modeling, computational fluid dynamics, and large-scale simulation as flagship uses of supercomputing.

High-performance computing centers report both strong-scaling and weak-scaling curves for every major machine precisely because customers ask both kinds of questions — "will my job finish faster" versus "how much bigger a job can I now afford." Climate and weather models, computational fluid dynamics, molecular dynamics, and cosmological N-body simulations are the classic Gustafson-regime workloads: as machines grow, scientists do not rerun old low-resolution simulations faster, they run finer grids, more particles, longer time horizons, or larger ensembles, filling the fixed time budget of "before the next funding review" or "before the storm arrives." Training ever-larger machine learning models on ever-larger clusters follows the same logic: adding GPUs does not primarily make yesterday's model train instantly, it enables training a model with more parameters or more data in a similar training-time budget, which is the philosophical ancestor of how modern large-scale AI training clusters are justified and scaled. Databases and MapReduce-style big-data systems weak-scale by design — sharding a dataset across more nodes lets an organization process a proportionally larger dataset in a similar batch window. This same reasoning about growing workload to match growing fleet size is exactly the mental model that recurs when reasoning about Warehouse-Scale Computing, where the operative question shifts from "how fast is one query" to "how much total serving capacity can the fleet sustain," and it underlies why capacity planners think in terms of throughput-per-added-machine rather than latency-per-fixed-job. It also disciplines how engineers write Parallel Algorithms: knowing whether a workload will be deployed in a strong-scaling or weak-scaling regime changes which serial bottlenecks are worth eliminating first.

Ask the tutor: Can you derive what happens to scaled speedup if the serial fraction itself grows as a function of the problem size, and show when that turns the curve from linear into something that eventually declines?