Foundations — Amdahl's Law and Gustafson's Law

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

Pehle tumhe parent note ka ek bhi line padhne se pehle har symbol ko kama na padega. Neeche, har symbol us order mein aata hai jis order mein woh pichle par build karta hai. Hum koi bhi letter use nahi karte jab tak uska seedha matlab aur ek picture na ho.

1. Work aur time — ek job ki picture

Ek job ko ek lamba horizontal bar samjho. Bar ki length yeh batati hai ki kaam kitna time leta hai. Us length ka ek naam hai.

Hum do specific times ki parwah karte hain, isliye hum $T$ ke neeche ek chhota number likhte hain (subscript).

Do naam kyun chahiye? Kyunki "speedup" (abhi aayega) unke beech ek comparison hai. Tum ek cheez ko khud se compare nahi kar sakte — tumhe $T_1$ aur $T_n$ dono chahiye.

2. Processors — $n$ kya count karta hai

Whole number kyun, fraction kyun nahi? Aadha processor nahi ho sakta. Lekin formulas mein hum phir bhi $n$ ko unbounded grow karne dete hain yeh poochne ke liye "absolute ceiling kya hai?" — yahi $n\to \infty$ notation hai, padho "as $n$ goes to infinity."

3. Bar ko kaatna — serial fraction $f$

Yahi sab kuch ka dil hai. $T_1$ bar lo aur use do rangeen tukdon mein kaato.

Ab hum measure karte hain ki bar ka kitna proportion coral hai. Woh proportion is topic ka sabse important symbol hai.

Kyunki poora bar $1$ hai (yaani $100\%$) aur coral part $f$ hai, mint part jo bacha woh hona chahiye:

$1-f$ kyun likhte hain instead of ek naye letter jaise $p$ ke? Kyunki woh hamesha $1$ mein add hote hain, unhe do alag letters dena yeh chhupa deta ki woh ek hi bar ke do halon hain. Ek letter $f$ poori kahani bata deta hai.

4. Mint piece ko kaatna — $n$ se divide karna

Jab $n$ workers parallel (mint) kaam share karte hain, har ek $\frac{1}{n}$ karta hai, toh woh $n$ guna jaldi khatam hota hai.

Serial part shrink kyun nahi karta? Kyunki "serial" ki definition hi yahi hai ki woh kaam split nahi ho sakta. Use $n$ se divide karna uski apni definition ke against hoga. Yahi zidd i coral floor Amdahl's Law mein ceiling ka poora reason hai.

5. Speedup — ratio $S(n)$

Ab hum finally dono bars compare karte hain. "Kitne guna tez?" ek ratio hai.

Ratio kyun, $T_1-T_n$ jaisa difference kyun nahi? Difference seconds mein hota hai aur job size par depend karta hai. Ratio ek pure number hai — "2.5×" ka matlab same hai chahe job milliseconds mein lage ya hours mein. Yahi portability reason hai ki performance hamesha speedup mein quote ki jaati hai.

6. Limit symbol — ceiling dhundhna

Infinity ki parwah kyun karte hain jab koi computer ke paas infinite cores nahi hain? Kyunki yeh hard ceiling reveal karta hai. Agar $f=0.1$ hai, toh kitna bhi hardware $10\times$ se zyada kabhi nahi de sakta. Ceiling jaanna tumhe un cores par paise waste karne se rokta hai jo help nahi kar sakte.

7. Gustafson ka rearrangement padhna

Gustafson ka formula $S(n)=n-f(n-1)$ same symbols use karta hai lekin naye shape mein. Har piece already defined hai:

• $n$ — processors (Section 2),
• $f$ — serial fraction (Section 3),
• $n-1$ — padho "one fewer than $n$"; yeh isliye aata hai kyunki Gustafson scale par parallel work (jo $n$ guna bada hai) ko ek worker ke sab kuch karne se compare karta hai.

Prerequisite map

Baayein har box solid hona chahiye pehle ki topic (daayein taraf) samajh aaye. Agar koi bhi baayaan box fuzzy hai, uska section upar dobara padho.

Related deep material jab ready ho: Performance Metrics, Scalability Analysis, Parallel Architectures, Load Balancing, Thread Synchronization, Cache Coherence, aur GPU Computing.

Equipment checklist

Khud test karo — daayein taraf chhupao aur zor se jawab do.