Amdahl Law Revisited

Amdahl Law Revisited

Amdahl law answers a sobering question: if only part of a program can be parallelized, how much faster can it get? It fixes the problem size and asks how speedup grows with processor count.

The serial fraction rules

Split the runtime into a serial fraction that cannot be parallelized and a parallel fraction that can. As processors grow, only the parallel part shrinks while the serial part stays put.

• The serial part becomes the limiting term.
• With infinite processors the parallel part vanishes, leaving just the serial time.
• So the maximum speedup is one divided by the serial fraction.

The lesson

If five percent of the work is serial, the best possible speedup is twenty, even with a thousand cores. Small serial sections quietly dominate. The takeaway is to attack the serial fraction first, since shaving it off raises the ceiling for everyone.

Key idea

With a fixed problem size the serial fraction caps speedup at one divided by that fraction, so reducing serial work matters most.