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.