Amdahl's Law and Gustafson's Law: Visual walkthrough

6.1.3 · D2 · Hardware › Parallelism & Multicore › Amdahl's Law and Gustafson's Law

Is page mein koi prior knowledge nahi chahiye, bas itna ki tum time measure kar sako. Related ideas Scalability Analysis, Performance Metrics, Parallel Architectures, aur Load Balancing mein hain — lekin abhi unki zaroorat nahi. Hinglish prefer karte ho? Yeh note Hinglish mein →.

Step 1 — Kaam ko ek time bar ki tarah draw karo

KYA. Ek program run hota hai. Usme kuch time lagta hai. Us time ko ek horizontal bar ki tarah draw karo. Bar ki length = job kitne time mein hoti hai — bas itna. Us total time ko $T_{1}$ kaho.

$T_{1}$ — yahan 1 ka matlab hai "ek processor par". Yeh woh time hai jo hamara single worker poori job shuru se end tak complete karne mein leta hai.

KYU. Pehle "faster jaana" ki baat karne se pehle, hume ek picture chahiye ki "kaam" hai kya. Bar ek honest picture hai: time left se right flow karta hai, aur poori job poora bar hai. Is page par baaki sab kuch hum is bar ko kaatna aur shrink karna hi hai.

PICTURE. Neeche wala poora bar $T_{1}$ hai. Abhi yeh ek solid colour hai — humne abhi ise parts mein split nahi kiya.

Figure — Amdahl's Law and Gustafson's Law

Step 2 — Bar ko serial aur parallel parts mein split karo

KYA. Sab kaam barabar nahi hota. Kuch kaam ek fixed order mein hi hona chahiye — jaise file padhna process karne se pehle, ya lock acquire karna. Us part ko serial kehte hain. Baaki kaam ko independent pieces mein kaata ja sakta hai jo ek saath work kiya ja sake — woh part parallel hai.

Hum bar ko do coloured segments mein kaatenge:

$T_{1} = serial part f \cdot T_{1} + parallel part (1 - f) \cdot T_{1}$

$f$ — serial fraction. Yeh $0$ aur $1$ ke beech ka number hai: total time ka kitna hissa sequential rehne par majboor hai. Agar $f = 0.2$ hai, toh bar ka ek-paanchwa hissa serial hai.
$f \cdot T_{1}$ — fraction $f$ times total time = serial segment ki actual length in seconds.
$1 - f$ — "jo bhi serial nahi hai", yani yeh parallel fraction hai.
$(1 - f) \cdot T_{1}$ — parallel segment ki length in seconds.

KYU. Yeh split dono laws ka poora idea hai. Serial piece villain hai — workers badhaake hum ise speed up nahi kar sakte. Parallel piece hero hai — jab workers badhate hain toh yeh shrink hota hai. Speedup ke baare mein reason karne ke liye hume pehle inhe naam dekar colour karna hoga.

PICTURE. Magenta chunk serial hai (frozen, kabhi nahi shrinks). Orange chunk parallel hai (jis part par hum attack karenge). Notice karo ki unki lengths milke poora bar bana deti hain.

Step 3 — Processors add karo aur sirf parallel part ko shrink karo

KYA. Ab $n$ processors ( $n$ workers) laao. Parallel kaam unhe sab ko ek saath do. Agar kaam perfectly divide ho jaata hai, toh $n$ workers use $1/ n$ time mein khatam kar denge. Serial part abhi bhi ek hi worker par run hoga — yeh bilkul bhi shrink nahi hoga.

$n$ processors par naya total time hai:

$T_{n} = serial: unchanged f \cdot T_{1} + parallel: shrunk n times \frac{( 1 - f ) \cdot T _{1}}{n}$

$n$ — processors ki sankhya. $n = 1$ matlab ek worker (wapas $T_{1}$ par); bada $n$ matlab bada crowd.
$\frac{( 1 - f ) \cdot T _{1}}{n}$ — parallel segment lo aur uski length ko $n$ se divide karo. Double workers → half parallel time. Das workers → one-tenth.
Serial term mein koi $n$ nahi — yahi poora tragedy hai. Zyada workers use touch nahi kar sakte.

KYU. Yeh cores add karne ka honest model hai: divisible kaam divide hoga, stubborn kaam ruka rahega. Amdahl ki pessimism ke baare mein sab kuch us ek term se aata hai jisme $n$ nahi hai.

PICTURE. Magenta (serial) block pehle jitna hi lamba hai. Orange (parallel) block apni width ka $1/ n$ ho gaya hai. Dekho kaise serial block ab shrunk bar ko dominate kar raha hai.

