Visual walkthrough — Dataflow architectures

6.5.9 · D2 · Hardware › Advanced & Emerging Architectures › Dataflow architectures

Step 1 — Ek node ek choti machine hai jisme input slots hote hain

KYA. Ek dataflow program ka sabse chhota piece hai node: ek box jo ek hi operation karta hai (ek $+$, ek $-$, ek $\times$). Har node ke upar input slots hote hain (jahan data aata hai) aur neeche ek output spout hota hai (jahan uska jawab niklta hai).

YE YAHAN SE KYU SHURU. Pehle "graph" ya "firing" ki baat karne se pehle, hume jaanna hai ki ek single box kya chahta hai: woh chahta hai ki uske har ek input slot bhar jaaye. Bas itna hi. Yahi ek khwaish poori engine hai.

PICTURE. Neeche, ek akela $+$ node hai. Uske do input slots hain jo upar ke do circles hain; uska output spout neeche ka arrow hai. Abhi dono slots khali hain (grey) — toh node so raha hai.

Step 2 — Ek token ek value hai jiske saath ek delivery van hai

KYA. Data yahan wires pe nahi baithta; yeh ek token ke roop mein travel karta hai. Token ko ek choti van socho jo ek number carry karti hai. Jab van ek slot pe pahunchti hai, woh slot ab bhar jaata hai.

VAN KYU, WIRE KYU NAHI? Normal circuit mein ek wire sirf ek voltage hamesha hold karti hai. Token alag hai: yeh produce hota hai, yeh flow karta hai, aur jab node fire karta hai toh yeh consume ho jaata hai (khatam). "Van jo deliver karti hai aur phir chali jaati hai" sochne se woh classic galti rukti hai jab log tokens ko permanent wire signals ki tarah treat karte hain.

PICTURE. Do tokens — $x=3$ (blue van) aur $y=4$ (yellow van) — $+$ node ke do slots ki taraf badh rahe hain. Dekho har van apne slot mein kaise land karti hai.

Picture mein, symbol $x=3$ ka matlab hai "value $3$, abhi left slot ki taraf ek token pe sawaar hai"; $y=4$ woh value $4$ hai jo right slot ki taraf ja rahi hai.

Step 3 — Firing rule: jaise hi har slot bhar jaaye, fire karo

KYA. Ab central law. Ek node fires — matlab actually apna operation perform karta hai — jaise hi uske saare input slots bhar jaate hain, ek pal bhi pehle nahi.

YEH EXACT RULE KYU? Yahi poora reason hai ki dataflow exist karta hai. Koi program counter nahi hai jo chilla raha ho "teri baari ab". Run karne ki permission sirf yeh cheez deti hai: kya mere paas saari ingredients hain? Isliye isko dataflow kaha jaata hai — data readiness trigger hai.

PICTURE. $+$ node jiske dono slots ab bhar gaye hain ($3$ aur $4$). Firing rule satisfy hua → node light up karta hai (green), $3+4$ compute karta hai, aur apne spout se ek naya token $t=7$ emit karta hai. Note karo ki do input vans ab gayi hain — consumed.

Formula left se right padhte hue: left ke do braces precondition hain (dono slots bhar gaye); beech wala brace action hai (fire); right wala brace effect hai (ek fresh token appear hota hai, sum carry karte hue).

Step 4 — Nodes ko wire karo: program ek graph hai

KYA. Ek node ke output spout ko doosre node ke input slot se ek edge (arrow) se connect karo. Poore expression ke liye aisa karo aur tumhare paas dataflow graph aa jaata hai — program khud, ek picture ki tarah drawn.

LIST KI JAGAH GRAPH KYU? Ek list ek single order force karta hai (line 1, phir line 2…). Ek graph sirf woh orderings draw karta hai jo actually matter karte hain: A se B ka arrow matlab hai "B ko A ka answer chahiye". Do nodes ke beech koi arrow nahi matlab woh independent hain — yeh fact graph visible banata hai. Yeh mathematical object hai jise Directed Acyclic Graph (DAG) kehte hain.

PICTURE. Yahan parent ka expression $r=(x+y)\times (x-z)$ assembled hai. $+$ node aur $-$ node dono $\times$ node ko feed karte hain. Importantly, $+$ aur $-$ ke beech koi arrow nahi hai: unhe ek doosre ki zaroorat nahi.

Har brace kis node ne woh piece produce kiya yeh name karta hai. Dono braces woh do inputs hain jinke liye $\times$ node wait kar raha hai.

Step 5 — Run karo: independent nodes saath fire karte hain (automatic parallelism)

