Real Time Systems Design And Analysis

Chapter 7.1.5 - Gustafson’s Law

7.1.5   Gustafson’s Law

Gustafson demonstrated with a 1024-processor system that the basic presumptions
in Amdahl’s Law are inappropriate for massive parallelism [Gustafson88].
Gustafson found that the underlying principle that “the problem size scales with
the number of processors, or with a more powerful processor, the problem
expands to make use of the increased facilities is inappropriate” [Gustafson88].

Gustafson’s empirical results demonstrated that the parallel or vector part of a
program scales with the problem size. Times for vector start-up, program loading,
serial bottlenecks, and I/O that make up the serial component of the run do not
grow with the problem size [Gustafson88].

Gustafson formulated that if the serial time, s, and parallel time, p = (1 − s),
on a parallel system with n processors, then a serial processor would require
the time:

 

Comparing the plots of Equations 7.1 and 7.2 in Figure 7.3, it can be seen that
Gustafson presents a much more optimistic picture of speedup due to parallelism
than does Amdahl. Unlike the curve for Amdahl’s Law, Gustafson’s Law is a
simple line, “one with a much more moderate slope: 1 − n. It is thus much
easier to achieve parallel performance than is implied by Amdahl’s paradigm”
[Gustafson88].

A different take on the flaw of Amdahl’s Law can be observed as “a more
efficient way to use a parallel computer is to have each processor perform similar
work, but on a different section of the data. . . where large computations are concerned
this method works surprisingly well” [Hillis98]. Doing the same task but
on a different range of data circumvents an underlying presumption in Amdahl’s
Law, that is, “the assumption that a fixed portion of the computation. . . must be
sequential. This estimate sounds plausible, but it turns out not to be true of most
computations” [Hillis98].


Figure 7.3 Linear speedup of Gustafson compared to ‘‘diminishing return’’ speedup of Amdahl with 50% of code available for parallelization. Notice as number of processors increase, speedup does not increase indefinitely for Amdahl due to serial component [Gilreath03].

 

UNLIMITED FREE
ACCESS
TO THE WORLD'S BEST IDEAS

SUBMIT
Already a GlobalSpec user? Log in.

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.

Customize Your GlobalSpec Experience

Category: PCMCIA Memory Cards
Finish!
Privacy Policy

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.