# Dataflow processor program representations: from tokens to graphs **Every major dataflow machine stored programs as node-centric instruction templates, encoding arcs as destination fields within those templates — but the token formats, matching strategies, and IR representations varied dramatically across generations.** This design choice, driven by the need to fetch instructions by address when tokens arrive, shaped everything from assembly language syntax to compiler intermediate representations. The evolution from Dennis's static presence bits through Manchester's associative matching to Monsoon's frame-based Explicit Token Store represents the central arc of dataflow architecture history. Modern successors like TRIPS, WaveScalar, and CGRAs inherit these ideas while adapting them to spatial computing paradigms. What follows is a detailed technical survey of actual instruction formats, token structures, IR syntaxes, and partitioning approaches across five decades of dataflow computing. --- ## Dennis's original template established the pattern all successors followed Jack Dennis's 1974 static dataflow processor defined the foundational instruction format that every subsequent machine adapted. Each instruction occupies a **three-word template** in the Memory Section: ``` | Op | dest1 | dest2 | PB | operand1 | PB | operand2 | ``` Here **Op** is the opcode, **dest1** and **dest2** encode `` pairs pointing to downstream consumers, **PB** fields are single-bit presence flags indicating whether an operand has arrived, and the operand slots hold data values. Tokens flowing through the system are simple triples: ``. When a token arrives, the Update Unit stores its value in the appropriate operand slot and sets the corresponding presence bit. When all presence bits are set, the instruction fires. A concrete example illustrates the encoding. For the expression `(a+b−c)×(a+b+c)`: ``` Instr 1: ADD dest: 3L, 4L ; a+b → instr 3 left, instr 4 left Instr 2: --- dest: 3R, 4R ; c → instr 3 right, instr 4 right Instr 3: SUB dest: 5L ; (a+b)−c → instr 5 left Instr 4: ADD dest: 5R ; (a+b)+c → instr 5 right Instr 5: MUL dest: out ; result ``` The static firing rule — at most one token per arc at any time — required **acknowledge arcs** from consumers back to producers, limiting parallelism but simplifying hardware. Dennis defined six template types: binary/unary operators, binary/unary deciders (predicates), and binary/unary Boolean operators. This template-with-destinations format became the universal pattern: every dataflow machine since Dennis encodes arcs as destination fields within node records. --- ## Manchester's 96-bit tokens and TASS assembly drove the first real system The Manchester Prototype Dataflow Computer (Gurd, Watson, Kirkham, 1985) was the first fully operational dynamic dataflow machine. Its **96-bit token format** is the most precisely documented in the literature: ``` | marker (1 bit) | data (37 bits) | tag (36 bits) | destination (22 bits) | ``` The **marker** bit distinguishes system packets from normal data tokens. The **data** field carries values (the Processing Unit used a 24-bit internal word length with microcode-based 32-bit floating-point support). The **tag** field — **36 bits** — encodes the dynamic context: iteration level and activation identifier, enabling multiple simultaneous instances of the same graph to coexist. The **destination** field encodes an **18-bit virtual instruction address** plus left/right port indicators and matching function bits. After the Matching Unit pairs two tokens with identical tags and destinations, it produces a **133-bit token-pair packet** that fetches the instruction from the Instruction Store. Manchester's **TASS (Template Assembly Language)** used mnemonics like `CGR` (compare greater), `SIL` (set iteration level), `BRR` (branch), `DUP` (duplicate), `MLR` (multiply real), `ADD`, `SUB`. Instructions had a maximum fan-out of **2 destinations** — higher fan-out required chains of `DUP` instructions. The Matching Unit operated as a pseudo-associative hash table, computing a **16-bit hash** on tag and destination fields, with 16 boards × 64K-token memory each providing **1 million token capacity**. Matching operations fell into two categories: bypass (monadic instructions pass through without matching) and extract/wait (dyadic instructions check for a stored partner). --- ## Monsoon's Explicit Token Store was the breakthrough that made dataflow practical The Monsoon processor (Papadopoulos and Culler, 1990) eliminated the expensive associative matching store that had plagued Manchester and MIT's TTDA. The **Explicit Token Store (ETS)** model replaced associative lookup with compiler-assigned frame offsets and simple presence bits — a conceptual leap that made dataflow machines implementable with standard SRAM. Monsoon tokens are **144 bits** wide entering the pipeline, structured as `` where **IP** (Instruction Pointer) indexes into instruction memory and **FP** (Frame Pointer) identifies an activation frame analogous to a conventional stack frame. The 64-bit data value provides full double-precision support. The instruction format packs five sub-operations into a single opcode word: ``` | EA | WM | RegOp | ALU | FormToken | ``` Each instruction is stored as `opcode, r, dest1 [dest2]` where **r** is the frame offset for operand matching and destinations are **IP-relative displacements** with left/right port indicators. For example, `ADD 2 +1,+2L` means "perform ADD, match at frame offset 2, send results to IP+1 and to IP+2 left port." The **8-stage pipeline** processes tokens through: (1) Instruction Fetch, (2) Effective Address computation (FP+r), (3) Presence Bit read/modify/write, (4) Frame Store read/write/exchange, (5–7) ALU stages with parallel tag computation, and (8) Form Token output. The Waiting-Matching (WM) sub-operation supports five modes: **Unary** (no matching needed), **Normal** (standard two-input matching), **Sticky** (value persists for loop invariants), **Exchange** (swap stored and incoming values), and **Imperative** (sequential state updates). Monsoon ran at **10 MHz** and sustained **5–10 million tokens per second** per PE. Sixteen-node systems were built at MIT and Los Alamos National Laboratory. The key insight was treating the dataflow processor as a "generalization of a primitive von Neumann architecture" — a single-accumulator machine with hardware multithreading, where the frame-based organization naturally supported program distribution across PEs without explicit partitioning. --- ## EM-4 and Epsilon-2 pushed instruction format sophistication further The **EM-4** (Electrotechnical Laboratory, Japan, 1990) introduced the **strongly connected arc model**, classifying arcs as either normal (requiring token matching) or strongly connected (executing sequentially within a block). Strongly connected blocks function as threads — once execution begins on a PE, all nodes in the block execute without interruption using a local register file. This hybrid dataflow/control-flow model reduced communication overhead and simplified matching. The architecture used a **direct matching scheme** similar to Monsoon, with dynamically allocated operand segments bound to template segments at function invocation time. The EMC-R single-chip processor contained 50,000 CMOS gates and targeted over 12 MIPS per PE across 80-PE configurations. The **Epsilon-2** (Sandia National Laboratories, Grafe and Hoch, 1989) provides the most detailed published token bit layout among dataflow machines: ``` Target portion: | type (8 bits) | IP (24 bits) | FP (40 bits) | Data portion: | type (8 bits) | value (64 bits) | ``` The target type identifies the resource (PE, structure memory, I/O), while the data type identifies the value format (floating-point, integer, pointer, logical). The instruction word format is unusually rich: ``` | Opcode | ResultReg | TargetOffset | MatchOffset | LMode | LOffset | RMode | ROffset | RepeatOffset | ``` The **RepeatOffset** field is Epsilon-2's most distinctive feature. It creates **linked lists of instructions** — adding RepeatOffset to the current IP generates a "repeat token" that chains through sequences of instructions for both data fan-out (replacing copy trees with linked lists) and grain scheduling (sequencing instructions within a computational grain, with intermediate results stored in registers). Synchronization uses a **direct match counter**: the match memory location is read, compared against the match count in the opcode, and either fired (count reached) or incremented (more tokens needed). This requires only one read and one write per synchronization event. --- ## SISAL's IF1 and IF2 remain the most documented dataflow compiler IRs The SISAL compiler pipeline produced the most thoroughly documented intermediate representations in dataflow computing. The compilation chain runs: `SISAL source → IF1 → IF1OPT → IF1 → IF2MEM → IF2 → C/Fortran → native code`. **IF1 (Intermediate Form 1)**, specified in the 1985 LLNL Reference Manual M-170, is a text-based, machine-independent graph representation where both nodes and edges are first-class entities. Nodes fall into two categories: **simple nodes** (primitive arithmetic, comparison, and logic operations with typed input/output ports) and **compound nodes** (conditionals, loops, let-expressions that contain hierarchical subgraphs). Edges are listed separately, each specifying source node, source port, destination node, destination port, and data type. This balanced representation — where edges are explicit rather than merely encoded as destination fields — makes IF1 notably different from machine-level dataflow representations. IF1 optimizations include function inlining (all non-recursive functions by default), invariant removal, common subexpression elimination across conditional branches, constant folding, loop fusion, and dead code elimination. **IF2** extends IF1 with memory management annotations critical for efficient execution on real hardware: build-in-place analysis (pre-allocating array storage), update-in-place analysis (reusing memory for arrays that are consumed only once), and prefetch directives. IF2 bridges the gap between abstract dataflow graphs and efficient execution on shared-memory machines. The final code generation step converts IF2 to C or Fortran, compiled by the platform's native compiler — targeting everything from Cray X/MP to Manchester's dataflow machine. **Id** (Arvind, MIT) compiled directly to dataflow graphs that served as machine code for the TTDA and Monsoon. Kenneth Traub's 1986 thesis (TR-370) describes the compilation from Id through **TL0** (a machine-independent intermediate form) to Monsoon code blocks. The later **TAM (Threaded Abstract Machine)** provided a path from dataflow graph representations to conventional control flow, enabling Id programs to run efficiently on stock hardware. **Lucid** (Ashcroft and Wadge) took a fundamentally different approach: its demand-driven (eductive) model represents programs as equation systems over infinite streams, with no explicit dataflow graph construction — the graph is implicit in equation dependencies. --- ## All historical machines chose node-centric storage, but arcs matter at the edges A striking finding across the entire history of dataflow computing is that **no major architecture adopted a purely arc-centric (edge-list) program representation**. The reason is fundamental: when a token arrives at a PE, it carries a destination instruction address. The hardware must look up that instruction's opcode and operand state by indexing into instruction memory — a node-indexed data structure. An edge-list representation would require an additional indirection to find the operation associated with an incoming token. However, several systems incorporated arc-centric elements worth noting. **IF1's balanced format** lists edges as separate entities alongside nodes, making it the closest to an arc-centric IR in the dataflow ecosystem. **EM-4's strongly connected arc classification** treats the arc type as the primary structural determinant of execution strategy — normal arcs trigger token matching while strongly connected arcs trigger sequential register-based execution. **Transport-Triggered Architectures (TTAs)** are genuinely arc-centric: they contain **no opcodes** — instructions consist entirely of data transport (move) specifications across buses. Each move slot encodes ``, and operations are triggered as side effects of writing to a function unit's trigger port. The MAXQ microcontroller (Maxim Integrated) is the only commercial TTA, implementing a single MOVE instruction. **Edge-Centric Modulo Scheduling (EMS)** for CGRAs (Park et al., 2008) takes routing as the primary objective, making placement a by-product of routing decisions — achieving 98% of simulated annealing quality at a fraction of compilation time. The theoretical distinction matters for hardware: node-centric representations map naturally to instruction memories indexed by destination address, while arc-centric representations would map more naturally to routing tables or crossbar configurations. Modern spatial architectures effectively use both — instruction memories for PE configuration and routing tables for interconnect configuration. --- ## LLVM-to-dataflow lowering centers on the Handshake dialect and three hard problems The observation that **LLVM IR's SSA form is essentially a restricted dataflow graph** — each variable defined once (like a token), def-use chains encoding data dependencies (like arcs), and φ-functions corresponding to merge operators — makes LLVM a natural starting point for dataflow compilation. The gap lies in converting control flow to dataflow token mechanics. **Dynamatic** (EPFL/ETH Zurich) is the most mature implementation. Its modern version uses **MLIR** with the pipeline: `C/C++ → Polygeist → MLIR (affine/scf/cf/arith dialects) → cf-to-handshake conversion → Handshake dialect → HW dialect → VHDL`. The critical `cf-to-handshake` pass converts CFG-based control flow into dataflow components: `handshake::BranchOp` (steers tokens by predicate), `handshake::MergeOp` (selects among inputs), `handshake::MCLoadOp`/`handshake::LSQLoadOp` (memory access through controllers or load-store queues). The **CIRCT Handshake dialect**, now part of the LLVM project, standardizes this dataflow IR with operations like `extmemory`, `store`, `buffer` (split into `OEHBOp` and `TEHBOp`), plus `Fork`, `Join`, `Sink`, `Source`, and `Mux`. Three core challenges dominate the lowering: - **Control flow conversion**: Branches become steering/switch nodes routing tokens by predicate. φ-functions become merge/mux nodes. Loop back-edges require merge/branch pairs with carefully inserted buffers to prevent deadlocks. **GSA (Gated Static Assignment)**, with η-instructions at loop exits, provides an alternative formulation with both control-flow and dataflow semantics. - **Memory ordering**: This is the single hardest problem. Sequential programs assume total load-store ordering; dataflow execution is inherently out-of-order. Dynamatic uses Memory Controllers and **Load-Store Queues (LSQs)** with dependence analysis to minimize ordering constraints. **RipTide** (CMU, MICRO 2022) computes an ordering graph with path-sensitive transitive reduction. WaveScalar annotates each memory operation with sequence numbers and predecessor/successor links for its wave-ordered memory protocol. - **Loop handling**: Dataflow graphs are naturally acyclic. Solutions include WaveScalar's `WAVE-ADVANCE` instructions (incrementing wave numbers), Dynamatic's merge/branch pairs with buffers, RipTide's fused stream operators for induction variables, and GSA's η-instructions marking loop exits. --- ## Modern spatial architectures converge on block-atomic and triggered execution models **TRIPS/EDGE** (UT Austin) represents programs as blocks of up to **128 instructions** that are fetched, executed, and committed atomically. Within a block, instructions communicate via **direct instruction-to-instruction dataflow** — each instruction specifies which instruction(s) receive its result, with no register file access needed. Between blocks, **128 registers** (four banks of 32) provide state. The compiler statically places instructions onto a **4×4 grid of execution tiles**, minimizing Manhattan-distance communication costs. Block formation uses convergent hyperblock construction: iteratively applying if-conversion, loop peeling, unrolling, and scalar optimizations until blocks approach the 128-instruction, 32 load/store hardware limits. **WaveScalar** (U. Washington) partitions control flow graphs into **waves** — connected DAGs with single entry points where each instruction executes at most once per wave instance. Wave numbers (analogous to tags in traditional dataflow) distinguish dynamic instances. The `WAVE-ADVANCE` instruction increments wave numbers at wave boundaries — entirely under software control, unlike centralized tag management in classical machines. Wave-ordered memory annotates each memory operation with a sequence number and predecessor/successor sequence numbers; the hardware store buffer uses these annotations to detect gaps and enforce correct ordering. Programs are dynamically placed: instructions are cached in PEs and a discovery protocol notifies dependents of new instruction locations. **CGRAs** represent programs as **Data Flow Graphs extracted from inner loops**, mapped onto PE grids through the combined scheduling-placement-routing problem. The mapping produces a **configuration bitstream** that programs each PE with an operation and configures crossbar switches for data routing. For modulo-scheduled CGRAs, the configuration is a 2D space-time table. State-of-the-art approaches range from exact formulations (ILP, SAT via SAT-MapIt) through simulated annealing (SPR) to machine learning (MapZero using Graph Attention Networks with Monte Carlo Tree Search, LISA using GNN-based portable mapping). **Triggered Instruction Architectures** eliminate the program counter entirely. Each PE holds a static set of instructions, each with a **trigger condition** (a Boolean query over input channel availability, predicate registers, and ALU flags), a read phase, an execute phase, and a write phase. The hardware scheduler continuously evaluates all trigger conditions and dispatches eligible instructions. PEs communicate through FIFO channels. This achieves **8× greater area-normalized performance** over general-purpose processors by eliminating branch prediction, register renaming, and instruction fetch overhead. --- ## Token format design reflects the matching strategy taxonomy Token format evolution tracks directly with the matching strategy each machine employed: | Machine | Token Width | Fields | Matching Strategy | |---|---|---|---| | Dennis Static | Variable | `` | Presence bits in instruction template | | Manchester | 96 bits | `` | Pseudo-associative hash (16-bit hash) | | MIT TTDA | Variable | ``, tag = `` | Fully associative token store | | Monsoon/ETS | 144 bits | `` | Presence bits on frame slots | | EM-4 | — | `` | Direct match via operand segments | | Epsilon-2 | ~136 bits | target: `` + data: `` | Direct match counter | The critical transition occurred between TTDA's associative matching (expensive, non-scalable hardware) and Monsoon's ETS (compiler-assigned frame offsets with simple presence bits). This shift moved complexity from hardware to the compiler: **the compiler now decided where tokens should match** by assigning frame offsets, eliminating the need for content-addressable memory. EM-4 extended this by eliminating matching entirely within strongly connected blocks — tokens within a block never leave the register file. Epsilon-2's direct match counter further simplified synchronization to a single read-compare-increment/fire operation. The tag field's purpose also evolved. In Manchester, the **36-bit tag** encoded iteration level and activation context for distinguishing dynamic instances. In Monsoon, the **Frame Pointer** subsumed this role, with the compiler managing frame allocation to create fresh contexts for each function invocation. In WaveScalar, the **wave number** (a small counter incremented by software `WAVE-ADVANCE` instructions) replaced hardware tag management entirely. This trajectory — from hardware-managed unbounded tags through fixed-size hardware tags to software-managed counters — represents the progressive transfer of complexity from hardware to compilers. --- ## Partitioning evolved from fine-grain dynamic distribution to static spatial mapping Multi-PE dataflow machines faced the NP-complete problem of distributing program graphs across processing elements. The approaches evolved significantly across generations: **Manchester's Multi-Ring Machine** used dynamic, runtime distribution where tokens carried tags that the matching unit used to pair operands. All instructions resided in shared (or replicated) instruction stores. A critical discovery was that tagged-token machines generate **too much parallelism**, necessitating throttle mechanisms — ultimately implemented as coarse-grain, process-level throttles rather than instruction-level controls. **Monsoon** took an elegant approach: **programs were replicated across all PEs**, and work distribution was determined by where activation frames were allocated. Frame pointer hashing across PEs provided natural load distribution. This meant "the Id run-time system and compiled Id programs should run on any number of Monsoon processors without change" — no static partitioning required. Multiple frames interleaved on each PE tolerated memory and communication latency, achieving over 7× speedup on 8-processor systems. **TRIPS** moved placement to compile time. The Scale compiler assigns instructions to specific tiles in the 4×4 execution grid to minimize producer-consumer distances (1 cycle per Manhattan hop). Algorithms explored include list scheduling, simulated annealing, and reinforcement learning — the search space of 128! possible placements per block motivated ML approaches. Convergent hyperblock formation iteratively applies if-conversion and optimizations until blocks approach hardware constraints. **CGRA mapping** represents the most sophisticated modern approach, combining scheduling (operation-to-time-slot), placement (operation-to-PE), and routing (data-path-through-interconnect) into a unified NP-complete problem formalized as graph minor containment. The field has produced a rich toolkit: exact methods (ILP, SAT), heuristics (simulated annealing, edge-centric modulo scheduling), and learned approaches (GNN-based RL with Monte Carlo Tree Search). Recent work like **SAT-MapIt** (2024) and **PRISA** (2025, using analytically identified potential regions in the solution space) continues pushing the frontier. ## Conclusion The history of dataflow program representation reveals a consistent tension between expressiveness and implementability. Dennis's clean formal model — actors and arcs as co-equal entities — was progressively constrained by hardware realities into node-centric instruction templates with destination-encoded arcs. The token format evolved in lockstep with matching strategy, culminating in Monsoon's frame-based ETS model that finally made dataflow machines practical by shifting matching complexity from associative hardware to compiler-assigned offsets. Modern architectures like TRIPS and WaveScalar inherited these lessons while adapting them to spatial computing paradigms. The most actionable insight for anyone designing a new dataflow IR today is that **MLIR's Handshake dialect represents the current convergence point** — it bridges LLVM's SSA-based world with dataflow circuit semantics through well-defined lowering passes. The three persistent hard problems (control-flow conversion, memory ordering, loop handling) remain active research areas, but the toolchain from C through LLVM IR through MLIR to spatial hardware configuration is now functional. For token format design, the lesson of five decades is clear: keep tags small and software-managed, use frame-based direct matching rather than associative stores, and let the compiler handle the complexity that early machines tried to solve in hardware.