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 Gustafson in 1988. The examples and perspective in this article or section may not represent a worldwide view. ... Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain results faster. ... The speedup of a program using multiple processors in parallel computing is limited by the sequential fraction of the program. ... 1988 (MCMLXXXVIII) was a leap year starting on Friday of the Gregorian calendar. ...

S(P) = P − α * (P − 1).

P... number of processors, S... speedup, α ... non-parallelizable part of 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. The speedup of a program using multiple processors in parallel computing is limited by the sequential fraction of the program. ...

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. To meet Wikipedias quality standards, this article or section may require cleanup. ...

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. Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain results faster. ...

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) + pb(n) where p is the number of processors in the parallel case. The term Parallel has a number of important meanings: Parallel (geometry) occurs in geometry. ...

Speedup is therefore:

 (a(n) + pb(n)) (parallel, relative to sequential a(n)+b(n)=1) 

and thus

 = a(n) + p*(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. Serial is a term, originating in literature, for a format by which a story is told in contiguous installments in sequential issues of a single periodical publication. ... In parallel computing, speedup refers to how much a parallel algorithm is faster than a corresponding sequential algorithm. ...

Thus Gustafson's law seems to rescue parallel processing from Amdahl's law. The term Parallel has a number of important meanings: Parallel (geometry) occurs in geometry. ... Typically, processing describes the act of taking something through an established and usually routine set of procedures to convert it from one form to another, as a manufacturing procedure (processing milk into cheese) or administrative procedure (processing paperwork to grant a mortgage loan). ... The speedup of a program using multiple processors in parallel computing is limited by the sequential fraction of the program. ...

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. The speedup of a program using multiple processors in parallel computing is limited by the sequential fraction of the program. ...

External links

• 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