Amdahl's Ceiling

Add workers to a job with a serial fraction and watch the speedup flatten — then add coordination cost and watch it reverse.

Ch 10 10.7

Simulator

Systems & Performance

15 mindifficulty 2/5

Controls

Serial fractions10.0%

The share of the work that cannot be parallelised at all.

Workersp16

Coordination overhead

Overhead coefficientc0.0040

Cost per unit of coordination, as a fraction of the serial runtime.

Show Gustafson's law

Scaled speedup when the problem grows with the machine.

Show efficiency

Speedup divided by workers.

Speedup against worker count

The dashed diagonal is linear speedup. The flat asymptote is 1/s — no machine gets past it.

Amdahl with overheadlinear speedupGustafson (scaled problem)Amdahl ceiling 1/sbest achievable p

Speedup at p = 16

4.62×

runtime 21.6% of serial

Amdahl ceiling

10×

s = 10.0%

Best p / best speedup

15 → 4.63×

beyond this, adding workers hurts

Efficiency

28.9%

11.4 workers' worth wasted

Parallel efficiency

Speedup per worker. Cloud bills are proportional to p, not to speedup.

What doubling buys you

Marginal return of each doubling of the machine.

p = 11×

p = 21.81×+0.81

p = 42.97×+1.16

p = 84.16×+1.19

p = 164.62×+0.47

p = 323.97×-0.66

p = 642.73×-1.23

p = 1281.63×-1.11

p = 2560.89×-0.74

Reading the two laws apart

Amdahl at p4.62×

Gustafson at p14.50×

overhead share at p27.7%

90%-of-peak worker count9

Amdahl fixes the problem size and asks how fast it can be solved. Gustafson fixes the time budget and asks how large a problem fits. Both are correct; they answer different questions.

Doubling the cores does not halve the runtime

With just 10% serial work, 16 workers give about 6× and 256 workers still give under 10×. Add any coordination cost and the curve stops rising, then falls: past the peak, every extra worker makes the job slower and the bill larger. Profile to find s before renting a cluster.

Predict before you look

A job is 90% parallelisable. You run it on 100 workers instead of 1. What speedup do you get, ignoring communication cost?

Scenarios

Teacher-ready starting points.

Documentation

What this shows

Speedup as a function of worker count for a job whose serial fraction and coordination cost you control, alongside linear speedup, the 1/s ceiling, Gustafson's scaled speedup, and parallel efficiency. The peak marker shows the worker count beyond which the job gets slower.

Two laws and one overhead term

Split unit runtime into a serial share s and a perfectly parallel share 1 − s. On p workers the time becomes s + (1 − s)/p, so the speedup is 1/(s + (1 − s)/p). As p grows without bound the parallel term vanishes and the speedup approaches 1/s: the ceiling depends only on the serial fraction, not on the hardware.

Real machines pay to coordinate. Adding a term that grows with p — linearly for broadcast-style communication, or like log₂ p for a tree reduction — makes runtime a sum of a decreasing and an increasing term, so it has an interior minimum. Past that point additional workers strictly increase runtime.

Gustafson's law changes the question. If the problem grows with the machine so that each worker keeps a fixed amount of parallel work, the scaled speedup is s + (1 − s)p, which is linear in p. Neither law contradicts the other: Amdahl describes strong scaling (fixed problem, more workers) and Gustafson describes weak scaling (fixed time, bigger problem). Efficiency, speedup/p, is what a bill is proportional to.

T(p) = s + (1 − s)/p + c·g(p)

S(p) = 1 / T(p),   S(∞) = 1/s   when c = 0

g(p) = p − 1 (linear)  or  log₂ p (tree)

Gustafson:  S_scaled(p) = s + (1 − s)p

efficiency E(p) = S(p)/p

Try this

Set s = 0 with no overhead and confirm speedup is exactly p.
Set s = 0.05 and predict the ceiling before reading the 1/s marker.
With s = 0.1, find how many workers are needed for 8×, then for 9×.
Switch overhead to linear with c = 0.004 and locate the peak. What happens at twice that worker count?
Compare the log₂ p and linear overhead models at p = 128: how much does the reduction strategy matter?
Turn on Gustafson and explain to a neighbour why both curves can be right at once.

Common misconception

“Our pipeline takes six hours on one machine, so on sixty machines it will take six minutes.”

Only if every step parallelises perfectly and coordination is free. Profile first: if 8% of the runtime is serial — reading configuration, writing a single output file, a final sort — the ceiling is 12.5×, so six hours becomes about 29 minutes at best, and any communication cost makes it worse. The honest engineering question is not how many workers to add but which serial fraction to remove.

DSPA3 Chapter 10 — Computational performance and big data