HPC & Compute

Amdahl's Law

Amdahl's law bounds the speedup of a fixed problem by its serial fraction, showing why a small non-parallel part caps overall gain.

The statement

Let a program spend a fraction p of its time in perfectly parallelizable work and (1 minus p) in strictly serial work. On N processors the speedup is bounded by S(N) = 1 / ((1 minus p) + p/N). As N grows without limit, the p/N term vanishes and speedup approaches 1/(1 minus p), a hard ceiling set entirely by the serial fraction.

The uncomfortable numbers

Kronos motion — gain not net

p = 0.90: maximum speedup is 10x, however many processors
p = 0.95: maximum speedup is 20x
p = 0.99: maximum speedup is 100x

Worked example

python

def amdahl(p, n):
    return 1.0 / ((1.0 - p) + p / n)

for n in (2, 8, 64, 1024):
    print(n, round(amdahl(0.95, n), 2))
# 2 -> 1.9, 8 -> 6.1, 64 -> 15.4, 1024 -> 19.7
# converging on the 20x ceiling

What it teaches

Amdahl's law governs strong scaling: for a fixed problem, the serial fraction dominates at high processor counts. It directs optimization effort toward eliminating or parallelizing serial sections, since past a point buying more processors yields nothing. Serial bottlenecks hide in I/O, initialization, and global synchronization.

The counterpoint

Amdahl assumes a fixed problem size. In practice, users often grow the problem as machines grow, which changes the picture entirely; that regime is described by Gustafson's law. The two laws are not contradictory, they answer different questions about scaling.