Amdahl's Law and Gustafson's Law: Worked examples — Hinglish deep dive

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

Is page mein parent laws ko har tarah ke inputs ke saath drill kiya gaya hai: ek aam middle-of-the-road case, do extreme cases ( $f = 0$ aur $f = 1$ ), "infinite cores" ka limit, ek word problem mein chupi hui serial fraction, aur woh classic exam trap jahan tumhe sahi law choose karni padti hai. Kuch bhi compute karne se pehle, har symbol ka naam le lete hain.

Scenario matrix

Neeche har worked example us cell ke saath tagged hai jahan woh fit hota hai. Saath milke yeh har cell ko cover karte hain.

#	Case class	Input mein kya khaas hai	Kaunsi law	Example
A	Typical mid-range	$0 < f < 1$ , finite $n$	Amdahl	Ex 1
B	Degenerate: $f = 0$	kuch bhi serial nahi	dono	Ex 2
C	Degenerate: $f = 1$	kuch bhi parallel nahi	dono	Ex 2
D	Limit $n \to \infty$	serial ceiling	Amdahl	Ex 3
E	Hidden $f$ (profiling trap)	$f$ time se, code lines se nahi	Amdahl	Ex 4
F	Scaled workload	problem $n$ ke saath badhti hai	Gustafson	Ex 5
G	Same numbers, dono laws	pessimist vs optimist compare karo	dono	Ex 6
H	Inverse problem	given $S$ , $f$ nikalo	Amdahl	Ex 7
I	Exam twist: law choose karo	word problem, ambiguous	judgment	Ex 8

Woh picture jo poori matrix ko jodhti hai — speedup kaise muda jaata hai jab $f$ badalta hai. Figure s01: horizontal axis processors ki sankhya $n$ hai (1 se 64); vertical axis Amdahl speedup $S_{A} (n)$ hai. Grey dashed line impossible ideal $S = n$ hai. Green curve ( $f = 0$ ) us ideal par chadhi hai; jaise $f$ badhta hai $0.05$ (blue), $0.15$ (orange), $0.3$ (red) tak, curves door hokar jaldi flatten ho jaate hain — red arrow dikhata hai ki bada $f$ kaise flatter, neechi curve deta hai.

Figure — Amdahl's Law and Gustafson's Law

Case A — ordinary Amdahl case ( $0 < f < 1$ )

Worked example Ex 1 · Ek fixed image render karna

Ek render ek core par $T_{1} = 200$ s leta hai. Colour-space setup $30$ s ka hai (serial); pixels shade karna $170$ s ka hai (parallel). 8 cores ke saath $S (8)$ nikalo.

Forecast: 8 cores hain, lekin ek chunk serial hai — andaza: kahin 4 aur 6 ke beech?

Step 1 — $f$ nikalo (Amdahl clock: $T_{1}$ ka fraction). $f = \frac{30}{200} = 0.15$ Yeh step kyun? Amdahl ke liye, $f$ one-core time $T_{1}$ ka fraction hota hai, aur yahan woh times seedhe diye gaye hain, toh serial-time ko $T_{1}$ se divide karte hain.

Step 2 — Amdahl mein plug karo. $S_{A} (8) = \frac{1}{0.15 + \frac{0.85}{8}} = \frac{1}{0.15 + 0.10625} = \frac{1}{0.25625}$ Yeh step kyun? Same problem hai, sirf jaldi finish karna chahte hain → Amdahl ( $S_{A}$ ), Gustafson nahi.

Step 3 — evaluate karo. $S_{A} (8) \approx 3.902$ Yeh step kyun? Speedup ek plain number hai, toh hum fraction $1/0.25625$ ko decimal mein convert karke finish karte hain — woh decimal hi "kitne guna tez" ka jawab hai jo question ne maanga tha.

Verify: New time $= T_{1} / S = 200/3.902 \approx 51.25$ s $= T_{8}$ . Seedha $T_{8}$ rebuild karke sanity check: serial $30$ s wahi rehta hai, parallel $170/8 = 21.25$ s, total $30 + 21.25 = 51.25$ s. ✓ Match karta hai — aur $3.9 < 8$ , exactly wahi "serial fraction tumse robbing kar raha hai" behaviour jo humne predict kiya tha.

