Amdahl's Law and Gustafson's Law: Exercises — Hardware deep dive

This page is a self-test. Each problem is stated cleanly, then hidden inside a collapsible solution. Try it on paper first, then open the [!recall]- block to check every step. Problems climb from L1 (just recognise the pieces) to L5 (mastery — combine everything).

Before you start, keep the two master formulas from the parent note Amdahl's Law and Gustafson's Law in front of you.

Every symbol above was built in the parent note; if $f$ or "serial fraction" is fuzzy, re-read the [!mistake] on counting time vs. lines before continuing.

Level 1 — Recognition

Goal: identify $f$ , $n$ , and which formula the wording asks for. No hard algebra yet.

Exercise 1.1

A program runs in $80$ seconds on one core. Of that, $16$ seconds is serial (cannot be split) and the rest is perfectly parallel. State $f$ and $n$ if we now run on $4$ cores, and say which law applies when the question is "how fast can I finish the same 80-second job?"

Recall Solution 1.1

What we do: $f$ is serial time over total time. $f = \frac{16}{80} = 0.2$ $n = 4$ . The job is fixed size ("the same 80-second job"), so we use Amdahl's Law. The parallel fraction is $1 - f = 0.8$ .

Exercise 1.2

Match each phrase to Amdahl or Gustafson: (a) "How much bigger a simulation can I run in the same hour with more nodes?" (b) "My batch job is fixed; will 16 cores finish it 16× faster?" (c) "Problem grows to keep every processor busy."

Recall Solution 1.2

(a) Gustafson — the workload scales with resources. (b) Amdahl — fixed workload, asking for finish-speed. (c) Gustafson — the defining assumption (problem grows with $n$ ).

Exercise 1.3

A code is measured as $95%$ parallel by runtime. Write $f$ , then write the Amdahl formula for $n = 8$ without simplifying (just substitute).

Recall Solution 1.3

Parallel is $0.95$ , so serial is $f = 1 - 0.95 = 0.05$ . $S (8) = \frac{1}{0.05 + \frac{1 - 0.05}{8}} = \frac{1}{0.05 + \frac{0.95}{8}}$ (Numerically this is $\approx 5.93$ — computed in L2.)

Level 2 — Application

Goal: turn the substitution into a clean number, including the finished runtime.

Exercise 2.1

Using $f = 0.05$ , $n = 8$ from Exercise 1.3, compute $S (8)$ to two decimals and the new runtime if the one-core time was $200$ ms.

Recall Solution 2.1

Step 1 — denominator: $0.05 + \frac{0.95}{8} = 0.05 + 0.11875 = 0.16875$ . Step 2 — speedup: $S (8) = \frac{1}{0.16875} \approx 5.93$ . Step 3 — runtime: $T_{8} = \frac{T _{1}}{S} = \frac{200}{5.93} \approx 33.7$ ms. Why: speedup is $T_{1} / T_{n}$ , so $T_{n} = T_{1} / S$ . Eight cores, but only $\approx 5.9 \times$ — the $5%$ serial tax bites.

Exercise 2.2

A rendering job is $30%$ serial. Compute Amdahl speedup at $n = 2, 4, \infty$ . Look at figure below to see why the curve flattens.

Figure — Amdahl's Law and Gustafson's Law

Recall Solution 2.2

$f = 0.3$ .

$n = 2 : S = \frac{1}{0.3 + 0.35} = \frac{1}{0.65} \approx 1.54$
$n = 4 : S = \frac{1}{0.3 + 0.175} = \frac{1}{0.475} \approx 2.11$
$n \to \infty : S_{m a x} = \frac{1}{0.3} \approx 3.33$ The curve in the figure rises fast then hugs the ceiling $S_{m a x} = 1/ f$ . Serial fraction, not core count, sets the ceiling.

Exercise 2.3 (Gustafson)

A climate run uses $50$ nodes; $8%$ of the wall-clock is serial setup. Using Gustafson, find the scaled speedup.

Recall Solution 2.3

$f = 0.08$ , $n = 50$ . $S (50) = 50 - 0.08 (50 - 1) = 50 - 0.08 \times 49 = 50 - 3.92 = 46.08$ Meaning: on $50$ nodes we do $\approx 46 \times$ more grid work per hour than one node could.

Level 3 — Analysis

Goal: reason about why numbers behave as they do; invert the formula; compare the two laws.

Exercise 3.1 (Back-calculate $f$ )

You measure a real speedup of $S = 6$ on $n = 16$ cores. What is the effective serial fraction?

Recall Solution 3.1