Step 4 — Speedup ko bar lengths ke ratio ki tarah define karo

KYA. "Hum kitna faster hue?" — is sawaal ka jawaab dono bars ko compare karke milta hai: purani length divided by nayi length. Us ratio ko speedup $S (n)$ kaho.

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

$S (n)$ — speedup. $S = 4$ matlab "ek processor se chaar guna faster".
Numerator $T_{1}$ — original bar length.
Denominator $T_{n}$ — shrunk bar length.

KYU. Speedup zaroor ek ratio hona chahiye, kyunki "faster" hamesha relative hota hai. Ratio units (seconds) bhi cancel karne deta hai — hume factor ki parwah hai, raw seconds ki nahi. Woh cancellation agla step hai aur woh beautiful hai.

PICTURE. Do bars ek ke upar ek: upar lamba original $T_{1}$ , neeche chota $T_{n}$ . Lal bracket ratio dikhata hai — chote bar ki kitni copies lambe bar ke andar fit hoti hain.

Step 5 — $T_{1}$ cancel karo aur Amdahl's Law paao

KYA. Fraction mein har term mein $T_{1}$ hai. Ise neeche se factor out karo aur upar wale se cancel karo. Absolute time gayab ho jaati hai.

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

Upar ka $T_{1}$ aur neeche factor out kiya $T_{1}$ cancel ho jaate hain — upar clean $1$ bachta hai.
Neeche: $f$ (frozen serial share) plus $\frac{1 - f}{n}$ (shrinking parallel share).

KYU. $T_{1}$ cancel karna hume kuch deep bataata hai: speedup is baat par depend nahi karta ki job kitni badi hai — sirf fraction $f$ aur worker count $n$ par. 3-second job aur 3-hour job agar same $f$ ke saath hain toh identically scale hote hain.

PICTURE. Upar aur neeche ke $T_{1}$ symbols glow karte hain, phir cross out ho jaate hain; jo bachta hai woh sirf $f$ aur $n$ se bana formula hai.

Step 6 — $n$ ko infinity tak le jao: ceiling

KYA. Unlimited processors ke saath best possible kya hai? $n$ ko bina bound ke badhne do. Term $\frac{1 - f}{n}$ ke denominator mein $n$ hai, toh jaise $n$ huge hota hai yeh term zero ho jaata hai. Sirf $f$ bachta hai.

$S_{m a x} = lim_{n \to \infty} \frac{1}{f + \frac{1 - f}{n}} = \frac{1}{f}$

$n \to \infty lim$ — "dekho kya hota hai jab $n$ enormous ho jaata hai". Hum yahan limit use karte hain kyunki hume ceiling chahiye — woh value jis ki taraf curve flatten hota hai lekin kabhi cross nahi karta.
$\frac{1 - f}{n} \to 0$ — ek fixed number divided by ever-bigger number zero ki taraf jaata hai.
Result $\frac{1}{f}$ — ek hard wall. Agar $f = 0.1$ hai, toh ceiling $10 \times$ hai. Ek million cores bhi ise beat nahi kar sakta.

KYU. Hum limit use karte hain kyunki "infinitely many processors" exactly wahi sawaal hai jo limit answer karta hai: hum kis value ki taraf approach karte hain? Yeh poori derivation ka single most important consequence hai — serial fraction ek unbreakable ceiling set karta hai.

PICTURE. Speedup curve climb karta hai, phir bend karke ek dashed horizontal line ke paas flatten ho jaata hai height $1/ f$ par. Woh ceiling ko hamesha ke liye hug karta hai bina touch kiye.

Step 7 — Degenerate cases: do extremes

KYA. Hamesha boundaries check karo, taaki koi reader surprise na ho.

$f = 0$ (kuch bhi serial nahi). Formula: $S (n) = \frac{1}{0 + \frac{1}{n}} = n$ . Perfect linear speedup — 8 cores exactly $8 \times$ dete hain. Bar sab orange hai; poora shrink hota hai.
$f = 1$ (sab serial). Formula: $S (n) = \frac{1}{1 + 0} = 1$ . Kabhi koi speedup nahi. Bar sab magenta hai; workers add karna literally kuch nahi karta.
$n = 1$ (ek worker). $S (1) = \frac{1}{f + ( 1 - f )} = \frac{1}{1} = 1$ . Sanity check: ek processor, by definition, exactly apne jitna hi fast hai.