Load imbalance aur coordination effective $f$ ko algorithmic $f$ se bura bana dete hain — dekho Load Balancing aur Thread Synchronization.

Cases B & C — do degenerate extremes ( $f = 0$ aur $f = 1$ )

Worked example Ex 2 · 16 cores par extremes

16 cores par (i) $f = 0$ (kuch bhi serial nahi) aur (ii) $f = 1$ (kuch bhi parallel nahi) ke liye dono laws compute karo.

Forecast: $f = 0$ dream dega ( $16 \times$ ); $f = 1$ nightmare dega ( $1 \times$ , koi help nahi).

Step 1 — Amdahl at $f = 0$ . $S_{A} (16) = \frac{1}{0 + \frac{1}{16}} = 16$ Kyun? Koi serial part nahi, toh denominator sirf $1/ n$ hai, isliye speedup $= n$ : perfect linear.

Step 2 — Amdahl at $f = 1$ . $S_{A} (16) = \frac{1}{1 + 0} = 1$ Kyun? Poora kaam serial hai; extra cores idle baithte hain → koi speedup kabhi nahi.

Step 3 — Gustafson same ends par. $S_{G} (16)_{f = 0} = 16 - 0 = 16, S_{G} (16)_{f = 1} = 16 - 1 \cdot 15 = 1$ Yeh step kyun? Degenerate ends par dono laws agree karni chahiye — $f = 0$ par "scale up" karne ke liye kuch nahi, $f = 1$ par kuch move nahi ho sakta. (In ends par dono clocks $T_{1}$ aur $T_{n}$ same $f$ dete hain, toh ambiguity khatam ho jaati hai.)

Verify: Chaaron numbers hain ${16, 1, 16, 1}$ ; dono laws boundaries par exactly coincide karte hain, jo sahi consistency check hai. ✓

Case D — infinite-core ceiling

Worked example Ex 3 · Zyada cores kabhi kitna

buy kar sakte hain? Ek pipeline mein $f = 0.2$ hai. $n = 4$ , $n = 100$ , aur limit $n \to \infty$ par $S_{A}$ compute karo.

Forecast: Cores double aur re-double karne par diminishing returns aana chahiye, kisi ceiling ke paas flatten hote hue.

Step 1 — $n = 4$ . $S_{A} (4) = \frac{1}{0.2 + \frac{0.8}{4}} = \frac{1}{0.2 + 0.2} = 2.5$ Yeh step kyun? Hum sabse chhote core count se baseline speedup establish karte hain; low- $n$ number hone par hi hum baad mein dekh sakte hain ki $n$ bahut zyada karne par returns kitna kam badhte hain.

Step 2 — $n = 100$ . $S_{A} (100) = \frac{1}{0.2 + \frac{0.8}{100}} = \frac{1}{0.208} \approx 4.808$ Yeh step kyun? 4 se 100 cores tak jaana (ek $25 \times$ ka jump) speedup ko sirf $2.5$ se $4.8$ tak le gaya — proof ki returns collapse ho rahe hain.

Step 3 — limit. Jaise $n \to \infty$ , term $\frac{1 - f}{n} \to 0$ , toh $S_{m a x} = \frac{1}{f} = \frac{1}{0.2} = 5$ Yeh step kyun? Parallel part zero time tak shrink ho jaata hai; sirf immovable serial part bachta hai, aur $1/ f$ woh hard wall hai.

Verify: $4.808 < 5$ aur $2.5 < 5$ : har finite case ceiling ke neeche hai, aur $n = 100$ already $96%$ wahan pahunch chuka hai. ✓ Dekho Scalability Analysis ke liye ki aakhri $4%$ chase karna rarely worth kyun nahi hota.

