Flynn's taxonomy (SISD - SIMD - MIMD): Worked examples

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

Yeh page Flynn's taxonomy (SISD - SIMD - MIMD) ka drill-room hai. Parent note ne ideas build kiye; yahan hum har tarah ke situation mein ek number push karte hain jo taxonomy throw kar sakti hai — "bas cycles gino" wale friendly case se lekar nasty zero-and-degenerate cases tak (kya ho agar koi task bilkul bhi parallelise na ho sake?), aur limiting case tak (kya ho agar aapke paas infinite cores hon?).

Scenario matrix

Neeche har worked example uss cell ke saath tagged hai jo woh cover karta hai. Saath milke yeh poora grid fill karte hain.

Cell	Case class	Mushkil kya hai	Example
A	SISD baseline	serial, ek instruction, ek datum	Ex 1
B	SIMD ideal	independent data, poora $N \times$	Ex 2
C	SIMD ragged	data count lanes ka multiple nahi	Ex 3
D	SIMD dependency (degenerate)	ek dependency parallelism khatam kar deti hai	Ex 4
E	MIMD task-parallel	har core ka alag code	Ex 5
F	Amdahl, ordinary $P$	mixed serial + parallel	Ex 6
G	Amdahl, $P = 0$ aur $P = 1$ (extremes)	do degenerate fractions	Ex 7
H	Amdahl, $N \to \infty$ (limit)	speedup ki ceiling	Ex 8
I	Real-world word problem	architecture chunna	Ex 9
J	Exam twist	usi array par SIMD vs MIMD	Ex 10

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

Upar board dekho: horizontal axis hai kitne instruction streams (ek vs kai), vertical axis hai kitne data streams. Har example ek region mein jhanda gaadata hai.

Ex 1 — Cell A: SISD baseline

Forecast: aage padhne se pehle total guess karo — kya yeh $2 ns$ hai, $8 ns$ hai, ya kuch aur?

Additions gino. Chaar numbers matlab chaar ADD operations. Yeh step kyun? SISD mein har datum exactly ek instruction se touch hota hai, ek ek karke — kuch bhi overlap nahi hota.
Dependency note karo. Doosre add ke baad sum ko pehle add ka result chahiye. Toh add #2 tab tak shuru nahi ho sakta jab tak add #1 khatam na ho. Yeh step kyun? Yahi cheez serial line force karti hai — yahi wajah hai ki SISD koi speedup nahi deta.
Multiply karo. Total $= N \cdot T = 4 \times 2 ns = 8 ns$ . Yeh step kyun? Koi overlap nahi hone se, times simply add up ho jaate hain.

Verify: chaar cycles $\times 2 ns = 8 ns$ . Units: $[count] \times [ns] = [ns]$ ✓. Sanity: yeh kisi bhi parallel version se slower hona chahiye — aur yeh hamara sabse slow number hai, acha.

Ex 2 — Cell B: SIMD, ideal case

Forecast: agar chaar lanes ek saath ek ek add karte hain, kitne $T$ ka time lagega?

Ek instruction, chaar data. Control unit ek ADD broadcast karta hai; lanes $1..4$ mein se har ek ek datum hold karta hai. Yeh step kyun? Yeh SIMD ki defining move hai — ek instruction stream, chaar data streams.
Saari lanes ek hi cycle mein fire karti hain. Kyunki $10, 20, 30, 40$ independent hain (kisi lane ko doosri lane ka answer nahi chahiye), yeh saath chalti hain. Yeh step kyun? Independence parallelise karne ka licence hai; iske bina hum Ex 4 mein wapas aa jaate.
Time. $T_{SIMD} = T = 2 ns$ .
Speedup. $\frac{T _{SISD}}{T _{SIMD}} = \frac{4 \times 2}{2} = 4$ .

$Speedup = \frac{N \cdot T}{T} = N = 4$

Verify: $8 ns \div 2 ns = 4 \times$ ✓. Sanity: speedup lane count $N = 4$ ke barabar hai, SIMD ka theoretical ceiling — ideal case ke liye sahi.

Ex 3 — Cell C: SIMD ke saath ragged tail

Forecast: $10/4$ poora number nahi hai — kya 2 passes lagenge ya 3?

Ceiling ke saath divide karo. $⌈ 10/4 ⌉ = 3$ passes: lanes elements ${0..3}$ , ${4..7}$ , phir ${8, 9}$ handle karti hain. Yeh step kyun? "Dhai" broadcasts nahi ho sakte — aakhri partial group phir bhi ek poora vector op ka time leta hai.
Teesra pass lanes waste karta hai. Pass 3 mein sirf 4 mein se 2 lanes use hoti hain; baaki 2 kuch nahi karti lekin phir bhi ek cycle burn hoti hai. Yeh step kyun? Yeh woh overhead hai jiske baare mein parent note ne warn kiya tha — real speedup rarely $N \times$ tak pahunchta hai.
Time. $3 \times 2 ns = 6 ns$ .
SISD se effective speedup (jo $10 \times 2 = 20 ns$ hai): $20/6 \approx 3.33 \times$ , nahi $4 \times$ .

