Amdahl's Law and Gustafson's Law

Core Concepts

Why These Laws Matter

Performance scaling is the central challenge of modern computing. We can't make single cores much faster (heat, power limits), so we add more cores. But does 8 cores give you 8× performance? These laws answer when and why not.

The Setup:

• You have some computation taking time $T$
• A fraction $f$ of it is inherently serial (cannot be parallelized)
• The rest $(1-f)$ is perfectly parallelizable
• You have $n$ processors

Amdahl's Law: Fixed Workload Perspective

Derivation from First Principles:

Let's start with the total execution time $T_1$ on one processor.

Step 1: Break down the work

• Serial portion takes: $T_{\text{serial}} = f \cdot T_1$
• Parallel portion takes: $T_{\text{parallel}} = (1-f) \cdot T_1$

Why this step? We're partitioning the total work into two categories based on whether it can be parallelized. The serial fraction $f$ is a proportion, so $f \cdot T_1$ gives us the actual time.

Step 2: Time on $n$ processors

With $n$ processors:

• Serial part still takes $f \cdot T_1$ (cannot be split!)
• Parallel part now takes $\frac{(1-f) \cdot T_1}{n}$ (perfect division)

Why this step? The serial work is fundamentally sequential—throwing more processors at it doesn't help. The parallel work divides evenly (ideal assumption).

$T_n = f \cdot T_1 + \frac{(1-f) \cdot T_1}{n}$

Step 3: Define speedup

Speedup is the ratio of single-processor time to multi-processor time:

$S(n) = \frac{T_1}{T_n} = \frac{T_1}{f \cdot T_1 + \frac{(1-f) \cdot T_1}{n}}$

Why this step? Speedup measures "how much faster." If $S(n) = 4$, you're 4× faster.

Step 4: Simplify

Factor out $T_1$:

$S(n) = \frac{1}{f + \frac{1-f}{n}}$

Why this step? The original time cancels out—speedup depends only on the fraction $f$, not absolute time.

What this means: If even 10% of your code is serial ($f = 0.1$), the best speedup you can ever achieve is $1/0.1 = 10×$, even with a million cores!

Gustafson's Law: Scaled Workload Perspective

Derivation from First Principles:

The conceptual flip: instead of asking "how fast can I run the same task," ask "how much more work can I do in the same time?"

Step 1: Time on $n$ processors (our reference)

With $n$ processors, we complete some workload in time $T_n$:

• Serial part: $T_{\text{serial}} = f \cdot T_n$
• Parallel part: $T_{\text{parallel}} = (1-f) \cdot T_n$

Why this step? We're measuring in terms of the parallel runtime, not the hypothetical single-core time.

Step 2: Equivalent work on 1 processor

If we ran this same amount of work on 1 processor:

• Serial part: still $f \cdot T_n$ (unchanged)
• Parallel part: $n \cdot (1-f) \cdot T_n$ (we did $n$ times as much parallel work!)

Why this step? The parallel work was distributed across $n$ cores. To do it serially would take $n$ times longer.

$T_1 = f \cdot T_n + n(1-f) \cdot T_n = T_n[f + n(1-f)]$

Step 3: Calculate speedup

$S(n) = \frac{T_1}{T_n} = \frac{T_n[f + n(1-f)]}{T_n} = f + n(1-f)$

Rearrange:

$S(n) = f + n - nf = n - f(n-1)$

Key Differences: When to Use Which Law

Connections to Other Topics

• Parallel Architectures: These laws inform why multicore CPUs exist and their limits
• GPU Computing: GPUs exploit Gustafson—scale problem size to thousands of cores
• Load Balancing: Minimizing $f$ by distributing serial work cleverly
• Cache Coherence: Coherence protocols add overhead that increases effective $f$
• Thread Synchronization: Locks and barriers are the primary sources of serial bottleneck
• Scalability Analysis: Strong scaling (Amdahl) vs weak scaling (Gustafson)
• Performance Metrics: Speedup, efficiency, and how to measure them

Practice Problems (Active Recall)

#flashcards/hardware

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)