VLIW architectures: Exercises — Hinglish deep dive

5.3.13 · D4 · Hardware › Advanced Microarchitecture › VLIW architectures

Shuru karne se pehle, ek picture hai jo poori page mein reuse hone wali vocabulary fix kar deti hai. Yeh poori page ke liye hai, lekin Level 1 mein sabse directly reference hoti hai.

Upar ki figure kya dikhati hai (Level 1 mein use hoti hai): ek row mein chaar boxes hain — ek VLIW instruction word ke chaar slots — jiske upar ek bracket hai jisme likha hai "one instruction word = one cycle." Memory slot (Slot 2) red mein drawn hai kyunki yahi woh single port hai jo almost har problem mein bottleneck ban jaata hai. Jab bhi solution kehta hai "only one memory op per cycle," yahi picture dimag mein rakho: red box mein zyada se zyada ek load ya store dala ja sakta hai har row mein.

Levels 2–5 kuch loop-scheduling terms par rely karti hain. Hum unhe sabko ek baar, yahan, plain words mein define karte hain, kisi bhi problem mein use hone se pehle.

Definition Loop-scheduling vocabulary (Level 2 se pehle padho)

Jab ek loop ko software-pipelined kiya jaata hai, toh compiler ek nayi iteration har kuch cycles mein start karta hai, chahe pichli khatam na hui ho — bilkul waise jaise runners ek track par ek ke baad ek set off hote hain. Key numbers hain:

Iteration — loop body se ek baar guzarna (i ki ek value).
II (Initiation Interval) — ek iteration launch karne aur agla launch karne ke beech ka cycles ka number. Chhota II = iterations zyada baar start hoti hain = faster loop. Yeh page ka sabse important loop-speed number hai.
Steady state — ek pipelined loop ka middle stretch pipeline fill hone ke baad aur drain hone se pehle, jahan har cycle same dikhti hai aur ek nayi iteration exactly har II cycles mein launch hoti hai. "Steady-state II" bas woh II hai jo us repeating middle region mein measure hota hai (fill/drain edges ignore karke). Yeh woh number hai jo loop ki long-run speed govern karta hai.
MII (Minimum Initiation Interval), $II_{m i n}$ likha jaata hai — sabse chhota legal II. Chahe schedule kitna bhi clever ho, isse faster nahi ja sakte; yeh ek hard floor hai jo hardware aur code set karta hai.
$u_{r}$ ("uses of resource $r$ ") — ek loop iteration mein kitne operations ko resource $r$ chahiye. Example: agar body 4 loads/stores karti hai, toh $u_{mem} = 4$ .
$c_{r}$ ("copies of resource $r$ ") — us resource ke kitne hardware units exist karte hain. Humare machine mein $c_{mem} = 1$ (ek memory port), $c_{ALU} = 2$ (do integer ALUs).
ResMII (Resource-constrained MII) — II par woh floor jo naakafi hardware ki wajah se aata hai. Agar ek resource $u_{r}$ baar per iteration use hota hai lekin sirf $c_{r}$ copies exist karti hain, toh un uses ko kam se kam $⌈ u_{r} / c_{r} ⌉$ cycles mein spread karna hoga.
Recurrence / dependency cycle $C$ — ek loop jahan ek value iterations ke across khud mein feed back karti hai (jaise acc = acc + x, jahan is iteration ka acc pichhli iteration ke acc ki zaroorat hai).
Lat(C) ("latency of cycle $C$ ") — us feedback loop mein ek baar ghoomne mein total cycles (us par ke operations ki latencies ka sum).
Dist(C) ("iteration distance of cycle $C$ ") — feedback kitni iterations peeche tak jaati hai. Agar is iteration ko ek value chahiye jo 2 iterations pehle produce hui thi, toh $Dist (C) = 2$ . Yeh jawaab deta hai "dependence ke do ends iteration-count mein kitne door hain?"
RecMII (Recurrence-constrained MII) — II par woh floor jo algorithm ke khud ke feedback se aata hai, hardware se nahi.

