Dataflow architectures: Visual walkthrough — Hardware deep dive

Step 1 — A node is a little machine with input slots

WHAT. The smallest piece of a dataflow program is a node: a box that does one operation (an $+$ , a $-$ , a $\times$ ). Each node has input slots on top (where data comes in) and one output spout at the bottom (where its answer leaves).

WHY start here. Before we can talk about a "graph" or "firing", we need to know what a single box wants: it wants every one of its input slots to be filled. Nothing else. This single desire is the whole engine.

PICTURE. Below, a lone $+$ node. Its two input slots are the two circles on top; its output spout is the arrow at the bottom. Right now both slots are empty (grey) — so the node is asleep.

Step 2 — A token is a value with a delivery van

WHAT. Data does not sit on wires here; it travels as a token. Picture a token as a small van carrying one number. When the van arrives at a slot, that slot is now filled.

WHY a van, not a wire? On a normal circuit a wire simply holds a voltage forever. A token is different: it is produced, it flows, and it is consumed (used up) when the node fires. Thinking "van that delivers and then leaves" stops the classic mistake of treating tokens like permanent wire signals.

PICTURE. Two tokens — $x = 3$ (blue van) and $y = 4$ (yellow van) — drive toward the $+$ node's two slots. Watch each van land in its slot.

In the picture, the symbol $x = 3$ means "the value $3$ , currently riding a token toward the left slot"; $y = 4$ is the value $4$ heading for the right slot.

Step 3 — The firing rule: fire the instant every slot is full

WHAT. Now the central law. A node fires — actually performs its operation — the moment all of its input slots are filled, and not one instant before.

WHY this exact rule? This is the whole reason dataflow exists. There is no program counter shouting "your turn now". The only thing that grants permission to run is: do I have all my ingredients? This is why it's called dataflow — data readiness is the trigger.

PICTURE. The $+$ node with both slots now full ( $3$ and $4$ ). The firing rule is satisfied → the node lights up (green), computes $3 + 4$ , and emits a new token $t = 7$ from its spout. Notice the two input vans are now gone — consumed.

left slot filled x = 3 and right slot filled y = 4 ⟹ rule satisfied [+] fires ⟹ new output token t = 7

Reading the formula left to right: the two braces on the left are the precondition (both slots full); the middle brace is the action (fire); the right brace is the effect (a fresh token appears, carrying the sum).

Step 4 — Wire nodes together: the program is a graph

WHAT. Connect one node's output spout to another node's input slot with an edge (an arrow). Do this for the whole expression and you get the dataflow graph — the program itself, drawn as a picture.

WHY a graph and not a list? A list forces a single order (line 1, then line 2…). A graph draws only the orderings that actually matter: an arrow from A to B means "B needs A's answer". Two nodes with no arrow between them are independent — a fact the graph makes visible. This is the mathematical object called a Directed Acyclic Graph (DAG).

PICTURE. Here is the parent's expression $r = (x + y) \times (x - z)$ assembled. The $+$ node and the $-$ node both feed the $\times$ node. Crucially, no arrow connects $+$ to $-$ : they don't need each other.

r = output of [+] node (x + y) \times output of [-] node (x - z)

Each brace names which node produces that piece. The two braces are the two inputs the $\times$ node is waiting for.

Step 5 — Run it: independent nodes fire together (automatic parallelism)

WHAT. Feed in the starting tokens $x, y, z$ and let the firing rule do everything. We watch the graph execute in waves.

WHY it goes parallel by itself. The $+$ node and the $-$ node both have their slots filled at the same instant (both consume $x$ ; one takes $y$ , the other $z$ ). Two firing rules satisfied simultaneously, no connecting edge → the hardware simply runs both at once. Nobody scheduled this; the graph's shape is the schedule. This is exactly the limit that Instruction-Level Parallelism chases.

PICTURE. Two firing waves.

Wave 1 (parallel): $[+]$ and $[-]$ fire together, producing $t_{1} = x + y$ and $t_{2} = x - z$ .
Wave 2: now $\times$ finally has both slots full, fires, and emits $r$ .

Trace with numbers $x = 3, y = 4, z = 1$ :

