Gustafson's Law

Gustafson’s Law is a principle in parallel computing that offers an optimistic view of scalability. Where Amdahl’s Law assumes a fixed problem size and concludes that speedup is limited by serial work, Gustafson’s Law changes the perspective.

It observes that when more processors are available, developers tend to increase the problem size to use that extra power. If you have a cluster twice as powerful, you might process twice as much data in the same time.

The parallel portion of work grows with N processors while the serial portion remains about the same, leading to “scaled speedup” that can be almost linear.

Gustafson’s insight is that developers naturally use more computing power by asking bigger questions.

• As computing resources grow, you can compute more problems in a given time, rather than solving the same issues faster.
• It opposes the pessimism of Amdahl's Law by assuming the size of the problem to be solved will increase proportionally with computing power, so that parallel processors remain busy.
• Practically, Gustafson's Law promotes the use of more resources in computation to achieve more in terms of the scope of tasks, rather than obtaining diminishing returns.
• Software should be designed to scale out: as more cores or machines are added, the problem size grows and the extra capacity does useful work.