Definition Data-dependence types (Level 4 se pehle padho)

Jab do operations ek hi register touch karte hain, toh unke beech ka order matter karta hai ya nahi bhi kar sakta:

RAW (Read After Write) — ek true dependency: op B woh value read karta hai jo op A pehle write karega (jaise A1 compute karta hai r3, phir A2 reads r3). Order nahi toda ja sakta — data genuinely A→B flow karta hai. Ek "RAW chain" bas aisi true dependencies ki string hai, ek se doosra feed hota hua.
WAR (Write After Read) — ek false (anti-)dependency: B ek register write karta hai jise A ko pehle read karna hai. Name reuse ki wajah se hota hai, renaming se remove kiya ja sakta hai.
WAW (Write After Write) — ek false (output) dependency: A aur B dono ek hi register write karte hain. Yeh bhi name reuse ki wajah se, aur yeh bhi renaming se remove ho sakta hai.

Sirf RAW real ordering force karta hai. VLIW mein compiler ko false WAR/WAW dependencies mitane ke liye registers rename karne padte hain.

Formula Do floors aur hum MAX kyun lete hain

\text{ResMII} = \max_r \left\lceil \frac{u_r}{c_r}\right\rceil, \qquad \text{RecMII} = \max_C \left\lceil \frac{\text{Lat}(C)}{\text{Dist}(C)}\right\rceil.$$ **Maximum kyun, sum ya average kyun nahi?** Har floor ek *alag promise hai jo schedule ko rakhni padti hai*: - ResMII kehta hai "aap physically in operations ko hardware se faster issue nahi kar sakte." - RecMII kehta hai "aap physically ek iteration tab tak start nahi kar sakte jab tak woh data exist nahi karta jis par depend karti hai." Ek legal II ko **dono** promises ek saath satisfy karne honge. Agar ResMII = 4 aur RecMII = 3 hai, toh II = 3 resource promise tod deta hai (ports kaafi nahi), aur II = 4 *dono* promises rakhta hai. Isliye sabse chhota II jo har promise rakhta hai woh dono mein se **bada** hai — exactly yahi "max" matlab hai. Yeh bilkul waisa hai jaise kisi group ka sabse dheema member group ka pace set karta hai: tum sirf apni *sabse restrictive* constraint se fast ja sakte ho, kabhi faster nahi. Sum lena over-counting hoga (constraints parallel mein act karte hain, sequence mein nahi), aur average lena under-counting hoga (tighter wale ko violate karne ki permission dega).

Level 1 — Recognition

L1-Q1

Ek superscalar aur ek VLIW processor dono 4 operations per cycle issue karte hain. Kaunsa hardware contain karta hai jo runtime par discover karta hai ki kaunse operations independent hain?

Recall Solution

Superscalar. Uska out-of-order engine (wakeup/select, reservation stations, register renaming) har cycle mein hardware mein parallelism dhundta hai. VLIW us kaam ko compiler par push karta hai, isliye VLIW hardware sirf pre-packed word execute karta hai bina runtime dependency checking ke.

L1-Q2

Humare 4-slot machine mein, ek single instruction word mein kitne memory (load/store) operations ho sakte hain? Kyun?

Recall Solution

Exactly ek. Ek hi memory port hai (Slot 2). Ek cycle mein do loads ke liye do ports chahiye hote jo hardware ke paas nahi hain, isliye compiler unhe saath pack karne se forbidden hai. (Yeh exactly page ke top par figure mein red box hai.)

L1-Q3

Blank fill karo: VLIW mein, agar compiler kisi slot ke liye parallel kaam nahi dhundh pata, toh use wahan NOP rakhna padta hai.

Recall Solution

Ek NOP. Slot fixed-width word mein exist karta rehta hai, isliye idle slots explicitly spell out kiye jaate hain. Yahi wajah hai ki low-parallelism code bits waste karta hai.

Level 2 — Application

L2-Q1

Humare 4-slot machine par parent note ka dependent Fibonacci-style body run hota hai, 3 instruction words mein 3 real operations ke saath scheduled. Slot utilisation compute karo.

