Amdahl's Law and Gustafson's Law: Visual walkthrough

This page assumes nothing except that you can measure time. Related ideas live in Scalability Analysis, Performance Metrics, Parallel Architectures, and Load Balancing — but you do not need them yet. Prefer Hindi? Yeh note Hinglish mein →.

Step 1 — Draw the work as a bar of time

WHAT. A program runs. It takes some amount of time. Draw that time as a horizontal bar. The length of the bar is how long the job takes — nothing more. Call that total time $T_{1}$ .

$T_{1}$ — the 1 means "on one processor". It is the time our single worker takes to finish the whole job, start to end.

WHY. Before we can talk about "going faster", we need a picture of what "the work" even is. A bar is the honest picture: time flows left to right, and the whole job is the whole bar. Everything else on this page is us cutting and shrinking this bar.

PICTURE. The full bar below is $T_{1}$ . Right now it is one solid colour — we have not yet split it into parts.

Figure — Amdahl's Law and Gustafson's Law

Step 2 — Split the bar into serial and parallel parts

WHAT. Not all work is equal. Some of it must happen in a fixed order — like reading a file before you can process it, or acquiring a lock. That part is called serial. The rest can be chopped into independent pieces worked on at the same time — that part is parallel.

We cut the bar into two coloured segments:

$T_{1} = serial part f \cdot T_{1} + parallel part (1 - f) \cdot T_{1}$

$f$ — the serial fraction. It is a number between $0$ and $1$ : what portion of the total time is stuck being sequential. If $f = 0.2$ , then one-fifth of the bar is serial.
$f \cdot T_{1}$ — the fraction $f$ times the total time = the actual length of the serial segment in seconds.
$1 - f$ — "everything that is not serial", so this is the parallel fraction.
$(1 - f) \cdot T_{1}$ — the length of the parallel segment in seconds.

WHY. This split is the entire idea behind both laws. The serial piece is the villain — we cannot speed it up by adding workers. The parallel piece is the hero — it shrinks when we add workers. To reason about speedup we must first name and colour these two enemies.

PICTURE. The magenta chunk is serial (frozen, never shrinks). The orange chunk is parallel (the part we will attack). Notice their lengths add back up to the full bar.

Step 3 — Add processors and shrink only the parallel part

WHAT. Now bring in $n$ processors ( $n$ workers). Hand the parallel work to all $n$ of them at once. If the work divides perfectly, $n$ workers finish it in $1/ n$ of the time. The serial part still runs on one worker — it does not shrink at all.

The new total time on $n$ processors is:

$T_{n} = serial: unchanged f \cdot T_{1} + parallel: shrunk n times \frac{( 1 - f ) \cdot T _{1}}{n}$

$n$ — the number of processors. $n = 1$ means one worker (back to $T_{1}$ ); big $n$ means a big crowd.
$\frac{( 1 - f ) \cdot T _{1}}{n}$ — take the parallel segment and divide its length by $n$ . Twice the workers → half the parallel time. Ten workers → one-tenth.
The serial term has no $n$ in it — that is the whole tragedy. More workers cannot touch it.

WHY. This is the honest model of adding cores: the divisible work divides, the stubborn work stays. Everything about Amdahl's pessimism comes from that one term with no $n$ .

PICTURE. The magenta (serial) block is exactly as long as before. The orange (parallel) block has been squeezed to $1/ n$ of its width. Watch how the serial block now dominates the shrunken bar.

Step 4 — Define speedup as a ratio of bar lengths

WHAT. "How much faster did we get?" is answered by comparing the two bars: the old length divided by the new length. Call that ratio speedup $S (n)$ .

$S (n) = \frac{T _{1}}{T _{n}} = \frac{T _{1}}{f \cdot T _{1} + \frac{( 1 - f ) \cdot T _{1}}{n}}$

$S (n)$ — speedup. $S = 4$ means "four times faster than one processor".
Numerator $T_{1}$ — the original bar length.
Denominator $T_{n}$ — the shrunken bar length.

WHY. Speedup must be a ratio, because "faster" is always relative. A ratio also lets us cancel the units (seconds) — we care about the factor, not the raw seconds. That cancellation is the next step and it is beautiful.

PICTURE. Two bars stacked: the long original $T_{1}$ on top, the short $T_{n}$ below. The red bracket shows the ratio — how many copies of the short bar fit inside the long one.

Step 5 — Cancel $T_{1}$ to get Amdahl's Law

WHAT. Every term in the fraction carries a $T_{1}$ . Factor it out of the bottom and cancel it against the top. The absolute time vanishes.

$S (n) = \frac{T _{1}}{T _{1} ( f + \frac{1 - f}{n} )} = \frac{1}{f + \frac{1 - f}{n}}$

The $T_{1}$ on top and the $T_{1}$ factored out below cancel — leaving a clean $1$ on top.
Bottom: $f$ (the frozen serial share) plus $\frac{1 - f}{n}$ (the shrinking parallel share).

WHY. Cancelling $T_{1}$ tells us something deep: speedup does not depend on how big the job is — only on the fraction $f$ and the worker count $n$ . A 3-second job and a 3-hour job with the same $f$ scale identically.

PICTURE. The $T_{1}$ symbols on top and bottom glow, then cross out; what remains is a formula built only from $f$ and $n$ .

Step 6 — Push $n$ to infinity: the ceiling

WHAT. What is the best you could ever do with unlimited processors? Let $n$ grow without bound. The term $\frac{1 - f}{n}$ has $n$ in its denominator, so as $n$ gets huge this term shrinks to zero. Only $f$ survives.

