Amdahl's Law

Add cores to a program and it gets faster, but only up to a point. Amdahl’s Law, from Gene Amdahl’s 1967 paper, names that point. It is one of the entries in my Laws note.

What the law says

Split a program’s running time into two parts:

• The parallel part (a fraction p) can be spread across cores.
• The serial part (1 − p) cannot. It runs on one core no matter how many you have: start-up, coordination, a lock everyone waits for.

With n cores the parallel part shrinks to p / n, while the serial part stays the same. The speed-up is the old time divided by the new time:

S(n) = 1 / ((1 − p) + p / n)

As n grows, p / n falls towards zero, and the speed-up approaches a ceiling of 1 / (1 − p). No amount of hardware gets past it.

Try it

Drag the sliders. Watch how close the curve gets to the dashed ceiling, and how early it flattens.

A worked example

Take a job that is 95% parallel, so p = 0.95 and the serial part is 5%.

The ceiling is 1 / 0.05 = 20×. Going from 64 to 1024 cores buys 16 times the hardware for about 27% more speed. The 5% serial slice, which looked harmless, now decides the result.

Why it matters

• The serial part dominates. Once you have a few dozen cores, shaving the serial part pays more than buying cores. Cutting it from 5% to 2.5% doubles the ceiling to 40×.
• Measure before you scale. Profile to find the serial part: the single-threaded set-up, the shared lock, the final merge. That number tells you the best you can hope for.
• Overheads make it worse. The formula assumes parallel work splits for free. Real systems pay for communication and synchronisation, so real curves often peak and then fall.

The counterpoint: Gustafson’s Law

Amdahl fixes the problem size and asks how fast it can go. Gustafson’s Law (1988) notes that with more cores we usually tackle bigger problems, where the parallel part grows and the serial part stays small, so speed-up keeps scaling. Both are true; they answer different questions.