Amdahl's Law and Gustafson's Law

6.1.3 · Hardware › Parallelism & Multicore

Core Concepts

Why These Laws Matter

Performance scaling modern computing ka central challenge hai. Hum single cores ko bahut zyada fast nahi bana sakte (heat, power limits), isliye hum zyada cores add karte hain. Lekin kya 8 cores tumhe 8× performance deta hai? Ye laws jawab dete hain kab aur kyun nahi.

The Setup:

• Tumhare paas koi computation hai jo time $T$ leta hai
• Uska ek fraction $f$ inherently serial hai (parallelize nahi ho sakta)
• Baaki $(1-f)$ perfectly parallelizable hai
• Tumhare paas $n$ processors hain

Amdahl's Law: Fixed Workload Perspective

Derivation from First Principles:

Chalo total execution time $T_1$ se shuru karte hain ek processor par.

Step 1: Kaam ko tod do

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

Ye step kyun? Hum total kaam ko do categories mein partition kar rahe hain—parallelize ho sakta hai ya nahi. Serial fraction $f$ ek proportion hai, isliye $f\cdot T_1$ actual time deta hai.

Step 2: $n$ processors par time

$n$ processors ke saath:

• Serial part phir bhi $f\cdot T_1$ leta hai (split nahi ho sakta!)
• Parallel part ab $\frac{(1-f)\cdot T_1}{n}$ leta hai (perfect division)

Ye step kyun? Serial kaam fundamentally sequential hai—uspe zyada processors lagane se koi faayda nahi. Parallel kaam evenly divide hota hai (ideal assumption).

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

Step 3: Speedup define karo

Speedup single-processor time aur multi-processor time ka ratio hai:

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

Ye step kyun? Speedup measure karta hai "kitna fast." Agar $S(n)=4$, toh tum 4× fast ho.

Step 4: Simplify karo

$T_1$ factor out karo:

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

Ye step kyun? Original time cancel ho jata hai—speedup sirf fraction $f$ par depend karta hai, absolute time par nahi.

Iska matlab: Agar tumhare code ka sirf 10% bhi serial hai ($f=0.1$), toh best speedup jo tum kabhi bhi achieve kar sakte ho woh hai $1/0.1=10\times$, chahe ek million cores ho!

Gustafson's Law: Scaled Workload Perspective

Derivation from First Principles:

Conceptual flip: "main same task kitni fast run kar sakta hoon" ki jagah poochho "main same time mein kitna zyada kaam kar sakta hoon?"

Step 1: $n$ processors par time (hamara reference)

$n$ processors ke saath, hum koi workload time $T_n$ mein complete karte hain:

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

Ye step kyun? Hum parallel runtime ke terms mein measure kar rahe hain, hypothetical single-core time mein nahi.

Step 2: 1 processor par equivalent kaam

Agar hum ye same amount of work 1 processor par run karein:

• Serial part: abhi bhi $f\cdot T_n$ (unchanged)
• Parallel part: $n\cdot (1-f)\cdot T_n$ (humne $n$ guna zyada parallel kaam kiya!)

Ye step kyun? Parallel kaam $n$ cores mein distributed tha. Ise serially karne mein $n$ guna zyada time lagta.

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

Step 3: Speedup calculate karo

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

Rearrange karo:

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

Key Differences: When to Use Which Law

Connections to Other Topics

• Parallel Architectures: Ye laws batate hain ki multicore CPUs kyun exist karte hain aur unki limits kya hain
• GPU Computing: GPUs Gustafson exploit karte hain—problem size thousands of cores tak scale karo
• Load Balancing: $f$ ko minimize karna serial kaam ko cleverly distribute karke
• Cache Coherence: Coherence protocols overhead add karte hain jo effective $f$ badhata hai
• Thread Synchronization: Locks aur barriers serial bottleneck ke primary sources hain
• Scalability Analysis: Strong scaling (Amdahl) vs weak scaling (Gustafson)
• Performance Metrics: Speedup, efficiency, aur unhe kaise measure karein

Practice Problems (Active Recall)

#flashcards/hardware

Concept Map