$S_{m a x} = lim_{n \to \infty} \frac{1}{f + \frac{1 - f}{n}} = \frac{1}{f}$

$n \to \infty lim$ — "watch what happens as $n$ becomes enormous". We use a limit here because we want the ceiling — the value the curve flattens toward but never crosses.
$\frac{1 - f}{n} \to 0$ — a fixed number divided by an ever-bigger number heads to zero.
Result $\frac{1}{f}$ — a hard wall. If $f = 0.1$ , the ceiling is $10 \times$ . A million cores cannot beat it.

WHY. We use a limit because "infinitely many processors" is exactly the question a limit answers: what value do we approach? This is the single most important consequence of the whole derivation — the serial fraction sets an unbreakable ceiling.

PICTURE. The speedup curve climbs, then bends and flattens against a dashed horizontal line at height $1/ f$ . It hugs the ceiling forever without touching it.

Step 7 — Degenerate cases: the two extremes

WHAT. Always check the boundaries, so no reader hits a surprise.

$f = 0$ (nothing serial). Formula: $S (n) = \frac{1}{0 + \frac{1}{n}} = n$ . Perfect linear speedup — 8 cores give exactly $8 \times$ . The bar is all orange; it shrinks fully.
$f = 1$ (all serial). Formula: $S (n) = \frac{1}{1 + 0} = 1$ . No speedup ever. The bar is all magenta; adding workers does literally nothing.
$n = 1$ (one worker). $S (1) = \frac{1}{f + ( 1 - f )} = \frac{1}{1} = 1$ . Sanity check: one processor is, by definition, exactly as fast as itself.

WHY. These extremes are the anchor posts of the whole formula. If a formula behaves sensibly at $f = 0$ , $f = 1$ , and $n = 1$ , you can trust it in between. They also show the two personalities of every program: fully parallel (dream) vs fully serial (nightmare).

PICTURE. Three little bars side by side — all-orange ( $f = 0$ ), all-magenta ( $f = 1$ ), and a single-worker bar — each labelled with the speedup it produces.

Step 8 — Gustafson's flip: measure from the parallel run

WHAT. Amdahl asked "same job, how much faster?" Gustafson asks the opposite: "same time, how much MORE work?" The trick is to start from the parallel run and imagine forcing it back onto one core.

Start with a job that fills $n$ processors in time $T_{n}$ , split as before:

$T_{n} = serial f \cdot T_{n} + parallel, on n cores (1 - f) \cdot T_{n}$

Now redo that same amount of work on one processor. The serial part is unchanged, but the parallel part — which $n$ cores chewed through together — would take $n$ times longer alone:

$T_{1} = f \cdot T_{n} + n (1 - f) \cdot T_{n} = T_{n} [f + n (1 - f)]$

Speedup is again the ratio, and $T_{n}$ cancels:

$S (n) = \frac{T _{1}}{T _{n}} = f + n (1 - f) = n - f (n - 1)$

$n (1 - f) \cdot T_{n}$ — the key move: the parallel work that $n$ cores did in time $(1 - f) T_{n}$ would take $n \times$ that on one core.
$n - f (n - 1)$ — grows almost linearly with $n$ when $f$ is small.

WHY. In real supercomputing we don't shrink the runtime — we grow the problem (finer weather grid, bigger neural net) to fill the new cores in the same wall-clock time. Gustafson measures that. The serial part now stays a fixed slice of the fixed runtime, so it no longer imposes a ceiling — that is why big machines feel worth it.

PICTURE. Left: the parallel bar (fixed time $T_{n}$ , small serial slice). Right: the same work stretched onto one core — the orange parallel block explodes to $n$ times its width while magenta stays put.

The one-picture summary

Two bars tell the whole story. Amdahl keeps the job fixed and shrinks time — the frozen serial slice grows to dominate, so speedup slams into the ceiling $1/ f$ . Gustafson keeps time fixed and grows the job — the serial slice stays a small fixed share, so speedup climbs almost like $n$ .

Recall Feynman retelling — say it like a story

Imagine a job as a bar of coloured time. One colour (magenta) is stubborn work that must go in order; the other (orange) can be shared. Add workers and only the orange shrinks — the magenta just sits there. Speedup is just the old bar length divided by the new one. When you cancel the length, you learn speedup depends only on the fractions, not the size. Send in infinitely many workers and the orange vanishes entirely, but the magenta remains, capping you at $1/ f$ forever — that's Amdahl. Then flip your question: don't ask "how much faster on the same job", ask "how much bigger a job in the same time". Now the stubborn part is a fixed sliver of a fixed clock, and the shareable part balloons with every worker — so speedup climbs almost straight up. That's Gustafson. Same two colours, two different questions, two different destinies.

Recall Quick self-test

With $f = 0.25$ and $n = 4$ , Amdahl speedup? ::: $\frac{1}{0.25 + 0.75/4} = \frac{1}{0.4375} \approx 2.29$ Same $f$ and $n$ , Gustafson speedup? ::: $4 - 0.25 (3) = 4 - 0.75 = 3.25$ Amdahl ceiling for $f = 0.25$ ? ::: $1/0.25 = 4$ At $f = 0$ , Amdahl $S (n)$ equals? ::: exactly $n$ (perfect linear speedup) At $f = 1$ , Amdahl $S (n)$ equals? ::: exactly $1$ (no speedup, all serial)