Recall Solution

Total slots used $= 3 instructions \times 4 slots = 12$ . Real operations $= 3$ . $Utilisation = \frac{3}{12} = 0.25 = 25%.$ Chain temp = fib, fib = fib + prev, prev = temp fully serial hai, isliye har row mein sirf ek slot kabhi busy ho sakta hai.

L2-Q2

Ek loop body ko 6 memory operations chahiye aur machine mein 1 memory port hai. Recurrences ignore karte hue, resource-constrained minimum initiation interval $ResMII$ kya hai? (Vocabulary box se yaad karo: $u_{r}$ = uses per iteration, $c_{r}$ = copies of resource, aur $ResMII = max_{r} ⌈ u_{r} / c_{r} ⌉$ .)

Recall Solution

Yahan busy resource sirf memory hai, isliye $u_{mem} = 6$ (chhe memory ops per iteration) aur $c_{mem} = 1$ (ek port): $ResMII = ⌈ \frac{u _{mem}}{c _{mem}} ⌉ = ⌈ \frac{6}{1} ⌉ = 6 cycles per iteration.$ Ek port se chhe memory operations simply chhe cycles lete hain, chahe ALU slots kitne bhi idle kyun na baithe hon.

L2-Q3

Ek VLIW word 128 bits ka hai (4 slots × 32 bits). Ek 100-operation program aise VLIW words mein compile hota hai jo average 40% full hain — matlab har word average mein $k = 1.6$ real operations carry karta hai, jahan $k$ average number of real (non-NOP) operations packed per instruction word hai (toh $40% \times 4 slots = 1.6$ ). Kitne VLIW instruction words emit hote hain, aur kitne bits of NOP waste hote hain?

Recall Solution

$k = 1.6$ real operations per word ke saath, words needed $= ⌈ 100/ k ⌉ = ⌈ 100/1.6 ⌉ = ⌈ 62.5 ⌉ = 63$ words. Total slots $= 63 \times 4 = 252$ ; real ops $= 100$ ; NOP slots $= 252 - 100 = 152$ . Wasted bits $= 152 \times 32 = 4864$ bits. Emitted code ka aadha se zyada NOP hai — classic VLIW code-bloat penalty.

Level 3 — Analysis

L3-Q1

Humare loop body mein issue hote hain: 4 memory ops, 5 integer ALU ops, 1 branch. Machine: 1 memory port ( $c_{mem} = 1$ ), 2 integer ALUs ( $c_{ALU} = 2$ ), 1 branch/FP unit ( $c_{br} = 1$ ). $ResMII$ dhundho aur bottleneck resource ka naam batao.

Recall Solution

Har resource ke liye $⌈ u_{r} / c_{r} ⌉$ evaluate karo ( $u_{r}$ = uses per iteration, $c_{r}$ = copies available):

Memory: $⌈ 4/1 ⌉ = 4$
Integer ALU: $⌈ 5/2 ⌉ = 3$
Branch/FP: $⌈ 1/1 ⌉ = 1$ $ResMII = max (4, 3, 1) = 4 cycles.$ Memory port bottleneck hai. Chahe ALU ops total mein zyada hain, do ALUs load share karte hain, jabki ek port ko charon accesses serialise karne padte hain.

L3-Q2

Isi loop mein ek dependency cycle $C$ hai: ek store-to-load recurrence jiska total latency $Lat (C) = 6$ cycles hai aur $Dist (C) = 2$ iterations span karta hai — matlab is iteration ka ek load ek aisi value chahiye hai jo ek store ne do iterations pehle produce ki thi, isliye feedback 2 iterations tak jaati hai. L3-Q1 ke saath combine karke true $II_{m i n}$ nikalo.

Recall Solution

