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

• 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.