VLIW architectures: Visual walkthrough — Hinglish deep dive

5.3.13 · D2 · Hardware › Advanced Microarchitecture › VLIW architectures

Koi bhi symbol aane se pehle, aao plain words par agree kar lete hain.

Hum ek running example use karenge poore time. Yeh ek loop hai jo ek running total rakhti hai:

for (int i = 0; i < N; i++) {
    x = load(a[i]);   // L : a[i] ko x mein read karo
    s = s + x;        // A : x ko running sum s mein add karo
    store(b[i], s);   // S : s ko b[i] mein write karo
}

Ek iteration mein teen operations hain: L (load), A (add), S (store). Hum iska $II$ bilkul scratch se discover karenge.

Step 1 — Loop ko factory line ki tarah picture karo

KYA. Hum har iteration ko uske teen operations ki ek vertical stack ki tarah draw karte hain, aur iterations ko time mein side by side rakhte hain.

KYU. Formulas se pehle, hume ek mental image chahiye jahan "ek naya iteration kitni baar shuru ho sakta hai" ek aisi cheez ho jise hum literally ruler se measure kar sakein. Factory line exactly yahi karti hai: parts ek steady rhythm mein enter karte hain.

PICTURE. Figure dekho. Time left se right jaata hai clock cycles mein. Iteration 0 kuch cycles occupy karta hai; iteration 1 right mein $II$ amount se shift hai; iteration 2 ek aur $II$ se. Do neighbours ke starts ke beech red gap hi $II$ hai.

Step 2 — Pehli wall: hardware kam hai (Resource bound)

KYA. Gino ki loop body kitni baar har functional unit use karti hai, aur compare karo ki us unit ki kitni copies maujood hain.

KYU. Ek single memory port ek memory operation per cycle serve kar sakta hai. Hamare body mein do memory operations hain (load L aur store S). Yahan tak ki ek perfect duniya mein jahan koi dependencies nahi hain, do memory ops ek hi port share nahi kar sakte same cycle mein — ek ko ek cycle wait karna padega. Yeh ek hardware wall hai, logic wall nahi.

PICTURE. Figure ek single memory-port "turnstile" dikhata hai. Do log (L aur S) har iteration mein ussse guzarna chahte hain, lekin sirf ek hi per cycle guzar sakta hai. Toh har naya iteration har 2 cycles mein ek baar se zyada fast nahi aa sakta, warna turnstile jam ho jaata hai.

Step 3 — Doosri wall: answer khud ko hi feed karta hai (Recurrence bound)

KYA. Sum notice karo: s = s + x. Iteration $i$ s read karta hai, aur apna naya s compute karne ke liye use iteration $i - 1$ ka s likhna khatam hone ka intezaar karna padta hai. Output wapas next input ban jaata hai.

KYU. Yeh ek logic wall hai, hardware se independent. Yahan tak ki infinitely many ALUs ke saath bhi, iteration $i$ literally s + x compute nahi kar sakta jab tak pichla s exist nahi karta. Yeh chain jo khud par vapas fold hoti hai use recurrence kehte hain (graph mein ek dependency cycle).

PICTURE. Figure dependency graph draw karta hai. Add node A se ek arrow nikalti hai aur curve hokar khud mein wapas aati hai, jisme do numbers label hain: latency (add kitne cycles leta hai) aur distance (value kitne iterations peeche se aayi). Woh self-loop hi recurrence hai.

Step 4 — Recurrence ko cycle count mein convert karna

KYA. Hum "sum khud ko latency $2$ , distance $1$ ke saath feed karta hai" ko minimum cycles per iteration mein convert karte hain.

KYU. Agar dependency cycle $C$ ke around ek chakkar laana $Lat (C)$ cycles cost karta hai, aur woh trip hume $Dist (C)$ iterations aage le jaati hai, toh woh $Dist (C)$ iterations milke kam se kam $Lat (C)$ cycles dene chahiye. Barabar spread karein toh woh hai $Lat (C) / Dist (C)$ cycles per iteration. Aur zyada squeeze karo aur value simply time par ready nahi hogi.

PICTURE. Figure recurrence ko time axis ke saath flat rakhta hai: iteration $i$ ka add tab tak fire nahi kar sakta jab tak iteration $i - 1$ ka add ke baad $2$ cycles na guzar jaayein. Toh consecutive adds kam se kam $2$ cycles apart forced hain — $II$ par ek floor jise green minimum-gap ruler ki tarah draw kiya gaya hai.

Step 5 — Dono walls ek saath: bada wala lo

KYA. Hamare paas do independent lower bounds hain. Koi bhi violate nahi kiya ja sakta, toh asli floor woh hai jo badi ho.

