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 tasks can be made parallel, then total time taken is
If we could accelerate parallel parts by a factor of , then
The speed up achieved by parallelization () is:
Key Implications
-
The sequential portion is the bottleneck
As , - 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 , using gives us a speedup of 2.5x, but doubling 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.