VLIW architectures: Worked examples — Hinglish deep dive

5.3.13 · D3 · Hardware › Advanced Microarchitecture › VLIW architectures

Yeh page VLIW architectures ka "har scenario" workbook hai. Parent note ne aapko machine aur do scheduling formulas di thi. Yahan hum unhe use karte hain, ek-ek worked case ke saath, jab tak koi bhi situation aapko surprise na kar sake.

Har cheez usi same 4-slot machine pe chalti hai jo parent note mein thi:

Kisi bhi formula se pehle, teen plain-word ideas jo parent ne use ki thi lekin ab hum unhe earn karenge:

Figure dekho: teen iterations ek doosre ke upar rakhi hain, har ek II cycles se neeche shift ki gayi hai. Chhota II = tightly overlapped = fast. Hamara poora kaam sabse chhota legal II dhundhna hai.

The scenario matrix

Har scheduling question jo aapse pucha ja sakta hai, in cells mein se kisi ek mein aata hai. Neeche ke examples us cell ke label ke saath hain jo woh cover karte hain, aur saath milkar yeh saari cells cover karte hain.

#	Cell (kya cheez use alag banati hai)	Kya cheez answer force karti hai	Example
A	Resource-bound, ek scarce unit	1 port ke liye bahut zyada memory ops	Ex 1
B	Recurrence-bound, dependency cycle dominate karta hai	ek value next iteration ko feed karti hai	Ex 2
C	Tie: ResMII = RecMII	dono bounds equal hain	Ex 3
D	Degenerate: koi loop-carried dependency nahi (`Dist = 0`)	RecMII undefined → resource decide karta hai	Ex 4
E	Zero parallelism: pure dependent chain (straight-line)	II / slot-count collapse ho jaata hai	Ex 5
F	Limiting case: zyada ALUs add karo — kab fark padna band hota hai?	resource ceiling saturate ho jaata hai	Ex 6
G	Real-world word problem: DSP filter tap	English → resources mein translate karo	Ex 7
H	Exam twist: ek "free" NOP-hiding trap	slot count ≠ throughput	Ex 8

Do tools jinka hum sahara lete hain, words mein phir se batate hain:

Example 1 — Cell A: ek memory port bottleneck hai

Worked example Array add, memory-bound

Loop body per iteration chahiye: 2 loads + 1 store (memory), 1 add (integer). Machine: 1 memory port, 2 integer ALUs, koi dependency iterations cross nahi karti. $II_{m i n}$ nikalo.

Forecast: Abhi guess karo — ALUs ya memory port pace set karegi?

Step 1 — Memory uses count karo. $u_{mem} = 2 + 1 = 3$ ops, aur $c_{mem} = 1$ port. Yeh step kyun? ResMII har resource se poochta hai "tumhe personally kitne cycles chahiye?" $⌈ 3/1 ⌉ = 3 cycles$

Step 2 — ALU uses count karo. $u_{alu} = 1$ add, $c_{alu} = 2$ ALUs. Yeh step kyun? Same sawaal, doosra resource. $⌈ 1/2 ⌉ = 1 cycle$

Step 3 — Max lo. $ResMII = max (3, 1) = 3$ . Yeh step kyun? Sabse slow resource sab kuch gate karta hai — aap next iteration tab tak shuru nahi kar sakte jab tak sabse busy unit free na ho.

Step 4 — Koi loop-carried dependency nahi, toh $RecMII = 0$ (koi cycle exist nahi karti). Yeh step kyun? Har iteration ek fresh c[i] likhti hai; kuch bhi last iteration ka wait nahi karta.

Step 5 — Combine karo. $II_{m i n} = max (3, 0) = 3$ .

Verify: 3 memory ops, 1 port → kam se kam 3 cycles chaahiye chahe ALUs idle baithe rahein. Parent ke "one memory op per cycle" statement se match karta hai. ✓

Example 2 — Cell B: ek dependency cycle pace set karta hai

Worked example Accumulator recurrence

sum = sum + a[i] har iteration. Add sum read karta hai aur sum likhta hai, toh iteration i ko iteration i−1 ka sum chahiye. Add latency = 3 cycles, iteration distance = 1. Resources per iteration: 1 load, 1 add — dono plentiful. $II_{m i n}$ nikalo.

Forecast: Load sasta hai. Kya isse loop fast ho jaata hai?

Step 1 — ResMII. Memory: $⌈ 1/1 ⌉ = 1$ ; ALU: $⌈ 1/2 ⌉ = 1$ → $ResMII = 1$ . Yeh step kyun? Resources abundant hain, toh woh bottleneck nahi ho sakte.

