Predicting Parallel Speedup: Amdahl's and Gustafson's Laws

1. Speedup: The Ideal vs. The Reality

The primary goal of parallel computing is to solve a problem faster. We measure this improvement using speedup, defined as the ratio of the execution time on a single processor to the execution time on multiple processors:

$S_p=\frac{T_1}{T_p}$

Where $T_1$ is the sequential execution time and $T_p$ is the parallel execution time on $p$ processors.

Ideally, if we use $p$ processors, we might expect the program to run $p$ times faster, achieving linear speedup ($S_p=p$). However, reality is more complex. Most programs contain portions that are inherently sequential—such as reading a file, initializing data structures, or parts of an algorithm that depend on previous steps. This unparallelizable part of the code becomes a bottleneck, a concept formalized by Amdahl's Law.

The following video provides an excellent introduction, starting with the ideal case and then explaining why the presence of serial code fundamentally limits potential speedup.

2. Amdahl's Law: The Law of Diminishing Returns

As you just saw, Amdahl's Law provides a model for the speedup of a program with a fixed workload. It considers that a program is composed of a serial fraction ($f$) and a parallelizable fraction ($1-f$).

The formula for Amdahl's Law is:

$S_p\le \frac{1}{f+\frac{1-f}{p}}$

Here:

• $f$ is the fraction of the program's original execution time that is sequential.
• $p$ is the number of processors.

A crucial insight from Amdahl's Law comes from considering the limit as the number of processors becomes infinite ($p\to \infty$). The term $\frac{1-f}{p}$ goes to zero, leaving:

$S_{\infty }\le \frac{1}{f}$

This means that if 20% of your program is serial ($f=0.2$), the maximum possible speedup you can ever achieve is $1/0.2=5\times$, no matter how many processors you throw at the problem. The serial part becomes the ultimate bottleneck.

This next video offers a concise, formal presentation of the law and visualizes this limiting behavior.

Practice Problem: Applying Amdahl's Law

Let's work through a typical problem. Here, we'll use the law to determine the minimum number of processors in a machine given its performance.

Let's break down the solution:

1. Identify Knowns:
   • Parallelizable work = 75%, so the non-parallelizable (serial) fraction $f=1-0.75=0.25$.
   • Sequential runtime $T_1=4$ hours.
   • Parallel runtime $T_p=2$ hours.
2. Calculate Actual Speedup:
   • The measured speedup is $S_p=T_1/T_p=4/2=2$.
3. Apply Amdahl's Law:
   • We know the actual speedup (2) must be less than or equal to the theoretical maximum predicted by the formula.
   • $2\le \frac{1}{0.25+\frac{1-0.25}{p}}$
   • $2\le \frac{1}{0.25+\frac{0.75}{p}}$
4. Solve for p:
   • Your background in mathematics makes this kind of algebraic manipulation straightforward. We need to solve the inequality for $p$.
   • $2\left(0.25+\frac{0.75}{p}\right)\le 1$
   • $0.5+\frac{1.5}{p}\le 1$
   • $\frac{1.5}{p}\le 0.5$
   • $1.5\le 0.5p$
   • $3\le p$
     The machine must have at least 3 processors.

3. Gustafson's Law: A Scaled Perspective

Amdahl's Law paints a somewhat pessimistic picture, suggesting that speedup is strictly limited. However, its assumption of a fixed problem size doesn't always hold. Often, with more processors, we want to solve a bigger problem (e.g., higher resolution simulation, larger dataset) in the same amount of time.

This is the premise of Gustafson's Law, which models scaled speedup. It assumes the parallel part of the workload scales with the number of processors, while the serial part remains fixed.

The formula is:

$S_p=f+p(1-f)=p-f(p-1)$

Here, $f$ has a slightly different meaning: it's the fraction of execution time spent in the serial part of the parallel execution. Under this model, speedup grows almost linearly with $p$.

Practice Problem: Applying Gustafson's Law

Let's solve a problem using this new law. Notice the calculation is a direct equality.

As the resource shows, with $f=0.2$ and $p=11$:

• $S_{11}=f+p(1-f)$
• $S_{11}=0.2+11(1-0.2)=0.2+11(0.8)=0.2+8.8=9$
  The scaled speedup is 9.

