Amdahl's Law and Gustafson's Law: Exercises — Hinglish deep dive

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

Yeh page ek self-test hai. Har problem saaf tarike se di gayi hai, phir ek collapsible solution ke andar chhupa di gayi hai. Pehle paper par try karo, phir [!recall]- block kholo aur har step check karo. Problems L1 (sirf pieces ko pehchano) se L5 (mastery — sab kuch combine karo) tak badhti hain.

Shuru karne se pehle, parent note Amdahl's Law and Gustafson's Law se do master formulas apne saamne rakh lo.

Upar har ek symbol parent note mein build kiya gaya tha; agar $f$ ya "serial fraction" unclear hai, to aage badhne se pehle [!mistake] wala section dobara padho jisme time vs. lines count karne ki baat hai.

Level 1 — Recognition

Goal: $f$ , $n$ , aur yeh identify karo ki wording kis formula ke liye pooch rahi hai. Abhi koi mushkil algebra nahi.

Exercise 1.1

Ek program $80$ seconds mein ek core par run karta hai. Isme se $16$ seconds serial hai (split nahi ho sakta) aur baaki perfectly parallel hai. $f$ aur $n$ batao agar ab hum $4$ cores par run karein, aur batao kaun sa law lagta hai jab question yeh ho ki "kya main same 80-second job jaldi finish kar sakta hoon?"

Recall Solution 1.1

Hum kya karte hain: $f$ hai serial time over total time. $f = \frac{16}{80} = 0.2$ $n = 4$ . Job fixed size hai ("the same 80-second job"), isliye hum Amdahl's Law use karte hain. Parallel fraction hai $1 - f = 0.8$ .

Exercise 1.2

Har phrase ko Amdahl ya Gustafson se match karo: (a) "Ek ghante mein zyada nodes ke saath kitna bada simulation run kar sakta hoon?" (b) "Meri batch job fixed hai; kya 16 cores use 16× jaldi finish karenge?" (c) "Problem grow karti hai taaki har processor busy rahe."

Recall Solution 1.2

(a) Gustafson — workload resources ke saath scale karta hai. (b) Amdahl — fixed workload, finish-speed ke liye pooch raha hai. (c) Gustafson — yahi defining assumption hai (problem $n$ ke saath badhti hai).

Exercise 1.3

Ek code ko runtime se $95%$ parallel measure kiya gaya hai. $f$ likho, phir $n = 8$ ke liye Amdahl formula likho bina simplify kiye (sirf substitute karo).

Recall Solution 1.3

Parallel $0.95$ hai, isliye serial hai $f = 1 - 0.95 = 0.05$ . $S (8) = \frac{1}{0.05 + \frac{1 - 0.05}{8}} = \frac{1}{0.05 + \frac{0.95}{8}}$ (Numerically yeh $\approx 5.93$ hai — L2 mein compute kiya gaya.)

Level 2 — Application

Goal: substitution ko ek clean number mein badlo, including final runtime.

Exercise 2.1

Exercise 1.3 se $f = 0.05$ , $n = 8$ use karke, $S (8)$ do decimals tak compute karo aur naya runtime nikalo agar one-core time $200$ ms tha.

Recall Solution 2.1

Step 1 — denominator: $0.05 + \frac{0.95}{8} = 0.05 + 0.11875 = 0.16875$ . Step 2 — speedup: $S (8) = \frac{1}{0.16875} \approx 5.93$ . Step 3 — runtime: $T_{8} = \frac{T _{1}}{S} = \frac{200}{5.93} \approx 33.7$ ms. Kyun: speedup hai $T_{1} / T_{n}$ , isliye $T_{n} = T_{1} / S$ . Aath cores, lekin sirf $\approx 5.9 \times$ — $5%$ serial tax kaata hai.

Exercise 2.2

Ek rendering job $30%$ serial hai. $n = 2, 4, \infty$ par Amdahl speedup compute karo. Neeche figure dekho aur samjho kyun curve flat hoti hai.

Figure — Amdahl's Law and Gustafson's Law

