Gustafson's law

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\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 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 respect to the improvement of the 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 the resources improve.[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 the 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 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 limitations imposed by the sequential part of a program may be countered by increasing the total amount of computation.

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 the parallel system is:

$${\displaystyle S={\frac {T'}{T}}={\frac {s+Np}{s+p}}={\frac {s+Np}{1}}=s+Np}$$

By substituting ${\displaystyle p=1-s}$ or ${\displaystyle s=1-p}$, several forms in the previous section can be derived.

Some problems do not have fundamentally larger datasets. As an example, processing one data point per world citizen gets larger at only a few percent per year. The principal point of Gustafson's law is that such problems are not likely to be the most fruitful applications of parallelism.

Algorithms with nonlinear runtimes may find it hard to take advantage of parallelism "exposed" by Gustafson's law. Snyder[3] points out an ${\displaystyle O(N^{3})}$ algorithm means that double the concurrency gives only about a 26% 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—however in practice there have still been considerable improvements.

Hill and Marty[4] emphasize also that methods of speeding sequential execution are still needed, even for multicore machines. They point out that locally inefficient methods can be globally efficient when they reduce the sequential phase. Furthermore, Woo and Lee[5] studied the implication of energy and power on future many-core processors based on Amdahl's law, showing that an asymmetric many-core processor can achieve the best possible energy efficiency by activating an optimal number of cores given the amount of parallelism is known prior to execution.

Al-hayanni, Rafiev et al have developed novel speedup and energy consumption models based on a general representation of core heterogeneity, referred to as the normal form heterogeneity, that support a wide range of heterogeneous many-core architectures. These modelling methods aim to predict system power efficiency and performance ranges, and facilitates research and development at the hardware and system software levels.[6][7]

• Scalable parallelism
• Parkinson's law
• Jevons paradox