Neeche figure mein dashed line exactly yahi $1/ f$ ceiling hai. Figure s02: horizontal axis $n$ hai (1 se 120), vertical axis $f = 0.2$ ke liye $S_{A} (n)$ hai (blue curve). Red dashed horizontal line $1/ f = 5$ par baithi hai. Do dots hamare worked points mark karte hain — orange dot $n = 4, S = 2.5$ par aur green dot $n = 100, S \approx 4.81$ par — dikhata hai curve red ceiling ki taraf creep kar raha hai lekin touch nahi karta.

Case E — hidden serial fraction (profiling trap)

Worked example Ex 4 · Jab lines count karna jhooth bolta hai

Ek loop 1000 iterations run karta hai. 990 parallelizable hain; 10 serially chalne chahiye. Naively tum kahoge $f = 10/1000 = 0.01$ . Lekin har serial iteration disk I/O karta hai aur parallel wale se $10 \times$ zyada time leta hai. Sachcha $f$ aur $S_{A} (20)$ nikalo.

Forecast: Real $f$ $0.01$ se kaafi upar hai; speedup disappointing hoga.

Step 1 — sab kuch time units mein daalo. Maano ek parallel iteration $= 1$ unit.

Parallel time $= 990 \times 1 = 990$ units.
Serial time $= 10 \times 10 = 100$ units. Yeh step kyun? $f$ time ka fraction hai; jo iterations zyada time lete hain unhe unki length ke hisaab se weight karna padega, equally count nahi kar sakte.

Step 2 — total aur fraction (Amdahl clock: $T_{1}$ ka fraction). $f = \frac{100}{990 + 100} = \frac{100}{1090} \approx 0.09174$ Yeh step kyun? Definition se $f = \frac{serial time}{total time T _{1}}$ , toh Step 1 ke do time pools ko add karke $T_{1}$ nikalte hain, phir uska serial slice lete hain — yeh hamare raw time units ko formula ke liye zarurat wali pure fraction mein convert karta hai.

Step 3 — Amdahl at $n = 20$ . $S_{A} (20) = \frac{1}{0.09174 + \frac{0.90826}{20}} = \frac{1}{0.09174 + 0.04541} = \frac{1}{0.13716} \approx 7.29$ Yeh step kyun? Ab hum honest $f$ (aur uska complement $1 - f = 0.90826$ ) ko requested 20 cores ke liye Amdahl mein feed karte hain — yeh payoff number hai jo expose karta hai ki naive $f = 0.01$ kitna jhooth bolta.

Verify: Fake $f = 0.01$ se tum predict karte $S_{A} (20) = 1/ (0.01 + 0.0495) = 16.8$ — sach se double se zyada. Performance Metrics ka lesson: hamesha time profile karo, kabhi code count mat karo. ✓

Case F — scaled workload (Gustafson)

Worked example Ex 5 · Ek bada climate model

Ek climate run $n = 256$ cores par $T_{n} = 1$ ghante mein finish hota hai. Setup 3 min ka hai (serial); grid solve 57 min ka hai (parallel). Gustafson speedup kya hai?

Forecast: Parallel part dominate karta hai, toh speedup $256$ ke paas hona chahiye.

Step 1 — parallel-run reference se $f$ (Gustafson clock: $T_{n}$ ka fraction). $f = \frac{3}{60} = 0.05$ Yeh step kyun? Gustafson fractions already-parallel run-time $T_{n}$ ke (yahan $T_{n} = 60$ min) against measure karta hai, aur woh minutes humein diye gaye hain.

Step 2 — Gustafson formula. $S_{G} (256) = 256 - 0.05 (256 - 1) = 256 - 0.05 \cdot 255 = 256 - 12.75 = 243.25$ Gustafson kyun? Hum wohi chhota model tezi se re-run nahi kar rahe — humne fixed 1-ghante ke budget mein ek finer grid pack kiya. Problem cores ke saath bada hua.

