Amdahl's law

The problem it solves

You parallelise a program, double the cores, and it runs 1.4 times faster. Double them again and it runs 1.6 times faster. Double again and nothing happens.

Amdahl’s law tells you that in advance, from one number: the fraction of the work that cannot be done in parallel. Whatever that fraction is, the speedup can never exceed its reciprocal — and the core count does not appear in that bound at all.

Five percent serial means twenty times, maximum, on any machine that has ever existed or ever will. Not twenty times on your machine; twenty times, full stop. That is a much harsher statement than most people carry, and it reframes every conversation about scaling from “how many cores can we get” to “how much of this is actually parallel”.

The mechanism

Split the work into a serial fraction s and a parallel fraction 1 − s. With n workers, the parallel part takes (1 − s)/n and the serial part still takes s, because nothing about having more workers makes sequential work go faster.

speedup = 1 / (s + (1 − s)/n)

As n grows, (1 − s)/n approaches zero and the whole expression approaches 1/s. That limit is the ceiling. It is set by the serial fraction alone.

The reason this feels surprising is that the serial fraction sounds small when stated as a percentage. Five percent sounds like a rounding error. It is a hard cap at 20×, and — the part that stings — you reach most of it early: at 5% serial, 32 cores already deliver 15.4× of the eventual 20×. The next 480 cores buy the remaining 4.6×.

The “serial fraction” is broader than people assume. It includes anything only one worker can do at a time: reading the input, writing the output, allocating from a shared pool, taking a contended lock, coordinating at a barrier, committing to a database. A lock is a serial fraction with a different name.

What the enumeration shows

This is a model page: drag the serial fraction and watch the ceiling move.

At the default 5%, the actual-speedup line rises steeply, bends, and flattens against a dashed ceiling at 20× while the perfect-scaling line disappears off the top of the chart. 512 cores reach 19.3×. 128 cores reach 18.3×. The last 384 cores bought one unit of speedup.

Drag the serial fraction to 20% and the ceiling collapses to 5×, with 64 cores already at 94% of it. Drag it to 1% and the ceiling is 100× — and now the curve is still climbing at 512, which is the regime where buying hardware is rational.

Watching the ceiling move while the shape stays identical is the lesson. The curve is always the same curve; the only question is where its asymptote sits, and that is a property of your program.

The numbers worth carrying

Serial fraction	Ceiling	Speedup at 64 cores
1%	100×	39×
5%	20×	15.4×
10%	10×	8.8×
25%	4×	3.9×
50%	2×	2.0×

Two things to read out of that table. At 25% serial, 64 cores get you 3.9× of a possible 4× — you are done, and 1,000 cores would add nothing. And halving the serial fraction doubles the ceiling, which is why profiling the sequential part is almost always where the win is: optimising the parallel part harder does not move the asymptote at all.

Where it breaks down

Gustafson’s law is the honest counterpoint. Amdahl fixes the problem size and asks how much faster it gets. In practice people use bigger machines for bigger problems, and if the serial part is a fixed setup cost while the parallel part grows with the data, the serial fraction shrinks as you scale. That is why supercomputers are useful despite Amdahl: they are not running the same problem faster, they are running a larger one. Which law applies depends on whether your problem size is fixed, and both are right about different questions.

The model ignores coordination overhead. Real parallelism adds cost that grows with the worker count — synchronisation, communication, scheduling, false sharing. Past some point real curves turn downward, which Amdahl’s never does. The law gives an optimistic bound.

Memory bandwidth is a shared serial resource nobody counts. Sixteen cores on one memory controller can saturate it, and then the cores are idle waiting on RAM regardless of how parallel your algorithm is. This is why real speedups often stall well below the Amdahl ceiling.

The serial fraction is usually unknown and often underestimated. People estimate it from what looks sequential in the source and forget allocation, I/O, lock contention and GC. Measuring it — by fitting the observed speedup curve — is more reliable than reading the code.

What people get wrong

“We will just add more cores.” Only if the serial fraction is small. Ask what it is before buying anything; the number is the whole answer.

“Our code is 95% parallel so we will get 95% of linear.” You will get a maximum of 20×, and about 15× on a 64-core machine. Percentages of work do not translate into percentages of speedup.

“Amdahl’s law is pessimistic and outdated.” It is exactly correct for a fixed problem size. Gustafson applies when the problem grows; knowing which regime you are in is the skill.

“The serial part is small so it does not matter.” It is the only thing that matters at scale. It is the sole term in the ceiling.

In production

The practical use is as a sanity check before spending. Before adding workers, estimate the serial fraction and compute the ceiling. If it is 4× and you already have 3.9×, the parallelism work is finished and every further hour should go somewhere else.

Measuring it is straightforward: run at one worker and at n, and solve for s. Two data points give you the ceiling and, unlike a code review, they include everything you forgot — the allocator, the GC, the shared queue, the memory bus.

Where the serial fraction usually hides: a single-threaded input parse before the parallel phase; a shared output writer or logger; contention on one lock; a barrier whose phase cost is the slowest participant; and memory bandwidth. In service code the equivalent is any resource every request must pass through — one connection pool, one queue, one leader.

And the reframing that makes it useful rather than discouraging: since the ceiling is 1/s, reducing the serial fraction is the highest-leverage optimisation available. Going from 10% to 5% serial doubles what your hardware can ever deliver. No amount of making the parallel part faster does that.

The follow-up questions

“Your program is 90% parallel. What is the maximum speedup?” — 10×. And at 64 cores, 8.8× — so you are nearly done already.

“You doubled the cores and got 10% faster. What is happening?” — You are near the ceiling. Estimate the serial fraction from those two data points.

“Where would you look for the serial part?” — I/O, allocation, locks, barriers, memory bandwidth. Not just what looks sequential in the source.

“When does Amdahl’s law not apply?” — When the problem grows with the machine. Naming Gustafson unprompted is a strong signal.