Amdahl's Law — Algorithmics

A job takes 100 seconds. You buy a machine with 16 cores. How long does it take now?

The tempting answer is 6.25 seconds. The real answer depends entirely on one number you have not been told: how much of those 100 seconds cannot be split up.

Where the ceiling comes from

Suppose 10 seconds of the job is inherently sequential — reading the input file, allocating the output, writing the result. That part takes 10 seconds on one core and 10 seconds on a thousand.

The other 90 seconds divide by the core count. So on 16 cores:

10 + \frac{90}{16} = 15.6\text{ seconds}

A 6.4× speedup, not 16×. And no number of cores gets below 10 seconds, so the best this job can ever do is 10×.

Move the sliders — note how quickly extra cores stop paying:

part that cannot be parallelised 10%cores 16

speedup: 6.4×
ceiling, any core count: 10×
cores actually earning: 40%

Even with infinite cores this program cannot beat 10×, because 10% of it runs on one core no matter what. At 16 cores you are already at 64% of that ceiling — buying more will not help.

The formula

With $s$ as the serial fraction and $n$ cores:

\text{speedup} = \frac{1}{s + \frac{1 - s}{n}}

As $n$ grows, the second term vanishes and you are left with $1/s$ . That is the whole law: the ceiling is the reciprocal of the serial fraction.

What counts as serial

More than people expect, and most of it is not obvious in the source:

Startup and teardown — reading input, writing output, JIT warm-up.
Any critical section. A mutex makes its body serial by definition. A lock held 5% of the time is a 5% serial fraction.
Synchronisation points. A barrier waits for the slowest worker, so the gaps between finishers are serial time.
Contended shared state — a counter, a cache, a connection pool.
Memory bandwidth. Sixteen cores share one bus. When you saturate it, the extra cores stall, which behaves exactly like serial time.

That last one is the usual surprise in practice: a program with no locks at all can still fail to scale because it is bandwidth-bound.

The optimistic counterpart

Gustafson’s law makes a different assumption and reaches a happier conclusion: in practice, people who get a bigger machine give it a bigger problem.

If the serial part stays fixed while the parallel part grows with the data, the serial fraction shrinks, and speedup scales nearly linearly with cores.

Both laws are correct; they answer different questions:

Amdahl — “same job, more cores.” Relevant to latency: how fast can this one request be?
Gustafson — “more cores, bigger job.” Relevant to throughput: how much work can this cluster do in an hour?

Latency questions are governed by Amdahl, and latency is usually what users notice.

What to do about it

Measure the serial fraction before buying anything. Run at 1, 2, 4 and 8 cores and fit the curve — you can solve for $s$ from two data points, and the answer is usually worse than the estimate.

Attack the serial part, not the parallel part. Optimising the 90% that already scales moves the ceiling not at all. Halving the 10% doubles it.

Shrink critical sections. Do the computation outside the lock and hold it only for the update. This is the single highest-leverage change in most concurrent code.

Consider not sharing. Actors and channels avoid locks by avoiding shared mutable state, which removes serial sections rather than shortening them.