Dataflow architectures: Exercises — Hinglish deep dive

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

Shuru karne se pehle, ek shared picture jo har exercise mein kaam aayegi:

Har item ke liye bolo ki woh Von Neumann machine ka hissa hai ya dataflow machine ka: (a) program counter, (b) firing rule, (c) tokens on edges, (d) fetch–decode–execute in address order, (e) "instruction tab chalti hai jab uske operands ready hon".

Recall Solution 1.1

(a) Von Neumann — program counter woh address-marcher hai. (b) Dataflow — firing rule PC ki jagah leta hai. (c) Dataflow — data graph edges par tokens ki tarah rehta hai. (d) Von Neumann — order instruction addresses se aata hai. (e) Dataflow — yeh hi firing rule hai, words mein bataya gaya. Kyun: ek program counter aur ek firing rule ek hi sawaal ke do rival jawab hain: "kya decide karta hai ki ek instruction kab chalegi?". Ek machine dono mein se ek use karti hai, kabhi bhi dono ko master nahi banati.

Exercise 1.2

Program hai $r = (x + y) \times (x - z)$ . Iske dataflow graph mein kitne nodes hain aur kitne edges? (Input tokens $x, y, z$ ko sources maano jo edges ko feed karte hain, nodes nahi.)

Recall Solution 1.2

Nodes = 3: ek $+$ , ek $-$ , ek $\times$ . Edges = 6: $x \to +$ , $y \to +$ , $x \to -$ , $z \to -$ , $+ \to \times$ , $- \to \times$ . Figure s01 dekho: $x$ do alag-alag nodes ko fan out karta hai, isliye $x$ do edges contribute karta hai, ek nahi.

Level 2 — Application

Exercise 2.1

$r = (x + y) \times (x - z)$ ke graph ko $x = 4, y = 3, z = 1$ ke saath use karke firing trace likho: kaun sa node har time step par fire karta hai, aur woh kaun sa token emit karta hai. Maano har operation exactly ek time step leti hai.

Recall Solution 2.1

Step 0: source tokens aate hain: $x = 4, y = 3, z = 1$ . Step 1: $+$ ke dono inputs hain ( $4, 3$ ) → fires → $t_{1} = 7$ emit karta hai. $-$ ke dono inputs hain ( $4, 1$ ) → fires → $t_{2} = 3$ emit karta hai. Dono ek hi step mein, kyunki unke firing rules ek saath satisfy hain aur unhe koi edge connect nahi karta. Step 2: $\times$ ke paas ab $t_{1} = 7$ aur $t_{2} = 3$ hain → fires → $r = 7 \times 3 = 21$ emit karta hai. Answer: $r = 21$ , 2 time steps mein khatam.

Exercise 2.2

Wahi expression ek Von Neumann CPU par jo likhe hue order $+, -, \times$ mein ek operation per step karta hai. Kitne time steps? Iska dataflow par speed-up kya hai?

Recall Solution 2.2

Von Neumann karta hai $+$ (step 1), $-$ (step 2), $\times$ (step 3) = 3 steps. Dataflow = 2 steps. Speed-up $= \frac{3}{2} = 1.5 \times$ . Gain kyun: $+$ aur $-$ independent hain (unke beech koi edge nahi), isliye dataflow unhe ek step mein overlap karta hai; PC ne unhe alag kiya tha.

Level 3 — Analysis

Exercise 3.1

Critical path dependent nodes ki sabse lambi chain hai — minimum steps jo koi bhi hardware beat nahi kar sakta. $r = (x + y) \times (x - z)$ ke liye critical path length nikalo. Phir argue karo ki ek teesra adder add karna isse kyun speed up nahi karega.

Recall Solution 3.1

Sabse lambi dependency chain hai: (ek $+$ ya $-$ ) $\to$ ( $\times$ ) = 2 nodes = 2 steps. Hardware add karna sirf independent kaam ko parallel mein chalane mein help karta hai. Lekin $\times$ ko apne parent ka token wait karna hi padega — woh wait ek data dependency hai, adders ki kami nahi. Teesre adder ke paas kuch ready nahi hai karne ko, isliye answer 2 steps hi rehta hai. Figure s02 mein, red path critical path hai; extra adder (grey, dashed) idle baitha hai. Rule of thumb: minimum time = critical path ki length; maximum useful parallelism = graph ki width.

