Gustafson's law
Encyclopedia
Gustafson's 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:
.
where P is the number of processors, S is the speedup, and
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 over
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.
The execution of the program on a parallel computer is decomposed into:
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
, where p is the number of processors in the parallel
case.
Speedup is therefore:
(parallel, relative to sequential 
)
and thus
where
is the serial function.
Assuming the serial function
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
.
Amdahl'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 Gustafson's law results from the idea that the influence of the serial part grows with the number of processes.
Gustafson's Law approximately states:
Gustafson, on the other hand, argues that more computing power will cause the data to be more carefully and fully analyzed: pixel by pixel or unit by unit, rather than on a larger scale. Where it would not have been possible or practical to simulate the impact of nuclear detonation on every building, car, and their contents (including furniture, structure strength, etc) because such a calculation would have taken more time than was available to provide an answer, the increase in computing power will prompt researchers to add more data to more fully simulate more variables, giving a more accurate result.
Gustafson's law argues that a quadruple increase in computing power will lead to a similar increase in expectations of what the system will be capable of. If the one-minute load time is acceptable to most users, then that is a starting point from which to increase the features and functions of the system. The time taken to boot to the operating system will be the same, i.e. one minute, but the new system will include more graphical or user-friendly features.
Nonlinear algorithms may make it hard to take advantage of parallelism "exposed" by Gustafson's law. Snyder points out an O(N3) 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.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
which says that problems with large, repetitive data sets can be efficiently parallelized
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
. Gustafson's Law contradicts Amdahl's law
Amdahl's law
Amdahl's law, also known as Amdahl's argument, is named after computer architect Gene Amdahl, and is used to find the maximum expected improvement to an overall system when only part of the system is improved...
, 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:
.where P is the number of processors, S is the speedup, and
the non-parallelizable part of the process.Gustafson's law addresses the shortcomings of Amdahl's law
Amdahl's law
Amdahl's law, also known as Amdahl's argument, is named after computer architect Gene Amdahl, and is used to find the maximum expected improvement to an overall system when only part of the system is improved...
, 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
Workload
-An amount of labor:While a precise definition of a workload is elusive, a commonly accepted definition is the hypothetical relationship between a group or individual human operator and task demands....
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 over
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:
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
, where p is the number of processors in the parallelParallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
case.
Speedup is therefore:
(parallel, relative to sequential )and thus
where
is the serial function.Assuming the serial function
diminishes with problem size n, then speedup approaches p as n approaches infinity, as desired.Thus Gustafson's law seems to rescue parallel processing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
from Amdahl's law
Amdahl's law
Amdahl's law, also known as Amdahl's argument, is named after computer architect Gene Amdahl, and is used to find the maximum expected improvement to an overall system when only part of the system is improved...
.
Amdahl's law
Amdahl's law
Amdahl's law, also known as Amdahl's argument, is named after computer architect Gene Amdahl, and is used to find the maximum expected improvement to an overall system when only part of the system is improved...
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 Gustafson'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:Gustafson's Law approximately states:
Application in research
Amdahl's law presupposes that the computing requirements will stay the same, given increased processing power. In other words, an analysis of the same data will take less time given more computing power.Gustafson, on the other hand, argues that more computing power will cause the data to be more carefully and fully analyzed: pixel by pixel or unit by unit, rather than on a larger scale. Where it would not have been possible or practical to simulate the impact of nuclear detonation on every building, car, and their contents (including furniture, structure strength, etc) because such a calculation would have taken more time than was available to provide an answer, the increase in computing power will prompt researchers to add more data to more fully simulate more variables, giving a more accurate result.
Application in everyday computer systems
An understanding of Amdahl's law would leave one expecting an increase in computer power to reduce the time it takes for a computer to boot to its operating system and be ready for use. Quadrupling computing power on a system that took one minute to load, assuming the process was parallel, would reduce the boot time to fifteen seconds.Gustafson's law argues that a quadruple increase in computing power will lead to a similar increase in expectations of what the system will be capable of. If the one-minute load time is acceptable to most users, then that is a starting point from which to increase the features and functions of the system. The time taken to boot to the operating system will be the same, i.e. one minute, but the new system will include more graphical or user-friendly features.
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(N3) 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.
External links
- Reevaluating Amdahl's Law and Gustafson's Law, Yuan Shi, October 1996. Unpublished monograph.