Foundations — Dataflow architectures

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

Yeh page kuch bhi assume nahi karta. Parent note Dataflow architectures padhne se pehle, aapko usmein use hone wale har squiggle ko padhna aana chahiye. Neeche, har symbol ko milega: plain words → picture → topic ko yeh kyun chahiye. Yeh is tarah order kiye gaye hain ki har ek upar wale pe lean kare.

1. Ek "node" aur ek "operation"

Socho ek akele worker ko ek desk pe. Desk pe do slots hain jinka label hai "input", aur ek out-tray jiska label hai "output". Worker ko exactly ek hi trick aati hai, maano $+$ (add).

Topic ko yeh kyun chahiye: parent kehta hai "Program = graph, list nahi." Graph inhi boxes se bana hota hai. Graph hone se pehle aapko yeh jaanna zaroori hai ki ek box kya hota hai — ek single operation jo apne inputs ka wait kar rahi hai.

2. Ek "edge" aur ek "arrow" ($\to$)

Topic ko yeh kyun chahiye: mnemonic D.A.T.A. literally kehta hai "Arrows are dependencies". Dataflow parallelism dhundh sakta hai kyunki missing arrows ka matlab hai koi dependency nahi — dekho §7.

3. Ek "token" — woh cheez jo arrow pe travel karti hai

Topic ko yeh kyun chahiye: parent ki firing rule "tokens present on all input edges" ke baare mein baat karti hai. Jab tak aap tokens ko slots mein baithe hue picture nahi karte, firing samajh nahi aayegi.

4. "Fire" aur firing rule

Ise zor se padhna: "Ek node fires if and only if har ek input slot mein ek token hai." Toh ek missing token = bilkul fire nahi, bas. Aur tokens ka poora set = woh turant fire karta hai, kisi ki permission ke bina.

Topic ko yeh kyun chahiye: yeh poore architecture ka dil hai. Von Neumann architecture mein ek program counter decide karta hai kab chalana hai. Yahan, kuch decide nahi karta — data ki maujoodgi hi decision hai.

5. Variables aur expression $r=(x+y)\times (x-z)$

Chaliye parent ke key expression ko dheere se left se right padhte hain:

$r=(x+y)\times (x-z)$

• Brackets $()$ un cheezon ko group karte hain jo pehle solve ki jaani chahiye.
• $(x+y)$ ek node ka kaam hai (ek add).
• $(x-z)$ doosre node ka kaam hai (ek subtract).
• $\times$ dono results leta hai aur multiply karta hai.
• $r=$ final answer ko naam deta hai.

Topic ko yeh kyun chahiye: parent is expression se graph derive karta hai. Agar aap dekh sako ki brackets nested boxes kaise bante hain, toh graph khud khich jaata hai.

6. Subscripts aur intermediate tokens $t_1,t_2$

Parent ke trace mein, $t_1=x+y$ aur $t_2=x-z$ woh tokens hain jo do lower nodes emit karte hain multiply fire hone se pehle.

Topic ko yeh kyun chahiye: derivations mein beech wali values ke liye names chahiye. $t_1,t_2$ ke bina hum nahi keh sakte "multiply $t_1$ aur $t_2$ ka wait karta hai".

7. Independence = "koi connecting edge nahi" (jahan parallelism chhupti hai)

Isliye parent kehta hai parallelism "free" hai: aap iske liye maangte nahi. Yeh arrows ki abscence hai. Yeh idea Instruction-Level Parallelism ki natural ceiling hai, aur yahi woh hai jo Out-of-Order Execution ek ordinary CPU ke andar chupke se rebuild karne ki koshish karta hai.

8. Tag $\tau$ aur notation $⟨v,\tau ⟩$

$f(v_1,v_2)$ padhna: $f$ "jo bhi yeh node karta hai" ka placeholder hai — agar yeh add node hai, toh $f(v_1,v_2)=v_1+v_2$.

Topic ko yeh kyun chahiye: ek loop mein, ek hi box ki kaafi saari copies ek saath active rehti hain. Tag rok deta hai ki iteration-3 ka number galti se iteration-7 ke number ke saath pair na ho jaaye. Yeh wahi cheez hai jo Loop-Level Parallelism ko sasta banati hai, aur yahi trick Tomasulo-style Out-of-Order Execution ke andar hai.

9. Graph ek DAG hai (koi cycles nahi)

Topic ko yeh kyun chahiye: "acyclic" guarantee karta hai ki computation actually khatam hoti hai — data aage badhta rehta hai aur apni hi tail ka peecha nahi karta. Yeh is page ki har cheez ke neeche ka mathematical skeleton hai.

Prerequisite map

Equipment checklist