Math derivation of Amdahl's Law

Amdahl's Law

Amdahl's Law describes the maximum speedup achievable when parallelizing a program. It tells us how much faster a program can run when we use multiple processors.

The Problem

When we parallelize code, only a portion can truly run in parallel. Some parts must still run sequentially. Amdahl's Law quantifies this limitation.

The Formula

Let's define: - S = overall speedup - p = fraction of the program that can be parallelized (0 ≤ p ≤ 1) - N = number of processors

S = 1 / ((1 - p) + p/N)

Breaking It Down

• (1 - p) = the sequential portion that cannot be parallelized
• p/N = the parallelizable portion divided among N processors

The denominator represents the total time relative to the original execution time.

Example

Suppose 90% of your program can be parallelized (p = 0.9) and 10% must run sequentially (1 - p = 0.1).

With 4 processors:

S = 1 / (0.1 + 0.9/4)
S = 1 / (0.1 + 0.225)
S = 1 / 0.325
S ≈ 3.08x speedup

Even with 4 processors, you only get ~3x faster, not 4x!

Key Insight

Adding more processors shows diminishing returns. As N approaches infinity:

S_max = 1 / (1 - p)

With 90% parallelizable code, the theoretical maximum speedup is only 10x, no matter how many processors you add.