Dataflow architectures: Worked examples — Hinglish deep dive

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

Yeh page Dataflow architectures ki "haath gande karo" companion hai. Parent note ne rules banaye the: ek program ek directed graph hota hai, edges tokens carry karte hain (ek value hold karne wale packets, aur dynamic case mein ek tag bhi), aur ek node fire karta hai jis instant saare input edges matching tokens hold kar rahe hon. Yahaan hum un rules ko haath se har tarah ki situation par run karte hain jo ek dataflow graph face kar sakta hai — taaki jab exam ya real machine aapko ek throw kare, aapne pehle se uska twin dekha ho.

Shuru karne se pehle, contract se ek vaada: kuch bhi use nahi hoga jab tak draw na kiya jaye. Agar token, tag, fire, epoch jaisa koi word aaye, toh uske saath wali picture dekho — picture hi definition hai.

The scenario matrix

Har dataflow question kuch gine-chune shapes mein se ek hota hai. Neeche ki table poora zoo hai. Neeche har worked example mein us cell ki stamp hai jisme woh rehta hai, aur milke woh har row cover karte hain.

#	Case class	Isme kya unusual hai	Example jo cover karta hai
A	Pure independent ops ("free parallelism" case)	Do nodes ka koi shared edge nahi → saath fire karo	Ex 1
B	Chained dependency (forced sequential order)	Ek ka output doosre ka input hai → order data se force hota hai, PC se nahi	Ex 2
C	Diamond (fan-out phir fan-in)	Ek value do nodes ko feed karti hai, results re-merge hote hain	Ex 3
D	Degenerate: constant / zero-input node	Ek node jisme koi data edge nahi — yeh kab fire karta hai?	Ex 4
E	Degenerate: identity / one-input op	Ek node jo sirf ek token maangta hai	Ex 4
F	Static conflict (do tokens ek hi edge pe jaana chahte hain)	Edge capacity = 1 token → machine stall karti hai	Ex 5
G	Dynamic loop with tags (overlapping iterations)	Iterations concurrently run karti hain, tags unhe alag rakhte hain	Ex 6
H	Tag mismatch / "garbage" limiting case	Kya hota hai agar tags drop ho jaayein	Ex 7
I	Real-world word problem	Ek everyday process ko firing rule pe map karo	Ex 8
J	Exam-style twist (throughput / speed-up numbers)	Firing "waves" count karo, parallel speed-up compute karo	Ex 9

Example 1 — Case A: pure independent operations

Forecast: abhi andaaza lagao — kya $-$ node ko $+$ node ka wait karna padega? Aage padhne se pehle "yes" ya "no" likh lo.

Wave 0 — tokens aate hain. Tokens $x = 4, y = 6$ , $+$ node ke do input edges par land karte hain; $p = 9, q = 2$ , $-$ node ke input edges par land karte hain. Yeh step kyun? Firing rule sirf input edges dekhti hai, isliye pehle hume starting data place karna hoga.
Wave 1 — har node check karo. $+$ node dono inputs dekhta hai → fire karta hai, $a = 4 + 6 = 10$ emit karta hai. $-$ node bhi dono inputs dekhta hai → same wave mein fire karta hai, $b = 9 - 2 = 7$ emit karta hai. Yeh step kyun? Unki firing rules independently satisfied hoti hain. Figure dekho: do nodes red islands hain jinke beech koi arrow nahi — koi shared edge nahi matlab koi dependency nahi matlab koi waiting nahi.

Verify: $a = 10, b = 7$ . Data arrive hone ke baad total waves $= 1$ . Ek program-counter machine ko 2 sequential steps chahiye honge (ek add, ek subtract). Speed-up $= 2/1 = 2 \times$ — exactly wahi "parallelism for free" jo parent note ne promise ki thi. Yeh Instruction-Level Parallelism ki natural limit hai: independence missing edge ke roop mein visible hai.

Example 2 — Case B: ek forced chain

Forecast: independent ops ne 1 wave li. Kya aapko lagta hai do adds ki chain bhi 1 wave leti hai? Guess karo.

