Amdahl's Law and Gustafson's Law: Worked examples — Hardware deep dive

This page drills the parent laws against every kind of input they can face: the friendly middle-of-the-road case, the two extremes ( $f = 0$ and $f = 1$ ), the "infinite cores" limit, a serial fraction hidden inside a word problem, and the classic exam trap where you must pick the right law. Before we compute anything, let us name every symbol.

The scenario matrix

Every worked example below is tagged with the cell it lands on. Together they touch every cell.

#	Case class	What is special about the input	Which law	Example
A	Typical mid-range	$0 < f < 1$ , finite $n$	Amdahl	Ex 1
B	Degenerate: $f = 0$	nothing serial	both	Ex 2
C	Degenerate: $f = 1$	nothing parallel	both	Ex 2
D	Limit $n \to \infty$	serial ceiling	Amdahl	Ex 3
E	Hidden $f$ (profiling trap)	$f$ from time, not code lines	Amdahl	Ex 4
F	Scaled workload	problem grows with $n$	Gustafson	Ex 5
G	Same numbers, both laws	compare pessimist vs optimist	both	Ex 6
H	Inverse problem	given $S$ , solve for $f$	Amdahl	Ex 7
I	Exam twist: choose the law	word problem, ambiguous	judgment	Ex 8

The picture that ties the whole matrix together — how speedup bends as $f$ changes. Figure s01: the horizontal axis is the number of processors $n$ (1 to 64); the vertical axis is the Amdahl speedup $S_{A} (n)$ . The grey dashed line is the impossible ideal $S = n$ . The green curve ( $f = 0$ ) rides on that ideal; as $f$ grows to $0.05$ (blue), $0.15$ (orange), $0.3$ (red) the curves peel away and flatten sooner — the red arrow marks how a bigger $f$ gives a flatter, lower curve.

Figure — Amdahl's Law and Gustafson's Law

Case A — the ordinary Amdahl case ( $0 < f < 1$ )

Worked example Ex 1 · Rendering a fixed image

A render takes $T_{1} = 200$ s on one core. Colour-space setup is $30$ s (serial); shading the pixels is $170$ s (parallel). Find $S (8)$ with 8 cores.

Forecast: 8 cores, but a chunk is serial — guess: somewhere between 4 and 6?

Step 1 — get $f$ (Amdahl clock: fraction of $T_{1}$ ). $f = \frac{30}{200} = 0.15$ Why this step? For Amdahl, $f$ is a fraction of the one-core time $T_{1}$ , and here we were handed those times directly, so we divide serial-time by $T_{1}$ .

Step 2 — plug into Amdahl. $S_{A} (8) = \frac{1}{0.15 + \frac{0.85}{8}} = \frac{1}{0.15 + 0.10625} = \frac{1}{0.25625}$ Why this step? Same problem, we only want it to finish faster → Amdahl ( $S_{A}$ ), not Gustafson.

Step 3 — evaluate. $S_{A} (8) \approx 3.902$ Why this step? A speedup is a plain number, so we finish by turning the fraction $1/0.25625$ into a decimal — that decimal is the "how many times faster" answer the question asked for.

Verify: New time $= T_{1} / S = 200/3.902 \approx 51.25$ s $= T_{8}$ . Sanity check by rebuilding $T_{8}$ directly: serial $30$ s stays, parallel $170/8 = 21.25$ s, total $30 + 21.25 = 51.25$ s. ✓ Matches — and $3.9 < 8$ , exactly the "serial fraction robs you" behaviour we predicted.

Load imbalance and coordination make the effective $f$ worse than the algorithmic one — see Load Balancing and Thread Synchronization.

Cases B & C — the two degenerate ends ( $f = 0$ and $f = 1$ )

Worked example Ex 2 · The extremes on 16 cores

Compute both laws at $n = 16$ for (i) $f = 0$ (nothing serial) and (ii) $f = 1$ (nothing parallel).

Forecast: $f = 0$ should give the dream ( $16 \times$ ); $f = 1$ should give the nightmare ( $1 \times$ , no help).

Step 1 — Amdahl at $f = 0$ . $S_{A} (16) = \frac{1}{0 + \frac{1}{16}} = 16$ Why? With no serial part, the denominator is just $1/ n$ , so speedup $= n$ : perfect linear.

