Amdahl's law

Amdahl's law is a formula that predicts the maximum speedup you can get from parallelizing a program, given that some fraction of it is inherently sequential. It was stated by Gene Amdahl in 1967. The key insight is that the sequential portion of a program acts as a hard ceiling on how much parallelism can help, no matter how many processors you throw at it.

Suppose a program takes time $T$ to run on a single core. Let $p$ be the fraction of that work that can be parallelized, so $1 - p$ is the fraction that must run sequentially. On $n$ processors, the parallel portion takes $\frac{p}{n}$ of the original time, while the sequential portion stays fixed at $1 - p$. The total time on $n$ processors is therefore:

$$T(n) = T \left( (1 - p) + \frac{p}{n} \right)$$

The speedup $S(n)$ is the ratio of single-core time to $n$-core time:

$$S(n) = \frac{T}{T(n)} = \frac{1}{(1 - p) + \dfrac{p}{n}}$$

As the number of processors $n \to \infty$, the $\frac{p}{n}$ term vanishes and speedup approaches a hard limit:

$$S_{\max} = \frac{1}{1 - p}$$

This is the ceiling Amdahl's law is famous for. If 90% of your program is parallelizable ($p = 0.9$), the maximum possible speedup is $\frac{1}{0.1} = 10\times$, regardless of whether you use 100 or 100,000 cores. The remaining 10% of sequential work is the bottleneck.

Amdahl's law is a pessimistic model in the sense that it assumes the problem size is fixed while you add more processors (strong scaling). In practice, the sequential fraction $p$ is rarely constant — initialization, I/O, barrier synchronization, and serial reduction steps all contribute to it. Profiling to find and shrink the sequential portion is often more impactful than adding more cores. The contrasting model for the case where problem size grows with processor count is Gustafson's law.