Flynn's taxonomy (SISD - SIMD - MIMD): Exercises — Hinglish deep dive

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

Yeh page ek self-test ladder hai. Har rung pichle se harder hai. Solution cover karo, problem try karo, phir reveal karo. Agar koi word ya symbol naya lage, toh hum usse zero se build karenge pehle use karne se.

Quick vocabulary jo tumhe chahiye hogi (sab parent Flynn's taxonomy (SISD - SIMD - MIMD) se):

Charon boxes bas do yes/no questions hain — "ek ya bahut saari instructions?" aur "ek ya bahut saare data streams?" — inko cross karo. Yeh grid hai taaki tum sab charon ek nazar mein dekh sako use karne se pehle:

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

Grid padhna: horizontal axis instruction question hai (Single baayi taraf, Multiple daayein); vertical axis data question hai (Single neeche, Multiple upar). Charon cells mein se har ek ek architecture hai. Top-left / bottom-right diagonal note karo: SISD (plain serial CPU) aur MIMD (bahut saare full cores) do "everyday" machines hain; SIMD (top-left column, many data) vector/GPU box hai; MISD (bottom-right, greyed) woh rare theoretical box hai jiske liye hum speedup formulas nahi banayenge.

Level 1 — Recognition

Exercise 1.1

Har machine ko SISD, SIMD, MISD, ya MIMD classify karo: (a) Ek Arduino Uno ek loop chala raha hai. (b) Ek GPU ek add instruction se do 1024-element arrays add kar raha hai. (c) Ek 8-core desktop ek saath browser, music player, aur compiler chala raha hai. (d) Chaar flight computers har ek ek alag safety algorithm usi sensor reading par chala rahe hain, answer par vote kar rahe hain.

Recall Solution

Hum kya dekhte hain: instruction streams count karo (kitne alag programs) aur data streams (kitne independent data items).

(a) Ek program, ek data item at a time → SISD.
(b) Ek add instruction 1024 data pairs par broadcast → SIMD.
(c) Kai cores, har ek ka apna program aur data → MIMD.
(d) Bahut saari alag instructions, lekin sab usi ek data stream par kaam karte hain → MISD (woh rare, mostly theoretical box — yahan uski ek real niche mein, fault-tolerant voting).

Exercise 1.2

Blanks bharo: "S____D means Single Instruction, Multiple Data. Iska speedup ____-level parallelism se aata hai, ____-level parallelism se nahi."

Recall Solution

SIMD.
Data-level parallelism (same op, bahut saara data).
Task-level parallelism nahi (yeh MIMD ka kaam hai).

Exercise 1.3

MISD box (Exercise 1.1(d)) koi time speedup kyun nahi deta, chahe chaar computers ek saath chal rahe hon? Iska point kya hai?

Recall Solution

Speedup kyun nahi: charon computers usi ek data stream ko process karte hain — koi kaam split nahi ho raha, toh job jaldi finish nahi hoti. Speedup $= \frac{baseline time}{accelerated time}$ ke liye accelerated time ko shrink karna chahiye; yahan hota nahi, toh speedup $\approx 1$ . Iska actual point: reliability, speed nahi. Chaar alag algorithms ek input par vote karke ek doosre ke bugs aur hardware faults pakad lete hain (avionics mein use hota hai). Isliye MISD hamari grid par ek niche/theoretical box rehta hai — yeh safety kharidta hai, performance nahi, toh neeche wale speedup formulas iske liye apply nahi hote.

Level 2 — Application

Exercise 2.1

Ek SISD CPU ek 16-element array add karta hai. Ek ADD mein $T = 2 ns$ lagta hai. Total kitna time lagega? (Yahan $N$ = data items ki sankhya = 16.)

Recall Solution

$N \cdot T$ kyun? SISD mein har add, agle se pehle finish hona chahiye (chalte sum ka pichle result par dependency hai), toh times add up hote hain. $T_{SISD} = N \cdot T = 16 \times 2 ns = 32 ns .$

Exercise 2.2

Ek SIMD unit mein 4 lanes hain. Woh usi 16-element array ko add karta hai (independent adds, koi running dependency nahi). Ek broadcast add mein $T = 2 ns$ lagta hai. Kitne broadcasts honge, aur total time aur speedup kya hoga?

Recall Solution

Step — kitne broadcasts? Har broadcast ek saath 4 lanes handle karta hai.

Figure padhna: baayi taraf chaar rows 4 lanes hain (green label) — parallel hardware channels. 16 numbered blue tiles data items 0–15 hain; yeh 4 columns mein pack hain, aur har column ek broadcast hai. Har column ke upar orange arrow ek instruction ko us column ke charon lanes par ek saath fire hote dikhata hai. Toh picture dikhati hai kyun 16 items exactly 4 broadcasts of 4 lanes each ban jaate hain.

broadcasts = ⌈ 16/4 ⌉ = 4.

(Upar define ceiling symbol use karte hue:

16/4 = 4.0

exactly, toh round up karne par

4

hi rehta hai.) Step — total time. Har broadcast

T

cost karta hai:

4 \times 2 ns = 8 ns

. Step — speedup (baseline SISD time over accelerated SIMD time):

Speedup = \frac{T _{SISD}}{T _{SIMD}} = \frac{32}{8} = 4.

Yeh lane count ke barabar hai — exactly wahi jo hum expect karte hain jab data evenly divide ho jaata hai.

Exercise 2.3

Wahi 4-lane SIMD unit, lekin ab 18 elements hain. Kitne broadcasts? Last broadcast mein kitne fraction lanes waste honge?

Recall Solution

Ceiling kyun? 18, 4 se divide nahi hota, toh hume ek partial final group chahiye. Yaad karo $⌈ x ⌉$ upar round karta hai. $⌈ 18/4 ⌉ = ⌈ 4.5 ⌉ = 5 broadcasts .$ Last broadcast mein sirf $18 - 4 \times 4 = 2$ items hain, $4 - 2 = 2$ lanes idle rehte hain. Us broadcast ka wasted fraction $= 2/4 = 0.5 = 50%$ .

Level 3 — Analysis

Exercise 3.1

Ek program 90% parallelizable hai ( $P = 0.9$ ). Amdahl's Law kehta hai (yahan $N$ = cores ki sankhya) $S (N) = \frac{1}{( 1 - P ) + \frac{P}{N}} .$ $N = 4$ cores aur $N = \infty$ cores ke saath speedup compute karo.

Recall Solution

Har piece ka matlab: $1 - P = 0.1$ serial part hai jo kabhi speed up nahi hota; $P / N$ parallel part hai jo cores badhne par shrink hota hai. $N = 4$ : $S (4) = \frac{1}{0.1 + \frac{0.9}{4}} = \frac{1}{0.1 + 0.225} = \frac{1}{0.325} \approx 3.077.$ $N \to \infty$ : term $P / N \to 0$ , toh $S (\infty) = \frac{1}{1 - P} = \frac{1}{0.1} = 10.$ Infinite cores ke saath bhi tum $10 \times$ se aage nahi ja sakte — serial 10% ek hard ceiling hai.

Exercise 3.2

Neeche ka curve $P = 0.9$ ke liye Amdahl's speedup $S (N)$ ko core count $N$ ke against plot karta hai. Pehle figure study karo, phir jawab do: zyaada cores add karne par ek point ke baad almost kuch kyun nahi milta?

Jawab dene se pehle figure padhna: horizontal axis $N$ = cores ki sankhya hai; vertical axis speedup $S (N)$ hai. Blue curve $P = 0.9$ ke liye $S (N)$ hai. Orange dot hamara $N = 4$ answer mark karta hai ( $\approx 3.08$ ). Red dashed horizontal line ceiling $1/ (1 - P) = 10$ hai. Notice karo blue curve pehle steeply rise karta hai, phir bend ho jaata hai aur red line se chipak jaata hai bina kabhi touch kiye.

Recall Solution

Kyun flatten hona zaroori hai: pehle ke cores runtime ka ek bada chunk remove karte hain; baad ke cores already-tiny parallel remainder ko shave karte hain jabki fixed serial slice $(1 - P)$ untouched rehta hai. Algebra mein, $P / N \to 0$ as $N$ grows, toh $S (N) \to 1/ (1 - P)$ — constant serial term dominate karta hai aur curve us ceiling par level off hota hai. Orange dot ( $N = 4$ ) already red ceiling ka roughly ek-tehai tak pahunch chuka hai; 8 cores pe double karne se barely kuch hota hai, jo exactly woh flattening hai jo picture dikhati hai.

Exercise 3.3

Do designs ek fixed job finish karte hain:

Design A: 8-lane SIMD, program 100% data-parallel.
Design B: 8-core MIMD, program sirf 60% parallel ( $P = 0.6$ ). Kaun faster hai (higher speedup)? Kitna zyaada?

Recall Solution

SIMD (A): 100% parallel, 8 lanes → ideal speedup $= 8$ (yeh $P = 1$ edge case hai: $S = N$ ). MIMD (B): $S (8) = \frac{1}{0.4 + \frac{0.6}{8}} = \frac{1}{0.4 + 0.075} = \frac{1}{0.475} \approx 2.105.$ A jeet ta hai, aur $8/2.105 \approx 3.80 \times$ yahan B se faster hai.

Level 4 — Synthesis

Exercise 4.1

Tumhe 1000 identical particles render karne hain (har ek par same physics equation) aur ek AI opponent (bilkul alag algorithm) chalana hai. Kaun sa architecture kis part ke liye, aur kyun?

Recall Solution

Particles: 1000 data items par same instruction → SIMD (ek GPU). Yeh textbook data parallelism hai. AI opponent: ek distinct algorithm, unrelated instructions → isko apna khud ka MIMD core do (ek CPU thread). Real systems dono karte hain: MIMD CPU cores kaam dispatch karte hain, jinmein se ek SIMD GPU drive karta hai. Dono classifications rivals nahi hain; yeh stack hote hain.

Exercise 4.2

Ek job ek core par 100 ms mein chalti hai. Uska 30 ms stubbornly serial hai. Sabse bada $P$ kya hai, aur $N \to \infty$ par best possible speedup kya hai?

Recall Solution

Symbols ke baare mein note: yahan baseline runtime ko normalize karke $1$ karna convenient hai. Hum us normalized whole ko $T_{0} = 1$ kehte hain (ek fresh symbol — ise vocabulary se $T$ , single-operation time, se confuse mat karo). $T_{0}$ ke fractions phir parallel/serial shares hain. $P$ find karo: parallel time $= 100 - 30 = 70$ ms, toh $P = \frac{70}{100} = 0.7, 1 - P = 0.3.$ Ceiling: $S (\infty) = \frac{1}{1 - P} = \frac{1}{0.3} \approx 3.33.$ Kitna bhi hardware ho, $100/3.33 \approx 30$ ms se tez finish nahi hoga — serial 30 ms floor hai.

Level 5 — Mastery

Exercise 5.1

Design target: ek workload ko exactly $5 \times$ speed up karna. Measurement dikhata hai $P = 0.85$ . (a) Kya $5 \times$ reachable bhi hai? (b) Agar haan, toh kitne cores $N$ chahiye?

Recall Solution

(a) Pehle ceiling check. $S (\infty) = 1/ (1 - 0.85) = 1/0.15 \approx 6.67$ . Kyunki $5 < 6.67$ , target reachable hai. (b) $N$ ke liye Amdahl solve karo given $S (N) = 5$ . Hum $N$ ko ek-ek motivated step mein isolate karte hain: $5 = \frac{1}{0.15 + \frac{0.85}{N}} .$ Step 1 — dono sides flip karo. 5 ka speedup matlab neeche ka bracket $1/5$ ke barabar hona chahiye; fraction invert karna bas yeh padhta hai "agar whole 5 hai, toh part one-fifth hai." Toh $0.15 + \frac{0.85}{N} = \frac{1}{5} = 0.2.$ Step 2 — serial term alag karo. Fixed $0.15$ (serial slice) cores se affect nahi hota, toh hum ise side mein rakhte hain taaki dekh sakein parallel term ka kya contribute karna chahiye: $\frac{0.85}{N} = 0.2 - 0.15 = 0.05.$ Step 3 — $N$ solve karo. Parallel kaam $0.85$ ko $0.05$ tak squeeze karna hai, aur $N$ squeeze factor hai, toh $N = 0.85/0.05$ : $N = \frac{0.85}{0.05} = 17.$ Tumhe 17 cores chahiye. (Kam hoge toh target miss hoga; yeh exact break-even hai.)

Exercise 5.2

Combined machine: ek program apna 40% time ek SIMD-friendly loop mein spend karta hai (8 lanes, ideal), 40% MIMD-parallel tasks mein 4 cores par ( $P = 1$ us part ke andar), aur 20% purely serial hai. Poore serial baseline ko normalized time $T_{0} = 1$ lo. Total speedup find karo.

Recall Solution

Idea — har slice ko apne factor se shrink karo, phir times add karo. (Sab slices normalized baseline $T_{0} = 1$ ke fractions hain; yeh $T_{0}$ ek fresh normalization symbol hai, single-operation time $T$ nahi.)

Serial slice: $0.20$ , speedup 1 → time $0.20$ .
SIMD slice: $0.40$ , speedup 8 → time $0.40/8 = 0.05$ .
MIMD slice: $0.40$ , speedup 4 → time $0.40/4 = 0.10$ . Naya total time $= 0.20 + 0.05 + 0.10 = 0.35$ . Overall speedup $= \frac{1}{0.35} \approx 2.857$ (baseline time $T_{0} = 1$ over accelerated time $0.35$ ). Serial 20% leftover time dominate karta hai — Amdahl ka lesson teen streams tak generalize hua.

Recall Ek-line self-check

Woh kaun si single quantity hai jo har MIMD speedup ko cap karti hai chahe kitne bhi cores hon? ::: Serial fraction $1 - P$ ; ceiling $1/ (1 - P)$ hai.