Amdahl's Law and Gustafson's Law: Question bank — Hinglish deep dive

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

Kisi bhi trap ko samajhne se pehle hume do formulas khud se banana aana chahiye — udhar nahi lena. Neeche sab kuch inhi par tika hai, isliye hum inhe yahan scratch se banate hain.

Amdahl's formula banana (fixed problem)

Pura job ek core par lo, time $T_{1}$ . Ise serial aur parallel slices mein baanto (neeche figure, top bar): serial $= f T_{1}$ , parallel $= (1 - f) T_{1}$ .

Figure — Amdahl's Law and Gustafson's Law

Ab parallel slice ko $n$ workers ko do. Serial slice split nahi ho sakti, isliye wo abhi bhi $f T_{1}$ cost karti hai; parallel slice evenly divide hoti hai $\frac{( 1 - f ) T _{1}}{n}$ mein (figure, lower bars). Dono jodo:

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

Speedup ratio hai, aur $T_{1}$ upar neeche cancel ho jaata hai:

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

$n \to \infty$ karo: term $\frac{1 - f}{n} \to 0$ , aur hard ceiling $S_{m a x} = 1/ f$ bachi rehti hai.

Gustafson's formula banana (growing problem)

Ab reference flip karo. Hamare paas $n$ cores hain aur ek fixed time $T_{n}$ hai. Slices ko usi run mein measure karo: serial $= f T_{n}$ , parallel $= (1 - f) T_{n}$ (neeche figure, upper bar). Trick ye hai: parallel slice $n$ cores mein spread thi, isliye usi kaam ko ek core par dobara karne mein $n$ guna zyada time lagega — parallel term inflate hokar $n (1 - f) T_{n}$ ho jaati hai (lower bar), jabki serial term unchanged rehti hai:

$T_{1} = f T_{n} + n (1 - f) 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 (1 - f) = n - n f$ expand karo aur collect karo:

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

Toh linear term $n$ directly $n \times$ parallel work karne se aata hai; $- f (n - 1)$ wo "tax" hai jo inflate na hone wali serial slice lagaati hai. ( $S (n) = n + (1 - n) f$ bhi wahi cheez hai.)

In do worlds ke do naam

Recall Which question does each law ask?

Amdahl (strong scaling) ::: "Problem ek fixed size ki hai — main ise kitni fast khatam kar sakta hoon?" $S (n) = \frac{1}{f + ( 1 - f ) / n}$ , $1/ f$ par capped. Gustafson (weak scaling) ::: "Mere paas $n$ workers aur ek fixed time budget hai — main kitna zyada kaam kar sakta hoon?" $S (n) = n - f (n - 1)$ , near-linear jab $f$ chhota ho.

True or false — justify

Har baar reason do; sirf true/false bola toh kuch nahi milega.

TF1. "Enough cores ke saath, koi bhi program arbitrarily fast banaya ja sakta hai."

False — Amdahl mein denominator

f + \frac{1 - f}{n}

kabhi bhi

f

se neeche nahi jaata, isliye

S (n) \leq 1/ f

;

f = 0.2

ke saath aap chahe kitne bhi cores lagao,

5 \times

se aage nahi ja sakte.

TF2. "Amdahl aur Gustafson ek doosre se contradict karte hain."

False — wo alag-alag sawaalon ka jawab dete hain (strong vs weak scaling). Amdahl problem size fix karta hai, Gustafson time fix karta hai aur problem badhata hai; dono apni-apni assumptions ke liye sahi hain.

TF3. "Agar

f = 0

ho, toh Amdahl's speedup

n

ke barabar hoti hai."

True —

f = 0

substitute karo:

S (n) = \frac{1}{0 + ( 1 - 0 ) / n} = \frac{1}{1/ n} = n

; koi serial term nahi hone ki wajah se denominator purely

1/ n

hai, isliye speedup exactly linear hai.

TF4. "Agar

f = 1

ho, toh cores add karne se thodi help milti hai."

False —

f = 1

set karo:

S (n) = \frac{1}{1 + 0/ n} = 1

har

n

ke liye; parallel term zero hai, isliye extra cores idle baithe rehte hain aur speedup exactly

1

rehti hai.

TF5. "Gustafson's speedup processors ki sankhya

n

se zyada ho sakti hai."

False —

S (n) = n - f (n - 1)

aur

f \geq 0

isliye subtracted term

\geq 0

hai, jo

S (n) \leq n

deta hai; ye

f \to 0

par

n

ke kareeb jaati hai lekin kabhi nahi paasti.

TF6. "Zyada serial fraction dono laws mein speedup ko hamesha kam karti hai."

True — Amdahl mein bada

f

denominator

f + \frac{1 - f}{n}

ko badhata hai (

f

mein derivative

1 - \frac{1}{n} \geq 0

hai), aur Gustafson mein

- f (n - 1)

