Flynn's taxonomy (SISD - SIMD - MIMD): Visual walkthrough

6.1.1 · D2 · Hardware › Parallelism & Multicore › Flynn's taxonomy (SISD - SIMD - MIMD)

Koi bhi letter aane se pehle, ek picture par agree karo: time ek horizontal bar hai. Lamba bar matlab program zyada time leta hai. Kaam ko cores mein split karna matlab bar ke pieces ko end-to-end ki jagah side-by-side stack karna taaki woh sath mein finish ho jayein. Bas yeh ek idea hi baaki sab kuch drive karta hai.

Step 1 — Poore kaam ko ek time ke bar ki tarah draw karo

KYA. Hum ek program ek core (ek worker) par chalate hain. Jo bhi time lagta hai, hum use $T$ kehte hain. Letter $T$ sirf "single-core run kitna lamba chalta hai" yeh name karta hai — kuch nahi.

KYUN. Humein ek fixed reference chahiye. Har speedup isi ek honest run ke against measure hoti hai. Agar hum $T$ pin nahi karte, toh "twice as fast" ka koi matlab nahi.

PICTURE. Ek solid bar. Uski puri length hi $T$ hai. Time left → right flow karta hai.

Figure — Flynn's taxonomy (SISD - SIMD - MIMD)

KYA. Kaam ke andar dekho. Kuch kaam zaroor order mein hona chahiye — ek config file padhna, setup karna, final answer print karna. Total ka jo fraction order mein stuck hai use serial part kehte hain. Baaki — independent data par loops, jaise parent note ke SIMD-style array adds — parallelizable part hai. Hum parallel fraction ko $P$ name karte hain.

KYUN. "Fraction" bas "bar ka kaunsa slice" hai. Agar $P = 0.75$ hai, toh bar ka teen-chauthai hissa cores mein spread ho sakta hai aur ek-chauthai nahi ho sakta. Yeh split hi ek aur ek cheez hai jo answer decide karegi, isliye hum ise pehle visible karte hain.

PICTURE. Wahi bar, ab do colours mein painted: length $(1 - P) T$ ka amber serial chunk aur length $P T$ ka cyan parallel chunk.

Step 3 — Parallel part ko $N$ cores ko do

KYA. $N$ = cores (workers) ki sankhya introduce karo. Hum sirf cyan parallel chunk lete hain aur use $N$ equal slices mein kaat lete hain, phir un slices ko ek saath, ek ke upar ek stack karke chalate hain. Serial amber chunk unchanged rehta hai — woh abhi bhi ek core par akela chalta hai.

KYUN. Yahi ek MIMD machine ka poora promise hai: independent kaam simultaneously hota hai. Independent slices time mein overlap ho sakti hain, isliye side-by-side rakhne par unka finish time bas ek slice ki length hoti hai. Cyan chunk ki ek slice $\frac{P T}{N}$ tak chalti hai: $N$ cores mein divide kiya gaya parallel time $P T$ .

PICTURE. Cyan chunk $N$ chote bars mein fan out hota hai jo vertically stack hain (woh sath chalte hain). Amber chunk unke aage puri length mein rehta hai.

Step 4 — Naya, chota bar wapas banao

KYA. Naya total run time — ise $T_{N}$ kehte hain — wahi hai jo end-to-end bachta hai: serial chunk jo kabhi nahi sika plus squeezed parallel chunk.

KYUN. Cores ne parallel kaam overlap kiya, lekin kuch bhi serial kaam overlap nahi kar sakta tha — ek akele worker ko abhi bhi use grind karna tha. Isliye hum baaki do lengths ko wapas ek bar mein glue karte hain.

PICTURE. Ek chota bar: puri amber serial piece, phir width $P T / N$ ka ek patla cyan stub.

Step 5 — "Chota bar" ko "kitna faster" mein badlo: divide karo

KYA. Speedup $S (N)$ ek ratio question poochta hai: "naya bar purane bar se kitne guna chota hai?" Isliye hum old time ko new time se divide karte hain.

KYUN. Hum division use karte hain subtraction nahi kyunki "twice as fast" ek ratio hai (bar aadha lambe = 2×), seconds mein difference nahi. Ratio wahi hai jiska matlab log "speedup" se lete hain.

$S (N) = \frac{T}{T _{N}} = \frac{T}{( 1 - P ) T + \frac{P T}{N}}$

