Worked examples — Dataflow architectures

This page is the "hands dirty" companion to Dataflow architectures. The parent note built the rules: a program is a directed graph, edges carry tokens (packets holding a value, and in the dynamic case a tag), and a node fires the instant all its input edges hold matching tokens. Here we run those rules by hand on every kind of situation a dataflow graph can meet — so that when an exam or a real machine throws one at you, you have already seen its twin.

Before we start, one promise from the contract: nothing is used before it is drawn. If a word like token, tag, fire, epoch appears, look at the picture beside it — the picture is the definition.

---

The scenario matrix

Every dataflow question is one of a small number of shapes. The table below is the whole zoo. Each worked example below is stamped with the cell it lives in, and together they cover every row.

#	Case class	What is unusual about it	Example that covers it
A	Pure independent ops (the "free parallelism" case)	Two nodes share no edge → fire together	Ex 1
B	Chained dependency (forced sequential order)	Output of one is input of next → order forced by data, not by a PC	Ex 2
C	Diamond (fan-out then fan-in)	One value feeds two nodes, results re-merge	Ex 3
D	Degenerate: a constant / zero-input node	A node with no data edges — when does it fire?	Ex 4
E	Degenerate: identity / one-input op	A node needing only one token	Ex 4
F	Static conflict (two tokens want the same edge)	Edge capacity = 1 token → the machine stalls	Ex 5
G	Dynamic loop with tags (overlapping iterations)	Iterations run concurrently, tags keep them apart	Ex 6
H	Tag mismatch / the "garbage" limiting case	What happens if tags are dropped	Ex 7
I	Real-world word problem	Map an everyday process onto the firing rule	Ex 8
J	Exam-style twist (throughput / speed-up numbers)	Count firing "waves", compute parallel speed-up	Ex 9

---

Example 1 — Case A: pure independent operations

Forecast: guess now — does the $-$ node have to wait for the $+$ node? Write down "yes" or "no" before reading on.

1. Wave 0 — tokens arrive. Tokens $x=4,y=6$ land on the two input edges of the $+$ node; $p=9,q=2$ land on the input edges of the $-$ node. Why this step? The firing rule only ever looks at input edges, so first we must place the starting data.
2. Wave 1 — check every node. The $+$ node sees both its inputs → it fires, emitting $a=4+6=10$. The $-$ node also sees both its inputs → it fires in the same wave, emitting $b=9-2=7$. Why this step? Their firing rules are satisfied independently. Look at the figure: the two nodes are the red islands with no arrow bridging them — no shared edge means no dependency means no waiting.

Verify: $a=10,b=7$. Total waves after data arrival $=1$. A program-counter machine would need 2 sequential steps (one add, one subtract). Speed-up $=2/1=2\times$ — exactly the "parallelism for free" the parent note promised. This is the natural limit of Instruction-Level Parallelism: independence is visible as a missing edge.

---

Example 2 — Case B: a forced chain

Forecast: independent ops took 1 wave. Do you think a chain of two adds also takes 1? Guess.

1. Wave 0. Tokens $x=1,y=2$ arrive on the first $+$ ("${+}_1$"). Token $z=3$ arrives on one input of the second $+$ ("${+}_2$"). The other input of ${+}_2$ is the edge coming from ${+}_1$ — it is empty. Why this step? We must notice ${+}_2$ is not yet fireable: one of its edges has no token.
2. Wave 1. ${+}_1$ has both inputs → fires → emits token $3$ onto the edge feeding ${+}_2$. ${+}_2$ still cannot fire this wave, because it only just now received that token — checking happens per wave. Why this step? The data dependency (the edge from ${+}_1$ to ${+}_2$) is the only thing forcing order here. There is no program counter saying "do the inner add first" — the empty edge says it.
3. Wave 2. ${+}_2$ now sees $3$ (from ${+}_1$) and $3$ ($=z$) → fires → $r=6$.

Verify: $r=(1+2)+3=6$. ✓ Waves $=2$. Contrast Ex 1: same count of operations (2 adds) but here they cannot overlap. The lesson: dataflow removes artificial order, never necessary order.

---

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

Forecast: $x$ is needed by both the $+$ and the $-$. Does that create a bottleneck? Guess yes/no.

