Gustafson's Law

Gustafson's Law (also known as Gustafson-Barsis' law) is a law in computer science which says that computations involving arbitrarily large data sets can be efficiently parallelized. Gustafson's Law provides a counterpoint to Amdahl's law, which describes a limit on the speed-up that parallelization can provide, given a fixed data set size. Gustafson's law was first described by John L. Gustafson and his colleague Edwin H. Barsis:

where P is the number of processors, S is the speedup, and the non-parallelizable fraction of any parallel process.

Gustafson's law addresses the shortcomings of Amdahl's law, which does not fully exploit the computing power that becomes available as the number of machines increases. Gustafson's Law instead proposes that programmers tend to set the size of problems to use the available equipment to solve problems within a practical fixed time. Therefore, if faster (more parallel) equipment is available, larger problems can be solved in the same time.

Accordingly, Gustafson called his metric scaled speedup, because in the above expression S(P) is the ratio of the total, single-process execution time to the per-process parallel execution time; the former scales with P, while the latter is assumed fixed or nearly so. This is in contrast to Amdahl's Law, which takes the single-process execution time to be the fixed quantity, and compares it to a shrinking per-process parallel execution time. Thus, Amdahl's law is based on the assumption of a fixed problem size: it assumes the overall workload of a program does not change with respect to machine size (i.e., the number of processors). Both laws assume the parallelizable part is evenly distributed over P processors.

The impact of Gustafson's law was to shift research goals to select or reformulate problems so that solving a larger problem in the same amount of time would be possible. In a way the law redefines efficiency, due to the possibility that limitations imposed by the sequential part of a program may be countered by increasing the total amount of computation.