Exercises — Dataflow architectures

(a) Von Neumann — the program counter is the address-marcher. (b) Dataflow — firing rule replaces the PC. (c) Dataflow — data lives as tokens on graph edges. (d) Von Neumann — order comes from instruction addresses. (e) Dataflow — this is the firing rule stated in words. Why: a program counter and a firing rule are two rival answers to the single question "what decides when an instruction runs?". A machine uses one or the other, never both as the master.

Nodes = 3: one $+$, one $-$, one $\times$. Edges = 6: $x\to +$, $y\to +$, $x\to -$, $z\to -$, $+\to \times$, $-\to \times$. Look at figure s01: $x$ fans out to two different nodes, which is why $x$ contributes two edges, not one.

Step 0: source tokens arrive: $x=4,y=3,z=1$. Step 1: the $+$ has both inputs ($4,3$) → fires → emits $t_1=7$. The $-$ has both inputs ($4,1$) → fires → emits $t_2=3$. Both in the same step, because their firing rules are satisfied at once and no edge connects them. Step 2: the $\times$ now has $t_1=7$ and $t_2=3$ → fires → emits $r=7\times 3=21$. Answer: $r=21$, finished in 2 time steps.

Von Neumann does $+$ (step 1), $-$ (step 2), $\times$ (step 3) = 3 steps. Dataflow = 2 steps. Speed-up $=\frac{3}{2}=1.5\times$. Why the gain: the $+$ and $-$ are independent (no edge between them), so dataflow overlaps them into one step; the PC forced them apart.

The longest dependency chain is: (a $+$ or $-$) $\to$ ($\times$) = 2 nodes = 2 steps. Adding hardware can only help independent work run in parallel. But the $\times$ must wait for its parent's token — that wait is a data dependency, not a shortage of adders. A third adder has nothing ready to do, so the answer stays 2 steps. In figure s02, the red path is the critical path; the extra adder (grey, dashed) sits idle. Rule of thumb: minimum time = length of critical path; maximum useful parallelism = width of the graph.

(a) Adding 8 numbers needs 7 additions (each $+$ removes one number from the pile: $8\to 1$ needs $7$ merges). (b) The balanced tree has depth ${\log }_{2}8=3$: level 1 does the four inner sums in parallel (1 step), level 2 does the two mid sums (1 step), level 3 does the final sum (1 step) → 3 steps. (c) A sequential accumulator does $7$ additions one after another → 7 steps. Speed-up $=7/3\approx 2.33\times$, and it grows like $\frac{n-1}{{\log }_{2}n}$ for $n$ numbers.

One $+$ node is reused. Its inputs are the current $sum$ token and the current $i$ token; its output feeds back into the $sum$ input edge (a cycle).

• $i=1$: tokens $⟨sum=0⟩,⟨i=1⟩$ → fires → $sum=1$.
• $i=2$: now $⟨sum=1⟩,⟨i=2⟩$ → fires → $sum=3$.
• $i=3$: $⟨sum=3⟩,⟨i=3⟩$ → fires → $sum=6$. Final $sum=6$. Why no overlap: the $sum$ edge may hold only one token at a time (static rule). Iteration 2 literally cannot place its inputs until iteration 1's token has left the edge. Each iteration also needs the previous $sum$, so the loop-carried dependency chains them anyway. Both facts force strict serial order → 3 steps.

One $\times$ node, but tokens carry tags ${\tau }_1,{\tau }_2,{\tau }_3$ (iteration stickers). The matching store fires the $\times$ only for tokens whose tags agree.

• Ready set 1: $⟨a_1,{\tau }_1⟩,⟨b_1,{\tau }_1⟩$ → fire → $⟨ou{t}_1,{\tau }_1⟩$.
• Ready set 2: $⟨a_2,{\tau }_2⟩,⟨b_2,{\tau }_2⟩$ → fire → $⟨ou{t}_2,{\tau }_2⟩$.
• Ready set 3: same with ${\tau }_3$. Because there is no loop-carried dependency (no output feeds a later input), all three tagged sets are independent. With three multiplier units they run in parallel = 1 step; with a single pipelined multiplier they stream through back-to-back. The point: tags let one graph host three concurrent instances without $a_2$ ever pairing with $b_1$.

(a) token $\leftrightarrow$ an operand value broadcast on the common data bus. (b) tag $\leftrightarrow$ the register-renaming tag / reservation-station ID identifying which pending result this is. (c) firing rule $\leftrightarrow$ a reservation station issues its instruction the instant all its source operands have arrived. (d) matching store $\leftrightarrow$ the reservation stations watching the bus, grabbing values whose tags they await. Global vs local: dataflow expresses the entire program as one dependency graph, so parallelism is unlimited by program size. Tomasulo only sees a small instruction window (a few dozen in-flight instructions), so it re-discovers dataflow locally and briefly. Same idea, different scope. See Out-of-Order Execution.

(a) Fastest time = critical-path depth = $D=8$ steps (nothing beats the longest dependency chain). (b) $P\ge W/D=64/8=8$ units. With fewer, some ready work would queue and push you past 8 steps; with more, the extra units idle. (c) Sequential time $=W=64$; parallel time $=D=8$; speed-up $=64/8=8\times$. This is the Instruction-Level Parallelism ceiling made explicit: dataflow reaches the natural limit set purely by the graph's shape.

Minimum steps in dataflow equal what? ::: The critical-path depth (longest chain of dependent nodes). What limits how much hardware can help? ::: The graph's depth; parallelism only shrinks width, never depth. Adding numbers $\mathrm{1..}n$ as a balanced tree takes how many steps? ::: About ${\log }_{2}n$ steps, using $n-1$ additions. Why can a static loop with sum+=i not overlap iterations? ::: One token per edge plus a loop-carried dependency forces strict serial order. What do tags fix, and what can they NOT fix? ::: They fix naming/matching across concurrent instances; they cannot remove a real loop-carried data dependency. Reservation stations in Tomasulo correspond to which dataflow unit? ::: The matching store (they fire when all tagged operands arrive). With work $W$ and depth $D$, roughly how many units keep you at the $D$-step floor? ::: About $P\ge W/D$.