Analyzing Scaled Speedup with Gustafson's Law

1. A New Perspective: Strong vs. Weak Scaling

The core difference between Amdahl's and Gustafson's views lies in their assumptions about the problem itself as you add more processors.

• Strong Scaling (Amdahl's Law): The total problem size is constant. The goal is to reduce the execution time. You use more processors to solve the same problem, faster.
• Weak Scaling (Gustafson's Law): The execution time is held constant. The goal is to solve a larger problem. You use more processors to do more work in the same amount of time.

Consider a practical engineering scenario, like running a complex fluid dynamics simulation.

• A strong scaling approach would be to use a 16-core workstation to make your existing simulation finish in one hour instead of eight.
• A weak scaling approach would be to use that 16-core workstation to run a simulation with 16 times the data points or a much finer-grained mesh, with the expectation that it will still finish in about eight hours—but yield a far more accurate result.

This shift from "time-constrained" to "problem-size-constrained" thinking is fundamental to high-performance computing (HPC) and big data analysis.

To solidify this distinction, please read the following brief article which frames the two laws and their application contexts.

2. Deriving Gustafson's Law

Let's formalize the idea of weak scaling into a mathematical law. The derivation starts by defining the workload in terms of its serial and parallel components, but with the assumption that the parallel part grows with the number of processors.

Let's define the components of our program's execution time on a single processor:

• Let $s$ be the fraction of time spent on the serial part.
• Let $p$ be the fraction of time spent on the parallelizable part.
• The total normalized time on one processor is $T_1=s+p=1$.

Now, under Gustafson's weak scaling model, we assume the total parallel workload scales linearly with the number of processors, $P$.

1. Scaled Workload: The total work for our scaled-up problem, if it were to run on a single processor, would be $W_{scaled}=s+p\times P$. The serial part remains the same size, but the parallel part has been increased $P$-fold.

2. Execution Time on P Processors: How long does it take to run this scaled workload on $P$ processors?

   • The serial part, $s$, must still run on a single core, so it takes time $s$.
   • The scaled parallel part, $p\times P$, can be perfectly divided among the $P$ processors, so it takes time $\frac{p\times P}{P}=p$.
   • Thus, the total time on $P$ processors, $T_P$, is simply $s+p$. Since we normalized the original single-core time to 1, the execution time remains constant: $T_P=1$.

3. Scaled Speedup: The scaled speedup, $S_{scaled}(P)$, is the ratio of the total scaled workload to the execution time on $P$ processors.

   $$S_{scaled}(P)=\frac{\text{Total Scaled Workload}}{\text{Execution Time on P Processors}}=\frac{s+p\times P}{s+p}$$

   Since $s+p=1$, this simplifies to:

   $$S_{scaled}(P)=s+p\times P$$

   And because $p=1-s$, the formula is often written as:

   $$S_{scaled}(P)=s+(1-s)P=P-(P-1)s$$

This is Gustafson's Law. It states that the scaled speedup grows linearly with the number of processors, with a slope determined by the parallel fraction $(1-s)$.

3. Applying Gustafson's Law: A Worked Example

Let's return to our practice problem from the previous lesson, where a program has a serial fraction $s=0.05$ (i.e., it's 95% parallelizable).

Problem:
You have a program with a 5% serial fraction. You are moving from a single-core machine to a 16-core workstation. According to Gustafson's Law, what is the scaled speedup you can expect?

Solution:
Here, $s=0.05$ and $P=16$.

Interpretation:
This result means that by using 16 cores, you can solve a problem that is 15.25 times larger in the same amount of time it took to solve the original problem on a single core.

Compare this to the Amdahl's Law result for the same program: the strong scaling speedup was only $\approx 9.14x$. Gustafson's Law presents a much more optimistic and often more relevant picture for large-scale systems.

The following video provides another walk-through of the law's formulation and its optimistic conclusions.

4. Amdahl vs. Gustafson: A Side-by-Side Comparison

The difference between the two laws is striking. Let's visualize it. The table below, taken from a lecture on scaling, compares the theoretical speedups predicted by both laws for a program with a 10% serial fraction ($s=0.1$).

As you can see from the table, while Amdahl's Law shows speedup quickly saturating (approaching a limit of $1/s=1/0.1=10x$), Gustafson's Law shows speedup continuing to grow almost linearly with the number of processors.

This reflects a common experience in fields that use supercomputers: bigger machines are used to enable bigger, more complex problems (e.g., higher-resolution weather models, training larger neural networks), not just to get results for old problems faster.

5. Practical Relevance in Modern Computing

Gustafson's Law is not just a theoretical curiosity; it's a guiding principle in many areas of scalable computing. Adding more resources (like GPUs) is often done with the intention of increasing the workload to achieve better results or higher throughput.

These examples show that in practice, practitioners often "think in Gustafson's terms" by scaling up the workload to match the available hardware, thereby keeping the parallel processors busy and achieving nearly linear gains in throughput or problem complexity.

Conclusion

In this lesson, we introduced a new lens through which to view parallel performance. By shifting our goal from solving a fixed problem faster to solving a larger problem in the same amount of time, we unlocked a much more optimistic model for scalability.

Key Takeaways:

• Gustafson's Law describes weak scaling, where the problem size grows with the number of processors to keep the execution time constant.
• The formula for scaled speedup is $S_{scaled}(P)=s+(1-s)P$, where $s$ is the serial fraction and $P$ is the number of processors.
• Unlike Amdahl's Law, which is limited by $1/s$, Gustafson's Law predicts that speedup can grow linearly with the number of processors.
• This law is highly relevant in domains like HPC, AI, and big data, where more computational power is often used to tackle bigger, more complex problems.

Preview of the Next Lesson

We have now formally defined two types of scaling: strong scaling (Amdahl) and weak scaling (Gustafson). In our next lesson, we will build on this by defining metrics to measure how well a program actually achieves these theoretical ideals. We will introduce the concept of parallel efficiency and formally distinguish between strong and weak scalability analysis.