Amdahl, Gustafson, and the Limits of Scaling

The 5% that eats your speedup

By now you can profile a program, build an honest micro-benchmark, and read a latency versus throughput distribution including its tail. So you find a fat compute loop in your flame graph, split it across all the cores you own, and expect the obvious payoff: eight cores, eight times faster. You measure, and it is faster by maybe five times, then you add eight more cores and it barely moves. Nothing is broken. You have just met Amdahl's law, the most important arithmetic in all of parallel performance — and it is humbling because it is so simple.

The idea is this. Take any program and split its run time into two parts: the fraction p that can run in parallel, and the fraction (1 - p) that is stubbornly serial — work that must happen one step after another no matter how many cores you have. Reading the input file, setting up data structures, the final reduction that combines everyone's partial answers, a critical section guarded by a lock: all serial. When you throw N cores at the parallel part, only that part shrinks; you divide p by N but you cannot touch (1 - p) at all. The serial fraction just sits there, an unmovable floor under your run time.

                       1
  speedup(N) = -----------------
               (1 - p) + p / N

  p = 0.95 (95% parallel),  N -> infinity

               1            1
  speedup = -------- = ----------- = 20x   <- the HARD ceiling
            (1 - p)       0.05

Stare at that ceiling, because it is the whole lesson. A program that is 95% parallel — which sounds wonderful — can never go faster than 20 times, no matter if you have 32 cores or 32,000. The last 5% dominates. And it is worse on the way there: at 8 cores that 95%-parallel program reaches about 6x, at 32 cores about 12x, so you are already burning three quarters of your hardware on diminishing returns. The serial fraction is not a rounding error you can ignore; it is the single number that decides whether parallelism pays off at all.

Why parallel is not concurrent, and where the serial part hides

Before going further, pin down a distinction the earlier rung drew and that Amdahl's law makes urgent: concurrency is not parallelism. Concurrency is structuring a program as independent tasks that can make progress in overlapping time; parallelism is actually running several of them at the same instant on several cores. Amdahl's law is about parallelism — it asks how much wall-clock time you save by running work simultaneously — and it only ever helps the part of the program that has genuine parallel work to hand out. If a stretch of code is serial by nature, no amount of concurrency machinery makes it parallel; you have just dressed up a queue.

So the real engineering question Amdahl forces on you is: *where does my serial fraction actually live, and can I shrink it?* It hides in more places than the obvious setup-and-teardown. Every lock you take serializes the threads that contend for it. Every reduction step that funnels N partial results into one answer is serial at the top. Memory bandwidth is shared, so if all cores hammer the same memory the bus itself becomes a serial bottleneck even with no explicit lock. The art of scaling is largely the art of hunting down these hidden serial chunks and either parallelizing them, removing the sharing that forces them, or making them so small the (1 - p) term shrinks.

Gustafson's answer: grow the problem, not just the cores

If Amdahl's law were the whole story, supercomputers with a million cores would be pointless, since a 95%-parallel program is stuck at 20x forever. Yet those machines plainly earn their keep. The resolution came from Gustafson in 1988, and it is a change of question, not a contradiction of Amdahl. Amdahl asks: I have a fixed problem — how much faster does it run as I add cores? Gustafson asks the question real users actually have: I have a fixed amount of time — how much bigger a problem can I solve if I add cores? These are not the same question, and they have very different answers.

The insight is that the serial part of real workloads tends to stay roughly constant in absolute terms while the parallel part grows with the problem size. Reading the config file takes the same half-second whether you simulate a thousand particles or a billion; the per-particle physics is what explodes. So as you scale a weather model to a finer grid, a render to more pixels, a training run to more data, the parallel work grows to fill the new cores while the fixed serial overhead becomes a smaller and smaller fraction of the whole. The serial 5% that doomed you in Amdahl's fixed-size world melts toward 0.5%, then 0.05%, as the problem grows.

This gives the two scaling regimes a name worth carrying. Strong scaling is Amdahl's world: fix the problem, add cores, watch speedup flatten against the 1 / (1 - p) ceiling — the hard mode, and the right model when a single fixed job must finish sooner. Weak scaling is Gustafson's world: grow the problem in step with the cores so each core keeps a constant slice of work — the regime where adding hardware keeps paying, and the reason the million-core machine is not a folly. Neither law is wrong; they answer different questions, and knowing which question your workload is asking is the difference between a sound scaling plan and a disappointed one.

Past a point, more cores make it slower

Amdahl's law is optimistic in one quiet way: it assumes the parallel part divides perfectly, that splitting work across cores is free. In a real machine it is not. Every core you add brings two new costs that Amdahl ignores. First, contention: threads queue for shared resources — locks, the memory controller, a shared cache — and that queueing is pure serialization that grows with the number of threads. Second, coherency: when many cores touch shared data, the hardware must keep their private caches consistent, shuttling cache lines between cores over the interconnect, and that cross-talk also grows with core count. These are not in Amdahl's formula at all.

The consequence is sharp and surprising the first time you hit it: a scaling curve that climbs, flattens, and then bends back down. With few cores the parallel speedup dominates and throughput rises. At some core count the contention and coherency costs — which keep growing as you add cores — overtake the shrinking parallel benefit, and adding the next core makes the program slower, not faster. There is a real peak, often well short of your core count, after which more hardware is actively harmful. This is the gap between Amdahl's tidy ceiling and the messy reality the Universal Scalability Law was built to capture.

This is exactly where mechanical sympathy earns its keep — the habit, central to this rung and the next, of writing code that works with the machine rather than against it. Two threads updating counters that happen to sit in the same cache line will ping that line back and forth between cores on every write, a coherency storm called false sharing that can make a parallel loop slower than the single-threaded version. The fix is structural: give each thread its own memory so cores stop fighting over shared lines. That is the heart of data-oriented design and the subject of the final guide in this rung — and it is the practical answer to the contention term that Amdahl's clean arithmetic leaves out.

Using the laws: a sober scaling checklist

These laws are not abstract trivia; they are a decision procedure that saves you from pouring weeks into a 2x ceiling. The point of carrying Amdahl, Gustafson, and the contention terms in your head is to run the arithmetic before you parallelize, and to read your scaling curve honestly after. Walk this sequence the next time someone says "just throw more cores at it."

1. Profile first and measure the parallel fraction p, then compute the hard ceiling 1 / (1 - p). If that ceiling is small (say under 3x), the honest move is often to speed up the serial part instead of parallelizing at all.
2. Decide which question you are answering: strong scaling (fixed problem, finish a set job sooner — Amdahl) or weak scaling (grow the problem to fill the cores in fixed time — Gustafson). They demand different designs and different success metrics.
3. Hunt the hidden serial fraction: locks, the final reduction, shared memory bandwidth, startup and teardown. Shrinking the (1 - p) term raises the ceiling far more than adding cores ever can.
4. Plot the real curve, do not trust the formula: run at 1, 2, 4, 8, 16 cores and graph speedup. A curve that flattens early reveals your true p; a curve that bends back down reveals contention and coherency costs the laws warned you about.
5. If the curve bends down, suspect false sharing and shared-line contention before anything else, and apply mechanical sympathy — give each thread its own memory — rather than reaching for more cores.