Dataflow architectures

6.5.9 · Hardware › Advanced & Emerging Architectures

WHAT hai ek dataflow architecture?

Teen ideas jo kabhi nahi bhoolne chahiye:

Program = graph, list nahi.
Execution rule = "fire when inputs ready" (jise firing rule kehte hain).
Parallelism automatic hai — koi bhi do nodes jinka inputs ready hain woh ek saath run kar sakte hain.

HOW execution kaam karti hai — first principles se

Is expression ko consider karein $r = (x + y) \times (x - z)$

Chalo derive karte hain dataflow graph ko instead of ise diya hua maanein.

Final operation $\times$ hai. Isko do inputs chahiye: $(x + y)$ aur $(x - z)$ .
$(x + y)$ khud ek node hai: ek $+$ jo tokens $x$ aur $y$ consume karta hai.
$(x - z)$ ek $-$ node hai jo $x$ aur $z$ consume karta hai.

Toh graph yeh hai:

x \to [+] y \to [+] ⟹ [+] \to \times

x \to [-] z \to [-] ⟹ [-] \to \times

Firing trace (Har step kyun?):

Tokens $x, y, z$ arrive karte hain. Kyun? Inputs starting data hain.
+ node ke paas dono inputs hain ( $x, y$ ) → fires, token $t_{1} = x + y$ emit karta hai. Saath hi - node ke paas $x, z$ hain → fires, $t_{2} = x - z$ emit karta hai. Kyun simultaneously? Dono firing rules ek saath satisfy hote hain aur nodes independent hain → hardware unhe parallel mein run karta hai.
× node ke paas ab $t_{1}, t_{2}$ hain → fires, $r$ emit karta hai. Kyun last? Uski firing rule pehle satisfy nahi ho sakti thi kyunki uske inputs exist hi nahi karte the — data dependency order force karti hai, kuch aur nahi.

Worked example — ek loop

$\sum_{i = 1}^{n} i$ ko conceptually ek dataflow ke roop mein compute karein.

Har iteration $i$ ka body: sum_new = sum_old + i.

Tags yahan kyun matter karte hain (step-by-step):

Iteration $i = 1$ : token $⟨ s u m = 0, τ_{1} ⟩$ , $⟨ i = 1, τ_{1} ⟩$ → fires → $⟨ 1, τ_{1} ⟩$ .
Iteration $i = 2$ ke paas apna $i$ -token already flow kar sakta hai jabki iteration 1 khatam ho rahi hai. Tags $τ_{1}, τ_{2}$ unhe alag rakhte hain taaki ek fast $i$ -token kabhi galti se kisi aur iteration ke slow $s u m$ -token ke saath pair na ho jaaye.
Result: pipeline parallelism across iterations bina kisi locks ke — "matching store" hardware tabhi fire karta hai jab tags agree karte hain.

Common mistakes

Recall Feynman: 12-saal ke bacche ko explain karo

Socho ek kitchen jahan har cook ek cheez banata hai lekin sirf tab jab uske saare ingredients table par ho. Koi bell ka ya boss ke "next!" chillane ka wait nahi. Jis moment cook ke paas sab kuch hota hai, woh cook karta hai — aur bahut saare cooks ek saath kaam kar sakte hain. "Recipe" ek numbered list nahi hai; yeh arrows ki ek picture hai jo dikhati hai kis ki taiyaar dish kis ka ingredient ban jaati hai. Fancy version mein, har ingredient par ek sticker hota hai jo batata hai yeh kaunse order ka hai, taaki table 3 ka salad table 7 ke soup ke saath kabhi mix na ho.

Active recall

Dataflow architecture mein program counter ki jagah kya leta hai?

Kuch nahi — execution data availability se drive hoti hai (the firing rule); koi PC nahi hota.

Ek dataflow node ki firing rule batao.

Ek node tab fire karta hai jab uske saare input edges par tokens present hon.

Ek dataflow program ko kaise represent kiya jaata hai?

Ek directed graph ke roop mein: nodes = operations, edges = data (tokens).

Dataflow mein execution order kya decide karta hai?

Sirf data dependencies (kaunse node ka output kisi doosre ka input feed karta hai).

Static aur dynamic dataflow mein kya difference hai?

Static mein zyaada se zyaada ek token per edge allow hota hai; dynamic tags attach karta hai taaki same graph ke kaafi concurrent instances run kar sakein.

Tagged-token dataflow mein node fire karne se pehle kya match karna zaroori hai?

Input tokens ke tags equal hone chahiye.

Dataflow "for free" parallelism kyun expose karta hai?

Independent operations mein koi connecting edge nahi hoti, toh unki firing rules independently satisfy hoti hain aur woh concurrently run karte hain.

Token kya hota hai?

Ek packet jo ek data value (aur dynamic dataflow mein, ek tag) carry karta hai jo ek edge ke along flow hota hai aur firing par consume hota hai.

Dynamic dataflow mein matching tokens ko pair karne wali hardware unit kya hai?

The matching store / matching unit.

Loop mein tags kyun zaroori hain?

Different iterations ke tokens ko galat pair hone se rokne ke liye aur iterations ko overlap karne (pipeline parallelism) ki permission dene ke liye.

Connections

Von Neumann architecture — woh sequential PC-based model jiske khilaf dataflow react karta hai.
Instruction-Level Parallelism — dataflow ILP ki natural limit hai: saari dependencies expose hoti hain.
Out-of-Order Execution — modern CPUs ek local, hidden dataflow engine use karte hain (Tomasulo/reservation stations = tagged-token matching!).
Systolic Arrays — regular computations ke liye ek aur data-driven, PC-free style.
Directed Acyclic Graph (DAG) — dataflow graph ka mathematical structure.
Loop-Level Parallelism — dynamic/tagged dataflow se easily enable hota hai.

WHAT hai ek dataflow architecture?

WHY chahiye yeh hume?