Exercise 3.2

$r = ((a + b) + (c + d)) + ((e + f) + (g + h))$ evaluate karo — 8 numbers ka sum ek balanced tree ki tarah. (a) Kitne $+$ nodes? (b) Unlimited hardware ke saath, kitne steps? (c) Strictly sequential accumulator (sum += next) kitne steps lega?

Recall Solution 3.2

(a) 8 numbers add karne ke liye 7 additions chahiye (har $+$ pile se ek number hatata hai: $8 \to 1$ ke liye $7$ merges chahiye). (b) Balanced tree ki depth $lo g_{2} 8 = 3$ hai: level 1 chaar inner sums parallel mein karta hai (1 step), level 2 do mid sums karta hai (1 step), level 3 final sum karta hai (1 step) → 3 steps. (c) Sequential accumulator $7$ additions ek ke baad ek karta hai → 7 steps. Speed-up $= 7/3 \approx 2.33 \times$ , aur $n$ numbers ke liye yeh $\frac{n - 1}{lo g _{2} n}$ ki tarah badhta hai.

Level 4 — Synthesis

Exercise 4.1

Loop sum = sum + i ko $i = 1, 2, 3$ ke liye draw (describe) karo, starting $s u m = 0$ , ek static machine mein (ek edge par zyada se zyada ek token). Phir step by step explain karo ki iterations yahan kyun overlap nahi kar sakti.

Recall Solution 4.1

Ek $+$ node reuse hota hai. Iske inputs current $s u m$ token aur current $i$ token hain; iska output back $s u m$ input edge mein feed hota hai (ek cycle).

$i = 1$ : tokens $⟨ s u m = 0 ⟩, ⟨ i = 1 ⟩$ → fires → $s u m = 1$ .
$i = 2$ : ab $⟨ s u m = 1 ⟩, ⟨ i = 2 ⟩$ → fires → $s u m = 3$ .
$i = 3$ : $⟨ s u m = 3 ⟩, ⟨ i = 3 ⟩$ → fires → $s u m = 6$ . Final $s u m = 6$ . Overlap kyun nahi: $s u m$ edge par ek waqt mein sirf ek token ho sakta hai (static rule). Iteration 2 literally apne inputs tab tak nahi rakh sakta jab tak iteration 1 ka token edge se nikal nahi jaata. Har iteration ko pichle $s u m$ ki bhi zaroorat hoti hai, isliye loop-carried dependency unhe chain kar deti hai. Dono facts strict serial order force karte hain → 3 steps.

Exercise 4.2

Ab ek loop unroll karo jiske body mein koi loop-carried dependency nahi hai: out[i] = a[i] * b[i] for $i = 1, 2, 3$ ek dynamic (tagged) machine par. Tokens $⟨ v a l u e, τ_{i} ⟩$ ki tarah likhe jaate hain. Firing trace aur total steps do.

Recall Solution 4.2

Ek $\times$ node, lekin tokens tags $τ_{1}, τ_{2}, τ_{3}$ (iteration stickers) carry karte hain. Matching store $\times$ ko sirf un tokens ke liye fire karta hai jinke tags agree karte hain.

Ready set 1: $⟨ a_{1}, τ_{1} ⟩, ⟨ b_{1}, τ_{1} ⟩$ → fire → $⟨ o u t_{1}, τ_{1} ⟩$ .
Ready set 2: $⟨ a_{2}, τ_{2} ⟩, ⟨ b_{2}, τ_{2} ⟩$ → fire → $⟨ o u t_{2}, τ_{2} ⟩$ .
Ready set 3: same with $τ_{3}$ . Kyunki koi loop-carried dependency nahi hai (koi output baad ke input ko feed nahi karta), teeno tagged sets independent hain. Teen multiplier units ke saath woh parallel mein = 1 step mein chalte hain; ek single pipelined multiplier ke saath woh back-to-back stream karte hain. Point: tags ek graph ko teen concurrent instances host karne dete hain bina $a_{2}$ ke kabhi $b_{1}$ se pair hue.

Level 5 — Mastery

Exercise 5.1

