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 $p$ tasks can be made parallel, then total time taken $T$ is

T = (1-p)T + pT

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

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

The speed up achieved by parallelization ( $S$ ) is:

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

Key Implications

The sequential portion is the bottleneck

As $s\to\infty$ , $S\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.
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
The returns diminish quickly.

Doubling the processors rarely doubles the speed. For example, if $p = 0.8$ , using $s=4$ gives us a speedup of 2.5x, but doubling $s$ 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.

Abhilash Meesala

Amdahl's Law and Optimization

Key Implications

Links

Socials