Website Logo

Abhilash Meesala

Amdahl's Law and Optimization

How much faster can we get by parallelizing a workload?

Amdahl’s law helps us to estimate the maximum speed up that can be achieved by parallelizing a program.

The equation and the derivation are fairly intuitive and simple.

Consider a workload taking time T. If proportion pp tasks can be made parallel, then total time taken TT is

T=(1p)T+pTT = (1-p)T + pT

If we could accelerate parallel parts by a factor of ss, then

Tnew=(1p)T+psTT_{new} = (1-p)T + \frac{p}{s}T

The speed up achieved by parallelization (SS) is:

S=TTnew=1(1p)+psS = \frac{T}{T_{new}} = \frac{1}{(1-p) + \frac{p}{s}}

Key Implications

  1. The sequential portion is the bottleneck

    As ss\to\infty, S11pS\to\frac{1}{1-p} - no matter how many processors you use, your program’s speed up is limited by the serial portion. To improve overall performance, focus on minimizing the sequential components.

  2. Optimising the longest step is a good strategy in general.

    Big optimisations in short steps don’t add much value - focus on optimising the largest bottlenecks, whether they’re sequential or parallelizable

  3. The returns diminish quickly.

    Doubling the processors rarely doubles the speed. For example, if p=0.8p = 0.8, using s=4s=4 gives us a speedup of 2.5x, but doubling ss to 8 only gives us a speedup of 3.3x.

Amdahl’s law highlights a critical insight - parallelization is not a silver bullet. Parallelization accelerates programs, but its benefits eventually plateau. To achieve significant speedups, we must focus on minimizing serial components, identifying bottlenecks, and adopting a balanced approach to optimization.