Amdahl’s Law and Gustafson’s Law

Amdahl’s law and Gustafson’s law are the two foundational results that bound how much faster a program can run when you add processors. Amdahl (1967) answers the fixed-problem question — for a task of unchanging size, the serial fraction caps speedup, so if even 5% of the work is inherently sequential you can never exceed a 20× speedup no matter how many cores you throw at it (Wikipedia). Gustafson (1988) answers the scaled-problem question — if you grow the problem to keep each processor busy, speedup rises almost linearly with processor count, because the serial part stays roughly constant while the parallel part balloons (Wikipedia). The two are not contradictory; they are the same arithmetic applied to two different questions — strong scaling (make a fixed job faster) versus weak scaling (do a bigger job in the same time). Knowing which question you are actually asking is the whole game.

This note is the language-agnostic theory. The hardware realities that make the parallel fraction hard to grow — cache misses, memory bandwidth, cross-core coherence — live in Cache-Conscious and NUMA-Aware Parallelism, and the contention penalty that makes more cores actually slower is The Universal Scalability Law. Amdahl and Gustafson are the optimistic bookends; the USL is the cautionary tale beyond them.

Mental Model

Every parallelizable program splits into two parts: work that must run sequentially (setup, I/O, coordination, the parts with true data dependencies) and work that can be spread across processors. Call the serial fraction s and the parallel fraction p, with s + p = 1. Adding processors compresses only the parallel part; the serial part is a fixed floor. The single most important consequence is that the serial floor, not the parallel ceiling, determines the outcome. The two laws differ only in one assumption: does the total amount of work stay fixed as you add processors, or does it grow?

flowchart TD
    subgraph AM["Amdahl — fixed work (strong scaling)"]
        A1["Total work fixed"] --> A2["Serial part: constant floor s"]
        A1 --> A3["Parallel part p<br/>shrinks as p/N"]
        A2 --> A4["Speedup ceiling = 1/s<br/>(even with N = infinity)"]
        A3 --> A4
    end
    subgraph GU["Gustafson — grown work (weak scaling)"]
        G1["Work grows with N"] --> G2["Serial part stays ~constant"]
        G1 --> G3["Parallel part grows<br/>to fill N processors"]
        G2 --> G4["Speedup ~ N - s(N-1)<br/>rises almost linearly"]
        G3 --> G4
    end

What it shows and the insight to take: both panels start from the same s/p split, but the left holds the total fixed (so the parallel slice becomes a vanishing sliver and the serial floor dominates) while the right lets the total grow (so the parallel slice keeps pace with the machine and the serial floor becomes negligible). The insight: pessimism and optimism about parallel hardware are not disagreements about arithmetic — they are disagreements about whether your workload is fixed-size or grows with your resources. Real workloads sit somewhere between these two idealizations.

Amdahl’s Law: The Serial Floor

Gene Amdahl was an IBM computer architect arguing, at the 1967 AFIPS Spring Joint Computer Conference, against the then-fashionable belief that massively parallel machines would straightforwardly deliver massive speedups (paper reference). His paper’s title — on the validity of the single-processor approach — signals the polemic: he was defending fast uniprocessors against multiprocessor hype.

A subtle historical point worth getting right: Amdahl never wrote down the formula now bearing his name. His paper made an empirical argument — that a substantial fraction of real programs’ instructions were inherently sequential “housekeeping” (data management), which he estimated in roughly the 20%–40% range and observed did not shrink as machines grew (HPCwire). The clean algebraic “law” was constructed by later commentators who distilled his observation into an inequality. So “Amdahl’s law” is Amdahl’s insight dressed in someone else’s algebra.

The formula and every symbol. Consider a program that takes time T on one processor. A fraction s of that time is serial and a fraction p = 1 − s is perfectly parallelizable across N processors. The parallel part, ideally, finishes in p·T / N — spread evenly with no overhead — while the serial part still takes s·T. So the time on N processors is:

$T_N=sT+\frac{pT}{N}=sT+\frac{(1-s)T}{N}$

Walking the symbols: s·T is the serial time, unchanged because you cannot parallelize it; (1−s)·T / N is the parallel time, the parallel work (1−s)·T divided evenly among N workers. Speedup is the ratio of one-processor time to N-processor time:

$S(N)=\frac{T}{T_N}=\frac{1}{s+\frac{1-s}{N}}$

Reading it: the denominator is the serial fraction s plus the shrunken parallel fraction (1−s)/N. As you add processors, only the second term shrinks; the first is a hard floor. Taking the limit as N → ∞, the parallel term vanishes and the whole expression collapses to:

$S_{\max }={\lim }_{N\to \infty }S(N)=\frac{1}{s}$

