Thought Toys · Computation & information · Exhibit 57

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.

Speedup versus processor count (log scale) speedup S(N) ceiling 1/s half-ceiling N*

—

Try it
↳ your turn — drag N far past N* and watch the curve go flat

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.

Also in Computation & information: Why a busy line explodes →

All 20 in Computation & information
  1. 101Noise sets a speed limit, not an accuracy limit.
  2. 111Any party of six hides a trio
  3. 120How one bit of ink makes a grey
  4. 125The ambulance that arrives sooner by going slower
  5. 131Every number is a sum of Fibonacci numbers
  6. 23Sorting algorithms
  7. 24PageRank & the random surfer
  8. 25Huffman coding
  9. 26Dijkstra's shortest path
  10. 33The learning-rate cliff
  11. 36A* pathfinding
  12. 44Diffie–Hellman key exchange
  13. 49Freeze too fast, stay stuck
  14. 56Catch one error, miss the next
  15. 57Why more processors stop helping — you are here
  16. 58Why a busy line explodes
  17. 59The set that's only sure when it says no
  18. 60The fit that memorizes instead of learns
  19. 61When the wire breaks, pick one
  20. 82Your computer can't hold one tenth

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