1. Wave 0. Tokens $x=5,y=3,z=1$ arrive. Crucially, $x$ is copied onto two edges — one into $+$, one into $-$. Why this step? Fan-out means one producer feeds many consumers; in dataflow a value that two nodes need becomes two tokens (a copy per edge). It does not cause waiting.
2. Wave 1. $+$ has $x=5,y=3$ → fires → $t_1=8$. Simultaneously $-$ has $x=5,z=1$ → fires → $t_2=4$. Both fire together (Case A behaviour inside the diamond's left half). Why this step? Sharing $x$ does not chain them — each has its own copy, so their firing rules are independent.
3. Wave 2. The $\times$ node now sees $t_1=8$ and $t_2=4$ → fires → $r=32$. Why this step? This is the fan-in: two edges merge into one node. Order is forced (Case B) because $\times$'s inputs did not exist before wave 1.

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

---

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

Forecast: a node with no input edges — when is its firing rule satisfied? Guess before reading.

1. Case D — the constant node. A node with zero input edges has an empty set of requirements. "All input edges hold a token" is vacuously true for the empty set, so a constant node is always ready and emits its value (here $1$, and separately $7$) at wave 0. Why this step? The firing rule says "all inputs present". With no inputs, there is nothing to wait for — the same way "every unicorn in this room is pink" is true when there are no unicorns.
2. Case E — the one-input identity-ish node. The $\times$ node still needs two tokens ($x$ and the constant $1$). It is not a one-input node. But suppose we had a node like neg(a) = $-a$: that fires as soon as its single edge holds a token. The general rule scales: fire when the (however many) input edges are all full. Why this step? Beginners assume every node needs two operands. The rule is "all its inputs", whatever that number is — including 0 (constant) and 1 (unary).
3. Wave 1. $\times$ has $x=12$ and $1$ → fires → $12$. The $+$ has this $12$? No — not yet (it arrived this wave). Wave 2: $+$ has $12$ and $7$ → fires → $r=19$.

Verify: $r=(12\times 1)+7=19$. ✓ The constants never stalled anything; the only forced order was the $\times \to +$ chain (Case B again).

---

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

Forecast: guess — does the machine silently overwrite, or stall?

1. Wave 1. Iteration 1's token (value $v_1$) sits on edge $E$, waiting to be consumed by the downstream node. Why this step? We must fix the state: $E$ is occupied, capacity is 1.
2. Wave 2. Iteration 2 finishes early and wants to emit $v_2$ onto $E$. But $E$ already holds $v_1$. In static dataflow, an edge may hold at most one token, so the producer for iteration 2 cannot fire — it stalls until $v_1$ is consumed. Why this step? This is the defining limitation of static dataflow (parent note): it cannot cleanly overlap invocations of the same subgraph. Look at the red token stuck behind the black one in the figure.
3. Consequence. Iterations are effectively serialized on that shared edge — no pipeline parallelism across iterations.

Verify (conceptual): The two "would-be" tokens = $\{v_1,v_2\}$ but edge capacity = $1$, so $|\text{tokens on }E|\le 1$ is violated by trying to place both → stall is the only legal outcome. This is exactly the problem Example 6 fixes with tags.

---

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

Forecast: the answer is $1+2+3$. But how many waves if iterations overlap? Guess.

Recall the tagged firing rule (parent note): a node fires only when it holds two tokens $⟨v_1,\tau ⟩$ and $⟨v_2,\tau ⟩$ with the same tag $\tau$, producing $⟨f(v_1,v_2),\tau ⟩$. The tag is the "which iteration am I" sticker — the red label on each token in the figure.

1. Iteration 1 (${\tau }_1$). Tokens $⟨sum=0,{\tau }_1⟩$ and $⟨i=1,{\tau }_1⟩$ match → fire → $⟨1,{\tau }_1⟩$. Why this step? Both tokens carry ${\tau }_1$, so the matching unit pairs them. This partial sum will feed iteration 2.
2. Iteration 2 (${\tau }_2$) can start while 1 is finishing. The $i=2$ token, tagged ${\tau }_2$, is already flowing. It waits only for its own $sum$ token $⟨1,{\tau }_2⟩$ (the result of iteration 1, re-tagged to ${\tau }_2$). Fire → $⟨3,{\tau }_2⟩$. Why this step? Because tags differ, iteration 2's fast $i$-token can never wrongly pair with iteration 1's slow $sum$-token — the machine only fires on matching $\tau$. This is what static dataflow could not do (Ex 5).
3. Iteration 3 (${\tau }_3$). $⟨3,{\tau }_3⟩+⟨i=3,{\tau }_3⟩$ → fire → $⟨6,{\tau }_3⟩$.

Verify: ${\sum }_{i=1}^{3}i=1+2+3=6=\frac{3\cdot 4}{2}$. ✓ The chain of sums is sequential (each needs the previous partial), but the ingredient tokens ($i=1,2,3$) all stream in parallel — this is loop-level / pipeline parallelism, enabled purely by the tags.

---

Example 7 — Case H: the limiting case — drop the tags, get garbage

Forecast: guess what value the machine might compute instead of the true running sum.

1. The bug. Without tags, the matching unit pairs any two tokens sitting on the two input edges. Suppose the $+$ node grabs $sum=0$ (iteration 1's) together with $i=2$ (iteration 2's). Why this step? This is the "iteration-3's $x$ matches iteration-7's $y$" failure the parent note warned about — the machine has no way to tell whose token is whose.
2. The garbage. It computes $0+2=2$ and labels it as "the partial sum after iteration 1", which is wrong (true value is $1$). Everything downstream is now corrupted. Why this step? One mismatched pair poisons the whole running total.

Verify: True partial after iteration 1 $=0+1=1$. Garbage value $=0+2=2$. Since $2\ne 1$, the computation is corrupted. ✓ This is why dynamic dataflow exists — the tag is not decoration, it is correctness. (Fun fact from the parent's Connections: Out-of-Order Execution solves the identical problem in real CPUs with register renaming / reservation stations = a tagged-token matcher.)

---

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

Forecast: naive sequential time is $3+2+1=6$ minutes. Guess the dataflow time before computing.

1. Build the graph. Nodes: Sandwich (3 min), Smoothie (2 min), Plate (1 min). Edges: Sandwich → Plate, Smoothie → Plate. This is a diamond without the shared source — a fan-in (Case C). Why this step? Independent tasks (Case A: sandwich vs smoothie) run concurrently; Plate waits for both (its firing rule needs both input edges full).
2. One combo timing. Sandwich and Smoothie fire at $t=0$ in parallel. Plate can only fire when both are done → it waits for the slower one $=\max (3,2)=3$ min. Then plating adds $1$ min. Why this step? The firing rule of Plate = "all inputs ready", so its start time = the max of its predecessors' finish times.
3. Total for one combo $=\max (3,2)+1=4$ minutes.
4. Two combos, dynamic machine. Tag combo-A as ${\tau }_A$, combo-B as ${\tau }_B$. With extra cooks, combo-B's sandwich/smoothie fire at $t=0$ too, tagged ${\tau }_B$. The Plate node fires once for ${\tau }_A$ tokens and once for ${\tau }_B$ tokens — tags keep table A's tray separate from table B's. Both plates can proceed at $t=3$. Total $=4$ minutes for both. Why this step? This is exactly Ex 6's tagged overlap, in an everyday costume — the sticker on each ingredient is the tag.

Verify: One combo dataflow time $=\max (3,2)+1=4$ min vs sequential $3+2+1=6$ min (speed-up $6/4=1.5\times$). Two combos: still $4$ min (limited by the 3-min sandwich, not by count) vs sequential $12$ min → speed-up $3\times$. ✓

---

Example 9 — Case J: exam-style throughput twist

Forecast: guess (a) — is it 12 (all nodes) or 4 (the chain)?

1. (a) Latency = critical path, not node count. With unlimited hardware, all independent nodes fire together; the only thing you cannot parallelize is a dependency chain. So minimum waves $=L=4$. Why this step? The critical path is the longest sequence of "output-of-one-is-input-of-next" edges (Case B stacked). Everything off the path overlaps (Case A). The $12$ nodes don't matter for latency — only the longest chain does.
2. (b) Pipelined throughput. Once the pipeline is full, one iteration completes every wave (initiation interval $=1$). The first iteration takes $L=4$ waves to drain; each of the remaining $99$ finishes one wave later. Why this step? This is the pipeline formula: total $=$ (fill latency) $+$ (remaining iterations) $=L+(K-1)$.
3. Compute: total $=4+(100-1)=103$ waves.

Verify: (a) $L=4$ waves. ✓ (b) $L+(K-1)=4+99=103$ waves. Sanity: without pipelining you'd pay $L\cdot K=4\times 100=400$ waves; tagged pipelining gives $103$, a $400/103\approx 3.88\times$ throughput win — the payoff of dynamic dataflow's overlapping (Case G) at scale.

---

Recall

Recall Which case forces sequential order?

Case B (chained dependency) and every fan-in (Case C, Ex 8's plating). Order comes from empty input edges, never from a program counter. ::: A node cannot fire until all its input edges hold tokens; a chain means each node's input doesn't exist until its predecessor fires.

Recall Why does a constant (zero-input) node fire immediately?

Question ::: Its set of required input edges is empty, so "all inputs present" is vacuously true — nothing to wait for.

Recall Static vs dynamic in one collision sentence?

Question ::: Static stalls when a second token wants an occupied capacity-1 edge (Ex 5); dynamic gives each iteration a tag so many tokens coexist and iterations overlap (Ex 6).

Recall Latency of a dataflow run with unlimited hardware?

Question ::: The length of the critical (longest dependency) path — not the total node count.

Connections

• Dataflow architectures — the parent note this page drills into.
• Von Neumann architecture — the sequential baseline we keep comparing speed-ups against.
• Instruction-Level Parallelism — Case A is its theoretical limit.
• Out-of-Order Execution — Ex 7's tag-matching is literally how reservation stations work.
• Systolic Arrays — a regular, statically-scheduled cousin (relevant to Ex 5's static case).
• Directed Acyclic Graph (DAG) — the structure whose critical path drives Ex 9.
• Loop-Level Parallelism — Examples 6 and 9 are its dataflow realization.