Wave 0. Tokens $x = 1, y = 2$ pehle $+$ (" $+_{1}$ ") par aate hain. Token $z = 3$ doosre $+$ (" $+_{2}$ ") ke ek input par aata hai. $+_{2}$ ka doosra input woh edge hai jo $+_{1}$ se aati hai — woh empty hai. Yeh step kyun? Humein notice karna hai ki $+_{2}$ abhi fireable nahi hai: uski ek edge mein token nahi hai.
Wave 1. $+_{1}$ ke dono inputs hain → fire karta hai → token $3$ emit karta hai $+_{2}$ ko feed karne wali edge par. $+_{2}$ abhi bhi is wave mein fire nahi kar sakta, kyunki woh token abhi-abhi mila hai — checking per wave hoti hai. Yeh step kyun? Data dependency ( $+_{1}$ se $+_{2}$ tak ki edge) sirf yahaan order force karti hai. Koi program counter nahi keh raha "pehle inner add karo" — khali edge yeh kehti hai.
Wave 2. $+_{2}$ ab $3$ ( $+_{1}$ se) aur $3$ ( $= z$ ) dekhta hai → fire karta hai → $r = 6$ .

Verify: $r = (1 + 2) + 3 = 6$ . ✓ Waves $= 2$ . Ex 1 se compare karo: same count of operations (2 adds) lekin yahaan woh overlap nahi kar sakte. Lesson: dataflow artificial order hataata hai, necessary order kabhi nahi.

Example 3 — Case C: diamond (fan-out + fan-in)

Forecast: $x$ dono $+$ aur $-$ ko chahiye. Kya yeh bottleneck create karta hai? Guess karo yes/no.

Wave 0. Tokens $x = 5, y = 3, z = 1$ aate hain. Specifically, $x$ do edges par copy hota hai — ek $+$ mein, ek $-$ mein. Yeh step kyun? Fan-out ka matlab hai ek producer kaafi consumers ko feed karta hai; dataflow mein jis value ki do nodes ko zaroorat hai woh do tokens ban jaati hai (ek copy per edge). Isse wait nahi hota.
Wave 1. $+$ ke paas $x = 5, y = 3$ hain → fire karta hai → $t_{1} = 8$ . Saath mein $-$ ke paas $x = 5, z = 1$ hain → fire karta hai → $t_{2} = 4$ . Dono saath fire karte hain (diamond ke left half ke andar Case A behavior). Yeh step kyun? $x$ share karna unhe chain nahi karta — har ek ki apni copy hai, isliye unki firing rules independent hain.
Wave 2. $\times$ node ab $t_{1} = 8$ aur $t_{2} = 4$ dekhta hai → fire karta hai → $r = 32$ . Yeh step kyun? Yeh fan-in hai: do edges ek node mein merge hoti hain. Order force hota hai (Case B) kyunki $\times$ ke inputs wave 1 se pehle exist nahi karte the.

Verify: $r = (5 + 3) \times (5 - 1) = 8 \times 4 = 32$ . ✓ Waves $= 2$ . Ek PC machine ko 3 steps chahiye (add, subtract, multiply). Speed-up $= 3/2 = 1.5 \times$ .

Example 4 — Cases D & E: degenerate nodes (constant aur identity)

Forecast: ek node jinke koi input edges nahi — uski firing rule kab satisfy hoti hai? Padhne se pehle guess karo.