Step 2 — Amdahl at $f = 1$ . $S_{A} (16) = \frac{1}{1 + 0} = 1$ Why? All work is serial; extra cores sit idle → no speedup ever.

Step 3 — Gustafson at the same ends. $S_{G} (16)_{f = 0} = 16 - 0 = 16, S_{G} (16)_{f = 1} = 16 - 1 \cdot 15 = 1$ Why this step? At the degenerate ends both laws must agree — with $f = 0$ there is nothing to "scale up," with $f = 1$ nothing can move. (At these ends the two clocks $T_{1}$ and $T_{n}$ give the same $f$ , so the ambiguity vanishes.)

Verify: All four numbers are ${16, 1, 16, 1}$ ; the two laws coincide exactly at the boundaries, which is the correct consistency check. ✓

Case D — the infinite-core ceiling

Worked example Ex 3 · How much can more cores

ever buy? A pipeline has $f = 0.2$ . Compute $S_{A}$ at $n = 4$ , $n = 100$ , and the limit $n \to \infty$ .

Forecast: Doubling and re-doubling cores should give diminishing returns, flattening near some ceiling.

Step 1 — $n = 4$ . $S_{A} (4) = \frac{1}{0.2 + \frac{0.8}{4}} = \frac{1}{0.2 + 0.2} = 2.5$ Why this step? We start with the smallest core count to establish a baseline speedup; only by having a low- $n$ number can we later see how little the returns grow when we crank $n$ way up.

Step 2 — $n = 100$ . $S_{A} (100) = \frac{1}{0.2 + \frac{0.8}{100}} = \frac{1}{0.208} \approx 4.808$ Why this step? Jumping from 4 to 100 cores (a $25 \times$ jump) only moved speedup from $2.5$ to $4.8$ — proof the returns are collapsing.

Step 3 — the limit. As $n \to \infty$ , the term $\frac{1 - f}{n} \to 0$ , so $S_{m a x} = \frac{1}{f} = \frac{1}{0.2} = 5$ Why this step? The parallel part shrinks to zero time; only the immovable serial part remains, and $1/ f$ is that hard wall.

Verify: $4.808 < 5$ and $2.5 < 5$ : every finite case sits below the ceiling, and $n = 100$ already gets $96%$ of the way there. ✓ See Scalability Analysis for why chasing the last $4%$ is rarely worth it.

The dashed line in the figure below is exactly this $1/ f$ ceiling. Figure s02: horizontal axis is $n$ (1 to 120), vertical axis is $S_{A} (n)$ for $f = 0.2$ (blue curve). The red dashed horizontal line sits at $1/ f = 5$ . Two dots mark our worked points — the orange dot at $n = 4, S = 2.5$ and the green dot at $n = 100, S \approx 4.81$ — showing the curve creeping toward but never touching the red ceiling.

Case E — the hidden serial fraction (profiling trap)

Worked example Ex 4 · When counting lines lies to you

A loop runs 1000 iterations. 990 are parallelizable; 10 must run serially. Naively you'd say $f = 10/1000 = 0.01$ . But each serial iteration does disk I/O and takes $10 \times$ as long as a parallel one. Find the true $f$ and $S_{A} (20)$ .

Forecast: The real $f$ is way above $0.01$ ; speedup will disappoint.

Step 1 — put everything in time units. Let one parallel iteration $= 1$ unit.

Parallel time $= 990 \times 1 = 990$ units.
Serial time $= 10 \times 10 = 100$ units. Why this step? $f$ is a fraction of time; iterations that take longer must be weighted by their length, not counted equally.

Step 2 — total and fraction (Amdahl clock: fraction of $T_{1}$ ). $f = \frac{100}{990 + 100} = \frac{100}{1090} \approx 0.09174$ Why this step? By definition $f = \frac{serial time}{total time T _{1}}$ , so we add the two time pools from Step 1 to get $T_{1}$ , then take the serial slice of it — this converts our raw time units into the pure fraction the formula needs.

Step 3 — Amdahl at $n = 20$ . $S_{A} (20) = \frac{1}{0.09174 + \frac{0.90826}{20}} = \frac{1}{0.09174 + 0.04541} = \frac{1}{0.13716} \approx 7.29$ Why this step? We now feed the honest $f$ (and its complement $1 - f = 0.90826$ ) into Amdahl for the requested 20 cores — this is the payoff number that exposes how badly the naive $f = 0.01$ would have lied.

