From Wikipedia, the free encyclopedia

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(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.

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.

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.

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.

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 given car will be traveling between two cities 60 miles apart, and has already traveled half the distance at 30 mph.

Amdahl's Law approximately suggests:

No matter how fast you drive the last half, it is impossible to achieve 90 mph average. 
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:

Given enough time, the car will approach the desired speed. 
90mph average is possible so long as you drive at 150 mph for an hour. 

Addressing a slightly different question allows for a significantly more useful analysis.

• 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

	Topics in Parallel Computing	v • d • e
General High-performance computing Parallelism Data parallelism • Task parallelism Theory Speedup • Amdahl's law • Flynn's Taxonomy • Cost efficiency • Gustafson's Law • Karp-Flatt Metric Elements Process • Thread • Fiber • Parallel Random Access Machine Coordination Multiprocessing • Multithreading •Multitasking • Memory coherency • Cache coherency • Barrier • Synchronization • Distributed computing • Grid computing Programming Programming model • Implicit parallelism • Explicit parallelism Hardware Computer cluster • Beowulf • Symmetric multiprocessing • Non-Uniform Memory Access • Cache only memory architecture • Asymmetric multiprocessing • Simultaneous multithreading • Shared memory • Distributed memory • Massively parallel processing • Superscalar processing • Vector processing • Supercomputer Software Distributed shared memory • Application checkpointing APIs Pthreads • OpenMP • Message Passing Interface (MPI) Problems Embarrassingly parallel • Grand Challenge