This is the punchline. If s = 0.05 (5% serial), the ceiling is 1/0.05 = 20× — with a thousand cores or a million, you never beat 20× on that fixed problem (Wikipedia). If s = 0.10, the ceiling is 10×; if s = 0.01, it is 100×. The serial fraction is a tyrant.

A worked table. Take a 10-second job that is 90% parallelizable (s = 0.1, p = 0.9), from the Dive Into Systems text (Dive Into Systems):

Cores N	Serial time	Parallel time	Total	Speedup
1	1 s	9 s	10 s	1.00×
10	1 s	0.9 s	1.9 s	5.26×
100	1 s	0.09 s	1.09 s	9.17×
1000	1 s	0.009 s	1.009 s	9.91×

Going from 10 to 1000 cores — a hundredfold increase in hardware — moves speedup from 5.26× to 9.91×, creeping toward the ceiling of 10× and never crossing it. The parallel time has become negligible; you are now paying entirely for the one immovable second of serial work. This is the phenomenon of diminishing returns: past a point, more cores buy essentially nothing.

The generalized form. Amdahl’s law is not only about processor count — it is the general law of partial optimization. If a fraction p of execution benefits from a speedup factor k (not necessarily parallelism — a faster disk, a vectorized loop, a better algorithm on part of the code), overall speedup is 1 / ((1 − p) + p/k) (Wikipedia). This is why optimizing 99% of a program by 100× still yields only about 50× overall — the untouched 1% now dominates. The engineering corollary is make the common case fast: speeding up a part that is rarely executed is nearly worthless, and the payoff of any optimization is capped by the fraction of time it touches.

Gustafson’s Law: The Scaled Reframe

For two decades Amdahl’s law was read as a death sentence for massive parallelism. Then, in 1988, John Gustafson and Edwin Barsis at Sandia National Laboratories published a two-page Communications of the ACM note reevaluating it, prompted by an inconvenient fact: their team had just achieved speedups over 1000× on a 1024-processor NCUBE hypercube — which Amdahl’s law, taken naively, said should be impossible if any meaningful serial fraction existed (ACM).

Their resolution was to challenge Amdahl’s hidden assumption: that the problem size is fixed as processors are added. Gustafson argued that in practice nobody buys a thousand-processor machine to run the same small problem faster — they run a bigger problem (finer mesh, more particles, higher resolution) in about the same wall-clock time they were willing to spend before. The observation that makes this work is that the serial part of scientific codes — reading input, initialization, final output — tends not to grow as the problem scales, while the parallel part grows with the data (Gustafson reprint via Bremen).

The formula and every symbol. Gustafson measures the serial and parallel fractions on the parallel machine, not on a hypothetical serial baseline — this reframing is the crux. Let s now be the fraction of time the N-processor run spends in serial code and p = 1 − s the fraction it spends in parallel code. Ask: how long would this same amount of work take on one processor? The serial part still takes its s; the parallel part, which ran in time p across N processors, would take p·N on one. So the hypothetical serial time is s + p·N, and the scaled speedup is that over the parallel time (normalized to 1):

$S_{\text{scaled}}(N)=s+pN=s+(1-s)N$

Simplifying gives the two equivalent forms usually quoted (Wikipedia):

$S_{\text{scaled}}(N)=N-s(N-1)=N+(1-N)s$

Walking the symbols: start from N (the ideal linear speedup) and subtract a penalty s·(N − 1) proportional to the serial fraction. With s = 0 the speedup is exactly N; with s small it is only slightly below N, and — crucially — it keeps rising as N grows rather than flattening at a ceiling. The relationship is linear in N, not asymptotically bounded.

Gustafson’s own numbers. On the 1024-processor NCUBE, three application classes reported scaled speedups very close to the 1024 ideal, corresponding to small measured serial fractions (Bremen reprint):

Application	Serial fraction s	Scaled speedup (N = 1024)
Wave / beam-stress mechanics	~0.4%	~1021
Fluid dynamics	~0.6%	~1020
Structural (beam strain) analysis	~0.8%	~1016

Plug s = 0.004 into N − s(N − 1) with N = 1024: 1024 − 0.004 × 1023 ≈ 1020, matching the reported figure. The lesson Gustafson drew: on a scaled workload, near-linear speedup is not only possible but ordinary.

Reconciling the Two: Same Arithmetic, Different Question

The apparent contradiction — Amdahl says “20× is your ceiling,” Gustafson says “1020× is routine” — dissolves once you notice the two laws answer different questions and even define the serial fraction differently. Amdahl’s s is measured against the single-processor run of a fixed problem; Gustafson’s s is measured on the parallel run of a grown problem. Yuan Shi showed the two are mathematically inter-translatable: Gustafson’s reported scaled serial fractions correspond to much smaller Amdahl-style (non-scaled) fractions on the correspondingly larger problem, and when properly converted, both formulas predict the same measured speedups (Shi, Temple). They are two views of one phenomenon, distinguished only by whether problem size is held constant or scaled with the machine (arXiv 0809.1177).

