Amdahl’s Law vs Gustafson’s Law: Understanding the Limits of Parallel Speedup

How much faster can a program become when more CPU cores are added?

It is tempting to assume that if one processor can execute a program in a certain amount of time, adding 100 processors should make it roughly 100 times faster. In practice, that is rarely the case. The reason lies in how much of a program can actually be executed in parallel.

As part of my SE3082 Parallel Computing module at SLIIT, I created an analytical video exploring this problem through two fundamental principles of parallel computing: Amdahl’s Law and Gustafson’s Law.

Starting with the Speedup Problem

A parallel program can generally be divided into two parts: work that can be executed concurrently and work that must remain sequential.

This distinction becomes important when increasing the number of processors. While the parallel portion can benefit from additional cores, the sequential portion still has to be executed by a single processor. As a result, the sequential component becomes a limiting factor on the overall speedup.

This is the problem addressed by Amdahl’s Law.

For a program where the fraction of work that can be parallelized is P, and the program runs on N processors, Amdahl's Law gives the theoretical speedup as:

$$S(N) = \frac{1}{(1-P)+\frac{P}{N}}$$

The equation captures an important limitation: increasing the processor count cannot eliminate the sequential portion of the workload.

A Simple Example

To make the concept more concrete, I used an example where 80% of the workload is parallelizable and 20% is sequential.

With four processors:

$$S(4) = \frac{1}{0.2+\frac{0.8}{4}}$$

which gives:

$$S(4) = 2.5$$

So, even though four processors are available, the program achieves only a 2.5× speedup, rather than the ideal 4×.

The effect becomes even clearer as the processor count increases. If we theoretically had an unlimited number of processors, the parallel portion could approach zero execution time, but the 20% sequential portion would remain.

Therefore:

$$S_{\max} = \frac{1}{1-P} = \frac{1}{0.2} = 5$$

Under these assumptions, the maximum theoretical speedup is 5×, regardless of how many processors are added.

This demonstrates one of the fundamental challenges in parallel computing: parallel hardware cannot compensate for work that cannot be parallelized.

But Is That the Whole Story?

This is where Gustafson’s Law provides a different perspective.

Amdahl’s Law assumes that we are trying to solve the same problem faster by adding processors. This is commonly associated with strong scaling.

But many real world high performance computing workloads do not remain fixed as more computational resources become available. Instead, we may use additional processors to solve a larger problem within a reasonable amount of time.

This is the perspective behind weak scaling and Gustafson’s Law.

Gustafson's Law can be expressed as:

$$S(N) = N-(1-P)(N-1)$$

Rather than asking how quickly the same workload can be completed, it considers how much larger a workload can be handled as more processors are introduced.

For example, using the same 80% parallel workload and four processors:

$$S(4) = 4-(0.2)(4-1)$$ $$S(4) = 3.4$$

This produces a 3.4× scaled speedup.

The difference is subtle but important. The two laws are not simply competing formulas giving different answers to the same question. They model different ways of thinking about scalability.

Amdahl vs Gustafson

The distinction can be summarized as two different questions:

Amdahl’s Law: How much faster can I solve the same problem?

Gustafson’s Law: How much larger a problem can I solve using more processors?

Amdahl's Law is particularly useful when the workload size is fixed and the goal is to reduce execution time. It highlights the impact of sequential bottlenecks and demonstrates why simply adding processors eventually produces diminishing returns.

Gustafson's Law is more representative of situations where the workload can grow with the available computing resources. In these cases, additional processors can allow us to tackle problems that would otherwise be impractical to process within a reasonable timeframe.

Why This Matters

These principles become especially relevant in high performance computing (HPC), where applications may run across large numbers of CPU cores or nodes.

Applications such as scientific simulations, numerical modelling, large scale data processing, and other computationally intensive workloads can involve enormous amounts of parallel work. In such environments, understanding scalability is essential when deciding whether additional computational resources will translate into meaningful performance improvements.

The important lesson is that processor count alone does not determine performance.

The structure of the algorithm matters. The amount of sequential work matters. The size of the workload matters. Communication and coordination overhead can also become significant as systems scale.

Creating the Video

Creating this video gave me an opportunity to approach the topic from a different perspective than simply studying it for the module.

I had to break down the concepts, work through the numerical examples, compare the assumptions behind the two laws, and present the distinction in a way that could be understood without losing the technical reasoning behind it.

That process helped me develop a clearer understanding of why parallel speedup is not simply a matter of adding more cores. It also reinforced the importance of considering both algorithmic parallelism and workload characteristics when evaluating parallel systems.

Ultimately, Amdahl's Law and Gustafson's Law provide two complementary ways of thinking about scalability. One emphasizes the limitations of accelerating a fixed workload, while the other shows the potential of using additional resources to address larger workloads.

That distinction is fundamental to understanding why parallel computing can deliver significant performance gains, while also showing why more cores do not automatically mean proportionally more speed.