Verify: $⌈ 10/4 ⌉ = 3$ ; $3 \times 2 = 6 ns$ ; $20/6 = 3.33 \dots$ ✓. Sanity: $3.33 < 4$ , toh ragged data speedup ko lane count se neeche le aata hai — exactly woh "ragged tail" penalty.

Ex 4 — Cell D: SIMD ko dependency ne haraaya (degenerate input)

Forecast: yeh Ex 2 se same numbers hain — kya SIMD phir bhi $4 \times$ dega?

Dependency spot karo. $b_{2}$ ko $b_{1}$ chahiye; $b_{3}$ ko $b_{2}$ chahiye. Lane 3 tab tak shuru nahi ho sakti jab tak lane 2 khatam na ho. Yeh step kyun? Elements ke beech data dependency Ex 2 step 2 ka "independent" licence chheen leti hai.
Lanes ko ek doosre ka intezaar karna padta hai. Naive broadcast illegal hai — aap woh value read kar rahe ho jo abhi likhi hi nahi gayi. Yeh step kyun? Yeh degenerate case hai: workload structurally lockstep parallelism se inkaar karta hai.
Result. Naively aap SISD-jaisi timing par wapas aa jaate ho: $4 \times 2 = 8 ns$ , speedup $= 1 \times$ (kuch nahi). (Clever "parallel scan" algorithms exist karte hain, lekin baat yeh hai: naive same-instruction trick fail hoti hai.)

Verify: speedup $= 8/8 = 1$ ✓. Sanity: Ex 2 jaisa data, phir bhi speedup $4$ se $1$ par collapse ho gaya — prove karta hai ki speedup dependency structure par depend karta hai, numbers par nahi.

Ex 5 — Cell E: MIMD, genuinely different code

Forecast: teen $30 ms$ kaam — kya wall-clock $90 ms$ hai ya $30 ms$ ?

Streams note karo. Teen alag instruction streams, teen alag data sets ⇒ MIMD. Yeh step kyun? SIMD impossible hai — koi ek common instruction nahi hai broadcast karne ke liye.
Yeh simultaneously aur independently chalte hain. Koi core doosre ka intezaar nahi karta (koi shared result nahi). Yeh step kyun? Task-parallel kaam fully overlap karta hai jab tasks ek doosre par depend nahi karte.
Wall-clock time = sabse lamba single kaam $= 30 ms$ (equal length hone ki wajah se saath khatam hote hain).

Verify: serial $3 \times 30 = 90 ms$ hota; MIMD $30 ms$ deta hai; speedup $90/30 = 3 \times$ ✓. Sanity: core count $3$ ke barabar hai kyunki kaam perfectly independent aur equal-sized hain.

Ex 6 — Cell F: Amdahl's Law, ordinary fraction

Forecast: aapke paas 8 cores hain aur 90% parallel hai — kya aap $8 \times$ ke kareeb pahunchoge?

Parent ka law yaad karo — symbol $S (N)$ ka matlab hai " $N$ cores ke saath kitna zyada fast":

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

Serial part wahin rehta hai. $1 - P = 0.1$ . Kaam ka woh daswaan hissa ek core par chalta hai, chahe kuch bhi ho. Yeh step kyun? Serial kaam woh anchor hai jise expose karne ke liye Amdahl's Law bana hai.
Parallel part $N$ se shrink hota hai. $\frac{P}{N} = \frac{0.9}{8} = 0.1125$ . Yeh step kyun? Parallel kaam ko 8 cores mein split karna uska time 8 se divide kar deta hai.
Add karo aur invert karo. Denominator $= 0.1 + 0.1125 = 0.2125$ ; toh $S (8) = 1/0.2125 \approx 4.71$ .

Verify: $1/ (0.1 + 0.9/8) = 1/0.2125 = 4.705 \dots \approx 4.71 \times$ ✓. Sanity: $8 \times$ se bahut neeche — woh ziddi 10% serial slice ne hamara speedup lagbhag aadha kar diya. Yahi Amdahl's Law ka poora sabak hai.

Ex 7 — Cell G: do degenerate fractions ( $P = 0$ aur $P = 1$ )

Forecast: inme se ek koi speedup nahi deta aur ek maximum deta hai — kaun sa kaun sa hai?