Verify: With the fake $f = 0.01$ you'd have predicted $S_{A} (20) = 1/ (0.01 + 0.0495) = 16.8$ — more than double the truth. The lesson of Performance Metrics: always profile time, never count code. ✓

Case F — the scaled workload (Gustafson)

Worked example Ex 5 · A bigger climate model

A climate run finishes in $T_{n} = 1$ hour on $n = 256$ cores. Setup is 3 min (serial); the grid solve is 57 min (parallel). Gustafson speedup?

Forecast: The parallel part dominates, so speedup should be close to $256$ .

Step 1 — $f$ from the parallel-run reference (Gustafson clock: fraction of $T_{n}$ ). $f = \frac{3}{60} = 0.05$ Why this step? Gustafson measures fractions of the already-parallel run-time $T_{n}$ (here $T_{n} = 60$ min), and we were given those minutes.

Step 2 — Gustafson formula. $S_{G} (256) = 256 - 0.05 (256 - 1) = 256 - 0.05 \cdot 255 = 256 - 12.75 = 243.25$ Why Gustafson? We are not re-running the same small model faster — we packed a finer grid into the fixed 1-hour budget. The problem grew with the cores.

Verify: How long would this same, bigger workload take on one core? Its serial part is unchanged at $f \cdot T_{n}$ ; its parallel part, done serially, is $n$ times longer, $n (1 - f) \cdot T_{n}$ . Adding these gives $T_{1} = f \cdot T_{n} + n (1 - f) \cdot T_{n} = T_{n} [f + n (1 - f)] .$ Numerically $T_{1} = 1 \cdot [0.05 + 256 \cdot 0.95] = 243.25$ hours. Divide by the 1-hour actual run $T_{n}$ → $S_{G} = T_{1} / T_{n} = 243.25 \times$ . ✓ Consistent with GPU Computing scaling intuition.

Where does $S_{G} (n)$ live relative to Amdahl? Figure s03: horizontal axis is $n$ (1 to 64); vertical axis is speedup. The green line is Gustafson $S_{G} (n)$ for $f = 0.05$ — it rides just under the grey dashed ideal $S = n$ and keeps climbing. The blue curve is Amdahl $S_{A} (n)$ for the same $f = 0.05$ , which flattens toward its $1/ f = 20$ ceiling (red dashed). The gap between green and blue is the whole "pessimist vs optimist" story.

Case G — same numbers, both laws (pessimist vs optimist)

Worked example Ex 6 ·

$f = 0.1$ , $n = 32$ , judged twice Compute $S_{A} (32)$ and $S_{G} (32)$ for the identical $f = 0.1$ .

Forecast: Amdahl small (near its $1/ f = 10$ wall), Gustafson large (near $32$ ).

Step 1 — Amdahl. $S_{A} (32) = \frac{1}{0.1 + \frac{0.9}{32}} = \frac{1}{0.1 + 0.028125} = \frac{1}{0.128125} \approx 7.805$ Why this step? We first answer the fixed-problem question ( $f$ against $T_{1}$ ): with the same job on 32 cores, the serial $0.1$ dominates the tiny $0.9/32$ , so the speedup is dragged down toward the $1/ f = 10$ wall.

Step 2 — Gustafson. $S_{G} (32) = 32 - 0.1 (31) = 32 - 3.1 = 28.9$ Why this step? Now we answer the scaled-problem question ( $f$ against $T_{n}$ ) on the identical numeric $f$ : here $n = 32$ leads and the serial term subtracts only a small $3.1$ , so speedup sits just under the linear ideal $n = 32$ — the deliberate contrast with Step 1.

Verify: $7.805 < 10 = 1/ f$ (below Amdahl's ceiling ✓) and $28.9 < 32 = n$ (below Gustafson's linear ideal ✓). Both obey their own upper bound. ✓

Case H — the inverse problem (given speedup, find the bottleneck)

Worked example Ex 7 · Back-calculating

$f$ You measured $S_{A} (8) = 5$ on 8 real cores. What effective serial fraction does this imply?

Forecast: $5$ out of a possible $8$ is decent, so $f$ should be modestly small (well under $0.1$ ).

