Gustafson's law

Gustafson's Law

Gustafson's Law (also known as Gustafson-Barsis' law) is a law in computer science which says that problems with large, repetitive data sets can be efficiently parallelized. Gustafson's Law contradicts Amdahl's law, which describes a limit on the speed-up that parallelization can provide. Gustafson's law was first described by John L. Gustafson and his colleague Edwin H. Barsis:

$S(P)=P-\alpha \cdot (P-1)$.

where P is the number of processors, S is the speedup, and $\alpha$ the non-parallelizable part of the process.

Gustafson's law addresses the shortcomings of Amdahl's law, which does not scale the availability of computing power as the number of machines increases. Gustafson's Law proposes that programmers 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.

Amdahl's law is based on fixed workload or fixed problem size. It implies that the sequential part of a program does not change with respect to machine size (i.e, the number of processors). However the parallel part is evenly distributed by $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 particular the law redefines efficiency as a need to minimize the sequential part of a program, even if it increases the total amount of computation.

Implementation of Gustafson's Law

Let n be a measure of the problem size.

The execution of the program on a parallel computer is decomposed into:

$a(n)+b(n)=1$

where a is the sequential fraction and b is the parallel fraction, ignoring overhead for now.

On a sequential computer, the relative time would be $a(n)+p\cdot b(n)$, where p is the number of processors in the parallel case.

Speedup is therefore:

$(a(n)+p\cdot {}b(n))$ (parallel, relative to sequential $a(n)+b(n)=1$)

and thus

$S=a(n)+p\cdot {}(1-a(n))$

where $a(n)$ is the serial function.

Assuming the serial function $a(n)$ diminishes with problem size n, then speedup approaches p as n approaches infinity, as desired.

Thus Gustafson's law seems to rescue parallel processing from Amdahl's law.

Gustafson's law argues that even using massively parallel computer systems does not influence the serial part and regards this part as a constant one. In comparison to that, the hypothesis of Amdahl's law results from the idea that the influence of the serial part grows with the number of processes.

A Driving Metaphor

Amdahl's Law approximately suggests:

Suppose a car is traveling between two cities 60 miles apart, and has already spent one hour traveling half the distance at 30 mph. No matter how fast you drive the last half, it is impossible to achieve 90 mph average before reaching the second city. Since it has already taken you 1 hour and you only have a distance of 60 miles total; going infinitely fast you would only achieve 60 mph.

Gustafson's Law approximately states:

Suppose a car has already been traveling for some time at less than 90mph. Given enough time and distance to travel, the car's average speed can always eventually reach 90mph, no matter how long or how slowly it has already traveled. For example, if the car spent one hour at 30 mph, it could achieve this by driving at 120 mph for two additional hours, or at 150 mph for an hour, and so on.

Limitations

Some problems do not have fundamentally larger datasets. As example, processing one data point per world citizen gets larger at only a few percent per year. The principal point of Gustafson's law is that such problems are not likely to be the most fruitful applications of parallelism.

Nonlinear algorithms may make it hard to take advantage of parallelism "exposed" by Gustafson's law. Snyder points out an O(N³) algorithm means that double the concurrency gives only about a 26% increase in problem size. Thus, while it may be possible to occupy vast concurrency, doing so may bring little advantage over the original, less concurrent solution—however in practice there have been massive improvements.

Hill and Marty emphasize also that methods of speeding sequential execution are still needed, even for multicore machines. They point out that locally inefficient methods can be globally efficient when they reduce the sequential phase. Furthermore, Woo and Lee studied the implication of energy and power on future many-core processors based on Amdahl's Law, showing that an asymmetric many-core processor can achieve the best possible energy efficiency by activating an optimal number of cores given the amount of parallelism is known prior to execution.

See also

• Scalable parallelism

External links

• Reevaluating Amdahl's Law and Gustafson's Law, Yuan Shi, October 1996. Unpublished monograph.