Step 2 — Dependency cycle dhundho. sum → add → sum (next iteration). Ek edge, latency 3, distance 1. Yeh step kyun? RecMII tabhi exist karta hai jab koi value iterations ke across khud pe loop back karti ho.

Step 3 — RecMII apply karo. $RecMII = ⌈ Lat / Dist ⌉ = ⌈ 3/1 ⌉ = 3$ Yeh step kyun? Aap literally next add tab tak shuru nahi kar sakte jab tak previous add ka 3-cycle result ready na ho.

Step 4 — Combine karo. $II_{m i n} = max (1, 3) = 3$ .

Verify: Infinite ALUs ke saath bhi, chain adds ke beech 3 cycles force karti hai. Bottleneck hardware se algorithm ke math mein shift ho gaya. ✓

Figure Ex 1 aur Ex 2 ko contrast karta hai: same II = 3, lekin ek hardware ki wall hai (memory port), doosra dependencies ki rope (recurrence). Same number, bilkul alag cause.

Example 3 — Cell C: exact tie

Example 4 — Cell D: degenerate, `Dist = 0`

Worked example Bilkul koi loop-carried dependency nahi

Loop: c[i] = a[i] * 2. Ek load, ek store, ek multiply — koi bhi iterations cross nahi karta. RecMII kya hai, aur $II_{m i n}$ kya set karta hai?

Forecast: Kya RecMII yahan defined bhi hai?

Step 1 — Cycle dhundho. Koi nahi hai — har arrow ek hi iteration ke andar point karta hai. Yeh step kyun? RecMII ka formula $Dist (C)$ se divide karta hai; koi cycle na ho toh divide karne ko kuch nahi, toh hum $RecMII = 0$ set karte hain (yeh koi constraint impose nahi karta). Mistake guard: $Dist = 0$ matlab zero se divide karna hoga — yeh sirf within-iteration chain ke liye hota hai, jo recurrence nahi hai aur simply exclude ki jaati hai.

Step 2 — ResMII decide karta hai. Memory: 1 load + 1 store $= ⌈ 2/1 ⌉ = 2$ ; ALU: $⌈ 1/2 ⌉ = 1$ . $ResMII = 2$ .

Step 3 — Combine karo. $II_{m i n} = max (2, 0) = 2$ .

Verify: Koi recurrence nahi, toh throughput purely ek resource story hai. 1 port pe 2 memory ops → 2. ✓

Example 5 — Cell E: zero parallelism (straight-line chain)

Worked example Fibonacci-style dependent chain (koi loop overlap nahi)

Teen ops, har ek ko pichle wale ka result chahiye (latency 1 each): MOV r3,r1 → ADD r1,r1,r2 → MOV r2,r3. Yeh loop nahi hai — bas ek straight chain hai. Kitne cycles, aur slot utilisation kya hai?

Forecast: Hamare paas 4 slots per cycle hain — kya yeh 3 ops ek cycle share kar sakte hain?

Step 1 — Chain length. Har op pichle wale pe wait karta hai → 3 sequential cycles. Yeh step kyun? Dependencies overlap forbid karti hain; parallel slots serial kaam mein help nahi kar sakte.

Step 2 — Slots offered. 3 instructions × 4 slots = 12 slots. Step 3 — Slots used. 3 real ops. $Utilisation = \frac{3}{12} = 0.25 = 25%$ Yeh step kyun? Yeh parent se "code density efficiency" idea hai, concrete banaya gaya.

Verify: Parent ke Fibonacci example se exactly match karta hai: 25% slot use, baaki 9 slots NOPs hain. VLIW parallelism expose karta hai; woh use invent nahi kar sakta. ✓

Example 6 — Cell F: limiting behaviour, ALUs tab tak add karo jab tak kaam na kare

Worked example Kितने ALUs ke baad ResMII saturate hota hai?

Loop body: 4 independent adds + 1 load. Memory: 1 port. Poochho: jaise hum ALU count $c$ ko 1 → 5 tak badhate hain, ResMII ka behaviour kaisa hoga?

Forecast: Kya ALUs double karne se speed hamesha double hoti rahegi?

Step 1 — ALU term as a function of $c$ . $⌈ 4/ c ⌉$ . Step 2 — Memory term (fixed). $⌈ 1/1 ⌉ = 1$ . Step 3 — $ResMII = max (⌈ 4/ c ⌉, 1)$ tabulate karo:

ALUs $c$	$⌈ 4/ c ⌉$	ResMII
1	4	4
2	2	2
4	1	1
5	1	1

