Gustafson’s Law

Context and Motivation

Gustafson’s Law addresses a simple but important question in parallel computing: what happens if we use more processors not to finish the same problem faster, but to solve a larger or more detailed problem in the same amount of time?

While Amdahl’s Law focuses on the limit of speedup for a fixed-size problem, Gustafson’s Law considers scaling the problem size with the number of processors. This perspective is often more realistic in scientific and engineering work, where users naturally increase resolution, accuracy, or complexity when more computational power becomes available.

From Amdahl’s View to Gustafson’s View

In the surrounding chapters you have already seen the idea of speedup and strong versus weak scaling. Gustafson’s Law belongs in the weak scaling picture.

Assume we have a program where part of the work can be parallelized and part is inherently serial. Let the total execution time on $P$ processors be normalized to 1 unit. Let $s$ be the fraction of that time spent in the serial part on $P$ processors, and $1 - s$ the fraction in the parallel part on $P$ processors.

The key shift compared to Amdahl’s Law is that we treat $s$ and $1 - s$ as measured on the parallel machine itself, for the larger problem that fits in the same total time.

Deriving Gustafson’s Law

To see how Gustafson’s Law emerges, imagine a program that runs in time 1 on $P$ processors. The serial portion uses time $s$ and the parallel portion uses time $1 - s$ on these $P$ processors.

If we hypothetically ran the same scaled problem on a single processor, the serial part would still take $s$ units of time, but the parallel part, which ran in time $1 - s$ on $P$ processors, would need $P$ times longer on one processor. So the total time on one processor for this scaled problem would be
$$
T_1 = s + P(1 - s).
$$

The speedup, measured as "time on 1 processor" divided by "time on $P$ processors," is therefore
$$
S(P) = \frac{T_1}{T_P} = \frac{s + P(1 - s)}{1}.
$$

So Gustafson’s Law is usually written as
$$
\boxed{S(P) = s + P(1 - s)}
$$
or, using $\alpha$ for the serial fraction,
$$
\boxed{S(P) = \alpha + P(1 - \alpha)}.
$$

Note that if $s$ is small, the speedup grows approximately linearly with $P$.

Interpreting the Serial Fraction

The meaning of $s$ in Gustafson’s Law is subtle but important. In Amdahl’s Law, the serial fraction is defined based on a fixed reference problem size and the runtime on one processor. In Gustafson’s Law, $s$ is defined for the scaled problem that actually runs on $P$ processors in a fixed time.

This means that as you increase the number of processors and scale up the problem, the serial part often does not grow as quickly as the parallel part. As a result, the serial fraction $s$ can shrink, which allows nearly linear speedup for large enough problems.

However, Gustafson’s Law does not say that the serial part disappears. It only states that for larger workloads, the relative impact of a fixed or slowly growing serial portion can become small.

Weak Scaling and Gustafson’s Law

Gustafson’s Law is closely connected to weak scaling, where the amount of work per processor is kept roughly constant as $P$ grows. Under ideal weak scaling, if each processor has the same workload, the total problem size grows proportionally to $P$, but the runtime remains roughly the same.

Gustafson’s Law quantifies the potential benefit of this scenario. For a well-designed parallel program under weak scaling, if most of the time is spent in the portion that scales with $P$, then $s$ is small and the speedup grows almost linearly:
$$
S(P) \approx P \quad \text{when } s \ll 1.
$$

This is in contrast to strong scaling, which is the focus of Amdahl’s Law and which keeps the total problem size fixed when $P$ changes.

Comparing Predictions with Amdahl’s Law

Although you will see Amdahl’s Law in detail elsewhere, it is useful here to compare the forms side by side to understand what is unique to Gustafson’s view.

If we denote the serial fraction by $\alpha$, Amdahl’s Law is often written as
$$
S_{\text{Amdahl}}(P) = \frac{1}{\alpha + \frac{1 - \alpha}{P}}.
$$
This formula is pessimistic for large $P$ because even a modest serial fraction forces a hard upper limit on speedup.

Gustafson’s Law,
$$
S_{\text{Gustafson}}(P) = \alpha + P(1 - \alpha),
$$
is more optimistic when we allow the problem size to grow. Instead of predicting a strict cap, it predicts that speedup can continue to increase with $P$ as long as the serial fraction stays small for the scaled problem.