Case D — constant node. Ek node jiske zero input edges hain uski requirements ka empty set hai. "Saare input edges ek token hold kar rahe hain" empty set ke liye vacuously true hai, isliye ek constant node hamesha ready rehta hai aur wave 0 par apni value emit karta hai (yahaan $1$ , aur alag se $7$ ). Yeh step kyun? Firing rule kehti hai "saare inputs present". Jab koi inputs nahi, toh wait karne ke liye kuch nahi — jaise "is room mein saare unicorns pink hain" tab sach hai jab koi unicorn hi nahi.
Case E — one-input identity-ish node. $\times$ node ko abhi bhi do tokens chahiye ( $x$ aur constant $1$ ). Yeh one-input node nahi hai. Lekin maan lo hamare paas neg(a) $= - a$ jaisa koi node tha: woh fire karta hai jaise hi uski single edge ek token hold kare. General rule scale karta hai: jitne bhi input edges hain sab full hone par fire karo — 0 (constant) aur 1 (unary) bhi include hai. Yeh step kyun? Beginners assume karte hain ki har node ko do operands chahiye. Rule hai "uske saare inputs", chahe woh number kuch bhi ho — 0 (constant) aur 1 (unary) bhi.
Wave 1. $\times$ ke paas $x = 12$ aur $1$ hain → fire karta hai → $12$ . $+$ ke paas yeh $12$ hai? Nahi — abhi nahi (yeh is wave mein aaya). Wave 2: $+$ ke paas $12$ aur $7$ hain → fire karta hai → $r = 19$ .

Verify: $r = (12 \times 1) + 7 = 19$ . ✓ Constants ne kuch bhi stall nahi kiya; sirf forced order $\times \to +$ chain thi (phir se Case B).

Example 5 — Case F: static dataflow token collision (stall)

Forecast: guess karo — kya machine silently overwrite karti hai, ya stall karti hai?

Wave 1. Iteration 1 ka token (value $v_{1}$ ) edge $E$ par baitha hai, downstream node se consume hone ka wait kar raha hai. Yeh step kyun? Hume state fix karni hai: $E$ occupied hai, capacity 1 hai.
Wave 2. Iteration 2 jaldi finish karta hai aur $v_{2}$ ko $E$ par emit karna chahta hai. Lekin $E$ pehle se $v_{1}$ hold kar raha hai. Static dataflow mein, ek edge mein zyada se zyada ek token ho sakta hai, isliye iteration 2 ka producer fire nahi kar sakta — woh stall karta hai jab tak $v_{1}$ consume nahi ho jaata. Yeh step kyun? Yeh static dataflow ki defining limitation hai (parent note): yeh ek hi subgraph ke invocations cleanly overlap nahi kar sakta. Figure mein red token dekho jo kale ke peeche atka hua hai.
Consequence. Iterations effectively us shared edge par serialize ho jaati hain — iterations mein koi pipeline parallelism nahi.

Verify (conceptual): Do "would-be" tokens = ${v_{1}, v_{2}}$ lekin edge capacity = $1$ , isliye dono place karne ki koshish se $∣ tokens on E ∣ \leq 1$ violate hota hai → stall hi ek legal outcome hai. Yahi woh problem hai jo Example 6 tags se fix karta hai.

Example 6 — Case G: dynamic (tagged) loop, overlapping iterations

Forecast: answer $1 + 2 + 3$ hai. Lekin kitni waves agar iterations overlap karein? Guess karo.

Tagged firing rule yaad karo (parent note): ek node tabhi fire karta hai jab uske paas same tag $τ$ wale do tokens $⟨ v_{1}, τ ⟩$ aur $⟨ v_{2}, τ ⟩$ hoon, $⟨ f (v_{1}, v_{2}), τ ⟩$ produce karta hai. Tag "main kaun si iteration hoon" wala sticker hai — figure mein har token par red label.

Iteration 1 ( $τ_{1}$ ). Tokens $⟨ s u m = 0, τ_{1} ⟩$ aur $⟨ i = 1, τ_{1} ⟩$ match karte hain → fire karo → $⟨ 1, τ_{1} ⟩$ . Yeh step kyun? Dono tokens $τ_{1}$ carry karte hain, isliye matching unit unhe pair karti hai. Yeh partial sum iteration 2 ko feed karega.
Iteration 2 ( $τ_{2}$ ) 1 finish hone ke while start ho sakti hai. $i = 2$ token, $τ_{2}$ tag ke saath, already flow kar raha hai. Yeh sirf apne $s u m$ token $⟨ 1, τ_{2} ⟩$ ka wait karta hai (iteration 1 ka result, re-tagged $τ_{2}$ mein). Fire karo → $⟨ 3, τ_{2} ⟩$ . Yeh step kyun? Kyunki tags alag hain, iteration 2 ka fast $i$ -token kabhi galti se iteration 1 ke slow $s u m$ -token se pair nahi ho sakta — machine sirf matching $τ$ par fire karti hai. Yahi hai jo static dataflow nahi kar sakta tha (Ex 5).
Iteration 3 ( $τ_{3}$ ). $⟨ 3, τ_{3} ⟩ + ⟨ i = 3, τ_{3} ⟩$ → fire karo → $⟨ 6, τ_{3} ⟩$ .