Verify: Yahi bada, scaled workload ek core par kitna time leta? Iska serial part $f \cdot T_{n}$ par unchanged hai; parallel part, serially kiya hua, $n$ guna lamba hai, $n (1 - f) \cdot T_{n}$ . Inhe add karne par $T_{1} = f \cdot T_{n} + n (1 - f) \cdot T_{n} = T_{n} [f + n (1 - f)] .$ Numerically $T_{1} = 1 \cdot [0.05 + 256 \cdot 0.95] = 243.25$ ghante. 1-ghante ke actual run $T_{n}$ se divide karo → $S_{G} = T_{1} / T_{n} = 243.25 \times$ . ✓ GPU Computing scaling intuition se consistent.

$S_{G} (n)$ Amdahl ke relative kahan rehta hai? Figure s03: horizontal axis $n$ hai (1 se 64); vertical axis speedup hai. Green line $f = 0.05$ ke liye Gustafson $S_{G} (n)$ hai — yeh grey dashed ideal $S = n$ ke thoda neeche chadhi rehti hai aur badhti rehti hai. Blue curve same $f = 0.05$ ke liye Amdahl $S_{A} (n)$ hai, jo apni $1/ f = 20$ ceiling (red dashed) ki taraf flatten hoti hai. Green aur blue ke beech ka gap poori "pessimist vs optimist" story hai.

Case G — same numbers, dono laws (pessimist vs optimist)

Worked example Ex 6 ·

$f = 0.1$ , $n = 32$ , do baar judge kiya gaya Identical $f = 0.1$ ke liye $S_{A} (32)$ aur $S_{G} (32)$ compute karo.

Forecast: Amdahl chhota (apni $1/ f = 10$ wall ke paas), Gustafson bada ( $32$ ke paas).

Step 1 — Amdahl. $S_{A} (32) = \frac{1}{0.1 + \frac{0.9}{32}} = \frac{1}{0.1 + 0.028125} = \frac{1}{0.128125} \approx 7.805$ Yeh step kyun? Pehle fixed-problem question ka jawab dete hain ( $f$ against $T_{1}$ ): 32 cores par same kaam ke saath, serial $0.1$ chhote $0.9/32$ par dominate karta hai, toh speedup $1/ f = 10$ wall ki taraf khinch jaati hai.

Step 2 — Gustafson. $S_{G} (32) = 32 - 0.1 (31) = 32 - 3.1 = 28.9$ Yeh step kyun? Ab identical numeric $f$ par scaled-problem question ka jawab dete hain ( $f$ against $T_{n}$ ): yahan $n = 32$ lead karta hai aur serial term sirf chhota $3.1$ subtract karta hai, toh speedup linear ideal $n = 32$ ke thoda neeche baithti hai — Step 1 ke saath deliberate contrast.

Verify: $7.805 < 10 = 1/ f$ (Amdahl ki ceiling ke neeche ✓) aur $28.9 < 32 = n$ (Gustafson ke linear ideal ke neeche ✓). Dono apni upper bound maante hain. ✓

Case H — inverse problem (given speedup, bottleneck dhundho)

Worked example Ex 7 ·

$f$ back-calculate karna Tumne 8 real cores par $S_{A} (8) = 5$ measure kiya. Iska matlab kya effective serial fraction hai?

Forecast: $5$ possible $8$ mein se decent hai, toh $f$ moderately chhota hona chahiye (well under $0.1$ ).

Step 1 — Amdahl invert karo. $S = \frac{1}{f + \frac{1 - f}{n}}$ se shuru karo, toh $\frac{1}{S} = f + \frac{1 - f}{n}$ . Yeh step kyun? Humein $S$ aur $n$ pata hai; unknown $f$ hai, toh algebraically solve karte hain — dono sides flip karne se awkward reciprocal ek plain linear equation mein badal jaata hai $f$ mein.

Step 2 — $f$ isolate karo. $n$ se multiply karo: $\frac{n}{S} = n f + 1 - f = 1 + f (n - 1) \Rightarrow f = \frac{\frac{n}{S} - 1}{n - 1}$ Yeh step kyun? $n$ se multiply karne par fraction $\frac{1 - f}{n}$ clear ho jaata hai isliye har term $f$ ka whole multiple hai; phir hum do $f$ -terms collect karte hain ( $n f - f = f (n - 1)$ ), akela $1$ cross karte hain, aur $(n - 1)$ se divide karte hain — standard "unknown gather karo, phir divide" moves jo $f$ ko akele ek side par chodh dete hain.