Har term mein $T$ ka factor hai. Woh common $T$ cancel ho jaata hai — speedup ko parwah nahi ki program kitna lamba hai, sirf yeh ki woh kaise split hai. Top aur bottom dono ko $T$ se divide karo:

Step 6 — Degenerate cases (check karo ki formula kabhi jhooth nahi bolta)

Humein dikhana hoga ki formula har extreme par sahi behave karta hai, taaki koi bhi reader aise scenario se na takraye jise hum skip kar gaye.

Case A — ek core, $N = 1$ . Plug in karo: $S (1) = \frac{1}{( 1 - P ) + P} = \frac{1}{1} = 1$ . Ek core exactly wahi speed deta hai jisse hum shuru hue. Accha — kuch nahi karne se koi free lunch nahi.

Case B — kuch bhi parallel nahi, $P = 0$ . Toh kisi bhi $N$ ke liye $S (N) = \frac{1}{1 + 0} = 1$ . Ek purely serial program har extra core ko ignore karta hai. Bar sab amber hai; zero cyan ko slice karna kuch nahi badalta.

Case C — sab kuch parallel, $P = 1$ . Toh $S (N) = \frac{1}{0 + 1/ N} = N$ . Perfect linear speedup — yahi parent note ka ideal SIMD case hai, jahan $N$ lanes sach mein $N \times$ dete hain.

PICTURE. Teen bars side by side jo yeh limits dikhate hain.

Step 7 — Wall: $N \to \infty$ jaane do

KYA. Cores ki sankhya ko infinity ki taraf push karo. $\frac{P}{N}$ mein, jaise $N$ badhta hai pura term $0$ ki taraf slide karta hai (ek bade number se divide karna). Kya bachta hai?

KYUN. Yeh headline question ka answer deta hai: speedup ke liye paisa kitna zyada khareed sakta hai? Zyada cores sirf $\frac{P}{N}$ term par attack karte hain; woh kabhi $(1 - P)$ ko touch nahi kar sakte.

$lim_{N \to \infty} S (N) = \frac{1}{( 1 - P ) + 0} = \frac{1}{1 - P}$

PICTURE. Jaise cores badhte hain, cyan stub gayab ho jaata hai lekin amber serial block rehta hai — bar ek floor par flatten hoti hai, aur speedup curve $1/ (1 - P)$ height ki ceiling mein bend ho jaata hai.

Ek picture ka summary

Yeh ek figure sab kuch tie karta hai: original bar serial (amber) + parallel (cyan) mein split hoti hai; cores sirf cyan ko squeeze karte hain; serial amber ek hard floor set karta hai; aur speedup curve fast rise karti hai, phir ceiling $1/ (1 - P)$ mein bend ho jaati hai.

Recall Feynman retelling — ise ek story ki tarah bolo

Socho ek fence paint karna hai. Kuch kaam — paint kharidna, tin kholna, clean up karna — tumhe akele, order mein karna hai. Yeh amber part hai; doston ki koi madad nahi ho sakti. Baaki — actual planks brush karna — tum helpers mein split kar sakte ho; yeh cyan part hai. Ek dost lao, dus, hazaar: brushing faster aur faster hoti jaati hai, lekin buying-and-cleanup ka time kabhi nahi badlta. Isliye poora kaam us lonely amber kaam se zyada fast kabhi nahi ho sakta. Amdahl's Law bas us fence ka arithmetic hai: original time ko (stubborn serial slice + parallel slice $N$ pieces mein kata hua) se divide karo, aur chahe kitne bhi dost aa jayein, tum one-over-the-serial-fraction ki ceiling se takrate ho.

Recall Quick self-test

$P = 0.95$ ke saath, cores infinity tak jaane par speedup ceiling kya hai? ::: $1/ (1 - 0.95) = 20 \times$ . Amdahl's Law mein kaunsa term hai jisme $N$ nahi hai, aur yeh kyun matter karta hai? ::: Serial term $(1 - P)$ ; yeh zyada cores ke saath kabhi nahi shrinkta, isliye yeh hard limit set karta hai. Speedup paane ke liye old time ko new time se subtract kyun nahi karte, divide karte hain? ::: Speedup ek ratio hai ("aadha lamba = 2×"), seconds mein difference nahi.

Parent par wapas jao: Flynn's taxonomy (SISD · SIMD · MIMD).