6.5.9 · D5Advanced & Emerging Architectures
Question bank — Dataflow architectures
True or false — justify
Every prompt is a statement. Decide true/false and say why — the reason is the real answer.
Dataflow has no execution order at all, so results can come out in any order.
False. There is no program-counter order, but there is a strict order: data dependencies. A node whose inputs aren't ready physically cannot fire, so dependent results always come out after the results they depend on.
Because there is no program counter, a dataflow machine cannot know when the program is finished.
False. The program is a graph with output nodes; "finished" means the final output node(s) have fired and no more tokens can move. Absence of a PC removes sequencing, not completion.
Static and dynamic dataflow differ only in how fast they run.
False. The real difference is token capacity per edge and re-entrancy: static allows at most one token per edge (no overlapping instances); dynamic tags tokens so many concurrent copies of the same subgraph coexist. Speed is a consequence, not the definition.
In dynamic dataflow, two tokens with matching values but different tags can fire a node together.
False. Firing needs matching tags, not matching values. Different tags mean different runs (iterations/invocations); pairing them would mix data across contexts and produce garbage.
Any expression can be run more in parallel simply by adding more processing units.
False. Parallelism is capped by the critical path of the dataflow graph — the longest chain of dependent nodes. Extra units cannot shorten a chain where each node needs the previous node's output.
Two nodes that are not connected by any edge can always fire at the same time.
True (given hardware). No edge between them means neither is the other's input, so their firing rules are independent — that is exactly why dataflow exposes parallelism "for free."
A token behaves like a voltage held on a wire in an ordinary circuit.
False. A wire's voltage persists and can be re-read many times; a token is produced once and consumed once. The matching unit must collect a complete set of input tokens before the node fires, then those tokens are gone.
Out-of-order superscalar CPUs are Von Neumann machines, so they share nothing with dataflow.
False. Their Out-of-Order Execution core is a small hidden dataflow engine: reservation stations wait for operands (tokens) and fire when ready — essentially tagged-token matching wrapped inside a PC-based front end.
If every edge in a static dataflow graph currently holds a token, the machine has deadlocked.
False in general. A full edge just means a producer has run ahead; nodes downstream will consume those tokens and free the edges as they fire. Deadlock occurs only if a cycle of full edges each waits on the other.
Spot the error
Each item contains a claim or a reasoning step with a flaw. Name the flaw and correct it.
"To parallelize a=x+y and b=p+q, a dataflow compiler must be told they are independent."
Error: independence is not told, it is visible. Because
a and b share no producer/consumer edge, their firing rules are satisfied separately — the graph structure already encodes independence."We can drop tags in a loop as long as each iteration finishes before the next starts."
Error: forcing that ordering throws away the whole benefit — pipeline overlap across iterations. Tags exist precisely so iterations can overlap safely; serializing them is just Von Neumann in disguise.
"A - node in x - z will fire twice if x and z arrive at different times."
Error: arrival time doesn't cause extra firings. The node waits until both input tokens are present, then fires once, consuming both. Staggered arrival only delays firing.
"Since the multiply in (x+y)*(x-z) needs x twice, x must be one token shared by both adders."
Error: a token is consumed on firing, so a single
x token cannot feed two nodes. The graph must duplicate x (a fan-out / copy node emits an x token to each consumer)."Dynamic dataflow needs no matching hardware because tags make firing automatic."
Error: tags are the key, not the mechanism. A matching store actively holds waiting tokens and searches for a partner with an equal tag; without it, tagged tokens would never be paired.
"Adding a program counter to a dataflow machine would speed it up by giving it a clear order."
Error: a PC reimposes the sequential bottleneck dataflow was built to remove, serializing independent nodes. It would slow the exposed parallelism, not help it.
"A dataflow graph can contain cycles freely because Directed Acyclic Graph (DAG) is only a special case."
Error: the acyclic form describes a single straight-line computation. Loops introduce controlled cycles, but they need extra machinery (tags, or explicit control nodes) — you cannot add cycles "freely" without risking tokens with no valid partner.
Why questions
The answer must give the mechanism, not restate the phenomenon.
Why does dataflow expose parallelism without any special "parallel for" annotation?
Because independence is a structural property: unconnected nodes have independently-satisfiable firing rules, so the hardware runs them together the moment their inputs exist. See Instruction-Level Parallelism — dataflow is its natural limit.
Why does tan-style "instruction address order" not exist here, yet the program still computes the right thing?
The correct partial order is enforced by data dependencies alone: a consumer literally has no input until its producer fires. Address order was always redundant extra ordering on top of that.
Why must each token in dynamic dataflow carry a tag rather than the hardware just using arrival order?
Arrival order is unreliable — a fast iteration-2 token can overtake a slow iteration-1 token. The tag is an identity that survives reordering, so pairing stays correct no matter who arrives first.
Why can Loop-Level Parallelism be extracted cheaply in tagged dataflow but painfully in a Von Neumann CPU?
Tagging makes each iteration a separately-identified set of tokens, so overlapping iterations self-organize by tag. A PC-based CPU must instead prove independence, rename registers, and track hazards to fake the same overlap.
Why is a systolic array considered "data-driven" like dataflow even though its schedule is fixed?
Data still pushes computation through the array as it arrives, cell-by-cell, with no program counter fetching instructions. The regular fixed rhythm is a specialized, hardwired version of "fire when data is present."
Why does removing artificial ordering not make results non-deterministic?
The value a node computes depends only on which tokens it consumes, and dependencies fix that. Timing may vary run to run, but the final values are pinned by the graph.
Edge cases
Boundary and degenerate scenarios — the ones exam-setters love.
A node has two inputs but one input edge never receives a token. What happens?
The node never fires; it waits forever. This is a genuine dataflow stall/deadlock, caused by a missing producer, not by any scheduler choice.
An operation node needs no inputs at all (e.g. a constant source). When does it fire?
Its firing rule is trivially satisfied (empty set of required inputs), so it may fire immediately at start-up, seeding the graph with a constant token.
A + node receives two tokens with the same tag but out of order (second operand first). Does the sum change?
No. Matching is by tag, not arrival order; once both same-tag tokens are present the node fires once with the correct pair. Addition's commutativity also makes operand order irrelevant here.
In static dataflow, a producer tries to emit a second token onto an edge that still holds one. What must happen?
The producer must stall (back-pressure) until the consumer drains the edge, because a static edge holds at most one token. This is the built-in flow control that dynamic dataflow relaxes with tags.
A loop runs zero times (n = 0). How does a dataflow loop handle it?
The loop's control/merge nodes route the initial value straight to the output with no body firings. "Zero iterations" is just a firing rule that never enables the body node.
Two independent subgraphs finish, but the whole program has one output node fed by both. When does output fire?
Only when both feeding tokens are present — the output waits on the later of the two, i.e. the critical path through the slower branch determines completion time.
A tagged token's partner with a matching tag never arrives (lost/omitted). What is the effect?
That token sits in the matching store indefinitely, a silent partial-match leak — a real hazard in dynamic dataflow that hardware must bound (limited matching store) or the program stalls.
Recall One-line litmus test for any dataflow claim
Ask: "Would this still be true if I only kept the rule 'fire when all matching-tag inputs are present'?" If the claim needs a clock, a PC, or arrival order to be true, it's a trap.
Connections
- Dataflow architectures — the parent topic these traps drill.
- Von Neumann architecture — the sequential model most misconceptions smuggle back in.
- Out-of-Order Execution — hidden tagged-token matching inside real CPUs.
- Instruction-Level Parallelism — dataflow as its theoretical limit.
- Loop-Level Parallelism — why tags unlock cheap iteration overlap.
- Systolic Arrays — a fixed-schedule cousin of data-driven execution.
- Directed Acyclic Graph (DAG) — the structure behind loop-free dataflow.