Amdahl Law
Amdahl's Law — the fundamental limit on parallel speedup, stating that the serial portion of a program limits the maximum achievable speedup regardless of how many processors are used.
Formula
$$S(n) = \frac{1}{(1-p) + \frac{p}{n}}$$
Where:
- $S(n)$ = speedup with $n$ processors
- $p$ = parallelizable fraction of execution time
- $(1-p)$ = serial fraction
Key Insights
| Serial Fraction | Max Speedup (infinite cores) |
|---|---|
| 1% | 100x |
| 5% | 20x |
| 10% | 10x |
| 25% | 4x |
| 50% | 2x |
- Even 5% serial code caps speedup at 20x — no matter how many cores
- 1000 cores with 1% serial: speedup = only 91x (not 1000x)
Parallel Efficiency
- $E = \frac{S(n)}{n}$ — ideal = 100%, practical = 60-90%
- Overhead sources: synchronization, communication, load imbalance, cache effects
Gustafson's Law (counterpoint)
- In practice, bigger machines solve bigger problems (not the same problem faster)
- If problem size scales with processors, parallel fraction grows
- More optimistic view of scalability
Amdahl's Law is the first thing to check when planning parallelization — identify and minimize the serial bottleneck.