Recall Solution 2.2

$f = 0.3$ .

$n = 2 : S = \frac{1}{0.3 + 0.35} = \frac{1}{0.65} \approx 1.54$
$n = 4 : S = \frac{1}{0.3 + 0.175} = \frac{1}{0.475} \approx 2.11$
$n \to \infty : S_{m a x} = \frac{1}{0.3} \approx 3.33$ Figure mein curve tezi se badhti hai phir ceiling $S_{m a x} = 1/ f$ ko hug karti hai. Serial fraction, core count nahi, ceiling set karta hai.

Exercise 2.3 (Gustafson)

Ek climate run $50$ nodes use karta hai; wall-clock ka $8%$ serial setup hai. Gustafson use karke scaled speedup nikalo.

Recall Solution 2.3

$f = 0.08$ , $n = 50$ . $S (50) = 50 - 0.08 (50 - 1) = 50 - 0.08 \times 49 = 50 - 3.92 = 46.08$ Matlab: $50$ nodes par hum ek ghante mein $\approx 46 \times$ zyada grid work karte hain jo ek node kar sakta tha.

Level 3 — Analysis

Goal: yeh reason karo ki numbers aisa behave kyun karte hain; formula invert karo; dono laws compare karo.

Exercise 3.1 (Back-calculate $f$ )

Tum $n = 16$ cores par real speedup $S = 6$ measure karte ho. Effective serial fraction kya hai?

Recall Solution 3.1

Amdahl invert karo. $S = \frac{1}{f + \frac{1 - f}{n}}$ se shuru karo, isliye $\frac{1}{S} = f + \frac{1 - f}{n}$ . $n$ se multiply karo: $\frac{n}{S} = n f + 1 - f = 1 + f (n - 1)$ . Solve karo: $f = \frac{\frac{n}{S} - 1}{n - 1}$ . $n = 16, S = 6$ plug karo: $\frac{16}{6} = 2.6667$ , minus $1 = 1.6667$ , over $15$ : $f = \frac{1.6667}{15} \approx 0.1111$ Isliye runtime ka $\approx 11.1%$ effectively serial hai — zyaatar logon ke algorithmic guess se bahut zyada, kyunki real overhead (sync, cache) andar chhupa hota hai.

Exercise 3.2 (Same $f$ , dono laws)

$f = 0.1$ aur $n = 20$ ke liye, dono Amdahl aur Gustafson speedups compute karo aur gap explain karo.

Recall Solution 3.2

Amdahl: $S = \frac{1}{0.1 + \frac{0.9}{20}} = \frac{1}{0.1 + 0.045} = \frac{1}{0.145} \approx 6.90$ . Gustafson: $S = 20 - 0.1 (19) = 20 - 1.9 = 18.1$ . Gap kyun hai: Amdahl problem ko fixed rakhta hai, isliye $10%$ serial part ek bada aur bada slice ban jaata hai jaise cores baaki ko speed up karte hain — $10 \times$ ke paas cap kar jaata hai. Gustafson parallel work ko $n$ ke saath grow hone deta hai, isliye serial part ek patla, near-constant slice rehta hai — speedup linear ke paas rehta hai ( $18.1$ of $20$ ). Same $f$ , opposite mood. Figure dekho.

Exercise 3.3 (Crossover thinking)

Amdahl ke liye $f = 0.25$ ke saath, smallest $n$ kya hai jis par $S \geq 3$ mile? (Pehle tumhe $S_{m a x}$ chahiye ho sakta hai.)

Recall Solution 3.3

Pehle ceiling check karo: $S_{m a x} = 1/ f = 1/0.25 = 4$ . Isliye $S = 3$ reachable hai ( $3 < 4$ ). Good. $3 = \frac{1}{0.25 + \frac{0.75}{n}}$ set karo. Phir $0.25 + \frac{0.75}{n} = \frac{1}{3}$ . $\frac{0.75}{n} = \frac{1}{3} - 0.25 = \frac{1}{12}$ , isliye $n = 0.75 \times 12 = 9$ . Smallest integer $n$ jis par $S \geq 3$ mile woh hai $n = 9$ (exactly $S = 3$ ).