Verify: $\sum_{i = 1}^{3} i = 1 + 2 + 3 = 6 = \frac{3 \cdot 4}{2}$ . ✓ Sums ki chain zaroor sequential hai (har ek ko pichla partial chahiye), lekin ingredient tokens ( $i = 1, 2, 3$ ) sab parallel mein stream karte hain — yeh loop-level / pipeline parallelism hai, sirf tags se enable hua.

Example 7 — Case H: limiting case — tags drop karo, garbage milo

Forecast: guess karo machine true running sum ki jagah kya value compute kar sakti hai.

Bug. Tags ke bina, matching unit do input edges par baithne wale kisi bhi do tokens ko pair kar deti hai. Maan lo $+$ node $s u m = 0$ (iteration 1 ka) ko $i = 2$ (iteration 2 ka) ke saath grab karta hai. Yeh step kyun? Yeh wahi "iteration-3 ka $x$ , iteration-7 ke $y$ se match karta hai" failure hai jiske baare mein parent note ne warn kiya tha — machine ke paas yeh batane ka koi tarika nahi ki kiska token kiska hai.
Garbage. Yeh $0 + 2 = 2$ compute karta hai aur ise "iteration 1 ke baad partial sum" label karta hai, jo galat hai (true value $1$ hai). Downstream sab kuch ab corrupted hai. Yeh step kyun? Ek mismatched pair poora running total poison kar deta hai.

Verify: Iteration 1 ke baad true partial $= 0 + 1 = 1$ . Garbage value $= 0 + 2 = 2$ . Kyunki $2 \neq = 1$ , computation corrupted hai. ✓ Isliye dynamic dataflow exist karta hai — tag decoration nahi hai, yeh correctness hai. (Parent ke Connections se fun fact: Out-of-Order Execution real CPUs mein register renaming / reservation stations = tagged-token matcher ke saath exactly yahi problem solve karta hai.)

Example 8 — Case I: real-world word problem (kitchen)

Forecast: naive sequential time $3 + 2 + 1 = 6$ minutes hai. Compute karne se pehle dataflow time guess karo.

Graph banao. Nodes: Sandwich (3 min), Smoothie (2 min), Plate (1 min). Edges: Sandwich → Plate, Smoothie → Plate. Yeh shared source ke bina diamond hai — ek fan-in (Case C). Yeh step kyun? Independent tasks (Case A: sandwich vs smoothie) concurrently run karte hain; Plate dono ka wait karta hai (uski firing rule chahti hai dono input edges full hon).
Ek combo timing. Sandwich aur Smoothie $t = 0$ par parallel mein fire karte hain. Plate tab tak fire nahi kar sakta jab tak dono done nahi — isliye woh slower ka wait karta hai $= max (3, 2) = 3$ min. Phir plating $1$ min add karta hai. Yeh step kyun? Plate ki firing rule = "saare inputs ready", isliye uska start time = predecessors ke finish times ka max.
Ek combo ka total $= max (3, 2) + 1 = 4$ minutes.
Do combos, dynamic machine. Combo-A ko $τ_{A}$ , combo-B ko $τ_{B}$ tag karo. Extra cooks ke saath, combo-B ka sandwich/smoothie bhi $t = 0$ par fire karta hai, $τ_{B}$ tagged. Plate node $τ_{A}$ tokens ke liye ek baar aur $τ_{B}$ tokens ke liye ek baar fire karta hai — tags table A ki tray ko table B se alag rakhte hain. Dono plates $t = 3$ par proceed kar sakti hain. Total $= 4$ minutes dono ke liye. Yeh step kyun? Yeh exactly Ex 6 ka tagged overlap hai, everyday costume mein — har ingredient par sticker hi tag hai.