Modern out-of-order CPUs (Tomasulo's algorithm, reservation stations) ko aksar "ek hidden dataflow engine" kaha jaata hai. In dataflow concepts ko unke CPU counterparts par map karo: (a) token, (b) tag, (c) firing rule, (d) matching store. Phir bolo ki dataflow globally kya karta hai jo Tomasulo sirf locally karta hai.

Recall Solution 5.1

(a) token $\leftrightarrow$ ek operand value jo common data bus par broadcast hoti hai. (b) tag $\leftrightarrow$ register-renaming tag / reservation-station ID jo identify karta hai ki kaun sa pending result yeh hai. (c) firing rule $\leftrightarrow$ ek reservation station apni instruction tab issue karta hai jab saare source operands aa jaayein. (d) matching store $\leftrightarrow$ reservation stations jo bus dekh rahe hain, woh values grab karte hain jinke tags unhe chahiye. Global vs local: dataflow poore program ko ek dependency graph ki tarah express karta hai, isliye parallelism program size se unlimited hai. Tomasulo sirf ek chhoti si instruction window (kuch dozen in-flight instructions) dekhta hai, isliye woh dataflow ko locally aur briefly re-discover karta hai. Same idea, alag scope. Dekho Out-of-Order Execution.

Exercise 5.2

Ek computation mein work $W = 64$ operations aur critical-path depth $D = 8$ hai. (a) Dataflow ke timing law ke according, fastest possible finishing time (unlimited hardware) kya hai? (b) Kitne processing units $P$ chahiye taaki $D$ steps mein finish karna hardware ki kami se block na ho? Rough balance $P \geq W / D$ use karo. (c) Saare $W$ ops sequentially chalane ke upar speed-up kya hai?

Recall Solution 5.2

(a) Fastest time = critical-path depth = $D = 8$ steps (koi bhi sabse lambi dependency chain ko beat nahi kar sakta). (b) $P \geq W / D = 64/8 = 8$ units. Isse kam hone par, kuch ready work queue karega aur tumhe 8 steps se aage le jaayega; zyada hone par extra units idle rahenge. (c) Sequential time $= W = 64$ ; parallel time $= D = 8$ ; speed-up $= 64/8 = 8 \times$ . Yeh Instruction-Level Parallelism ceiling hai jo explicitly dikhaya gaya hai: dataflow woh natural limit reach karta hai jo purely graph ki shape se set hoti hai.

Recall summary

Recall Quick self-quiz

Dataflow mein minimum steps kiske barabar hote hain? ::: Critical-path depth (dependent nodes ki sabse lambi chain). Hardware kitni help kar sakta hai, yeh kya limit karta hai? ::: Graph ki depth; parallelism sirf width ko shrink karta hai, depth ko kabhi nahi. Numbers $1.. n$ ko balanced tree ki tarah add karne mein kitne steps lagte hain? ::: About $lo g_{2} n$ steps, $n - 1$ additions use karke. Static loop mein sum+=i iterations overlap kyun nahi kar sakti? ::: Ek edge par ek token plus loop-carried dependency strict serial order force karti hai. Tags kya fix karte hain, aur kya nahi fix kar sakte? ::: Woh concurrent instances mein naming/matching fix karte hain; woh ek real loop-carried data dependency nahi hata sakte. Tomasulo mein reservation stations kaun se dataflow unit se correspond karte hain? ::: Matching store se (woh fire karte hain jab saare tagged operands aa jaayein). Work $W$ aur depth $D$ ke saath, roughly kitne units tumhe $D$ -step floor par rakhte hain? ::: About $P \geq W / D$ .

Connections

Dataflow architectures — woh parent concepts jinhe yeh exercises drill karte hain.
Directed Acyclic Graph (DAG) — woh structure jiska depth minimum time set karta hai.
Instruction-Level Parallelism — woh natural ceiling jo exercise 5.2 compute karta hai.
Out-of-Order Execution — exercise 5.1 ka "hidden local dataflow engine".
Loop-Level Parallelism — exercises 4.1 vs 4.2 dikhate hain ki yeh kab available hai aur kab nahi.
Systolic Arrays — ek aur data-driven style jisme fixed, regular graph hota hai.
Von Neumann architecture — woh sequential baseline jiske against har speed-up measure hota hai.

Exercises — Dataflow architectures

Level 1 — Recognition

Exercise 1.1