Invert Amdahl. Start from $S = \frac{1}{f + \frac{1 - f}{n}}$ , so $\frac{1}{S} = f + \frac{1 - f}{n}$ . Multiply by $n$ : $\frac{n}{S} = n f + 1 - f = 1 + f (n - 1)$ . Solve: $f = \frac{\frac{n}{S} - 1}{n - 1}$ . Plug $n = 16, S = 6$ : $\frac{16}{6} = 2.6667$ , minus $1 = 1.6667$ , over $15$ : $f = \frac{1.6667}{15} \approx 0.1111$ So $\approx 11.1%$ of runtime is effectively serial — much larger than most people's algorithmic guess, because real overhead (sync, cache) hides inside it.

Exercise 3.2 (Same $f$ , both laws)

For $f = 0.1$ and $n = 20$ , compute both Amdahl and Gustafson speedups and explain the gap.

Recall Solution 3.2

Amdahl: $S = \frac{1}{0.1 + \frac{0.9}{20}} = \frac{1}{0.1 + 0.045} = \frac{1}{0.145} \approx 6.90$ . Gustafson: $S = 20 - 0.1 (19) = 20 - 1.9 = 18.1$ . Why the gap: Amdahl holds the problem fixed, so the $10%$ serial part becomes a bigger and bigger slice as cores speed up the rest — capping near $10 \times$ . Gustafson lets the parallel work grow with $n$ , so the serial part stays a thin, near-constant slice — speedup stays close to linear ( $18.1$ of $20$ ). Same $f$ , opposite mood. See the figure.

Exercise 3.3 (Crossover thinking)

For Amdahl with $f = 0.25$ , what is the smallest $n$ giving $S \geq 3$ ? (You may need $S_{m a x}$ first.)

Recall Solution 3.3

First check the ceiling: $S_{m a x} = 1/ f = 1/0.25 = 4$ . So $S = 3$ is reachable ( $3 < 4$ ). Good. Set $3 = \frac{1}{0.25 + \frac{0.75}{n}}$ . Then $0.25 + \frac{0.75}{n} = \frac{1}{3}$ . $\frac{0.75}{n} = \frac{1}{3} - 0.25 = \frac{1}{12}$ , so $n = 0.75 \times 12 = 9$ . Smallest integer $n$ with $S \geq 3$ is $n = 9$ (exactly $S = 3$ ).

Level 4 — Synthesis

Goal: build $f$ yourself from messy data, then feed it through a law. Watch out for weighted time.

Exercise 4.1 (Weighted serial time)

A loop has $1000$ iterations. $990$ are parallelisable and each costs $1$ unit. The other $10$ are serial and each costs $10$ units (they do disk I/O). Find $f$ , then Amdahl $S (10)$ .

Recall Solution 4.1

Build $f$ from time, not counts. Serial time $= 10 \times 10 = 100$ . Parallel time $= 990 \times 1 = 990$ . Total $= 1090$ . $f = \frac{100}{1090} \approx 0.0917$ Amdahl at $n = 10$ : parallel term $= \frac{1 - 0.0917}{10} = \frac{0.9083}{10} = 0.09083$ . Denominator $= 0.0917 + 0.09083 = 0.18257$ . $S (10) = \frac{1}{0.18257} \approx 5.48$ . Trap avoided: counting iterations would give $f = 10/1000 = 0.01$ and an over-optimistic $S \approx 9.2$ .

Exercise 4.2 (Amdahl → back to time budget)