Recurrence bound (vocabulary box se: $Lat (C)$ = feedback loop mein ek baar ghoomne ke cycles, $Dist (C)$ = kitni iterations peeche jaata hai): $RecMII = ⌈ \frac{Lat ( C )}{Dist ( C )} ⌉ = ⌈ \frac{6}{2} ⌉ = 3.$ Intuition: 6 cycles ka kaam 2 iterations mein spread hota hai, matlab kam se kam 3 cycles har iteration start ke beech hone chahiye. Overall, $II_{m i n} = max (ResMII, RecMII)$ apply karte hue: $II_{m i n} = max (ResMII, RecMII) = max (4, 3) = 4 cycles.$ Resources abhi bhi dominate karte hain; recurrence, 3 par, binding constraint nahi hai yahan.

Do floors aur woh kaise compete karte hain neeche dikhaya gaya hai (yeh figure L3-Q2 ko support karta hai).

Upar ki figure kya dikhati hai (L3-Q2 mein use hoti hai): teen bars — memory ResMII (4), ALU ResMII (3), aur RecMII (3) — cycles per iteration mein measured. Sabse tall bar (memory, red mein) wahi hai jo $II_{m i n}$ set karta hai, exactly kyunki $II_{m i n}$ sabhi floors ka max hai. Pedagogically yeh poora Level-3 idea ek nazar mein hai: average mat karo, add mat karo — sabse tall bar dhundho. Red arrow us winning bar ki taraf point karta hai yeh hammer home karne ke liye ki kaunsi constraint binding hai.

L3-Q3

L3-Q1/Q2 ke loop ke liye, agar hum ek second memory port add karein ( $c_{mem}$ 1 se 2 ho jaaye), toh new $II_{m i n}$ kya hoga? Yeh kya reveal karta hai?

Recall Solution

New memory bound: $⌈ 4/2 ⌉ = 2$ . Recompute:

Memory: $2$ , ALU: $3$ , Branch: $1$ → new $ResMII = max (2, 3, 1) = 3$ .
$RecMII$ unchanged $= 3$ . $II_{m i n} = max (3, 3) = 3 cycles.$ Port add karne se improvement sirf 4 se 3 tak aayi. Ab ALU aur recurrence tie karte hain as new limits — dono se neeche nahi ja sakte bina dono zyada ALUs aur shorter dependency cycle ke. Yeh analyst ka lesson hai: ek bottleneck relieve karo aur agla wala appear ho jaata hai.

Level 4 — Synthesis

L4-Q1

Is loop body ko 4-slot machine (1 mem, 2 ALU, 1 br/FP) par schedule karo. Maano ki sabhi latencies 1 cycle hain aur koi cross-iteration recurrence nahi hai:

L1: r1 = LD a[i]
L2: r2 = LD b[i]
A1: r3 = r1 + r2      (needs L1, L2)
A2: r4 = r3 * 2       (needs A1)
S1: ST c[i] = r4      (needs A2)

Ek legal single-iteration VLIW schedule produce karo aur uska cycle count do.

Recall Solution

Constraints: ek memory op per cycle (isliye L1, L2, S1 ek cycle share nahi kar sakte); ek RAW (Read After Write) chain — true data dependencies ki ek string jahan har op woh read karta hai jo pichle ne likha — yaani L1,L2 → A1 → A2 → S1.

Slot layout:  [ ALU1        | ALU2 | MEMORY   | BR/FP ]
Cycle 1:      [ NOP         | NOP  | LD r1,a  | NOP   ]
Cycle 2:      [ NOP         | NOP  | LD r2,b  | NOP   ]
Cycle 3:      [ ADD r3,r1,r2| NOP  | NOP      | NOP   ]
Cycle 4:      [ MUL r4,r3,2 | NOP  | NOP      | NOP   ]
Cycle 5:      [ NOP         | NOP  | ST c,r4  | NOP   ]

5 cycles. Do loads single port ki wajah se serialise hone chahiye; ADD dono ka wait karta hai; MUL ADD ka wait karta hai; store MUL ka wait karta hai. Utilisation $= 5/20 = 25%$ — serial chain wide issue se benefit nahi uthata.

L4-Q2