Case $P = 0$ . Denominator $= (1 - 0) + 0/8 = 1$ . Toh $S (8) = 1/1 = 1 \times$ . Yeh step kyun? Agar kuch split nahi ho sakta, extra cores useless hain — honest degenerate result.
Case $P = 1$ . Denominator $= (1 - 1) + 1/8 = 0 + 0.125 = 0.125$ . Toh $S (8) = 1/0.125 = 8 \times$ . Yeh step kyun? Zero serial kaam ke saath, law plain $S (N) = N$ tak reduce ho jaata hai — ideal SIMD/MIMD picture se match karta hai.

Verify: $P = 0 \Rightarrow S = 1$ ; $P = 1 \Rightarrow S = 8$ ✓. Sanity: yeh Amdahl speedup ka floor ( $1$ ) aur ceiling ( $N$ ) hain — har real program strictly inke beech rehta hai.

Ex 8 — Cell H: limit $N \to \infty$

Forecast: unlimited cores — kya speedup infinity tak jaata hai, ya koi wall hit karta hai?

$N \to \infty$ lo. Term $\frac{P}{N} = \frac{0.9}{N} \to 0$ . Yeh step kyun? Parallel kaam ko endless cores mein divide karna uska time zero ki taraf le jaata hai.
Jo bacha woh serial floor hai. $N \to \infty lim S (N) = \frac{1}{1 - P} = \frac{1}{0.1} = 10$ . Yeh step kyun? Serial fraction kabhi speed up nahi ho sakta, toh woh sab kuch cap kar deta hai.

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

Verify: $1/ (1 - 0.9) = 1/0.1 = 10 \times$ ✓. Sanity: infinite hardware bhi yahan sirf $10 \times$ deta hai — serial 10% ek hard ceiling hai. Isliye "bas aur cores add karo" eventually kaam karna band kar deta hai.

Upar ka curve (Ex 6, 7, 8 se) speedup ko dashed ceiling $1/ (1 - P)$ ki taraf flatten hote dikhata hai jaise cores badhte hain — aap iske kareeb jaate ho lekin kabhi cross nahi karte.

Ex 9 — Cell I: real-world word problem (architecture chunna)

Forecast: kya yeh dono SIMD hain? Dono MIMD? Ya ek ek?

Kaam (a): ek operation, laakhon data. Har pixel ko identical "add brightness" instruction milti hai. Yeh step kyun? Ek instruction + kai data ⇒ yeh textbook SIMD (GPU) kaam hai.
Kaam (b): har thread ka alag code. Physics, AI, aur audio unrelated algorithms hain. Yeh step kyun? Multiple instruction streams + multiple data ⇒ MIMD (multicore CPU).

Verify: (a) SIMD, (b) MIMD ✓. Sanity: parent note se match karta hai — "GPUs SIMD hain, modern CPUs MIMD hain."

Ex 10 — Cell J: exam twist

Forecast: dono mein "4-wide" hardware hai — kya yeh tie karenge?

Machine X (SIMD). $⌈ 16/4 ⌉ = 4$ vector ops $\Rightarrow 4 \times 2 = 8 ns$ . Yeh step kyun? Ek broadcast 4 elements handle karta hai; 16 elements ko 4 broadcasts chahiye.
Machine Y (MIMD). Har core $16/4 = 4$ scalar multiplies karta hai, doosron ke saath parallel mein $\Rightarrow 4 \times 2 = 8 ns$ . Yeh step kyun? Cores ek saath chalte hain, toh wall-clock bas ek core ka share hai.
Compare karo. Dono $8 ns$ dete hain — is idealised workload par tie.

Verify: X $= 4 \times 2 = 8$ ; Y $= 4 \times 2 = 8$ ; equal ✓. Sanity: trap yeh sochna hai ki ek ko jeetna chahiye — identical independent operations ke liye, timing mein wide-vs-many distinction gayab ho jaata hai (yeh cost, flexibility, aur instruction-fetch bandwidth mein wapas aata hai, jise parent note discuss karta hai).

Recall Quick self-test

Kisi bhi $N$ par $P = 0$ speedup ke liye kya deta hai? ::: Exactly $1 \times$ — kuch parallel nahi, extra cores useless. $P = 0.9$ ke liye $N \to \infty$ par speedup ki ceiling? ::: $1/ (1 - 0.9) = 10 \times$ . Prefix-sum (Ex 4) ko SIMD speedup kyun nahi mila? ::: Har element pichle par depend karta hai — koi independence nahi, koi lockstep nahi. $4$ lanes par $10$ floats sirf $\approx 3.33 \times$ kyun hai, $4 \times$ nahi? ::: Ragged last pass mein idle lanes waste hoti hain ( $⌈ 10/4 ⌉ = 3$ passes).