Foundations — Dataflow architectures

This page assumes nothing. Before you read the parent note Dataflow architectures, you should be able to read every squiggle it uses. Below, each symbol gets: plain words → the picture → why the topic needs it. They are ordered so each one leans on the ones above it.

1. A "node" and an "operation"

Picture a single worker at a desk. On the desk are two slots labelled "input", and one out-tray labelled "output". The worker knows exactly one trick, say $+$ (add).

Why the topic needs it: the parent says "Program = graph, not a list." A graph is made of these boxes. Before you can have a graph you must know what one box is — a single operation waiting for its inputs.

2. An "edge" and an "arrow" ($\to$)

Why the topic needs it: the mnemonic D.A.T.A. literally says "Arrows are dependencies". The whole reason dataflow can find parallelism is that missing arrows mean no dependency — see §7.

3. A "token" — the thing that travels the arrow

Why the topic needs it: the parent's firing rule talks about "tokens present on all input edges". You can't understand firing until you picture the tokens sitting in the slots.

4. "Fire" and the firing rule

Reading it aloud: "A node fires if and only if every input slot holds a token." So one missing token = no firing, full stop. And a full set of tokens = it fires immediately, with nobody's permission.

Why the topic needs it: this is the heart of the whole architecture. In Von Neumann architecture a program counter decides when to run. Here, nothing decides — the presence of data is the decision.

5. Variables and the expression $r=(x+y)\times (x-z)$

Let us read the parent's key expression slowly, left to right:

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

• The brackets $()$ group things that must be worked out first.
• $(x+y)$ is one node's job (an add).
• $(x-z)$ is another node's job (a subtract).
• $\times$ takes the two results and multiplies them.
• $r=$ names the final answer.

Why the topic needs it: the parent derives the graph from this expression. If you can see how brackets become nested boxes, the graph draws itself.

6. Subscripts and intermediate tokens $t_1,t_2$

In the parent's trace, $t_1=x+y$ and $t_2=x-z$ are the tokens the two lower nodes emit before the multiply fires.

Why the topic needs it: derivations need names for the in-between values. Without $t_1,t_2$ we can't say "the multiply waits for $t_1$ and $t_2$".

7. Independence = "no connecting edge" (where parallelism hides)

This is why the parent says parallelism is "free": you don't ask for it. It is simply the absence of arrows. This idea is the natural ceiling of Instruction-Level Parallelism, and it's what Out-of-Order Execution tries to rebuild in secret inside an ordinary CPU.

8. The tag $\tau$ and the notation $⟨v,\tau ⟩$

Reading $f(v_1,v_2)$: $f$ is a stand-in for "whatever this node does" — if it's an add node, $f(v_1,v_2)=v_1+v_2$.

Why the topic needs it: in a loop, many copies of the same box are active at once. The tag stops iteration-3's number from wrongly pairing with iteration-7's number. This is what makes Loop-Level Parallelism cheap, and it is exactly the trick inside Tomasulo-style Out-of-Order Execution.

9. The graph is a DAG (no cycles)

Why the topic needs it: "acyclic" guarantees the computation actually finishes — data marches forward and never chases its own tail. It is the mathematical skeleton beneath everything on this page.

Prerequisite map

Equipment checklist