zyada subtract karta hai; dono serial work ko punish karte hain.

TF7. "Cores

n

2 n

tak double karne se Amdahl speedup double ho jaati hai."

False — sirf parallel term

\frac{1 - f}{n}

half hokar

\frac{1 - f}{2 n}

banta hai; serial

f

denominator mein jaisa tha waisa rehta hai, isliye speedup badhti hai lekin double se strictly kam, aur har double karne par kam return milta hai.

TF8. "Parallel fraction

(1 - f)

simply serial fraction ka one minus hai, dono time mein measure ki gayi hain."

True — ye same 100% run time ke do hisse hain (

f T_{1}

aur

(1 - f) T_{1}

), isliye by definition inका sum

1

hota hai.

TF9. "Gustafson

f = 0

ke saath exactly linear speedup deta hai."

True —

S (n) = n - 0 \cdot (n - 1) = n

, wahi perfect-scaling endpoint jo Amdahl

f = 0

par reach karta hai; dono laws no-serial extreme par agree karte hain.

TF10. "Agar measured speedup

1/ f

predict karne se kaafi kam hai, toh aapke algorithm ka

f

galat hai."

Aksar spirit mein sahi — real overheads (Cache Coherence traffic, Thread Synchronization waits, communication) aisa time add karte hain jo extra serial fraction ki tarah behave karta hai, isliye effective

f

aapke assumed algorithmic

f

se bada hota hai.

Spot the error

Har statement mein ek flaw chhupa hai — use naam do.

SE1. "Meri 100 functions mein se sirf 3 serially run hoti hain, isliye

f = 0.03

Error hai code ginne mein, time nahi.

f

run-time ka hissa hai; teen tiny functions ek lock ho sakti hain jo 40% clock kha rahi ho, ya teen heavy ones dominate kar sakti hain. Aapko profile karna hoga.

SE2. "Mere paas 8 cores hain isliye mujhe

8 \times

milega."

Ye assume karta hai

f = 0

aur zero overhead. Koi bhi serial slice

f

ko Amdahl ke denominator mein rakhti hai, aur real synchronization plus Load Balancing costs effective speedup ko strictly

8

se neeche push karti hain.

SE3. "Mera problem fixed-size hai, isliye main Gustafson use karke near-linear scaling promise karunga."

Galat law — ek fixed problem strong scaling hai, jo Amdahl ka domain hai. Gustafson assume karta hai ki problem

n

ke saath badhti hai; fixed problem ke liye Amdahl honest cap

1/ f

deta hai.

SE4. "10 cores par

6.9

speedup matlab code broken hai."

Zaruri nahi —

f = 0.05

ke saath, Amdahl deta hai

\frac{1}{0.05 + 0.95/10} \approx 6.9

exactly. Sub-

n

speedup ek serial slice ka normal consequence hai, koi bug nahi.

SE5. "Kyunki Gustafson 100 cores par

90 \times

deta hai, hum original job

90 \times

faster khatam karte hain."

Error hai zyada kaam aur faster ko confuse karna. Gustafson ka

90 \times

ek weak-scaling claim hai — same time mein

90 \times

bada problem — na ki purana problem

1/90

time mein.

SE6. "

f

tab change hota hai jab main 4 cores se 400 cores par switch karta hoon."

Ideal models mein

f

workload ki property hai,

n

vary hote waqt constant rakhte hain (isliye

T_{1}

T_{n}

cancel hota hai). Real overhead effective

f

ko drift karwa sakta hai, lekin textbook laws ise per problem fixed maante hain.

SE7. "Amdahl's denominator

f + \frac{1 - f}{n}

bade

n

ke liye negative ho sakta hai."

Impossible —

f \geq 0

aur

\frac{1 - f}{n} \geq 0

dono, isliye denominator hamesha positive rehta hai aur

f

ki taraf shrink hota hai, kabhi neeche nahi.

Why sawaal

WQ1. Amdahl's speedup se total single-core time

T_{1}

cancel kyun ho jaata hai?

Kyunki

S (n) = T_{1} / T_{n}

aur

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

mein

T_{1}

common factor hai; divide karne par wo remove ho jaata hai, isliye speedup sirf fraction

f

aur

n

par depend karta hai, absolute time par nahi.

WQ2.

n

se divide karte waqt serial term kyun untouched rehta hai?

Serial work dependent steps ki ek chain hai — har step ko previous ka result chahiye — isliye extra workers ke paas karna kuch nahi hota; sirf independent parallel slice

(1 - f) T_{1}

n

se divide hoti hai.

WQ3. Amdahl's law

n \to \infty

par infinity ki jagah

1/ f

kyun approach karta hai?

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

mein term

\frac{1 - f}{n} \to 0

S = 1/ f

bacha rehta hai; fixed serial slice poora remaining runtime ban jaata hai aur hard floor ki tarah act karta hai.

WQ4. Gustafson