Verify: Ek combo dataflow time $= max (3, 2) + 1 = 4$ min vs sequential $3 + 2 + 1 = 6$ min (speed-up $6/4 = 1.5 \times$ ). Do combos: abhi bhi $4$ min (3-min sandwich se limited, count se nahi) vs sequential $12$ min → speed-up $3 \times$ . ✓

Example 9 — Case J: exam-style throughput twist

Forecast: (a) guess karo — kya yeh 12 (saare nodes) hai ya 4 (chain)?

(a) Latency = critical path, node count nahi. Unlimited hardware ke saath, saare independent nodes saath fire karte hain; sirf woh cheez jo aap parallelize nahi kar sakte woh ek dependency chain hai. Isliye minimum waves $= L = 4$ . Yeh step kyun? Critical path "output-of-one-is-input-of-next" edges ka sabse lamba sequence hai (Case B stacked). Path se bahar sab overlap karta hai (Case A). $12$ nodes latency ke liye matter nahi karte — sirf sabse lambi chain matter karti hai.
(b) Pipelined throughput. Jab pipeline full ho jaati hai, har wave mein ek iteration complete hoti hai (initiation interval $= 1$ ). Pehli iteration drain hone mein $L = 4$ waves leti hai; baaki $99$ mein se har ek ek wave baad finish hota hai. Yeh step kyun? Yeh pipeline formula hai: total $=$ (fill latency) $+$ (remaining iterations) $= L + (K - 1)$ .
Compute: total $= 4 + (100 - 1) = 103$ waves.

Verify: (a) $L = 4$ waves. ✓ (b) $L + (K - 1) = 4 + 99 = 103$ waves. Sanity: pipelining ke bina aap $L \cdot K = 4 \times 100 = 400$ waves paate; tagged pipelining $103$ deta hai, ek $400/103 \approx 3.88 \times$ throughput win — scale par dynamic dataflow ke overlapping (Case G) ka payoff.

Recall

Recall Kaun sa case sequential order force karta hai?

Case B (chained dependency) aur har fan-in (Case C, Ex 8 ki plating). Order khali input edges se aata hai, program counter se kabhi nahi. ::: Ek node tab tak fire nahi kar sakta jab tak uske saare input edges tokens hold na karein; ek chain ka matlab hai har node ka input tab tak exist nahi karta jab tak uska predecessor fire na kare.

Recall Ek constant (zero-input) node immediately fire kyun karta hai?

Question ::: Uski required input edges ka set empty hai, isliye "saare inputs present" vacuously true hai — wait karne ke liye kuch nahi.

Recall Static vs dynamic ek collision sentence mein?

Question ::: Static stall karta hai jab doosra token ek occupied capacity-1 edge par jaana chahta hai (Ex 5); dynamic har iteration ko ek tag deta hai taaki kaafi tokens coexist kar sakein aur iterations overlap ho sakein (Ex 6).

Recall Unlimited hardware ke saath dataflow run ki latency?

Question ::: Critical (sabse lambi dependency) path ki length — total node count nahi.

Connections

Dataflow architectures — woh parent note jisme yeh page drill karta hai.
Von Neumann architecture — sequential baseline jiske against hum speed-ups compare karte rehte hain.
Instruction-Level Parallelism — Case A uski theoretical limit hai.
Out-of-Order Execution — Ex 7 ka tag-matching literally reservation stations ka kaam karne ka tarika hai.
Systolic Arrays — ek regular, statically-scheduled cousin (Ex 5 ke static case se relevant).
Directed Acyclic Graph (DAG) — woh structure jiska critical path Ex 9 ko drive karta hai.
Loop-Level Parallelism — Examples 6 aur 9 uski dataflow realization hain.