Other meanings of Gustafson's law
Computer Science
Gustafson's law, also known as Gustafson–Barsis's law, is a principle in parallel computing that states that the speedup achievable on a parallel system is limited not by the number of processors but by the fraction of work that must be performed serially, provided the problem size is allowed to scale with the number of processors. It was formulated by John L. Gustafson in 1988 as a counterpoint to Amdahl's law, which assumes a fixed problem size. Gustafson's law is often expressed as scaled speedup and is used to justify the effectiveness of massively parallel processing.
Gustafson's law states that the speedup S achievable on a parallel computer with P processors is given by S(P) = P − α(P − 1), where α is the fraction of work that is inherently serial. This contrasts with Amdahl's law, which assumes a fixed problem size and predicts diminishing returns as P increases. Gustafson argued that in practice, the problem size grows with the available computing power, so the serial fraction becomes relatively smaller. The law is derived by considering the time taken on a single processor as the sum of the serial time and the parallel time, scaled by the number of processors.
Gustafson's law was introduced in a 1988 paper titled "Reevaluating Amdahl's Law," published in Communications of the ACM. Gustafson, working at Sandia National Laboratories, demonstrated near-linear speedup on a 1024-processor hypercube for three real applications: beam stress analysis, electronic circuit simulation, and fluid dynamics. This empirical evidence challenged the pessimistic view of parallel computing that Amdahl's law implied. The law became a foundational justification for massively parallel processing (MPP) and influenced the design of supercomputers and parallel algorithms. It is also known as the scaled speedup model, in contrast to Amdahl's fixed-size speedup.
Gustafson's law is widely used in high-performance computing (HPC) to predict the performance of parallel applications when the problem size is scaled with the number of processors. It is particularly relevant in scientific simulations, where larger problems can be tackled as more processors become available. The law also guides the design of parallel algorithms that minimize the serial fraction, such as those using domain decomposition. In practice, achieving Gustafson's speedup requires that the parallel portion of the workload scales linearly with the number of processors, which is often true for grid-based computations. The law is also used in benchmarking, such as in the HPC Challenge benchmarks, to measure scaled speedup.
Gustafson's law is sometimes called the Gustafson–Barsis's law, acknowledging the contribution of his colleague Edwin Barsis. The original paper was published in the same issue as a response by Amdahl, who defended his own law. Gustafson's law has been extended to account for memory-bound and communication-bound workloads, leading to models like the roofline model. A common misconception is that Gustafson's law contradicts Amdahl's law; in fact, they address different scenarios: fixed-size vs. scaled-size problems. The law also has implications for energy efficiency, as scaling problem size can improve performance per watt. Gustafson later co-authored a book on the topic, and his work influenced the development of the Beowulf cluster approach to parallel computing.
Gustafson's law is a cornerstone of parallel computing theory, offering a more optimistic view than Amdahl's law when problem sizes scale with resources.
Help improve the encyclopedia. Reports go straight to the site manager.