Amdahl's Law: Calculating Theoretical Speedup

The Ideal vs. The Reality of Speedup

Imagine you have a task that takes 100 seconds to run on a single processor. Ideally, if you could use 10 processors, you might expect the task to finish in 10 seconds—a 10x speedup. If you had 100 processors, you might hope for it to finish in 1 second—a 100x speedup. This concept is known as linear speedup.

The critical insight, as the video explains, is that virtually no non-trivial program is 100% parallelizable. Most programs consist of:

• A serial portion: Code that must be executed sequentially, one instruction after another. This can include tasks like initialization, reading configuration files, or final result aggregation.
• A parallel portion: Code that can be divided among multiple processors or SIMD lanes, such as processing the pixels of an image or updating the elements of a large matrix.

No matter how many processors you throw at the parallel portion, the serial portion's execution time remains a fixed bottleneck. This is the essence of Amdahl's Law.

Formulating Amdahl's Law

Let's formalize this intuition. We can derive the law by thinking about the total execution time of a program before and after an enhancement. We'll use the following variables:

• $f$: The fraction of the program's original execution time that can be parallelized or enhanced. This value is between 0 and 1.
• $1-f$: The fraction of the program's execution time that is inherently serial and cannot be enhanced.
• $s$: The speedup factor for the enhanced portion. For example, if we make the parallel part run on 8 processors, $s=8$.

As explained in the video, we can express the overall speedup as the ratio of the old execution time to the new execution time.

1. Old Execution Time: Let's normalize the total time before any improvements to 1 unit.

   $$T_{\text{old}}=1$$

2. New Execution Time: The new time is the sum of the time for the serial part (which doesn't change) and the time for the enhanced parallel part.

   • Time for the serial part = $1-f$
   • Time for the enhanced part = $\frac{f}{s}$ (The original time $f$ divided by its speedup factor $s$)

   So, the total new execution time is:

   $$T_{\text{new}}=(1-f)+\frac{f}{s}$$

3. Overall Speedup: The overall speedup, $S_{\text{overall}}$, is the ratio $T_{\text{old}}/T_{\text{new}}$.

   $$S_{\text{overall}}=\frac{1}{(1-f)+\frac{f}{s}}$$

This is Amdahl's Law. It elegantly captures the relationship between the parallelizable fraction of a task, the improvement applied to that fraction, and the resulting overall system speedup.

The Law of Diminishing Returns

Let's apply the formula to build your intuition. Suppose you optimize a part of your code that accounts for 80% of the execution time ($f=0.8$). You use 4 processors to make this part 4 times faster ($s=4$).

Even though you made 80% of the code 4 times faster, your overall speedup is only 2.5x, not 4x. The remaining 20% of serial code holds you back.

What if you use an infinite number of processors ($s\to \infty$)? The term $\frac{f}{s}$ goes to zero.

For our example where $f=0.8$, the maximum possible speedup is:

This is a profound result. Even with infinite processors, a program that is 80% parallel can never be more than 5 times faster. The 20% serial portion creates a hard ceiling on performance.

The graph below, based on Amdahl's Law, visualizes this effect. Notice how for any parallelizable fraction less than 100%, the speedup curve flattens out, approaching a horizontal asymptote defined by $1/(1-f)$.

Solving Problems with Amdahl's Law

As a performance engineer, you'll often use Amdahl's Law to reason about potential optimizations. For instance, you might need to determine how much of a program must be parallelized to meet a performance target.

Let's work through an example of our own, relevant to your AI goals.

Scenario: You are optimizing an AI inference pipeline. Profiling shows that 95% of the time is spent in a large matrix multiplication (GEMM) kernel, which is highly parallelizable. The remaining 5% is spent in serial setup and file I/O.

Question: What is the overall speedup if you run the GEMM kernel on a GPU that makes it 64 times faster?

• Identify variables:

  • The fraction that can be enhanced, $f=0.95$.
  • The speedup of the enhancement, $s=64$.

• Apply Amdahl's Law:

  $$S_{\text{overall}}=\frac{1}{(1-0.95)+\frac{0.95}{64}}=\frac{1}{0.05+0.01484}=\frac{1}{0.06484}\approx 15.42$$

Conclusion: Even though the core GEMM operation is 64 times faster, the overall pipeline speedup is only about 15.4x. The 5% serial portion dramatically limits the end-to-end gain. This illustrates why optimizing the entire system, including data loading and preprocessing, is critical in real-world applications.

Now, consider the maximum theoretical speedup for this pipeline:

No matter how powerful the GPU, this pipeline can never be more than 20 times faster than the original, single-processor version, unless you also reduce the 5% serial portion.

Conclusion

In this lesson, we have formalized the intuition that serial bottlenecks limit parallel performance. Amdahl's Law gives us the tool to quantify this limit precisely. As someone aiming for a career in low-level optimization, this law is not just an academic formula; it's a guiding principle for your work. It teaches you to be a detective, to use profilers to find the parts of a program where your optimization efforts will yield the greatest returns—the parts with the largest $f$.

Key Takeaways:

• Amdahl's Law states that the maximum speedup from an improvement is limited by the fraction of time that the improvement can be used.
• The formula is $S_{\text{overall}}=\frac{1}{(1-f)+\frac{f}{s}}$, where $f$ is the parallelizable fraction and $s$ is the speedup of that fraction.
• The performance of any program is ultimately constrained by its serial portion.
• The theoretical maximum speedup with infinite processors is $S_{\text{max}}=\frac{1}{1-f}$.
• This principle dictates that performance engineers must focus on optimizing the "common case"—the parts of the program that consume the most time.

We have now examined parallelism on a CPU (ILP, SIMD) and the theoretical bounds of that parallelism (Amdahl's Law). But GPUs are the kings of parallelism in AI. What makes their design so different from CPUs? In our next lesson, we will explore the fundamental design philosophies that distinguish latency-oriented CPUs from throughput-oriented GPUs, setting the stage for our deep dive into modern GPU architecture.