Gustafson's law - Wikipedia
Jump to content
Search
Search
Donate
Create account
Log in
Personal tools
Donate
Create account
Log in
Gustafson's law
16 languages
العربية<br>Català<br>Deutsch<br>Español<br>Français<br>日本語<br>한국어<br>Македонски<br>Nederlands<br>Polski<br>Română<br>Русский<br>Српски / srpski<br>Svenska<br>Türkçe<br>Українська
Edit links
From Wikipedia, the free encyclopedia
Theoretical speedup formula in computer architecture
Evolution according to Gustafson's Law of the theoretical speedup in latency of the execution of a program as a function of the number of processors executing it, for different values of a<br>In computer architecture, Gustafson's law (or Gustafson–Barsis's law [1]) gives the speedup in the execution time of a task that theoretically gains from parallel computing, using a hypothetical run of the task on a single-core processor as the baseline. To put it another way, it is the theoretical slowdown of an already parallelized task if running on a serial processor. The law is named after computer scientist John L. Gustafson and his colleague Edwin H. Barsis, and was presented in the article Reevaluating Amdahl's Law in 1988.[2]
In contrast to Amdahl's law, which assumes a fixed problem size and yields pessimistic scaling, Gustafson's law assumes that problem sizes grow with available computing resources, allowing far greater effective speedup from parallel execution.
Definition<br>[edit]
Gustafson estimated the speedup
{\displaystyle S}
of a program gained by using parallel computing as follows:
{\displaystyle {\begin{aligned}S&=s+p\times N\\&=s+(1-s)\times N\\&=N+(1-N)\times s\\&=N-(N-1)\times s\end{aligned}}}
where
{\displaystyle S}
is the theoretical speedup of the program with parallelism (scaled speedup[2]);
{\displaystyle N}
is the number of processors;
{\displaystyle s}
and
{\displaystyle p}
are the fractions of time spent executing the serial parts and the parallel parts of the program, respectively, on the parallel system, where
{\displaystyle s+p=1}
Alternatively,
{\displaystyle S}
can be expressed using
{\displaystyle p}
{\displaystyle {\begin{aligned}S&=(1-p)+p\times N\\&=1+(N-1)\times p\end{aligned}}}
Gustafson's law addresses the shortcomings of Amdahl's law, which is based on the assumption of a fixed problem size, that is, of an execution workload that does not change with growing resources. Gustafson's law instead proposes that programmers tend to increase the size of problems to fully exploit the computing power that becomes available as resources grow.[2]
Gustafson and his colleagues further observed from their workloads that time for the serial part typically does not grow as the problem and the system scale,[2] that is,
{\displaystyle s}
is fixed. This gives a linear model between the processor count
{\displaystyle N}
and the speedup
{\displaystyle S}
with slope
{\displaystyle 1-s}
, as shown in the figure above (which uses different notations:
{\displaystyle P}
for
{\displaystyle N}
and
{\displaystyle a}
for
{\displaystyle s}
). Also,
{\displaystyle S}
scales linearly with
{\displaystyle s}
rather than exponentially in Amdahl's Law.[2] With these observations, Gustafson "expect[ed] to extend [their] success [on parallel computing] to a broader range of applications and even larger values for
{\displaystyle N}
".[2]
The impact of Gustafson's law was to shift[citation needed] research goals to select or reformulate problems so that solving a larger problem in the same amount of time would be possible. In a way, the law redefines efficiency, due to the possibility that limits imposed by the sequential part of a program may be countered by increasing the total amount of computing.
Derivation<br>[edit]
The execution time of a program running on a parallel system can be split into two parts:
a part that does not benefit from the increasing number of processors (serial part);
a part that benefits from the increasing number of processors (parallel part).
Example – A computer program that processes files from disk. A part of that program may scan the directory of the disk and create a list of files internally in memory. After that, another part of the program passes each file to a separate thread for processing. The part that scans the directory and creates the file list cannot be sped up on a parallel computer, but the part that processes the files can.
Without loss of generality, let the total execution time on the parallel system be
{\displaystyle T=1}
. Denote the serial time as
{\displaystyle s}
and the parallel time as
{\displaystyle p}
, where
{\displaystyle s+p=1}
. Denote the number of processors as
{\displaystyle N}
Hypothetically, when running the program on a serial system (only one processor), the serial part still takes
{\displaystyle s}
, while the parallel part now takes
{\displaystyle Np}
. The execution time on the serial system is:
{\displaystyle T'=s+Np}
Using
{\displaystyle T'}
as the baseline, the speedup for...