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 \le p \le 1\)
\(N\) — number of processors

\[ S = \frac{1}{(1 - p) + \frac{p}{N}} \]

Breaking it down

\((1 - p)\) is the sequential portion that cannot be parallelized.
\(p/N\) is 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 four processors:

\[ S = \frac{1}{0.1 + \frac{0.9}{4}} = \frac{1}{0.325} \approx 3.08 \]

Even with four processors you only get about 3x faster, not 4x.

Key insight

Adding more processors shows diminishing returns. As \(N \to \infty\):

\[ S_{\max} = \frac{1}{1 - p} \]

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