Scalability Laws

Although horizontal and vertical scaling can be used to scale applications, there are basic concerns that need to be taken account when scaling applications. There are two classic formulations -- or laws -- that discuss scaling, effectively outlining that linear scalability is often impossible.

Amdahl's Law

Amdahl's Law posits that programs have parts that can be parallelized and parts that cannot be parallelized. The total execution time of a program is the sum of the execution time of the parts that can be parallelized and the parts that cannot be parallelized. Through identification of parts that cannot be parallelized and parts that can be parallelized, Amdahl's Law can be used to determine a maximum theoretical improvement in program execution time when parallelizable parts are parallelized over a number of workers.

Improvement = N / (1 + p(N - 1))

The formula for Amdahl's Law is outlined above. The p refers to the proportion of the program that cannot be parallelized and N refers to the number of workers to which the parallel work can be divided to.

As an example, if we would have a program where 20% of the work cannot be parallelized and 5 workers, the maximum theoretical improvement would be calculated as follows.

Improvement = 5 / (1 + 0.2 * (5 - 1))

Improvement = 5 / (1 + 0.8)

Improvement = 5 / 1.8

Improvement ~ 2.778

That is, there would be the possibility to improve the execution time of the program by 177.8%.

On the other hand, if we would have a program where 95% of the work cannot be parallelized and 10 workers, the maximum theoretical improvement would be calculated as follows.

Improvement = 10 / (1 + 0.95 * (10 - 1))

Improvement = 10 / (1 + 8.55)

Improvement = 10 / 9.55

Improvement ~ 1.047

Here, there would be the possibility to improve the execution time of the program by 4.7%.

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

Amdahl's Law does not account for communication between the workers (e.g. synchronization of tasks), however, which Gunther's Universal Scalability Law adds.

Improvement = N / (1 + p(N - 1) + pyN(N - 1))

The formula for Gunther's Universal Scalability Law is outlined above. Similar to Amdahl's Law, p refers to the proportion of the program that cannot be parallelized, and N refers to the number of workers to which the parallel work can be divided. The y refers to a communication overhead (e.g. using shared data, invalidating caches, etc).

Despite our above formulation, 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.

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.

Improvement = 5 / (1 + (0.2 * (5 - 1)) + (0.2 * 0.05 * 5 * (5 - 1)))

Improvement = 5 / (1 + (0.8) + (0.2 * 0.05 * 5 * (5 - 1)))

Improvement = 5 / (1 + (0.8) + (0.2))

Improvement = 5 / 2

Improvement ~ 2.5

That is, there would be the possibility to improve the execution time of the program by 150%.

Similarly, if we would have a program where 95% of the work cannot be parallelized, 10 workers, and 5% communication overhead, the maximum theoretical improvement would be calculated as follows.

Improvement = 10 / (1 + (0.95 * (10 - 1)) + (0.95 * 0.05 * 10 * (10 - 1)))

Improvement = 10 / (1 + (8.55) + (4.275))

Improvement = 10 / 13.825

Improvement ~ 0.723

That is, 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.

Key takeaway

The key takeaway with the scalability laws is that they remind us that scalability is not linear. There are parts in programs that cannot be parallelized, and when there are parts that can be parallelized, there is often communication overhead related to parallelization. In essence, the laws also remind us that parallelization is not always an answer: Parallelization of a system with high communication overhead and a high proportion of parts that cannot be parallelized can lead to a decrease in performance when compared to a setup without parallelization.