Step 3 — $S = 5, n = 8$ plug karo. $f = \frac{\frac{8}{5} - 1}{7} = \frac{1.6 - 1}{7} = \frac{0.6}{7} \approx 0.0857$

Verify: Forward-check: $S_{A} (8) = \frac{1}{0.0857 + \frac{0.9143}{8}} = \frac{1}{0.0857 + 0.11429} = \frac{1}{0.2} = 5$ . ✓ Recovered $f \approx 8.6%$ batata hai kahan dhundhna hai (locks, Cache Coherence traffic).

Case I — exam twist: kaunsi law?

Worked example Ex 8 · Law choose karo, phir compute karo

"Ek search engine ek fixed 1 TB corpus index karta hai. 1 machine par $T_{1} = 800$ s lagta hai; usme se 80 s ek serial merge step hai. 10 machines par kya speedup expect hai?" Phir ek doosra clause: "Agar instead tum 10 machines par 10 TB tak badhne wale corpus ko index karo jabki 80 s merge wahi rahe, toh speedup kya hoga?"

Forecast: Clause 1 = fixed problem → Amdahl. Clause 2 = problem machines ke saath scale hoti hai → Gustafson.

Step 1 — clause 1, $f$ nikalo (Amdahl clock: $T_{1}$ ka fraction) aur Amdahl choose karo. $f = \frac{80}{800} = 0.1$ $S_{A} (10) = \frac{1}{0.1 + \frac{0.9}{10}} = \frac{1}{0.1 + 0.09} = \frac{1}{0.19} \approx 5.263$ Amdahl kyun? Word fixed bata deta hai — same kaam, jaldi finish, toh $f$ one-core time $T_{1} = 800$ s ka slice hai.

Step 2 — clause 2, same $n = 10$ , lekin scaled → Gustafson. $f^{'}$ us serial fraction ko denote kare jo 10-machine run $T_{n}$ ke against measured ho (Gustafson clock), clause 1 ke single-machine $f$ ke opposite. Parallel kaam woh hai jo $10 \times$ bada hua; merge 800 s ke ten-machine run mein se 80 s par rehta hai, toh $f^{'} = \frac{80}{800} = 0.1, S_{G} (10) = 10 - f^{'} (10 - 1) = 10 - 0.1 \cdot 9 = 10 - 0.9 = 9.1$ Gustafson kyun? Corpus machines ke saath bada — classic Gustafson signal, toh run-referenced fraction $f^{'}$ ke saath $S_{G}$ use karo.

Verify: Same physical hardware, same numeric fraction ( $f = f^{'} = 0.1$ ), lekin question answer ko $5.26$ (fixed) se $9.1$ (scaled) par flip kar deta hai. ✓ Dono apni bounds ke neeche hain ( $1/ f = 10$ aur $n = 10$ ). Exam ka point: padho ki problem size hold hai ya grow ho rahi hai.

Recall Quick self-test

$T_{1}$ aur $T_{n}$ ka matlab hai ::: ek core par run-time, aur $n$ cores par run-time, respectively. Amdahl $f$ kaunsi clock ke against measure karta hai? ::: one-core time $T_{1}$ . Gustafson $f$ kaunsi clock ke against measure karta hai? ::: $n$ -core run-time $T_{n}$ . $f = 0$ par Amdahl aur Gustafson dono dete hain ::: $S = n$ (woh agree karte hain). $n \to \infty$ par Amdahl ceiling hai ::: $1/ f$ . Measured $S_{A} (n)$ se $f$ recover karne ke liye use karo ::: $f = \frac{n / S - 1}{n - 1}$ . Woh akela word jo Amdahl-vs-Gustafson decide karta hai ::: kya problem fixed hai ya scaled.