Yeh step kyun? Poora range dekhne se limit reveal hoti hai, sirf ek point nahi.

Step 4 — Limit padho. Jab $c \geq 4$ ho jaata hai, ALU term 1 pe aa jaati hai aur memory port (=1) control le leta hai. 4 se zyada ALUs zyada karne se zero additional speedup milta hai.

Verify: $lim_{c \to \infty} ⌈ 4/ c ⌉ = 1$ ; ResMII $max (1, 1) = 1$ pe floor karta hai. Hardware ka ek saturation point hota hai — classic VLIW "resource ceiling." ✓

Curve flatten hoti hai: har extra ALU kam help karta hai, phir bilkul nahi jab memory wall ban jaati hai.

Example 7 — Cell G: real-world word problem (DSP filter)

Worked example Ek 4-tap FIR filter

Ek audio filter har output ko y = a·x0 + b·x1 + c·x2 + d·x3 ke roop mein compute karta hai. Har output ke liye: 4 multiplies, 3 adds (compute), aur 5 memory ops (4 coefficient loads + 1 result store; x samples registers mein hain, har iteration shift hote hain). Multiply latency 2, distance 1 shift chain ke through. Memory: 1 port. Multiplies 2 integer/mult ALUs use karte hain. $II_{m i n}$ nikalo.

Forecast: Compute-heavy aur memory-heavy — kaun dominate karta hai?

Step 1 — English ko counts mein translate karo. memory $u = 5$ , mult+add $u = 4 + 3 = 7$ on 2 ALUs. Yeh step kyun? Word problems 90% translation hain; pehle counts sahi karo.

Step 2 — ResMII. Memory: $⌈ 5/1 ⌉ = 5$ . ALU: $⌈ 7/2 ⌉ = 4$ . $ResMII = max (5, 4) = 5$ .

Step 3 — RecMII. Sample-shift chain: ek shift next iteration ko feed karti hai, latency 2, distance 1 → $⌈ 2/1 ⌉ = 2$ .

Step 4 — Combine karo. $II_{m i n} = max (5, 2) = 5$ .

Verify: Single memory port (5 accesses) ek compute-rich kernel dominate karta hai. Real DSP chips iska jawab multiple memory ports add karke dete hain — exactly wahi fix jo Ex 3/6 ne predict ki thi. ✓

Example 8 — Cell H: exam trap

Worked example "8 slots, toh 8× faster?" — jhooth pakdo

Ek vendor machine ko 8 slots tak double kar deta hai lekin 1 memory port rakhta hai. Aapke loop ko per iteration 4 memory ops aur 2 adds chahiye. Kya II Example-1-style values se drop hoga?

Forecast: Zyada slots — zaroor faster hoga?

Step 1 — Memory term. $⌈ 4/1 ⌉ = 4$ . Slot count se unchanged! Yeh step kyun? Slots decode width hain; woh memory ports nahi add karte.

Step 2 — ALU term. Ab 4 ALUs ke saath: $⌈ 2/4 ⌉ = 1$ . Step 3 — Combine karo. $II_{m i n} = max (4, 1) = 4$ .

Step 4 — The point. 4 se 8 slots tak widen karne se kuch nahi badla — 1 memory port abhi bhi II = 4 force karta hai.

Verify: Slot count ≠ throughput. Bound scarcest replicated resource set karta hai, exactly jaise ResMII ka $max_{r}$ kehta hai. Yeh sabse common VLIW exam trick hai. ✓

Recall

Recall Koi recurrence na ho toh memory-bound loop mein

$II_{m i n}$ kya set karta hai? Resource bound: $ResMII = ⌈ u_{mem} / c_{mem} ⌉$ ; RecMII 0 hai.

ResMII mein Ceiling isliye aati hai kyunki ::: aap ek unit pe operation ka fraction nahi chala sakte — cycles ko upar round karo. Latency 3, distance 1 wale recurrence ka RecMII hai ::: $⌈ 3/1 ⌉ = 3$ cycles. Zyada ALUs add karna tab kaam karna band karda hai jab ::: ALU term kisi doosre resource ke level tak (jaise memory port) aa jaati hai, jo phir dominate karta hai. Slot count (issue width) throughput ke barabar hai? ::: Nahi — scarcest replicated resource (aksar 1 memory port) true limit set karta hai. $Dist = 0$ wale dependency cycle ka matlab hai ::: code impossible hai (ek op jo same cycle mein khud pe depend karti hai); sahi code yeh kabhi produce nahi karta.