KYU. $ResMII$ kehta hai "kam se kam 2 cycles warna port jam ho jaata hai." $RecMII$ kehta hai "kam se kam 2 cycles warna sum ready nahi hoga." Ek legal schedule dono ko obey karna chahiye. Dono ko obey karna matlab stricter (bade) wale ko obey karna — maximum.

PICTURE. Do floors stacked hain; $II$ ke liye feasible region dono ke upar baithti hai. $II_{m i n}$ woh unchal floor hai.

Step 6 — Edge aur degenerate cases (reader ko stranded mat chhodna)

KYA. Hum check karte hain ki formula apni extremes par kya kehta hai taaki koi bhi scenario surprise na kare.

KYU. Ek formula jis par tum trust karo use boundaries par sahi behave karna chahiye: koi dependencies nahi, koi hardware limit nahi, ya distance zero wala cycle.

PICTURE. Char mini-panels, ek har case ke liye, har ek dikhata hai ki gap ka kya hota hai.

Worked example Corner cases

Koi recurrence nahi (har iteration independent, jaise c[i]=a[i]+b[i]): koi dependency cycle nahi hai, toh $RecMII = 0$ (ya undefined → $0$ treat karo). Tab $II_{m i n} = ResMII$ — tum purely hardware-bound ho. Yeh parent note ka memory-bound array-add hai.
Infinite resources (har op ke liye har unit ki ek copy): $u_{r} \leq c_{r}$ hamesha, toh $ResMII = 1$ . Tab $II_{m i n} = RecMII$ — tum purely dependency-bound ho.
Dono trivial (independent iterations aur enough units): $II_{m i n} = max (1, 0) = 1$ — har single cycle mein ek naya iteration. Dream case.
Distance-zero cycle ( $Dist (C) = 0$ ): value usi iteration ke andar ready honi chahiye — division by zero ek impossible loop-carried self-dependency within one cycle flag karta hai. Real modulo schedulers isse reject karte hain; ek genuine loop mein hamesha $Dist (C) \geq 1$ hota hai.

Ek-picture summary

Ek canvas par sab kuch: loop, uski do walls, aur winning floor.

Recall Feynman retelling — ise ek story ki tarah bolo

Ek factory line imagine karo jo running totals bana rahi hai. Ek naya part line mein har thodi der mein enter karta hai; us rhythm ko initiation interval kaho. Do cheezein rhythm ko infinitely fast hone se rokti hain. Pehla, stockroom mein sirf ek darwaza hai (memory port), lekin har part ko do baar jaana padta hai (ek load aur ek store) — toh parts har do beats mein ek baar se zyada fast enter nahi kar sakte: yeh hai resource wall, "uses over copies, rounded up." Doosra, har naya total pichle total ke upar bana hai — tum literally ek aisi sankhya mein nahi jod sakte jo tumhare paas hai hi nahi, aur use banane mein do beats lagte hain — toh consecutive adds do beats apart forced hain: yeh hai recurrence wall, "latency over distance, rounded up." Tumhe dono walls obey karni hain, toh tum unchi wali obey karte ho — yeh hai max. Agar loop mein koi self-feeding total nahi hota, toh sirf darwaza matter karta; agar darwaza infinitely wide hota, toh sirf feeding matter karti. Kisi bhi case mein, $II_{m i n} = max (ResMII, RecMII)$ sabse fast honest rhythm hai jo line run kar sakti hai.

Recall Khud check karo

$ResMII$ kya measure karta hai aur ceiling kyun? ::: Yeh $⌈ u_{r} / c_{r} ⌉$ hai — sabse busy resource ke uses uski copies se divide karo, upar round karo kyunki iterations poore cycles apart shuru hote hain aur neeche round karna unit ko overload kar deta. Ek recurrence floor kyun set karta hai infinite hardware ke saath bhi? ::: Kyunki ek true (RAW) loop-carried dependency ka matlab hai is iteration ki value tab tak compute nahi ho sakti jab tak ek past iteration ka result exist nahi karta; cycle ke around jaane mein $Dist (C)$ iterations mein $Lat (C)$ cycles lagte hain, toh kam se kam $Lat (C) / Dist (C)$ cycles per iteration unavoidable hain. Dono bounds ka max kyun lete hain, sum ya min kyun nahi? ::: Ek legal schedule dono constraints simultaneously satisfy karna chahiye; dono satisfy karna equivalent hai stricter (bade) wale ko satisfy karne ke, toh asli floor unka maximum hai. Hamare sample loop ke liye (2 mem ops, 1 port; add latency 2, distance 1) $II_{m i n}$ kya hai? ::: $max (⌈ 2/1 ⌉, ⌈ 2/1 ⌉) = max (2, 2) = 2$ cycles.