Level 4 — Synthesis

Goal: messy data se khud $f$ banao, phir use ek law mein feed karo. Weighted time se savdhaan raho.

Exercise 4.1 (Weighted serial time)

Ek loop mein $1000$ iterations hain. $990$ parallelisable hain aur har ek ki cost $1$ unit hai. Baaki $10$ serial hain aur har ek ki cost $10$ units hai (woh disk I/O karte hain). $f$ nikalo, phir Amdahl $S (10)$ nikalo.

Recall Solution 4.1

$f$ ko time se banao, counts se nahi. Serial time $= 10 \times 10 = 100$ . Parallel time $= 990 \times 1 = 990$ . Total $= 1090$ . $f = \frac{100}{1090} \approx 0.0917$ Amdahl at $n = 10$ : parallel term $= \frac{1 - 0.0917}{10} = \frac{0.9083}{10} = 0.09083$ . Denominator $= 0.0917 + 0.09083 = 0.18257$ . $S (10) = \frac{1}{0.18257} \approx 5.48$ . Trap avoid kiya: iterations count karne par $f = 10/1000 = 0.01$ milta aur over-optimistic $S \approx 9.2$ milta.

Exercise 4.2 (Amdahl → time budget mein wapas)

Ek $100$ s job mein $f = 0.05$ serial hai. Management chahta hai yeh $\leq 20$ s mein ho jaaye. (a) Kya yeh Amdahl aur enough cores ke saath possible hai? (b) Agar nahi, to kaun sa serial fraction $f^{'}$ $20$ s ko limit mein reachable banayega?

Recall Solution 4.2

(a) Best case hai $S_{m a x} = 1/0.05 = 20$ , jo $n \to \infty$ par best time $= 100/20 = 5$ s deta hai. Ruko — yeh $20$ s se better hai, isliye $20$ s reachable hai. $n$ nikalo: $S \geq 5$ chahiye (kyunki $100/20 = 5$ ). $5 = \frac{1}{0.05 + \frac{0.95}{n}} \Rightarrow 0.05 + \frac{0.95}{n} = 0.2$ $\Rightarrow \frac{0.95}{n} = 0.15 \Rightarrow n = 6.33 \to n = 7$ cores. Achievable hai. (b) Yahan zarurat nahi kyunki (a) succeed karta hai; lekin general rule: $20$ s ko $S \geq 5$ chahiye, aur ceiling hai $1/ f^{'}$ , isliye koi bhi $f^{'} \leq 1/5 = 0.2$ limit mein $20$ s ko reachable rakhta hai. Hamara $f = 0.05$ iske andar hi hai.

Exercise 4.3 (Gustafson from wall-clock breakdown)

$128$ GPUs par ek training run $3$ ghante leti hai: $9$ minutes synchronisation (serial) hain, baaki gradient work hai. $f$ aur Gustafson speedup nikalo.

Recall Solution 4.3

Total $= 180$ min, serial $= 9$ min, isliye $f = 9/180 = 0.05$ . $S (128) = 128 - 0.05 (128 - 1) = 128 - 0.05 \times 127 = 128 - 6.35 = 121.65$ Hum same wall-clock mein ek GPU se $\approx 122 \times$ bada model train karte hain.

Level 5 — Mastery

Goal: ek chain of reasoning mein inversion, dono laws, aur ek limiting/degenerate case combine karo.

Exercise 5.1 (Dono laws ko reconcile karo)

$n = 32$ processors par tum Gustafson speedup $S_{G} = 29$ observe karte ho. (a) $f$ recover karo. (b) Usi $f$ ko use karke, $32$ cores fixed-problem Amdahl speedup kya denge? (c) Ek sentence mein batao, dono itne alag kyun hain?

Recall Solution 5.1

(a) Gustafson invert karo: $S_{G} = n - f (n - 1) \Rightarrow f = \frac{n - S _{G}}{n - 1} = \frac{32 - 29}{31} = \frac{3}{31} \approx 0.0968$ . (b) Amdahl: denominator $= 0.0968 + \frac{1 - 0.0968}{32} = 0.0968 + \frac{0.9032}{32} = 0.0968 + 0.02823 = 0.12503$ . $S_{A} = \frac{1}{0.12503} \approx 8.00$ . (c) Same $\approx 9.7%$ serial fraction: Amdahl (fixed problem) $\approx 8 \times$ ke paas cap karta hai kyunki serial slice ka relative weight badhta hai; Gustafson (scaled problem) $\approx 29 \times$ ke paas rehta hai kyunki parallel work cores ke saath badhta hai.

Exercise 5.2 (Degenerate / limiting cases)

Dhyan se evaluate karo: (a) Amdahl with $f = 0$ at any $n$ . (b) Amdahl with $f = 1$ at any $n$ . (c) Gustafson with $f = 0$ ; with $f = 1$ . (d) Amdahl at $n = 1$ .

Recall Solution 5.2

(a) $f = 0$ (fully parallel): $S = \frac{1}{0 + \frac{1}{n}} = n$ . Perfect linear speedup — ideal hai. (b) $f = 1$ (fully serial): $S = \frac{1}{1 + 0} = 1$ . Kabhi speedup nahi; extra cores idle rehte hain. (c) Gustafson $f = 0$ : $S = n - 0 = n$ (linear). $f = 1$ : $S = n - 1 (n - 1) = 1$ (koi speedup nahi). Dono laws do extremes $f = 0$ aur $f = 1$ par agree karte hain — yeh sirf beech mein alag hote hain, jahan "fixed vs. scaled" assumption actually matter karti hai. (d) $n = 1$ (Amdahl): $S = \frac{1}{f + \frac{1 - f}{1}} = \frac{1}{f + 1 - f} = \frac{1}{1} = 1$ . Sanity check: ek core khud se tez nahi ho sakta — speedup exactly $1$ hona chahiye. ✓

Exercise 5.3 (Design decision)

Tumhari Amdahl-limited job mein $f = 0.2$ hai. Tum ya to (A) cores $8$ se $16$ kar sakte ho, ya (B) serial fraction ko $f = 0.1$ tak halve kar sakte ho jabki $8$ cores rakhte ho. Kaun jitega?

Recall Solution 5.3

Baseline ( $f = 0.2, n = 8$ ): $S = \frac{1}{0.2 + \frac{0.8}{8}} = \frac{1}{0.2 + 0.1} = \frac{1}{0.3} \approx 3.33$ . (A) $f = 0.2, n = 16$ : $S = \frac{1}{0.2 + \frac{0.8}{16}} = \frac{1}{0.2 + 0.05} = \frac{1}{0.25} = 4.00$ . (B) $f = 0.1, n = 8$ : $S = \frac{1}{0.1 + \frac{0.9}{8}} = \frac{1}{0.1 + 0.1125} = \frac{1}{0.2125} \approx 4.71$ . Winner: (B). Serial fraction par attack karna hardware throw karne se better hai, kyunki ceiling $1/ f$ $5$ se $10$ tak badh gayi. Yahi Amdahl ka pura moral hai.

Recall Quick self-check (answers reveal karo)

Amdahl $S_{m a x}$ jab $f = 0.05$ ho ::: $1/0.05 = 20$ Scaled problems ke liye kaun sa law optimistic hai ::: Gustafson Amdahl ko $S, n$ given $f$ ke liye invert karo ::: $f = \frac{n / S - 1}{n - 1}$ Gustafson ko $S, n$ given $f$ ke liye invert karo ::: $f = \frac{n - S}{n - 1}$ Dono laws kaun se $f$ values par agree karte hain ::: $f = 0$ aur $f = 1$

Aage badhne ke liye related vault topics: Scalability Analysis, Performance Metrics, Load Balancing, Thread Synchronization, Parallel Architectures, GPU Computing, Cache Coherence.