KYU. Yeh extremes poore formula ke anchor posts hain. Agar ek formula $f = 0$ , $f = 1$ , aur $n = 1$ par sensibly behave kare, toh tum uspar beech mein trust kar sakte ho. Yeh har program ki do personalities bhi dikhate hain: fully parallel (sapna) vs fully serial (darawna sapna).

PICTURE. Teen chote bars side by side — all-orange ( $f = 0$ ), all-magenta ( $f = 1$ ), aur ek single-worker bar — har ek par us speedup ka label jo woh produce karta hai.

Step 8 — Gustafson ka flip: parallel run se measure karo

KYA. Amdahl ne pucha "same job, kitna faster?" Gustafson ulta puchta hai: "same time mein, kitna ZYADA kaam?" Trick yeh hai ki parallel run se shuru karo aur imagine karo ki use ek core par force karte hain.

Ek aise job se shuru karo jo $n$ processors ko time $T_{n}$ mein fill kare, pehle jaisi split ke saath:

$T_{n} = serial f \cdot T_{n} + parallel, on n cores (1 - f) \cdot T_{n}$

Ab itni hi amount of work ko ek processor par karo. Serial part unchanged hai, lekin parallel part — jo $n$ cores ne milke chaba diya — akele $n$ guna zyada time leta:

$T_{1} = f \cdot T_{n} + n (1 - f) \cdot T_{n} = T_{n} [f + n (1 - f)]$

Speedup phir se ratio hai, aur $T_{n}$ cancel ho jaata hai:

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

$n (1 - f) \cdot T_{n}$ — key move: woh parallel work jo $n$ cores ne time $(1 - f) T_{n}$ mein kiya, ek core par iska $n \times$ lagta.
$n - f (n - 1)$ — jab $f$ small ho toh $n$ ke saath almost linearly badhta hai.

KYU. Real supercomputing mein hum runtime shrink nahi karte — hum problem grow karte hain (finer weather grid, bada neural net) nayi cores ko same wall-clock time mein fill karne ke liye. Gustafson yahi measure karta hai. Serial part ab fixed runtime ka ek fixed slice rehta hai, isliye woh ceiling impose nahi karta — yahi wajah hai ki badi machines worth it lagti hain.

PICTURE. Left: parallel bar (fixed time $T_{n}$ , chota serial slice). Right: same kaam ek core par stretch kiya — orange parallel block $n$ guna width ka ho jaata hai jabki magenta wahi rehta hai.

Ek-picture summary

Do bars poori kahani batate hain. Amdahl job fixed rakhta hai aur time shrink karta hai — frozen serial slice dominate karne lagti hai, isliye speedup $1/ f$ ceiling par ja dabaati hai. Gustafson time fixed rakhta hai aur job grow karta hai — serial slice ek chota fixed share rehta hai, isliye speedup almost $n$ jaisi tarah climb karta hai.

Recall Feynman retelling — ek story ki tarah bolo

Ek job ko coloured time ki bar imagine karo. Ek colour (magenta) stubborn kaam hai jo order mein jaana chahiye; doosra (orange) share kiya ja sakta hai. Workers add karo aur sirf orange shrinks — magenta wahan baith rehta hai. Speedup bas purani bar length divided by nayi hai. Jab tum length cancel karte ho, tum seekhte ho ki speedup sirf fractions par depend karta hai, size par nahi. Infinitely many workers bhejo aur orange poori tarah gayab ho jaata hai, lekin magenta bachta hai, tumhe $1/ f$ par hamesha ke liye cap karta hai — yahi Amdahl hai. Phir apna sawaal flip karo: mat pucho "same job par kitna faster", pucho "same time mein kitna bada kaam". Ab stubborn part ek fixed clock ka fixed sliver hai, aur shareable part har worker ke saath balloon karta hai — toh speedup almost seedha upar jaata hai. Yahi Gustafson hai. Same do colours, do alag sawaal, do alag destinies.

Recall Quick self-test

$f = 0.25$ aur $n = 4$ ke saath, Amdahl speedup? ::: $\frac{1}{0.25 + 0.75/4} = \frac{1}{0.4375} \approx 2.29$ Same $f$ aur $n$ ke saath, Gustafson speedup? ::: $4 - 0.25 (3) = 4 - 0.75 = 3.25$ $f = 0.25$ ke liye Amdahl ceiling? ::: $1/0.25 = 4$ $f = 0$ par, Amdahl $S (n)$ kya hai? ::: exactly $n$ (perfect linear speedup) $f = 1$ par, Amdahl $S (n)$ kya hai? ::: exactly $1$ (koi speedup nahi, sab serial)