Amdahl Law
Amdahl law predicts the maximum speedup of a program when you add processors. Its key insight is that only part of a program can run in parallel. The rest is serial and runs the same no matter how many cores you have.
Let the serial fraction be S and the parallel fraction be P, where S plus P equals one. With N processors the speedup is one divided by the quantity S plus P over N. As N grows very large, the parallel term shrinks toward zero, so the speedup approaches one divided by S.
This ceiling is brutal. If just ten percent of the work is serial, the best possible speedup is ten times, no matter how many cores you throw at it. A serial fraction of one percent still caps you at one hundred times.
Practical consequences:
- Optimizing the serial portion often matters more than adding cores
- There are diminishing returns once you have enough processors
- Coordination overhead like locking adds to the effective serial fraction
Amdahl law assumes a fixed problem size. A companion result, Gustafson law, notes that in practice we grow the problem with the machine, which is more optimistic. But for a fixed task, Amdahl sets a hard upper bound.
Key idea
The serial fraction of a program sets a hard ceiling on speedup, so even infinite cores cannot beat one divided by that fraction.