Amdahl's vs Gustafson's Law

Two formulas describe how speed increases when you add processors to a parallel program. They assume different things about the program as it grows, so they give different limits. This note explains when to use each and why the assumptions matter.

The idea

Part of every program runs in serial, and part can run in parallel. The serial part is a bottleneck: you can add as many processors as you like, but that serial fraction always takes the same time. If 10% of your code is serial, you can never speed up more than 10x, no matter how many cores you have. This is the insight behind Amdahl's law.

But real programs do not stay the same size as you add cores. If you buy a machine with 100 cores instead of 10, you probably have a bigger problem to solve. You might parallelise more of it now that you have the capacity. Gustafson's law asks: how much work can you do in the same time with more cores? The answer depends on how you scale your problem.

The maths

Let $p$ be the fraction of your program that is serial, so $1-p$ is the parallel part. On $P$ processors:

S_p = \frac{1}{(1 - p) + p/P}

This is Amdahl's law. The speedup approaches $1/p$ as $P$ grows. If 10% is serial, speedup caps at 10x. If 1% is serial, the cap is 100x.

Gustafson's law says: suppose on a single processor you spend fraction $p$ of time in serial code and fraction $1-p$ in parallel code. If you now have $P$ processors and run the same serial code, how much more parallel work can fit in the same time?

S_p = P - p(P - 1)

This scales linearly with $P$ . You get $P - p(P-1)$ speedup, which is much better than Amdahl's fixed ceiling. The serial part costs the same either way, but the parallel part expands to fill the extra cores.

Try it

The widget below shows both laws. Move the sliders and watch how the two curves diverge. Amdahl hits a limit; Gustafson keeps growing. The choice between them is about what question you are asking.

Cores: 16

Serial fraction: 10.0%

Amdahl

6.40x

Gustafson

14.50x

Amdahl: 1 / (0.100 + 0.0563)

Gustafson: 16 - 1.500

At 16 cores with {serialFraction} serial, Amdahl: 6.40x, Gustafson: 14.50x

Sliders for cores and serial fraction.

Keep serial fraction at 10%. Amdahl caps at 10x even with 1,000 cores. Gustafson keeps growing.
Drop serial fraction to 1%. Amdahl now caps at 100x. Gustafson still scales linearly.
The crossover is at small $P$ . For 4-8 cores, both laws give similar speedup. At 1,000 cores, they differ by orders of magnitude.

Where I used it

Easy to get wrong

Sources

Amdahl's LawWikipediaClear derivation of the speedup limit and discussion of its implications for parallel computing.
Gustafson's LawWikipediaGustafson's 1988 rebuttal to Amdahl, showing how scaled speedup differs when problem size grows with processor count.