4. Comparing the Laws and Solving More Problems

The key difference lies in the assumptions:

• Amdahl's Law: Fixed workload. Answers: "How much faster will my program run?"
• Gustafson's Law: Scaled workload (fixed time). Answers: "How much more work can my program do?"

This next resource provides a fantastic, formal explanation of this difference.

The following plot visually captures this fundamental difference. Amdahl's Law shows speedup flattening towards an asymptote, while Gustafson's Law shows a nearly linear increase.

Advanced Problem Solving

Let's tackle two more complex problems to solidify your understanding.

A. Finding the Serial Fraction

Sometimes you know the speedup and need to deduce the serial fraction.
Let's use the problem from Task 3b in the ETH Zurich PDF (LINK):

• Question: A program shows a speedup of 3 on 4 cores. What is the serial fraction f according to Amdahl's Law?

• Solution:

  1. Start with Amdahl's formula: $S_p=\frac{1}{f+\frac{1-f}{p}}$
  2. Substitute known values: $p=4$, $S_p=3$.
     $3=\frac{1}{f+\frac{1-f}{4}}$
  3. Solve for $f$:
     $3\left(f+\frac{1-f}{4}\right)=1$
     To clear the fraction, multiply the terms in the parenthesis by 4:
     $3\left(\frac{4f+(1-f)}{4}\right)=1$
     $3\left(\frac{3f+1}{4}\right)=1$
     $\frac{9f+3}{4}=1$
     $9f+3=4$
     $9f=1⟹f=\frac{1}{9}$
     The serial fraction of the program is approximately 11.1%.

B. Combining Speedup with System Parameters

Real-world performance depends on more than just processor count. This next problem integrates CPU frequency, another key parameter.

Let's review the logic. To compare the two machines against the baseline (1 processor at 1 GHz), we need a total performance factor that combines parallel speedup and frequency improvement.

• Serial Fraction: $f=0.5$
• Baseline: 1 processor, 1 GHz frequency.

Machine A (2 processors, 3 GHz):

1. Parallel Speedup (Amdahl):
   $S_{pA}=\frac{1}{0.5+\frac{1-0.5}{2}}=\frac{1}{0.5+0.25}=\frac{1}{0.75}=\frac{4}{3}$
2. Frequency Speedup: $3\text{ GHz}/1\text{ GHz}=3\times$
3. Overall Performance Factor: $S_{pA}\times (\text{Freq. Speedup})=\frac{4}{3}\times 3=4$

Machine B (5 processors, 2 GHz):

1. Parallel Speedup (Amdahl):
   $S_{pB}=\frac{1}{0.5+\frac{1-0.5}{5}}=\frac{1}{0.5+0.1}=\frac{1}{0.6}=\frac{10}{6}=\frac{5}{3}$
2. Frequency Speedup: $2\text{ GHz}/1\text{ GHz}=2\times$
3. Overall Performance Factor: $S_{pB}\times (\text{Freq. Speedup})=\frac{5}{3}\times 2=\frac{10}{3}\approx 3.33$

Conclusion: Since $4>3.33$, Machine A will run the program faster, even though it has fewer cores. Its higher clock frequency more than compensates for its lower parallel speedup.

Conclusion

In this lesson, we explored two fundamental models for predicting parallel performance. You learned how to apply their formulas to solve numerical problems, a key skill for analyzing scalable systems.

Key Takeaways:

• Amdahl's Law models speedup for a fixed-size problem and shows that performance is ultimately limited by the serial fraction ($S_{\infty }\le 1/f$).
• Gustafson's Law models speedup for a problem that scales with processors (scaled speedup) and provides a more optimistic view of parallel performance ($S_p=p-f(p-1)$).
• Choosing the correct law depends on the problem's context: are you trying to solve the same problem faster (Amdahl) or solve a bigger problem in the same amount of time (Gustafson)?
• Real-world performance analysis often requires combining these models with other system parameters, like CPU frequency.

In our next lesson, we will move from these high-level theoretical models to the nitty-gritty of code. You will learn to analyze C++ code fragments to identify data dependencies, race conditions, and performance bottlenecks—the very issues that create the "serial fraction" we've been modeling today.