Amdahl's Law
Suppose you have a program that takes an hour to run, and you throw a hundred processors at it. Does it
finish in 36 seconds? Almost never — and Amdahl's law is the reason. It is the single
most sobering equation in computer architecture: a hard ceiling on how much any speedup can help, set
entirely by the part of the work you cannot speed up.
The idea is disarmingly simple. Split a task into the fraction p that benefits
from your improvement and the fraction 1-p that does not. Speed the good part
up by a factor s, and the overall speedup is
S \;=\; \frac{1}{(1-p) \;+\; \dfrac{p}{s}}.
The stubborn (1-p) term never goes away, no matter how big
s gets — and that is what caps you.
The ceiling: let the fast part become free
Push the improvement to its limit — make the accelerated part infinitely fast,
s \to \infty. The term p/s vanishes and the speedup
hits a wall:
S_{\max} \;=\; \lim_{s\to\infty} \frac{1}{(1-p) + p/s} \;=\; \frac{1}{1-p}.
Read that carefully. If 10\% of your program is stubbornly serial
(p = 0.9), then even with an infinitely fast parallel part you can
never beat 1/(1-0.9) = 10\times. Halve every parallel instruction to zero
time and the serial tenth still costs a tenth of the original hour. The slow part you ignored becomes the
whole story.
- speeding up a fraction p of the work by s\times
gives an overall speedup S = \dfrac{1}{(1-p) + p/s};
- the absolute ceiling, as s \to \infty, is
S_{\max} = \dfrac{1}{1-p};
- the serial fraction (1-p) dominates: shrinking it
matters far more than growing s.
Watch the curve flatten
Here s = N, the number of processors, so
S(N) = 1/\big((1-p) + p/N\big). Drag the parallel-fraction slider and watch
two things: the curve bends over and hugs a horizontal ceiling, and that ceiling
1/(1-p) shoots up dramatically as p approaches
1. Getting from p = 0.9 to
p = 0.99 is worth far more than getting from 16 to 64 cores.
Worked example: the 95% program
A workload is 95\% parallelisable (p = 0.95). With
N = 8 processors,
S = \frac{1}{0.05 + 0.95/8} = \frac{1}{0.05 + 0.11875} = \frac{1}{0.16875} \approx 5.93\times.
Eight processors, but only a 5.9\times speedup — you have "lost" two cores'
worth of work to the serial 5\%. Push to N = 1024
and you get \approx 19.6\times; the ceiling is
1/0.05 = 20\times. A thousand cores buys you essentially the same result as a
few dozen. Run the code below to see the diminishing returns line by line.
// Amdahl's law: overall speedup when a fraction p is sped up by a factor s (here s = N cores).
function speedup(p: number, n: number): number {
return 1 / ((1 - p) + p / n);
}
const p = 0.95; // 95% of the work is parallelisable
console.log(`Parallel fraction p = ${p}, ceiling = ${(1 / (1 - p)).toFixed(1)}x`);
for (const n of [1, 2, 4, 8, 16, 64, 256, 1024]) {
console.log(`N = ${n}\tspeedup = ${speedup(p, n).toFixed(2)}x`);
}
Amdahl assumed a fixed problem size — the same hour of work, spread over more cores. But in
practice, when you buy a bigger machine you also solve a bigger problem: a finer weather grid, a
larger neural network. Gustafson's law captures this — if the parallel part grows with
the machine while the serial part stays roughly constant, the achievable speedup scales almost linearly
with the core count after all. Both laws are true; they just answer different questions. Amdahl asks "how
much faster is this job?", Gustafson asks "how much more can I do in the same time?" The
supercomputer wins on Gustafson's terms.
The number p is the fraction of the original running time spent in
the part you can speed up — not the fraction of lines, functions, or instructions. A single line inside a
hot loop can be 90\% of the runtime; a thousand lines of start-up code can be
0.1\%. Always weight by where the machine actually spends its cycles (a
profiler tells you), or Amdahl's law will quietly lie to you. This is also why architects obsess
over the common case: "make the common case fast" is Amdahl's law turned into advice.
Why architects live by it
Amdahl's law is why "make the common case fast" is the golden rule of this course. Every optimisation you
will meet — pipelining, caches, wider issue, more cores — speeds up some fraction of execution,
and its payoff is always throttled by whatever it leaves untouched. It is also the reason the industry
pivoted to
parallelism
only once single-core gains stalled: parallelism is powerful, but Amdahl reminds you that a small serial
remainder sets a hard ceiling you can never climb past.