Amdahl's Law

Amdahl's Law is the mathematical boundary that constrains the speedup achievable by parallelizing a computation. Formulated by Gene Amdahl in 1967, it states that if a fraction f of a program is inherently sequential, the maximum speedup on N processors is bounded by 1/(f + (1-f)/N). As N approaches infinity, the speedup approaches 1/f. A program that is 10% sequential can never achieve more than 10x speedup, regardless of how many processors are thrown at it.

The law is often invoked pessimistically — as proof that parallel computing is futile — but this misreads its purpose. Amdahl's Law is not a prophecy; it is a diagnostic. It tells us where to look for parallelization opportunities and what the theoretical ceiling is. The sequential fraction f is not a constant of nature; it is a property of the algorithm and the programming model. Some algorithms have large f; others, particularly those in scientific computing and machine learning, have vanishingly small f.

The law has profound implications for the multicore revolution. If software cannot be parallelized, adding cores yields diminishing returns. This is the parallelism wall: not a physical limit but a software one. The hardware industry bet that software would adapt. Amdahl's Law measures whether that bet is paying off.

Amdahl's Law is frequently taught as a reason to despair about parallel speedup, but the deeper truth is more unsettling: we do not know the true sequential fraction of most real programs because we have never had the tools to measure it precisely. The law exposes not just limits but ignorance.