Amdahl's Law and Gustafson's Law: Question bank — Hardware deep dive

Before any trap makes sense we must own the two formulas outright — not borrow them. Everything below rests on these, so we build them here from scratch.

Building Amdahl's formula (fixed problem)

Take the whole job on one core, time $T_{1}$ . Split it into its serial and parallel slices (figure below, top bar): serial $= f T_{1}$ , parallel $= (1 - f) T_{1}$ .

Figure — Amdahl's Law and Gustafson's Law

Now hand the parallel slice to $n$ workers. The serial slice cannot be split, so it still costs $f T_{1}$ ; the parallel slice divides evenly into $\frac{( 1 - f ) T _{1}}{n}$ (figure, lower bars). Add them:

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

Speedup is the ratio, and $T_{1}$ cancels top and bottom:

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

Let $n \to \infty$ : the term $\frac{1 - f}{n} \to 0$ , leaving the hard ceiling $S_{m a x} = 1/ f$ .

Building Gustafson's formula (growing problem)

Now flip the reference. We own $n$ cores and a fixed time $T_{n}$ . Measure the slices in that run: serial $= f T_{n}$ , parallel $= (1 - f) T_{n}$ (figure below, upper bar). The trick is: the parallel slice was spread across $n$ cores, so to redo that same amount of work on one core takes $n$ times as long — the parallel term inflates to $n (1 - f) T_{n}$ (lower bar), while the serial term is unchanged:

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

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

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

Expand $n (1 - f) = n - n f$ and collect:

$S (n) = n - f (n - 1)$

So the linear term $n$ comes directly from doing $n \times$ the parallel work; the $- f (n - 1)$ is the "tax" the un-inflatable serial slice charges. (Same thing as $S (n) = n + (1 - n) f$ .)

The two names for these two worlds

Recall Which question does each law ask?

Amdahl (strong scaling) ::: "The problem is a fixed size — how fast can I finish it?" $S (n) = \frac{1}{f + ( 1 - f ) / n}$ , capped at $1/ f$ . Gustafson (weak scaling) ::: "I have $n$ workers and a fixed time budget — how much more work can I do?" $S (n) = n - f (n - 1)$ , near-linear when $f$ is small.

True or false — justify

Give a reason every time; a naked true/false earns nothing.

TF1. "With enough cores, any program can be made arbitrarily fast."

False — in Amdahl the denominator

f + \frac{1 - f}{n}

never falls below

f

, so

S (n) \leq 1/ f

; with

f = 0.2

you can never beat

5 \times

however many cores you add.

TF2. "Amdahl and Gustafson contradict each other."

False — they answer different questions (strong vs weak scaling). Amdahl fixes the problem size, Gustafson fixes the time and grows the problem; both are correct for their own assumption.

TF3. "If

f = 0

, Amdahl's speedup equals

n

True — substitute

f = 0

S (n) = \frac{1}{0 + ( 1 - 0 ) / n} = \frac{1}{1/ n} = n

; with no serial term the denominator is purely

1/ n

, so speedup is exactly linear.

TF4. "If

f = 1

, adding cores still helps a little."

False — set

f = 1

S (n) = \frac{1}{1 + 0/ n} = 1

for every

n

; the parallel term is zero, so extra cores sit idle and speedup stays exactly

1

TF5. "Gustafson's speedup can exceed the number of processors

n

False —

S (n) = n - f (n - 1)

and

f \geq 0

so the subtracted term is

\geq 0

, giving

S (n) \leq n

; it approaches

n

f \to 0

but never passes it.

TF6. "A larger serial fraction always lowers speedup in both laws."

True — in Amdahl a bigger

f

raises the denominator

f + \frac{1 - f}{n}

(its derivative in

f

1 - \frac{1}{n} \geq 0

), and in Gustafson

- f (n - 1)

subtracts more; both punish serial work.

TF7. "Doubling cores from

n

2 n

doubles Amdahl speedup."

False — only the parallel term

\frac{1 - f}{n}

halves to

\frac{1 - f}{2 n}

; the serial

f

stays put in the denominator, so speedup rises but by strictly less than double, and less each time you double.

TF8. "The parallel fraction

(1 - f)

is simply one minus the serial fraction, both measured as time."

True — they are two shares of the same 100% of run time (

f T_{1}

and

(1 - f) T_{1}

), so by definition they add to

1

TF9. "Gustafson with

f = 0

gives exactly linear speedup."

True —

S (n) = n - 0 \cdot (n - 1) = n

, the same perfect-scaling endpoint Amdahl reaches at

f = 0

; the laws agree at the no-serial extreme.

TF10. "If measured speedup is much lower than

1/ f

predicts, your algorithm's

f

is wrong."

Often true in spirit — real overheads (Cache Coherence traffic, Thread Synchronization waits, communication) add time that behaves like extra serial fraction, so the effective

f

is bigger than the algorithmic one you assumed.

Spot the error

Each statement hides one flaw — name it.

SE1. "Only 3 of my 100 functions run serially, so

f = 0.03

The error is counting code, not time.

f

is the share of run-time; three tiny functions could be a lock eating 40% of the clock, or three heavy ones could dominate. You must profile.

SE2. "I have 8 cores so I'll get

8 \times

This assumes

f = 0

and zero overhead. Any serial slice keeps

f

in Amdahl's denominator, and real synchronization plus Load Balancing costs push effective speedup strictly below

8

SE3. "My problem is fixed-size, so I'll use Gustafson to promise near-linear scaling."

Wrong law — a fixed problem is strong scaling, which is Amdahl's domain. Gustafson assumes the problem grows with

n

; for a fixed problem Amdahl gives the honest cap

1/ f

SE4. "Speedup of

6.9

on 10 cores means the code is broken."

