Scalability Laws
Learning Objectives
- You know of Amdahl’s Law and Gunther’s Universal Scalability Law.
- You can apply the laws to calculate the potential speedup from parallelization.
Vertical and horizontal scalability highlight classic strategies to scaling software. There are, however, theoretical limits on scaling.
Scalability laws are formulations of how the performance of a system changes as the resources change. Two classic formulations — Amdahl’s Law and Gunther’s Universal Scalability Law — outline that linear scalability is often impossible.
Amdahl’s Law
Amdahl’s Law posits that the speedup of a program using parallel computing is limited by the portion of the program that cannot be parallelized. It models the total execution time of a program as consisting of two parts: the fraction that is inherently sequential and cannot be parallelized, and the fraction that is parallelizable and can benefit from being executed across multiple workers.
Amdahl’s Law provides a formula for the maximum theoretical speedup achievable by parallelizing the parallelizable parts of a program, which diminishes as the number of workers increases due to the sequential portion dominating the total execution time.
The formula for Amdahl’s Law is as follows:
Where:
- is the speedup of the program when using workers (e.g. processors).
- is the proportion of the program that cannot be parallelized.
- is the number of workers to which the parallel work can be divided.
As an example, if we have a program where 20% of the work cannot be parallelized and 5 workers, the maximum theoretical speedup would be calculated as follows:
This means that there is a possibility to improve the execution time of the program by 178%, or, in other words, the execution time of the program could be reduced to approximately 36% of the original execution time ().
Similarly, if we would have a program where 95% of the work cannot be parallelized and 10 workers, the maximum theoretical speedup would be calculated as follows:
Here, there would be the possibility to improve the execution time of the program by slightly less than 5%, or, in other words, the execution time of the program could be reduced to approximately 95% of the original execution time (). Depending on the context, it is a good question whether the parallelization would be worth the effort.
For additional details, see: G. M. Amdahl, “Validity of the single processor approach to achieving large scale computing capabilities”. AFIPS spring joint computer conference. 1967.
Gunther’s Universal Scalability Law
Gunther’s Universal Scalability Law extends Amdahl’s Law by including communication overhead. It models the total execution time of a program as consisting of three parts: the fraction that is inherently sequential and cannot be parallelized, the fraction that is parallelizable, and the fraction that is communication overhead related to parallelization.
Note that we are intentionally simplifying the formulation of Gunther’s Universal Scalability Law here. Gunther’s Universal Scalability Law does not just discuss programs, but resources in general. In effect, it describes how the performance of a system changes as the number of users or resources changes.
The formula for Gunther’s Universal Scalability Law is as follows:
Where:
- is the improvement of the program when using workers.
- represents contention in the system (i.e., the proportion of the program that cannot be parallelized).
- represents coherency traffic (i.e., communication overhead).
As an example, if we would have a program where 20% of the work cannot be parallelized, 5 workers, and a 5% communication overhead, the maximum theoretical improvement would be calculated as follows:
That is, there would be the possibility to improve the execution time of the program by 150%, or, in other words, the execution time of the program could be reduced to approximately 40% of the original execution time. When compared to the calculation using Amdahl’s Law, the communication overhead has somewhat decreased the maximum theoretical improvement.
When we consider the case with 95% of the work that cannot be parallelized and 10 workers, where Amdahl’s Law would suggest a slight improvement, adding a 5% communication overhead leads to a decrease in performance:
Above, there would be no possibility to improve the execution time. Instead, the parallelization of the work would lead to a decrease in performance.
For additional details, see: (1) N. J. Gunther, A Simple Capacity Model of Massively Parallel Transaction Systems. CMG National Conference. 1993.; (2) http://www.perfdynamics.com/Manifesto/USLscalability.html.