Part 7 · 1 chapters · ~8 min

Amdahl's Law and Parallel Speedup

Amdahl's law with worked numbers, Gustafson's law, contention and coherence costs that make real speedup worse than Amdahl, the universal scalability law, measuring speedup curves, and finding the serial part.

12

The serial fraction

code
speedup(N) = 1 / (s + (1 - s) / N)
s = 0.05, N = 16  → 1 / (0.05 + 0.95/16) = 1 / 0.109 ≈ 9.1
s = 0.50, N = 16  → 1 / (0.50 + 0.50/16) = 1 / 0.531 ≈ 1.9

Neil Gunther's universal scalability law adds a coherence term: with contention, throughput can
peak and then FALL as you add cores or nodes (the false sharing measurement in Computers part 8 is one cause).
AMDAHL'S LAW
maximum speedup on 16 cores, by the fraction of the work that is serial
0% serial16×5% serial9.1×10% serial6.4×25% serial3.4×50% serial1.9×
swipe the figure sideways, or tap expand for full screen
1/4
the law
Speedup on N cores = 1 / (s + (1 − s) / N), where s is the serial fraction. The serial part caps everything.
speedup = 1 / (s + (1 − s)/N)the serial part caps the gain