Why more processors stop helping

Throw ten times the processors at a job and you'd expect it to finish ten times faster. It doesn't — some sliver of the work insists on running one step at a time, no matter how much help arrives, and that sliver alone sets a hard ceiling no number of processors can ever break.

What you're seeing

Split a job across N processors and the part that parallelizes perfectly gets N times faster — but not every part can be split. Some fraction s has to run one step after another no matter how much help shows up: initial setup, a shared lock, a final step that depends on everything before it. With almost no processors, adding more is a straightforward win — the curve climbs in near lock-step with N, just like you'd hope. Keep adding processors, though, and the parallel part keeps shrinking toward zero time while that stubborn serial sliver just sits there, unmoved. Past a point, you're not speeding up the job anymore; you're speeding up the part that was already nearly free, while the part that mattered hasn't budged.

The curve bends over and creeps toward a hard ceiling — the fastest this job can ever finish, relative to one processor, no matter how many you throw at it. Drag s down toward 0 and the ceiling rockets away, out of reach — a fully parallel job never stops speeding up. Drag it up and the ceiling crashes down close to home: at s=0.5, a thousand processors will never buy you more than 2× — half the job runs one step at a time regardless, and that alone caps everything.

The rule, exactly. Relative to one processor, running time is T(N) = s + (1−s)⁄N, so speedup is S(N) = 1 ⁄ T(N), which climbs toward a hard ceiling 1⁄s as N → ∞ and never reaches it. The half-ceiling threshold N* = (1−s)⁄s is an exact crossing: S(N*) = 1⁄(2s), precisely half the ceiling — below it, each doubling still buys a large share of what's left; past it, each further doubling buys a strictly shrinking sliver, one that never quite disappears but keeps getting thinner. Verified in node (improve/verify/57-amdahl.js): S(1)=1 exactly for any s; at huge N, S(N) sits within 0.01% of the ceiling for several serial fractions; S(N*) equals the ceiling's exact half at five different s values, crossed monotonically and only once; adding N* more processors again and again buys a strictly decreasing gain each time, with the second such addition worth exactly half of the first. Negative control: at s=0 speedup equals N exactly, with no ceiling at any size tested — while at s=0.05, a modest 500 processors already sits within 5% of that run's ceiling, a limit the s=0 case never approaches at all.

← the cabinet · Thought Toys — a cabinet of explorable explanations. Exhibit 57.