The key distinction is this: Amdahl describes what happens if the problem size is fixed. Gustafson describes what can happen if the problem size grows with $P$ but the runtime target stays fixed.

Simple Numerical Examples

To build intuition, consider a program where the serial fraction, measured on $P$ processors for the scaled problem, is $s = 0.05$.

For $P = 16$ processors, Gustafson’s Law gives
$$
S(16) = 0.05 + 16 \times 0.95 = 0.05 + 15.2 = 15.25.
$$
This is close to perfect linear speedup of 16.

If we increase to $P = 128$ processors and the serial fraction remains $s = 0.05$, then
$$
S(128) = 0.05 + 128 \times 0.95 = 0.05 + 121.6 = 121.65.
$$
Again, this is close to 128. This shows why, in practice, scaling up problem size can justify large parallel systems, provided that the serial fraction stays small.

In reality, as $P$ becomes very large, the serial fraction may increase due to algorithmic limitations or overheads such as communication and synchronization. When that happens the speedup will deviate from the ideal prediction.

Assumptions and Limitations

Gustafson’s Law is not a guarantee of performance. It rests on several assumptions that are important to understand when reasoning about real systems.

First, the law assumes that you can scale the problem size so that each processor gets a roughly constant amount of useful work. In some applications, such as certain real-time or fixed-resolution tasks, this is not possible.

Second, it treats the serial fraction $s$ as roughly constant as $P$ changes. In practice, larger processor counts often increase communication, synchronization, and I/O overheads, which means the effective serial or non-scaling portion can grow with $P$.

Third, the law assumes that the overhead of managing more processors stays small. On real clusters, startup costs, load imbalance, and network contention can limit scalability before the ideal speedup is reached.

Recognizing these assumptions helps you interpret Gustafson’s Law as a useful upper bound or design guideline rather than an exact prediction.

Practical Implications for HPC Applications

In many HPC domains, higher resolution, larger datasets, or more complex physics are always desirable. For example, climate models can use finer spatial grids, molecular simulations can include more atoms, and engineering simulations can use more detailed meshes. In such settings, Gustafson’s perspective is very natural: when more processors are available, users increase problem size instead of merely accelerating a fixed case.

From a practical standpoint, Gustafson’s Law encourages developers to design algorithms and implementations that keep the serial portion small for large workloads and many processes. It also motivates careful attention to communication and synchronization patterns, since these components effectively behave like serial or weakly scaling parts.

When you plan an HPC simulation, Gustafson’s Law suggests asking: if you had twice as many nodes, how could you double the problem size while keeping runtime similar? If the answer involves simply giving each process more independent work while only slightly increasing shared or serial work, then the application is a good candidate for large-scale parallelization.

Measuring the Serial Fraction on Real Systems

To apply Gustafson’s Law in practice, you need an estimate of the serial fraction $s$ for the scaled problem on $P$ processors.

One simple strategy is to profile the application on a given system and workload and measure how much of the runtime is spent in clearly serial code sections, for example, initialization, final I/O, or sequential algorithm parts, compared to parallel kernels that span many threads or processes.

If your profiled runtime on $P$ processors is
$$
T_P = T_{\text{serial}} + T_{\text{parallel}},
$$
you can compute
$$
s = \frac{T_{\text{serial}}}{T_P}.
$$
You can then plug this measured $s$ into
$$
S(P) = s + P(1 - s)
$$
to obtain an approximate upper bound on how well your code might scale under similar conditions.

Keep in mind that if you later increase $P$ and change the workload, $s$ can change. Repeating this measurement at multiple scales provides insight into where scalability problems start to appear.

Using Gustafson’s Law for Design and Expectations

Gustafson’s Law is primarily a way to shape expectations and guide design decisions in HPC software. It tells you that large-scale parallelism is worthwhile when:

The workload can grow proportionally with the number of processors.

The serial or poorly scaling part of the computation stays relatively small for these larger problems.

This perspective suggests some design goals. You want to maximize the portion of your algorithm that can be parallelized across many processes or threads. You want to minimize global synchronization and sequential bottlenecks. You want to ensure that data structures and communication patterns still scale gracefully as you add more nodes.

When you evaluate a parallel algorithm, you can ask how the serial fraction behaves as the problem and machine sizes grow together. If $s$ remains small, Gustafson’s Law indicates that you can continue to benefit from more processors and solve ever larger problems within acceptable time.