Dataflow architectures

WHAT is a dataflow architecture?

The three ideas you must never forget:

1. Program = graph, not a list.
2. Execution rule = "fire when inputs ready" (called the firing rule).
3. Parallelism is automatic — any two nodes whose inputs are ready can run at the same time.

WHY do we want this?

HOW execution works — from first principles

Consider the expression $r = (x + y) \times (x - z)$

Let's derive the dataflow graph instead of being handed one.

• The final operation is $\times$. It needs two inputs: $(x+y)$ and $(x-z)$.
• $(x+y)$ is itself a node: a $+$ that consumes tokens $x$ and $y$.
• $(x-z)$ is a $-$ node consuming $x$ and $z$.

So the graph is:

Firing trace (Why each step?):

1. Tokens $x,y,z$ arrive. Why? Inputs are the starting data.
2. + node has both inputs ($x,y$) → fires, emits token $t_1=x+y$. Simultaneously - node has $x,z$ → fires, emits $t_2=x-z$. Why simultaneously? Both firing rules are satisfied at once and the nodes are independent → hardware runs them in parallel.
3. × node now has $t_1,t_2$ → fires, emits $r$. Why last? Its firing rule could not be satisfied earlier because its inputs didn't exist yet — the data dependency forces the order, nothing else does.

Static vs Dynamic dataflow

Worked example — a loop

Compute $\sum_{i=1}^{n} i$ conceptually as a dataflow.

Body per iteration $i$: sum_new = sum_old + i.

Why tags matter here (step-by-step):

1. Iteration $i=1$: token $\langle sum=0,\tau_1\rangle$, $\langle i=1,\tau_1\rangle$ → fires → $\langle 1,\tau_1\rangle$.
2. Iteration $i=2$ can already have its $i$-token flowing while iteration 1 finishes. Tags $\tau_1,\tau_2$ keep them separate so a fast $i$-token never wrongly pairs with a slow $sum$-token from another iteration.
3. Result: pipeline parallelism across iterations with no locks — the "matching store" hardware only fires when tags agree.

Common mistakes

Active recall

Connections

• Von Neumann architecture — the sequential PC-based model dataflow reacts against.
• Instruction-Level Parallelism — dataflow is the natural limit of ILP: all dependencies exposed.
• Out-of-Order Execution — modern CPUs use a local, hidden dataflow engine (Tomasulo/reservation stations = tagged-token matching!).
• Systolic Arrays — another data-driven, PC-free style for regular computations.
• Directed Acyclic Graph (DAG) — the mathematical structure of a dataflow graph.
• Loop-Level Parallelism — enabled cheaply by dynamic/tagged dataflow.

Concept Map

Hinglish (regional understanding)