JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Amdahl's Law and the Limits of Parallelism

Buying eight cores almost never buys eight times the speed — and there is a precise, honest reason why. This guide derives Amdahl's law from one simple picture, shows why a tiny serial fraction caps everything, weighs the optimistic reply of Gustafson's law, and counts the real-world taxes — coherence, synchronization, and NUMA — that pull true speedup even lower.

The picture behind the law

We have spent this whole rung making many cores cooperate: private caches kept in step by coherence, threads kept in order by synchronization. Now comes the honest accounting. The promise of multicore is that adding cores adds thread-level parallelism and so adds speed. Amdahl's law is the cold-water rule that says exactly how much of that promise you can actually collect — and the answer is almost always less than you hoped.

The whole law falls out of one simple picture. Split your program's running time into two parts: a fraction P that can be perfectly parallelized (do it on as many cores as you have) and the rest, (1 - P), that is inherently serial — it must run one step at a time no matter how many cores are idle nearby. Now hand the work to N cores. The serial part still takes (1 - P) of the original time, because parallel hardware does nothing for it. The parallel part shrinks from P down to P/N, because N cores split it N ways. Add them up and you have the new running time.

  serial part           parallel part
  |<-- (1 - P) -->|<--------- P --------->|     time on 1 core  = 1

  with N cores:
  |<-- (1 - P) -->|< P/N >|                      time on N cores = (1 - P) + P/N

  speedup  S(N) = 1 / ( (1 - P) + P/N )
  ceiling  S(infinity) = 1 / (1 - P)        <- set by the serial fraction alone
Amdahl's law in one diagram. The serial slice never shrinks; only the parallel slice divides by N. As N grows without bound the parallel slice vanishes but the serial slice remains, so speedup tops out at 1 / (1 - P).

Why a tiny serial slice ruins everything

Put real numbers on it and the result is sobering. Suppose 95% of your program parallelizes perfectly, so P = 0.95 and only 5% is serial. With 16 cores the speedup is 1 / (0.05 + 0.95/16), which is about 9 times — not 16. Push to 256 cores and you get 1 / (0.05 + 0.95/256), barely 19 times, even though you spent sixteen times as much hardware as the 16-core machine. And the absolute ceiling, with infinitely many cores, is just 1 / 0.05 = 20 times. That stubborn 5% serial slice caps you at 20x forever; you cannot buy your way past it with any number of cores.

Now watch the diminishing returns by walking the cores up. With 5% serial (P = 0.95), 4 cores give about 3.5x, 16 cores 9.1x, 64 cores only 15.4x, 256 cores barely 18.6x, and infinity gives 20x — each doubling of cores buys a smaller sliver as you crawl toward the ceiling. The deepest lesson is in the comparison: cut the serial part to just 1% (P = 0.99) and the ceiling leaps from 20x to 100x, and 64 cores now reach 39x instead of 15x. Halving the serial fraction was worth far more than any number of extra cores — cutting the serial work beats buying hardware.

The optimist's reply: Gustafson's law

If Amdahl's law were the whole story, supercomputers with a million cores would be pointless — yet they are not. The catch is an assumption hiding in Amdahl's setup: it keeps the problem size fixed and asks how much faster the same job runs. That is called strong scaling. But in practice, when people are handed a bigger machine they usually solve a bigger problem — a finer weather grid, a larger neural network, more web requests per second. This is weak scaling, and Gustafson's law describes it.

Here is the key insight. The serial part of a program — reading the input, setting up, printing the answer — often stays roughly the same size as the problem grows, while the parallel part swells with it. So as the problem gets bigger, the serial fraction shrinks, and the wall Amdahl built quietly recedes. Gustafson's law says scaled speedup is about (1 - P) + P times N: nearly linear in the number of cores, as long as you let the problem grow to feed them. This is exactly how request-level parallelism works in a warehouse-scale computer — twice the servers serve twice the users, almost perfectly, because each user's request is independent work.

The taxes Amdahl never charged you

Amdahl's law is already pessimistic, yet it is still too optimistic, because it pretends the parallel part splits into N pieces for free. It does not. Every mechanism we built in this rung to make sharing safe also costs time, and that cost is pure overhead that Amdahl's tidy formula ignores. Keeping caches in step costs coherence traffic; whenever a core writes a shared cache line, the coherence protocol must invalidate the copies on every other core's desk, and those messages cross the chip while real work waits.

Three taxes bite hardest. First, synchronization: threads that take a lock to touch shared data spend time spinning or sleeping while they wait, and a lock held too long serializes the very part you hoped was parallel — quietly inflating (1 - P). Second, false sharing: two cores updating neighbouring slots of one array touch different variables but the same cache line, so coherence ping-pongs the line back and forth even though the threads never truly conflict — covered earlier in this rung, and a classic way to make a 'parallel' loop run slower than the serial one. Third, NUMA: on a multi-chip machine, a thread running far from its data reaches non-uniform memory slowly, so where data physically lives now changes the answer.

  1. Profile first to find the real serial bottleneck — do not guess. The biggest, most stubborn serial slice is what Amdahl's ceiling is built on, and attacking anything else wastes effort.
  2. Shrink the serial fraction before adding cores: a smaller (1 - P) raises the whole ceiling, which no number of extra cores can do.
  3. Minimize sharing and synchronization: pad data to avoid false sharing, keep critical sections short, and prefer designs where threads work on independent data.
  4. Place data near the core that uses it (NUMA-aware allocation), so threads are not quietly taxed by reaching across the machine for every access.

Reading speedup numbers honestly

With all this in hand you can read parallel-performance claims with a clear eye. A reported 'speedup' is only meaningful against a stated baseline — and the fair baseline is the best single-core implementation, not a deliberately slow one. A common sleight of hand is to compare a tuned parallel version against an untuned serial version and credit the cores with gains that really came from better code. Always ask: speedup over what, and at what problem size?

One genuinely surprising case deserves an honest mention: sometimes you measure more than N-times speedup on N cores, called super-linear speedup. This is not magic and it does not break Amdahl's law. It usually happens because N cores bring N times as much total cache, so a working set that thrashed in one core's cache now fits across many — the speedup came from the bigger combined cache, not from the parallelism itself. Naming the real cause keeps you honest, and reminds you that 'cores' and 'caches' scale together in ways the tidy formula never captures.

Step back to the whole arc of this ladder. The power wall forced the move from one fast core to many cooperating ones, and everything since — coherence, consistency models, atomics and locks, NUMA — is the price of that cooperation. Amdahl's law is the honest scoreboard tallying what you get back: real, valuable, but bounded by the serial work that no hardware can split. The craft of parallel performance is not buying more cores; it is finding the independent work, feeding it to the cores cleanly, and respecting the ceiling that the serial fraction sets.