A $100$ s job is $f = 0.05$ serial. Management wants it done in $\leq 20$ s. (a) Is that possible with Amdahl and enough cores? (b) If not, what serial fraction $f^{'}$ would make $20$ s reachable in the limit?

Recall Solution 4.2

(a) Best case is $S_{m a x} = 1/0.05 = 20$ , giving best time $= 100/20 = 5$ s at $n \to \infty$ . Wait — that's better than $20$ s, so $20$ s is reachable. Find the $n$ : need $S \geq 5$ (since $100/20 = 5$ ). $5 = \frac{1}{0.05 + \frac{0.95}{n}} \Rightarrow 0.05 + \frac{0.95}{n} = 0.2$ $\Rightarrow \frac{0.95}{n} = 0.15 \Rightarrow n = 6.33 \to n = 7$ cores. Achievable. (b) Not needed here since (a) succeeds; but the general rule: $20$ s needs $S \geq 5$ , and the ceiling is $1/ f^{'}$ , so any $f^{'} \leq 1/5 = 0.2$ keeps $20$ s reachable in the limit. Our $f = 0.05$ is well inside that.

Exercise 4.3 (Gustafson from wall-clock breakdown)

A training run on $128$ GPUs takes $3$ hours: $9$ minutes are synchronisation (serial), the rest is gradient work. Find $f$ and Gustafson speedup.

Recall Solution 4.3

Total $= 180$ min, serial $= 9$ min, so $f = 9/180 = 0.05$ . $S (128) = 128 - 0.05 (128 - 1) = 128 - 0.05 \times 127 = 128 - 6.35 = 121.65$ We train a model $\approx 122 \times$ larger in the same wall-clock than one GPU could.

Level 5 — Mastery

Goal: combine inversion, both laws, and a limiting/degenerate case in one chain of reasoning.

Exercise 5.1 (Reconcile the two laws)

On $n = 32$ processors you observe Gustafson speedup $S_{G} = 29$ . (a) Recover $f$ . (b) Using that same $f$ , what fixed-problem Amdahl speedup would $32$ cores give? (c) In one sentence, why are they so different?

Recall Solution 5.1

(a) Invert Gustafson: $S_{G} = n - f (n - 1) \Rightarrow f = \frac{n - S _{G}}{n - 1} = \frac{32 - 29}{31} = \frac{3}{31} \approx 0.0968$ . (b) Amdahl: denominator $= 0.0968 + \frac{1 - 0.0968}{32} = 0.0968 + \frac{0.9032}{32} = 0.0968 + 0.02823 = 0.12503$ . $S_{A} = \frac{1}{0.12503} \approx 8.00$ . (c) Same $\approx 9.7%$ serial fraction: Amdahl (fixed problem) caps near $8 \times$ because the serial slice grows in relative weight; Gustafson (scaled problem) stays near $29 \times$ because the parallel work grows with the cores.

Exercise 5.2 (Degenerate / limiting cases)

Evaluate carefully: (a) Amdahl with $f = 0$ at any $n$ . (b) Amdahl with $f = 1$ at any $n$ . (c) Gustafson with $f = 0$ ; with $f = 1$ . (d) Amdahl at $n = 1$ .

Recall Solution 5.2

(a) $f = 0$ (fully parallel): $S = \frac{1}{0 + \frac{1}{n}} = n$ . Perfect linear speedup — the ideal. (b) $f = 1$ (fully serial): $S = \frac{1}{1 + 0} = 1$ . No speedup ever; extra cores idle. (c) Gustafson $f = 0$ : $S = n - 0 = n$ (linear). $f = 1$ : $S = n - 1 (n - 1) = 1$ (no speedup). Both laws agree at the two extremes $f = 0$ and $f = 1$ — they only diverge in between, where the "fixed vs. scaled" assumption actually matters. (d) $n = 1$ (Amdahl): $S = \frac{1}{f + \frac{1 - f}{1}} = \frac{1}{f + 1 - f} = \frac{1}{1} = 1$ . Sanity check: one core can't beat itself — speedup must be exactly $1$ . ✓

Exercise 5.3 (Design decision)

Your Amdahl-limited job has $f = 0.2$ . You can either (A) double the cores from $8$ to $16$ , or (B) halve the serial fraction to $f = 0.1$ while keeping $8$ cores. Which wins?

Recall Solution 5.3

Baseline ( $f = 0.2, n = 8$ ): $S = \frac{1}{0.2 + \frac{0.8}{8}} = \frac{1}{0.2 + 0.1} = \frac{1}{0.3} \approx 3.33$ . (A) $f = 0.2, n = 16$ : $S = \frac{1}{0.2 + \frac{0.8}{16}} = \frac{1}{0.2 + 0.05} = \frac{1}{0.25} = 4.00$ . (B) $f = 0.1, n = 8$ : $S = \frac{1}{0.1 + \frac{0.9}{8}} = \frac{1}{0.1 + 0.1125} = \frac{1}{0.2125} \approx 4.71$ . Winner: (B). Attacking the serial fraction beats throwing hardware at the wall, because the ceiling $1/ f$ rose from $5$ to $10$ . This is the whole moral of Amdahl.

Recall Quick self-check (reveal answers)

Amdahl $S_{m a x}$ when $f = 0.05$ ::: $1/0.05 = 20$ Which law is optimistic for scaled problems ::: Gustafson Invert Amdahl for $f$ given $S, n$ ::: $f = \frac{n / S - 1}{n - 1}$ Invert Gustafson for $f$ given $S, n$ ::: $f = \frac{n - S}{n - 1}$ Both laws agree at which $f$ values ::: $f = 0$ and $f = 1$

Related vault topics to push further: Scalability Analysis, Performance Metrics, Load Balancing, Thread Synchronization, Parallel Architectures, GPU Computing, Cache Coherence.