Ab L4-Q1 loop ko iterations ke across software-pipeline karo taaki throughput badhao. Recurrence-free body mein $u_{mem} = 3$ (2 loads + 1 store) aur $u_{ALU} = 2$ hai. Steady-state $II$ kya hai — pipelined loop ke repeating middle mein II, fill ke baad aur drain se pehle (vocabulary box dekho) — aur ise kya limit karta hai?

Recall Solution

Formula box ke do floors apply karo: $ResMII = max (⌈ \frac{u _{mem}}{c _{mem}} ⌉, ⌈ \frac{u _{ALU}}{c _{ALU}} ⌉) = max (⌈ \frac{3}{1} ⌉, ⌈ \frac{2}{2} ⌉) = max (3, 1) = 3.$ Koi recurrence nahi hai, isliye $RecMII = 1$ . Therefore: $II_{m i n} = max (ResMII, RecMII) = max (3, 1) = 3 cycles per iteration.$ Toh steady state mein har 3 cycles mein ek nayi iteration launch hoti hai. Chahe ek iteration standalone 5 cycles leti hai (L4-Q1 se), pipelining memory port ko per iteration 3 accesses back-to-back stream karne deta hai jabki earlier iterations ka ALU work gaps mein chhup jaata hai. Throughput $1/5$ se $1/3$ iterations per cycle ho jaata hai. Single memory port ise limit karta hai.

L4-Q3

L4-Q2 se $II = 3$ use karte hue, full 100-iteration loop kitne cycles lega, agar pipeline prologue (fill) steady state se pehle 4 extra fixed cycles add karta hai?

Recall Solution

Steady-state cost $= II \times iterations = 3 \times 100 = 300$ cycles. Prologue add karo: $300 + 4 = 304$ cycles. (Formally, total $\approx prologue + II \cdot N$ large $N$ ke liye; prologue 100 iterations mein nearly nothing tak amortise ho jaata hai.)

Level 5 — Mastery

L5-Q1

Ek DSP kernel mein yeh dependency cycle hai: acc = acc + (x[i] * h) jahan multiply-add khud ko har iteration feed karta hai. Multiply-add ki latency 3 cycles hai, aur recurrence 1 iteration span karta hai ( $Dist (C) = 1$ — is iteration ke acc ko immediately pichle wale ki zaroorat hai). Kernel har iteration mein 1-port machine par 2 memory loads bhi issue karta hai. $II_{m i n}$ nikalo, aur explain karo kaunsa bound jeetta hai aur kyun hardware add karne se use beat nahi kiya ja sakta.

Recall Solution

$ResMII = ⌈ u_{mem} / c_{mem} ⌉ = ⌈ 2/1 ⌉ = 2$ (memory port).
$RecMII = ⌈ Lat (C) / Dist (C)⌉ = ⌈ 3/1 ⌉ = 3$ . $II_{m i n} = max (2, 3) = 3 cycles.$ Recurrence jeetta hai. Crucially, memory ports ya ALUs add karne se $ResMII$ drop hoga lekin $RecMII$ nahi lower kar sakta: iteration $i$ ka accumulator genuinely iteration $i - 1$ ki value chahiye, jise produce hone mein 3 cycles lagte hain. Yeh ek algorithmic limit hai, resource limit nahi — koi bhi extra silicon ek true data dependence nahi hata sakta. (Sirf algorithm restructuring se — jaise partial sums mein split karna — cycle short ho sakta hai.)

L5-Q2

Ek hi loop ke do schedules compare karo jinka $II_{m i n} = 3$ hai: Schedule A achieves $II = 3$ ; Schedule B achieves $II = 5$ kyunki compiler ek register rename karne mein fail raha, ek false WAW dependency ek cycle mein create kar raha. 300 iterations mein throughput loss quantify karo, aur ek-line fix batao.

Recall Solution

