Gustafson’s Law

Intuition Behind Gustafson’s Law

Amdahl’s Law assumes that the total problem size stays fixed as you increase the number of processors. This is useful for some questions, but in many realistic HPC scenarios you do increase the problem size when more resources are available (e.g., higher resolution, more time steps, larger datasets).

Gustafson’s Law starts from this different viewpoint:

• Keep the parallel execution time roughly constant (e.g., “I’m okay with my job taking 1 hour”).
• Ask: how much larger a problem can I solve in that same time when I have more processors?
• Measure speedup relative to a single-processor version of that larger problem.

So instead of “How much faster is my code for the same problem?”, we ask “How much more work can I do in the same time?” This often produces a much more optimistic and realistic view of parallel scalability for large-scale HPC workloads.

Formal Statement and Equation

Let:

• $P$ = number of processors.
• $\alpha$ = fraction of the total runtime (on the parallel machine) that is serial (non-parallelizable) work.
• $(1 - \alpha)$ = fraction of runtime that is parallel work.

Gustafson’s Law defines the scaled speedup $S_G$ as:

$$
S_G = P - \alpha (P - 1)
$$

You will often see it written equivalently as:

$$
S_G = \alpha + (1 - \alpha) P
$$

These two forms are algebraically identical:

• $\alpha$ fraction of time is serial → contributes speedup of $1$.
• $(1 - \alpha)$ fraction is parallel, running on $P$ processors → contributes speedup of $P$.

So the overall scaled speedup is a weighted sum of these contributions.

Comparing to Amdahl’s Law

Recall that Amdahl’s Law (fixed problem size) says:

$$
S_A = \frac{1}{\alpha + \frac{1 - \alpha}{P}}
$$

Key conceptual differences:

• Amdahl:
• Problem size is fixed.
• As $P$ increases, the speedup is limited by the serial fraction.
• Emphasizes the “ceiling” on speedup.
• Gustafson:
• Execution time is fixed, problem size grows with $P$.
• Focuses on how much more work can be done.
• Shows that large speedups are possible even with a non-trivial serial fraction, for sufficiently large $P$.

The same $\alpha$ can imply a modest speedup under Amdahl’s Law, but a much more encouraging scaled speedup under Gustafson’s Law when you scale the problem.

Deriving Gustafson’s Law (Conceptually)

Work with normalized time on the parallel system:

1. Assume the parallel runtime is normalized to 1 unit of time:
• Serial work time on the parallel machine: $\alpha$.
• Parallel work time on the parallel machine: $(1 - \alpha)$.
2. On a single processor, that same amount of work would take:
• Serial work: still $\alpha$ (no change).
• Parallel work: now cannot be divided across processors, so it takes $P$ times longer:
  $$
  P (1 - \alpha)
  $$
3. So the total single-processor time is:
   $$
   T_1 = \alpha + P (1 - \alpha)
   $$
4. The parallel time (on $P$ processors) is normalized to:
   $$
   T_P = 1
   $$
5. The scaled speedup is:
   $$
   S_G = \frac{T_1}{T_P} = \alpha + P (1 - \alpha)
   $$

Which is the Gustafson’s Law expression.

Numerical Examples

Example 1: Moderate serial fraction

Take:

• $P = 16$
• $\alpha = 0.1$ (10% serial, 90% parallel)

Gustafson’s Law:

$$
S_G = \alpha + (1 - \alpha) P = 0.1 + 0.9 \times 16 = 0.1 + 14.4 = 14.5
$$

Interpretation: With 16 processors, you can solve a problem about 14.5 times larger in the same time as the 1-processor version would need for that larger problem.

Compare to Amdahl’s Law for the same $\alpha$:

$$
S_A = \frac{1}{0.1 + \frac{0.9}{16}}
= \frac{1}{0.1 + 0.05625}
\approx 6.4
$$

• Fixed-size speedup is about 6.4×.
• Scaled speedup (bigger problem in same time) is about 14.5×.

Example 2: Small serial fraction, many processors

Let:

• $P = 1024$
• $\alpha = 0.01$ (1% serial)

Then:

$$
S_G = 0.01 + 0.99 \times 1024 \approx 0.01 + 1013.76 \approx 1013.77
$$

Even with 1% serial work, you can achieve a very large scaled speedup: you can use 1024 cores to handle a problem ~1000× larger in the same wall-clock time.

Interpretation in Real HPC Workloads

In many HPC applications (e.g., simulations, large-scale data analysis), practitioners do the following when more cores are available:

• Increase grid resolution in space or time.
• Increase the size of the dataset being analyzed.
• Extend the duration or complexity of the simulation.
• Add more physics or more detailed models.

All of these effectively increase the parallel portion of the workload while keeping the serial overhead (I/O, setup, global coordination) relatively small. This is exactly the scenario that Gustafson’s Law models: scaled problem sizes.

Implications:

• Large core counts are still very useful even when there is some sequential overhead.
• The key is to design problems and codes that scale the parallel work as resources increase.
• When planning and justifying new HPC systems, Gustafson’s perspective is often more realistic than Amdahl’s for scientific workloads.

Limitations and Assumptions

Although Gustafson’s Law is optimistic, it also relies on assumptions that can be violated in practice:

1. Serial fraction $\alpha$ remains small and does not grow with $P$
• In reality, some overheads (synchronization, communication, I/O) may increase with the number of processors.
• This can effectively increase the serial (or non-scalable) portion.
2. The problem can be meaningfully scaled
• Not all problems have a natural way to “just make them bigger” while still being scientifically or practically useful.
• Some applications genuinely care about fixed-size speedup.
3. Parallel work scales efficiently
• Gustafson’s formula does not explicitly model communication costs, load imbalance, or memory limits.
• In practice, these reduce the effective parallel fraction as $P$ grows.
4. Homogeneous processors and ideal scheduling
• The model assumes identical processors and perfect distribution of parallel work.
• Heterogeneous systems and real-world scheduling can degrade scalability.

Gustafson’s Law should therefore be seen as a best-case guideline for scaled problems rather than a strict prediction.

Practical Use in HPC Planning

In practical HPC discussions, Gustafson’s Law helps to:

• Argue that it is productive to invest in more cores, as long as:
• The code can use them effectively, and
• The scientific or industrial problem can be scaled.
• Encourage problem formulation and algorithm design that:
• Increase the parallel fraction $(1 - \alpha)$ with growing resources.
• Keep coordination and serial overheads from growing too fast.
• Frame performance goals as:
• “What problem size can I solve in 1 hour?” instead of
• “How fast can I solve this fixed small test case?”

When you perform scaling studies, Gustafson’s viewpoint corresponds to weak scaling behavior: keeping runtime (or runtime per unit of work) approximately constant while increasing problem size and resources together.

Relationship to Other Parallel Concepts

Within the broader context of parallel computing concepts:

• Strong scaling: aligns more with Amdahl’s Law (fixed problem size).
• Weak scaling: aligns more with Gustafson’s Law (growing problem size).
• Load balancing and overheads: in practice, change the effective value of $\alpha$ and can reduce the real-world speedup compared to the ideal Gustafson prediction.

Gustafson’s Law provides the theoretical optimistic limit of what weak scaling can achieve under ideal conditions, assuming the serial fraction stays small and overheads are controlled.