Wave 1: Wave 2: t_{1} = x + y = 3 + 4 = 7, t_{2} = x - z = 3 - 1 = 2 r = t_{1} \times t_{2} = 7 \times 2 = 14

Here $t_{1}$ is "the token leaving the $+$ node", $t_{2}$ is "the token leaving the $-$ node", and $r$ is the final token — the answer. The $\times$ node could not have fired in Wave 1: one of its slots was still empty. The data dependency, and nothing else, forced it to wait.

Step 6 — Degenerate case: what if a token never arrives? (deadlock)

WHAT. Suppose the $z$ token gets lost / is never produced. Then the $-$ node has slot-1 filled ( $x$ ) but slot-2 empty forever.

WHY show this. A rule as strict as "fire only when all slots full" has a shadow: if an input never comes, the node never fires, and everything downstream of it stalls too. This is a real hazard — called a deadlock — and you must be able to see it.

PICTURE. The $-$ node stuck half-full; the $\times$ node behind it starving because one of its inputs ( $t_{2}$ ) can never be born. The $+$ branch, being independent, still completes — showing the stall is local to the dependency chain.

WHAT. Now reuse the same graph for a loop. Iteration 1 computes sum + i for $i = 1$ ; iteration 2 for $i = 2$ . But there is only one $+$ node. If iteration 2's fast $i$ -token arrives while iteration 1's slow $s u m$ -token is still in flight, the node might pair $s u m$ from run 1 with $i$ from run 2 — garbage.

WHY this breaks static dataflow. In static dataflow an edge holds at most one token, so the node just grabs whatever two tokens are present — it cannot tell them apart. To overlap iterations safely we need each token to say which run it belongs to.

PICTURE. Left: static — a fast blue $i_{2}$ wrongly meets slow yellow $s u m_{1}$ (red collision). Right: the fix — every token wears a tag $τ$ (a coloured sticker); the node fires only when both slots hold the same tag.

Trace the loop $\sum_{i = 1}^{3} i$ with tags $τ_{1}, τ_{2}, τ_{3}$ :

τ_{1} : τ_{2} : τ_{3} : 0 + 1 = 1 1 + 2 = 3 3 + 3 = 6

The hardware unit that holds waiting tokens and releases a pair only when tags match is the matching store. Because non-matching tokens simply wait rather than colliding, the iterations may overlap in a pipeline — this cheap overlap is exactly what enables Loop-Level Parallelism. (Modern CPUs hide this same trick inside Out-of-Order Execution: reservation stations are a tagged-token matching store.)

The one-picture summary

Everything above, on one canvas: tokens ride in ( $x, y, z$ ), independent nodes fire in the same wave, the multiply waits for its dependency, a lost token can starve a chain, and tags keep concurrent runs from crossing.

Recall Feynman: tell it back in plain words

Every cook in the kitchen wants all their ingredients on the table before they start — that's the firing rule. Ingredients arrive as little delivery vans (tokens), each carrying one number; when a van lands in a cook's slot, that slot is full. The recipe isn't a numbered list — it's a picture of arrows (the graph) showing whose finished dish becomes whose ingredient. Cooks with no arrow between them share nothing, so they cook at the same time — free parallelism. But if a van gets lost, its cook waits forever and starves everyone downstream (deadlock). And when the same kitchen serves many tables at once, every ingredient wears a sticker (a tag) saying which table it's for, so table 3's salad never mixes with table 7's soup — that's dynamic, tagged dataflow, checked by the matching store.

Active recall

Why can the

+

and

-

nodes fire in the same wave?

They share no edge (are independent) and both their slots fill at once, so both firing rules are satisfied simultaneously.

Why must the

\times

node wait?

One of its inputs (

t_{2} = x - z

) does not exist until the

-

node fires — the data dependency forces the order.

What happens if an input token is never produced?

That node never fires (deadlock) and every node depending on it stalls; independent branches still finish.

In the loop, why can

i_{2}

wrongly meet

s u m_{1}

in static dataflow?

An edge holds only one token and the node cannot tell which iteration a token belongs to, so it pairs whatever is present.

What condition does the matching store enforce before firing?

Both waiting tokens must carry the same tag

τ