The community names for the two questions are strong scaling and weak scaling:

• Strong scaling (Amdahl): fixed total problem size, increasing processors. Metric: how much faster does the same job finish? Bounded by 1/s. This is what you want when you have one big computation and need the answer sooner.
• Weak scaling (Gustafson): problem size grows in proportion to processors, roughly fixed wall-clock time. Metric: how much bigger a job can you do in the same time? Rises linearly. This is what you want when accuracy or resolution is limited by compute and you would gladly solve a larger instance.

Neither is “right.” A latency-bound service that must answer one query fast lives under Amdahl’s ceiling; a climate simulation that can always use a finer grid lives in Gustafson’s optimistic regime. The practitioner’s job is to identify which regime the workload is in before estimating payoff.

Failure Modes and Common Misunderstandings

Ignoring parallel overhead — both laws are optimistic. Both formulas assume the parallel part divides perfectly with zero coordination cost. Reality adds thread creation, synchronization, communication, and load imbalance, all of which grow with N. So real curves fall below even Amdahl’s pessimistic ceiling and can turn downward past an optimum — the regime The Universal Scalability Law models with an explicit contention-and-coherency penalty. Treat Amdahl as an upper bound you will not reach, not a target.

Confusing the two serial fractions. Quoting “our code is 5% serial” is meaningless without saying 5% of what — the single-processor fixed run (Amdahl) or the scaled parallel run (Gustafson). They are different numbers about different problems, and conflating them is the single most common error in scaling discussions.

Assuming the serial fraction is constant. The serial fraction is rarely a fixed property of the code; it depends on input size, data layout, and even N. Super-linear speedups (S > N) occasionally appear — usually because more processors bring more aggregate cache, so the per-processor working set fits where it did not before, or because a parallel algorithm does asymptotically less total work than the serial one (Shi’s “non-structure-persistent” algorithms) (Shi, Temple). These do not violate the laws; they violate the laws’ assumptions (equal total work, no memory-hierarchy effects).

Uncertain

Verify: the exact serial-fraction figures (~0.4%, 0.6%, 0.8%) and the mapping to specific application domains on the 1024-processor NCUBE. Reason: these come from a secondary reprint and a fetched-PDF summary of Gustafson’s 1988 CACM note, not a clean primary read (the ACM PDF returned HTTP 403 and johngustafson.net failed the TLS handshake during this task). The numbers are internally consistent (0.4% → ~1020 via the formula) but the domain labels vary slightly across secondary sources. To resolve: obtain the primary CACM note (doi:10.1145/42411.42415) and confirm the per-application figures. #uncertain

Uncertain

Verify: Amdahl’s original serial-fraction estimate as “20%–40% data-management housekeeping.” Reason: Amdahl’s 1967 PDF would not parse cleanly during this task (binary/compressed), so this rests on secondary summaries (HPCwire and search-index snippets) that variously quote “~40%” or “20–40%.” To resolve: read the primary AFIPS 1967 paper text directly. #uncertain

Practical Lesson

The engineering takeaway compresses to a few rules. First, estimate the serial fraction before you parallelize — if 30% of your runtime is inherently sequential, Amdahl caps you at about 3.3× and buying more cores is nearly pointless; the leverage is in shrinking s, not adding N. Second, decide whether your problem is fixed-size or scalable — if you can profitably solve a bigger instance, Gustafson says the hardware pays off and you should scale the problem to the machine; if the instance is fixed, respect the ceiling. Third, attack the serial part, because under Amdahl it is worth vastly more than optimizing the already-parallel part (the generalized law: payoff is bounded by the fraction of time you touch). Fourth, measure, don’t extrapolate — both laws ignore overhead, so past a modest N the empirical curve is the only truth, and Scalability Bottlenecks and Contention plus the USL explain why it may bend down rather than merely flatten.

See Also

• The Universal Scalability Law — Gunther’s extension that adds contention and coherency penalties; explains why real throughput can peak then fall, beyond Amdahl’s mere flattening
• Scalability Bottlenecks and Contention — diagnosing where parallelism stops paying; hot locks, serialization points, Little’s Law
• Concurrency versus Parallelism — the prior distinction; these laws bound parallelism (throughput), not concurrency (structure)
• Data Parallelism and SIMD — the embarrassingly-parallel regime where s ≈ 0 and both laws are kind
• Cache-Conscious and NUMA-Aware Parallelism — the memory-hierarchy realities that keep the parallel fraction from dividing perfectly (and cause super-linear anomalies)
• Task Parallelism versus Data Parallelism — how the decomposition choice affects the achievable parallel fraction
• Concurrency and Parallelism MOC — parent map (§9 Parallelism — Patterns and Performance)