Not necessarily — with

f = 0.05

, Amdahl gives

\frac{1}{0.05 + 0.95/10} \approx 6.9

exactly. A sub-

n

speedup is the normal consequence of a serial slice, not a bug.

SE5. "Since Gustafson gives

90 \times

on 100 cores, we finish the original job

90 \times

faster."

The error is confusing more work with faster. Gustafson's

90 \times

is a weak-scaling claim — a

90 \times

bigger problem in the same time — not the old problem in

1/90

of the time.

SE6. "

f

changes when I switch from 4 cores to 400 cores."

In the ideal models

f

is a property of the workload, held constant while

n

varies (that is exactly why

T_{1}

T_{n}

cancels). Real overhead makes effective

f

drift, but the textbook laws treat it as fixed per problem.

SE7. "Amdahl's denominator

f + \frac{1 - f}{n}

can go negative for big

n

Impossible — both

f \geq 0

and

\frac{1 - f}{n} \geq 0

, so the denominator is always positive and shrinks toward

f

, never below it.

Why questions

WQ1. Why does the total single-core time

T_{1}

cancel out of Amdahl's speedup?

Because

S (n) = T_{1} / T_{n}

and

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

has

T_{1}

as a common factor; dividing removes it, so speedup depends only on the fraction

f

and

n

, never on absolute time.

WQ2. Why is the serial term left untouched when we divide by

n

The serial work is a chain of dependent steps — each needs the previous one's result — so extra workers have nothing to do; only the independent parallel slice

(1 - f) T_{1}

divides by

n

WQ3. Why does Amdahl's law approach

1/ f

rather than infinity as

n \to \infty

S (n) = \frac{1}{f + ( 1 - f ) / n}

the term

\frac{1 - f}{n} \to 0

, leaving

S = 1/ f

; the fixed serial slice becomes the entire remaining runtime and acts as a hard floor.

WQ4. Why does Gustafson measure work relative to the parallel run time

T_{n}

instead of

T_{1}

Because the practical situation is "I own

n

cores and a fixed time window" — the observed quantity is

T_{n}

, and we ask how long that same work would take alone (

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

), which produces the

n (1 - f)

inflation.

WQ5. Why is Gustafson called "optimistic" and Amdahl "pessimistic"?

Gustafson (weak scaling) lets the parallel workload grow with

n

, so the serial slice becomes a shrinking share and

S (n) \to n

; Amdahl (strong scaling) freezes the workload, so the fixed serial slice dominates and caps speedup at

1/ f

WQ6. Why can optimizing the serial 5% beat adding more cores?

Once cores are plentiful, Amdahl's speedup is pinned near

1/ f

; halving

f

doubles that ceiling directly, while adding cores only nudges

\frac{1 - f}{n}

toward zero with diminishing return. See Scalability Analysis.

WQ7. Why do communication and Cache Coherence traffic make real speedup worse than either law predicts?

Both ideal laws assume the parallel part divides perfectly and for free; real cores must exchange data, invalidate cache lines, and wait at barriers, adding time that behaves like extra serial fraction. Track it via Performance Metrics.

WQ8. Why does GPU Computing fit Gustafson's mindset so well?

GPUs win by attacking huge data-parallel problems (millions of pixels/particles) — you scale the problem to the hardware, exactly Gustafson's weak-scaling assumption, rather than racing a tiny fixed task.

Edge cases

EC1. What is Amdahl's speedup at

n = 1

S (1) = \frac{1}{f + ( 1 - f ) /1} = \frac{1}{f + 1 - f} = \frac{1}{1} = 1

— one processor is the baseline, so by construction speedup equals exactly

1

EC2. What is Gustafson's speedup at

n = 1

S (1) = 1 - f (1 - 1) = 1 - 0 = 1

— also exactly

1

, so both laws correctly agree that a single processor gives no speedup.

EC3. Both laws at

f = 0

— what happens and do they agree?

Amdahl gives

\frac{1}{0 + 1/ n} = n

, Gustafson gives

n - 0 = n

; with no serial work both collapse to perfect linear speedup, so the laws coincide at this extreme.

EC4. Both laws at

f = 1

— what happens?

Amdahl gives

\frac{1}{1 + 0} = 1

; Gustafson gives

n - [1 \cdot (n - 1)] = n - (n - 1) = 1

; a fully serial job cannot be sped up in either framework, again agreeing.

EC5. What does

S (n) < 1

ever mean, and can the ideal formulas produce it?

S (n) < 1

means the parallel version is slower than serial — a real "slowdown" from overhead swamping the work; the ideal

\frac{1}{f + ( 1 - f ) / n}

and

n - f (n - 1)

never dip below

1

, so seeing it signals real-world costs the models omit.

EC6. As

n \to \infty

, what does Gustafson's speedup do?

It grows without bound as

S (n) = n - f (n - 1) \approx n (1 - f)

— a straight line of slope

(1 - f)

— because the problem keeps growing, unlike Amdahl which flat-lines at

1/ f

EC7. If a job is truly embarrassingly parallel (

f \approx 0

) but you observe only

5 \times

on 8 cores, what's the culprit?

The algorithmic

f

is near zero, so the loss must come from effective serial overhead — poor Load Balancing, synchronization stalls, or memory bandwidth limits — inflating the effective

f

toward the value that solves

\frac{1}{f + ( 1 - f ) /8} = 5

, roughly

f \approx 0.086

EC8. Two programs both have

f = 0.1

but one runs 1 ms and the other 1 hour — do they get the same Amdahl speedup on the same

n

Yes — Amdahl depends only on

f

and

n

(absolute time cancels), so both reach the same

S (n)

; in practice the 1 ms job may be dominated by fixed launch overhead the model ignores.