Schedule A: $3 \times 300 = 900$ cycles.
Schedule B: $5 \times 300 = 1500$ cycles.
Loss: $1500 - 900 = 600$ cycles, yaani Schedule B $1500/900 \approx 1.67 \times$ slower hai. Fix: compiler ko register rename karna hoga taaki WAW (write-after-write) independent ho jaaye. WAW aur WAR false dependencies hain (data-dependence definition box dekho) — woh register names reuse karne se arise karte hain, real data flow se nahi — aur VLIW mein compiler (hardware nahi) ko unhe eliminate karna padta hai. Renaming $II = 3$ restore kar deta hai.

L5-Q3 (capstone)

Design decision: Tumhare paas ek loop hai jisme $u_{mem} = 6$ , $u_{ALU} = 4$ , aur ek recurrence hai jisme $Lat (C) = 8$ , $Dist (C) = 4$ hai. Tumhare baseline machine mein 1 memory port aur 2 ALUs hain. Tum exactly ek add kar sakte ho: (a) ek second memory port, ya (b) ek third ALU. Kaunsa upgrade $II_{m i n}$ zyada lower karta hai, aur kitna?

Recall Solution

Baseline:

Memory: $⌈ 6/1 ⌉ = 6$ ; ALU: $⌈ 4/2 ⌉ = 2$ ; toh $ResMII = 6$ .
$RecMII = ⌈ 8/4 ⌉ = 2$ .
$II_{m i n} = max (6, 2) = 6$ .

(a) Second memory port: memory $⌈ 6/2 ⌉ = 3$ ; ALU $2$ ; $ResMII = 3$ ; $RecMII = 2$ ⇒ $II_{m i n} = max (3, 2) = 3$ .

(b) Third ALU: memory $⌈ 6/1 ⌉ = 6$ (unchanged!); ALU $⌈ 4/3 ⌉ = 2$ ; $ResMII = 6$ ; ⇒ $II_{m i n} = max (6, 2) = 6$ .

Answer: Second memory port (a) $II_{m i n}$ ko 6 se 3 tak cut karta hai — ek 2× speedup. Third ALU kuch nahi badalta kyunki ALU kabhi bottleneck nahi tha (woh 2 par baitha tha jabki memory 6 par tha). Hamesha hardware binding resource par spend karo.

Upgrade decision exactly yeh "attack the tallest bar" logic hai (yeh figure L5-Q3 ko support karta hai):

Upar ki figure kya dikhati hai (L5-Q3 mein use hoti hai): har resource ke liye bars ka ek pair — baseline bound (left, black) aur second memory port add karne ke baad bound (right). Sirf memory bar move karta hai, 6 se (red mein, kyunki woh binding tallest bar tha) 3 tak girta hai; ALU aur recurrence bars khade rehte hain. Yeh capstone lesson visual banata hai: ek non-tallest bar (third ALU) par kharchaa kiya hua paisa red bar ko — aur isliye $II_{m i n}$ ko — bilkul unchanged chhod deta. Tum loop ko sirf tabhi speed up karte ho jab jo abhi tallest hai use shrink karo.

Recall Self-test summary

II stands for ::: Initiation Interval — successive iterations launch karne ke beech cycles. Steady state means ::: pipelined loop ka repeating middle fill ke baad aur drain se pehle, jahan ek nayi iteration har II cycles mein launch hoti hai. k in the code-density problem means ::: per instruction word average real (non-NOP) operations packed ka number. RAW means ::: Read After Write — ek true data dependency jahan ek op woh read karta hai jo ek pichle op ne likha; order nahi toda ja sakta. Every II floor is max(ResMII, RecMII) and we take max because ::: dono promises (kaafi hardware AUR data ready) ek saath hold karne chahiye, isliye tighter wala govern karta hai. ResMII per resource ::: ceil(u_r / c_r) — uses per iteration over copies available, phir resources par max. RecMII per cycle ::: ceil(Lat(C) / Dist(C)) — feedback-loop latency over iteration distance, phir cycles par max. Dist(C) means ::: kitni iterations peeche ek recurrence pahunhti hai. Why a third ALU can be useless ::: woh tabhi help karta hai jab ALU bottleneck ho (tallest bar). Why more ports cannot beat a recurrence ::: ek true data dependence algorithmic hai, resource-bound nahi.