# Gustafson's law

Gustafson's law

Gustafson's Law (also known as Gustafson-Barsis' law) is a law in computer engineering which states that any sufficiently large problem can be efficiently parallelized. Gustafson's Law is closely related to Amdahl's law, which gives a limit to the degree to which a program can be sped up due to parallelization. It was first described by John L. Gustafson in 1988.

:$S\left(P\right) = P - alphacdot\left(P-1\right)$.

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 cannot scale to match availability of computing power as the machine size increases. It removes the fixed problem size or fixed computation load on the parallel processors: instead, he proposed a fixed time concept which leads to scaled speed up.

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 n processors.

The impact of the law was the shift in research to develop parallelizing compilers and reduction in the serial part of the solution to boost the performance of parallel systems.

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\left(n\right) + b\left(n\right) = 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\left(n\right) + pcdot\left\{\right\}b\left(n\right)$, where "p" is the number of processors in the parallel case.

Speedup is therefore:

:$\left(a\left(n\right) + pcdot\left\{\right\}b\left(n\right)\right)$ (parallel, relative to sequential $a\left(n\right)+b\left(n\right)=1$)

and thus

:$S= a\left(n\right) + pcdot\left\{\right\}\left(1-a\left(n\right)\right)$

where $a\left(n\right)$ is the serial function.

Assuming the serial function $a\left(n\right)$ 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

Suppose a car is traveling between two cities 60 miles apart, and has already spent one hour traveling half the distance at 30 mph.

Amdahl's Law approximately suggests:

Gustafson's Law approximately states:

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.

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 9% 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.

* [http://www.scl.ameslab.gov/Publications/Gus/AmdahlsLaw/Amdahls.html Reevaluating Amdahl's Law] - the paper in which John Gustafson first described his Law. Originally published in Communications of the ACM 31(5), 1988. pp. 532-533
* * [http://www.scl.ameslab.gov/Publications/Gus/AmdahlsLaw/Amdahls.html Reevaluating Amdahl's Law]
* [http://www.cis.temple.edu/~shi/docs/amdahl/amdahl.html Reevaluating Amdahl's Law and Gustafson's Law] - a paper in which Yuan Shi proves that both laws are equivalent: Gustafson just used a different definition of s (the serial part)
* [http://www.cs.washington.edu/homes/snyder/TypeArchitectures.pdf] -- Lawrence Snyder, "Type Architectures, Shared Memory, and The Corrolary of Modest Potential"

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Gustafson — A derivative of the name Gustav, Gustafson, Gustafsson, Gustavson, and/or Gustavsson, is a group of fairly common surnames of Swedish origin, and may refer to any of the following people: Gustafson *Andy Gustafson, American collegiate football… …   Wikipedia

• Gustafson v. Payless — Infobox Court Case name = Gustafson v. Payless Drug Stores court = Oregon Supreme Court date filed = December 3 1973 date decided = August 8 1974 full name = Albertina Gustafson v. Payless Drug Stores NW, Inc. citations = 269 Or. 354, 525 P.2d… …   Wikipedia

• John Gustafson (scientist) — John L. Gustafson (born January 19, 1955) is an American computer scientist and businessman, chiefly known for his work in High Performance Computing (HPC) such as the invention of Gustafson s Law, introducing the first commercial computer… …   Wikipedia

• Amdahl's law — Amdahl s law, also known as Amdahl s argument, [Rodgers 85, p.226] 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. It is often used …   Wikipedia

• John Gustafson — may refer to:*John Gustafson (scientist), computer scientist, inventor of Gustafson s Law and CEO of Massively Parallel Technologies *John Gustafson (musician), bassist and vocalist …   Wikipedia

• David Gustafson — Judge David Gustafson, 2010 David Gustafson (born in Greenville, South Carolina, 1956), is a judge of the United States Tax Court. Biography Gustafson graduated summa cum laude from Bob Jones University in 1978, and with distinction from the Duke …   Wikipedia

• Sophie Gustafson — (born December 27 1973) is a Swedish professional golfer. She is a member of U.S. based LPGA Tour and a life member of the Ladies European Tour. cite web title = Gustafson named Life Member of the Ladies European Tour publisher = LPGA url =… …   Wikipedia

• Georgetown University Law Center — Infobox University image size = 172px name = Georgetown University Law Center established = 1870 type = Private motto = Law is but the means Justice is the end [Expressed by Joseph A. Cantrel (Class of 1922), at the 50th Anniversary Celebration… …   Wikipedia

• Florida State University College of Law — College of Law Established 1966 Type Public Dean Donald J. Weidner Location Tallahassee, Florida, USA …   Wikipedia

• University of Connecticut School of Law — Infobox University name = University of Connecticut School of Law image size = 150px established = 1921 type = Public city = Hartford state = Connecticut country = USA postgrad = 621 website = [http://www.law.uconn.edu] The University of… …   Wikipedia