Step 1 — invert Amdahl. Start from $S = \frac{1}{f + \frac{1 - f}{n}}$ , so $\frac{1}{S} = f + \frac{1 - f}{n}$ . Why this step? We know $S$ and $n$ ; the unknown is $f$ , so we solve algebraically — flipping both sides turns the awkward reciprocal into a plain linear equation in $f$ .

Step 2 — isolate $f$ . Multiply through by $n$ : $\frac{n}{S} = n f + 1 - f = 1 + f (n - 1) \Rightarrow f = \frac{\frac{n}{S} - 1}{n - 1}$ Why this step? Multiplying by $n$ clears the fraction $\frac{1 - f}{n}$ so every term is a whole multiple of $f$ ; then we collect the two $f$ -terms ( $n f - f = f (n - 1)$ ), move the lone $1$ across, and divide by $(n - 1)$ — the standard "gather the unknown, then divide" moves that leave $f$ alone on one side.

Step 3 — plug $S = 5, n = 8$ . $f = \frac{\frac{8}{5} - 1}{7} = \frac{1.6 - 1}{7} = \frac{0.6}{7} \approx 0.0857$

Verify: Forward-check: $S_{A} (8) = \frac{1}{0.0857 + \frac{0.9143}{8}} = \frac{1}{0.0857 + 0.11429} = \frac{1}{0.2} = 5$ . ✓ The recovered $f \approx 8.6%$ tells you where to hunt (locks, Cache Coherence traffic).

Case I — the exam twist: which law?

Worked example Ex 8 · Choose the law, then compute

"A search engine indexes a fixed 1 TB corpus. On 1 machine it takes $T_{1} = 800$ s; of that, 80 s is a serial merge step. On 10 machines, what speedup do you expect?" Then a second clause: "If instead you index a corpus that grows to 10 TB on the 10 machines while keeping the 80 s merge, what speedup?"

Forecast: Clause 1 = fixed problem → Amdahl. Clause 2 = problem scales with machines → Gustafson.

Step 1 — clause 1, get $f$ (Amdahl clock: fraction of $T_{1}$ ) and pick Amdahl. $f = \frac{80}{800} = 0.1$ $S_{A} (10) = \frac{1}{0.1 + \frac{0.9}{10}} = \frac{1}{0.1 + 0.09} = \frac{1}{0.19} \approx 5.263$ Why Amdahl? The word fixed is the tell — same work, finish sooner, so $f$ is a slice of the one-core time $T_{1} = 800$ s.

Step 2 — clause 2, same $n = 10$ , but scaled → Gustafson. Let $f^{'}$ denote the serial fraction measured on the 10-machine run $T_{n}$ (the Gustafson clock), as opposed to the single-machine $f$ of clause 1. The parallel work is the part that grew $10 \times$ ; the merge stays $80$ s out of the $800$ s ten-machine run, so $f^{'} = \frac{80}{800} = 0.1, S_{G} (10) = 10 - f^{'} (10 - 1) = 10 - 0.1 \cdot 9 = 10 - 0.9 = 9.1$ Why Gustafson? The corpus grew with the machines — the classic Gustafson signal, so we use $S_{G}$ with the run-referenced fraction $f^{'}$ .

Verify: Same physical hardware, same numeric fraction ( $f = f^{'} = 0.1$ ), but the question flips the answer from $5.26$ (fixed) to $9.1$ (scaled). ✓ Both live below their bounds ( $1/ f = 10$ and $n = 10$ ). The exam point: read whether the problem size is held or grown.

Recall Quick self-test

$T_{1}$ and $T_{n}$ mean ::: run-time on one core, and run-time on $n$ cores, respectively. Amdahl measures $f$ against which clock? ::: the one-core time $T_{1}$ . Gustafson measures $f$ against which clock? ::: the $n$ -core run-time $T_{n}$ . At $f = 0$ Amdahl and Gustafson both give ::: $S = n$ (they agree). The Amdahl ceiling as $n \to \infty$ is ::: $1/ f$ . To recover $f$ from a measured $S_{A} (n)$ use ::: $f = \frac{n / S - 1}{n - 1}$ . The single word that decides Amdahl-vs-Gustafson is ::: whether the problem is fixed or scaled.