KYA. Starting tokens $x,y,z$ daalo aur firing rule ko sab kuch karne do. Hum graph ko waves mein execute hote dekhte hain.

YEH KHUD PARALLEL KYU HOTA HAI. $+$ node aur $-$ node dono ke slots ek hi pal mein bhar jaate hain (dono $x$ consume karte hain; ek $y$ leta hai, doosra $z$). Do firing rules simultaneously satisfy, koi connecting edge nahi → hardware simply dono ek saath run karta hai. Kisi ne yeh schedule nahi kiya; graph ki shape hi schedule hai. Yeh exactly woh limit hai jise Instruction-Level Parallelism chase karta hai.

PICTURE. Do firing waves.

• Wave 1 (parallel): $[+]$ aur $[-]$ saath fire karte hain, $t_1=x+y$ aur $t_2=x-z$ produce karte hain.
• Wave 2: ab $\times$ ke finally dono slots bhar gaye hain, fire karta hai, aur $r$ emit karta hai.

Numbers $x=3,y=4,z=1$ ke saath trace karo:

Yahan $t_1$ hai "$+$ node se nikla token", $t_2$ hai "$-$ node se nikla token", aur $r$ final token hai — answer. $\times$ node Wave 1 mein fire nahi kar sakta tha: uska ek slot abhi bhi khali tha. Data dependency, aur sirf wahi, use wait karne pe majboor kiya.

Step 6 — Degenerate case: agar token kabhi aaye hi na? (deadlock)

KYA. Maano $z$ token kho gaya / kabhi produce hi nahi hua. Toh $-$ node ka slot-1 bhar gaya ($x$) lekin slot-2 hamesha ke liye khali hai.

YEH KYU DIKHATE HAIN. "Sirf tab fire karo jab sare slots bhar jaayein" jaisi strict rule ka ek shadow bhi hai: agar ek input kabhi nahi aata, toh node kabhi fire nahi karta, aur uske baad wali har cheez bhi ruk jaati hai. Yeh ek real hazard hai — deadlock kehte hain — aur tumhe ise dekhna aana chahiye.

PICTURE. $-$ node half-full mein atka hua; uske peeche $\times$ node bhookha hai kyunki uska ek input ($t_2$) kabhi paida hi nahi ho sakta. $+$ branch, independent hone ki wajah se, phir bhi complete ho jaata hai — dikhata hai ki stall local hai dependency chain mein.

Step 7 — Overlap problem: do runs ek graph share karte hain

KYA. Ab usi same graph ko ek loop ke liye reuse karo. Iteration 1 compute karta hai sum + i $i=1$ ke liye; iteration 2 $i=2$ ke liye. Lekin sirf ek $+$ node hai. Agar iteration 2 ka fast $i$-token tab aata hai jab iteration 1 ka slow $sum$-token abhi bhi in flight hai, toh node run 1 ka $sum$ aur run 2 ka $i$ pair kar sakta hai — garbage output.

YEH STATIC DATAFLOW KYU TODATA HAI. Static dataflow mein ek edge at most ek token hold karta hai, toh node jo bhi do tokens present hain unhe grab kar leta hai — woh unhe alag nahi bata sakta. Iterations ko safely overlap karne ke liye hume har token ko yeh batana hoga ki woh kis run ka hai.

PICTURE. Left: static — ek fast blue $i_2$ galti se slow yellow $su{m}_1$ se milta hai (red collision). Right: fix — har token ek tag $\tau$ pehanta hai (ek coloured sticker); node sirf tab fire karta hai jab dono slots mein same tag hो.

Loop ${\sum }_{i=1}^{3}i$ ko tags ${\tau }_1,{\tau }_2,{\tau }_3$ ke saath trace karo:

Woh hardware unit jo waiting tokens hold karta hai aur ek pair sirf tab release karta hai jab tags match hon use matching store kehte hain. Kyunki non-matching tokens simply wait karte hain na ki collide karte hain, iterations ek pipeline mein overlap kar sakti hain — yeh sasta overlap exactly wahi hai jo Loop-Level Parallelism enable karta hai. (Modern CPUs yahi trick Out-of-Order Execution ke andar chupaate hain: reservation stations hain hi ek tagged-token matching store.)

Ek-picture summary

Upar wali sab cheez, ek canvas pe: tokens ride in karte hain ($x,y,z$), independent nodes same wave mein fire karte hain, multiply apni dependency ke liye wait karta hai, ek lost token ek chain ko starve kar sakta hai, aur tags concurrent runs ko cross karne se rokti hain.

Active recall