T_{1}

ki jagah parallel run time

T_{n}

ke relative kaam measure kyun karta hai?

Kyunki practical situation hai "mere paas

n

cores aur fixed time window hai" — observed quantity

T_{n}

hai, aur hum poochte hain ki wahi kaam akele kitna time leta (

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

), jo

n (1 - f)

inflation produce karta hai.

WQ5. Gustafson ko "optimistic" aur Amdahl ko "pessimistic" kyun kaha jaata hai?

Gustafson (weak scaling) parallel workload ko

n

ke saath badhne deta hai, isliye serial slice shrinking share ban jaati hai aur

S (n) \to n

; Amdahl (strong scaling) workload freeze karta hai, isliye fixed serial slice dominate karta hai aur speedup

1/ f

par cap ho jaati hai.

WQ6. Serial 5% optimize karna zyada cores add karne se better kyun ho sakta hai?

Jab cores plentiful hote hain, Amdahl's speedup

1/ f

ke kareeb pin ho jaati hai;

f

half karne se wo ceiling directly double ho jaati hai, jabki cores add karne se

\frac{1 - f}{n}

zero ki taraf sirf diminishing return ke saath jaata hai. Dekhein Scalability Analysis.

WQ7. Communication aur Cache Coherence traffic real speedup ko dono laws se worse kyun banate hain?

Dono ideal laws assume karte hain ki parallel part perfectly aur free mein divide hota hai; real cores ko data exchange karna, cache lines invalidate karna, aur barriers par wait karna padta hai, jo extra serial fraction ki tarah behave karne wala time add karta hai. Track karo via Performance Metrics.

WQ8. GPU Computing Gustafson ki mindset mein itna well kyun fit hota hai?

GPUs bahut bade data-parallel problems (millions of pixels/particles) attack karke jeette hain — aap problem ko hardware ke hisaab se scale karte ho, exactly Gustafson's weak-scaling assumption, na ki ek chhoti fixed task ko race karte ho.

Edge cases

EC1.

n = 1

par Amdahl's speedup kya hoti hai?

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

— ek processor baseline hai, isliye by construction speedup exactly

1

hoti hai.

EC2.

n = 1

par Gustafson's speedup kya hoti hai?

S (1) = 1 - f (1 - 1) = 1 - 0 = 1

— ye bhi exactly

1

, isliye dono laws sahi agree karte hain ki single processor koi speedup nahi deta.

EC3. Dono laws

f = 0

par — kya hota hai aur kya wo agree karte hain?

Amdahl deta hai

\frac{1}{0 + 1/ n} = n

, Gustafson deta hai

n - 0 = n

; koi serial work nahi hone par dono perfect linear speedup par collapse ho jaate hain, isliye laws is extreme par coincide karte hain.

EC4. Dono laws

f = 1

par — kya hota hai?

Amdahl deta hai

\frac{1}{1 + 0} = 1

; Gustafson deta hai

n - [1 \cdot (n - 1)] = n - (n - 1) = 1

; ek fully serial job ko dono frameworks mein speed up nahi kiya ja sakta, phir se agree karte hain.

EC5.

S (n) < 1

ka matlab kya hota hai, aur kya ideal formulas ye produce kar sakte hain?

S (n) < 1

matlab parallel version serial se slower hai — ek real "slowdown" jab overhead kaam ko daba deta hai; ideal

\frac{1}{f + ( 1 - f ) / n}

aur

n - f (n - 1)

kabhi

1

se neeche nahi jaate, isliye ye dekhna real-world costs ka signal hai jo models omit karte hain.

EC6.

n \to \infty

par Gustafson's speedup kya karta hai?

Ye bina bound ke badhta hai kyunki

S (n) = n - f (n - 1) \approx n (1 - f)

— slope

(1 - f)

ki seedhi line — kyunki problem badhti rehti hai, unlike Amdahl jo

1/ f

par flat-line karta hai.

EC7. Agar ek job truly embarrassingly parallel hai (

f \approx 0

) lekin aap 8 cores par sirf

5 \times

observe karte ho, toh culprit kya hai?

Algorithmic

f

near zero hai, isliye loss effective serial overhead se aana chahiye — poor Load Balancing, synchronization stalls, ya memory bandwidth limits — jo effective

f

ko us value ki taraf inflate karte hain jo

\frac{1}{f + ( 1 - f ) /8} = 5

solve karta hai, roughly

f \approx 0.086

EC8. Do programs dono ke

f = 0.1

hain lekin ek 1 ms run karta hai aur doosra 1 ghanta — kya dono same

n

par Amdahl speedup paate hain?

Haan — Amdahl sirf

f

aur

n

par depend karta hai (absolute time cancel ho jaata hai), isliye dono same

S (n)

tak pahunchte hain; practically 1 ms job fixed launch overhead se dominate ho sakti hai jo model ignore karta hai.