# Dynamic Dataflow CPU — Design Alternatives & Roads Not Travelled Companion document to the architecture docs. Captures rejected, deferred, and superseded approaches, their advantages, disadvantages, and why we went the way we did. Updated to reflect decisions from ongoing design discussions. --- ## 1. Routing Network Topology ### Chosen: Hierarchical Prefix-Based Routing (target architecture) ### v0 Implementation: Shared Bus with Type-Based Routing For 4 PEs + 1-2 SMs + I/O controller, a shared pipelined bus with latches is sufficient. type field in the packet header is the primary routing discriminator. prefix routing is the target for scaling but doesn't need to be built until Phase 3+. ### Alternative A: Manchester-Style Omega / Sorting Network - **How it works**: log2(n) stages of 2x2 routing elements. Every token traverses all stages. Destination bits are consumed one per stage. - **Advantages**: - Maximally general: any-to-any routing in fixed time - No routing tables to configure — topology IS the routing algorithm - Well-understood, proven in Manchester hardware - **Disadvantages**: - Fixed latency regardless of distance (the "DRAM from the moon" problem) - Latency grows with PE count even for local traffic - All tokens pay full traversal cost — devastating for locality-heavy programs - Hardware grows as n * log2(n) routing elements - **Why rejected**: our design explicitly exploits compiler-assigned locality. paying full network traversal for a token going to the PE next door is wasteful. hierarchical routing makes the common case fast. ### Alternative B: Crossbar - **How it works**: full n*n switch. any source to any destination in one cycle. - **Advantages**: - Minimum latency: everything is 1 hop - Simple conceptually - **Disadvantages**: - Hardware grows as n^2. 4 PEs = 16 crosspoints, fine. 8 PEs = 64. - Each crosspoint needs a mux + arbiter. gets expensive fast. - Contention handling needs buffering or stalling - **Why rejected**: doesn't scale. fine for 4 PEs but we want the architecture to extend beyond that. could revisit as a LOCAL interconnect within a cluster, with hierarchical routing between clusters. ### Alternative C: Ring Bus - **How it works**: tokens travel around a ring, each node inspects and either consumes or passes through. - **Advantages**: - Dead simple hardware: each node is a register + comparator + mux - Trivially extensible: add a node, extend the ring - **Disadvantages**: - Worst-case latency is n-1 hops - Average latency grows linearly with PE count - Bandwidth shared: total ring bandwidth is fixed regardless of PE count - **Status**: not rejected, just unnecessary at v0 scale. **worth reconsidering** as an intermediate step between shared bus and full prefix routing if the system grows to 8-16 PEs. ### Alternative D: Shared Bus (chosen for v0) - **Advantages**: - Absolute minimum hardware - Trivially simple - With pipelined latches, multiple packets in flight - **Disadvantages**: - Bandwidth limited - Doesn't scale past ~4-8 nodes - **Status**: v0 physical implementation. token format is designed for the prefix-routed future, but physical wires are shared bus. the type field provides a natural decomposition path — CN/AN/DN can be split onto separate physical paths when contention shows up. --- ## 2. Token Format ### Chosen: Type-Tagged Flit-Based Tokens (4 types, 16-bit flits) **UPDATED**: supersedes the 32-bit monolithic token format. See `bus-architecture-and-width-decoupling.md` for full rationale. - 2-bit type field as primary routing discriminator (unchanged) - Type 11 subdivided by 2-bit subtype for I/O, config, and future system management traffic (unchanged) - All tokens serialised into 16-bit flits on a 16-bit external bus - Standard tokens are 2 flits (32 bits logical); extended ops are 3-4 flits - Flit 1 is self-describing: type + destination enable routing after one flit - All standard tokens carry full 16-bit data in flit 2 (no more 14-bit dyadic data limitation) - See `architecture-overview.md` for full format specification ### Alternative A: Fixed-Field Flat Token - **Why rejected**: wastes bits on monadic and structure tokens. type-tagged approach reclaims 6+ bits. decoding cost is trivial. ### Alternative B: 36-bit Bus (RETIRED) - **Previous status**: escape hatch if 14-bit dyadic data was too limiting. - **Why retired**: the 16-bit bus with flit-based encoding eliminates the 14-bit dyadic data problem entirely — all tokens carry 16-bit data in flit 2. Mode B (2x bus clock) recovers full throughput on the narrower bus. 36 bits of physical bus traces is unnecessary. ### Alternative C: Variable-Width Tokens (PARTIALLY ADOPTED) - **Previous status**: rejected for complexity. - **Current status**: partially adopted via flit-based encoding. tokens are "as long as they need to be" — 2 flits for standard operations, 3-4 flits for extended ops. But flit size is fixed at 16 bits, avoiding the complexity of truly variable-width encoding. The routing layer only inspects flit 1; subsequent flits are forwarded blindly. ### Alternative D: 8-bit Bus (REJECTED) - 4 flits per standard token is too much latency - Mode B (2x) would still give only 2 flit-cycles per token — same as 16-bit bus at Mode A, but with half the data per flit - Not enough bits in flit 1 for routing after the type field --- ## 3. Matching Store Architecture ### Chosen: Pure Direct-Indexed Context Slots, Possible Overflow Fallback **UPDATED**: hash fallback removed from the primary pipeline. The matching operation is pure direct indexing — single cycle, always. No hash path, no CAM search, no set-associative lookup. See `pe-design.md` for detailed design. Overflow fallback (if ever needed) would be to external RAM or SM RAM with address translation via a small TLB/LUT, rather than the previously-considered CAM-based approach. Not needed for v0 — the compiler prevents overflow by construction. ### Alternative A: Pure Hashing (Manchester-Style) - **Why rejected**: <20% memory utilisation, 16 parallel banks per PE, overflow subsystem. too much hardware for the benefit. the semi-CAM approach gives single-cycle matching for the common case. ### Alternative B: Full CAM - **Why rejected**: discrete CAM chips are tiny (4x4 bits) or expensive. can't practically build a matching store out of them at needed scale. ### Alternative C: Software Matching (in the PE pipeline) - **Why rejected**: turns every dyadic operation into a multi-cycle search. destroys throughput. the whole point is hardware matching. ### FPGA Prototyping (recommended) Before committing to a TTL matching store, prototype in a small FPGA (iCE40, etc.). validate the addressing scheme, test with real token streams, measure collision rates. doesn't compromise the "discrete logic" goal — it's a prototyping step. **strongly recommended** before building boards. --- ## 5. Separate Communication Networks (CN/AN/DN) ### Chosen: Shared Physical Bus for v0, Logically Separate **UPDATED**: the Amamiya architecture has physically separate CN, AN, and DN. we're sharing a physical bus for v0 but maintaining the logical separation via the type field. The type field provides a clean decomposition path: - When SM access contention becomes measurable, split type-10 traffic onto a dedicated AN/DN bus - CN (types 00/01) and system (type 11) stay on the original bus - Further splits as needed This is a topology change, not a protocol change. no module interfaces change when the bus is split. ### Alternative: Physically Separate from Day One - **Advantages**: - No contention between traffic classes - Closer to Amamiya's proven architecture - **Disadvantages**: - 3x the bus wiring, routing logic, and board area for v0 - At 4 PEs, contention is unlikely to be the bottleneck - Premature optimisation - **Why deferred**: build it when the measurements say you need it. --- ## 6. Interrupt Handling ### Chosen: Unsolicited Token Injection from I/O Controller **UPDATED**: previous design had interrupt tokens injected directly into PE input FIFOs via hardware edge detectors on I/O pins. this is superseded by the I/O controller model where the controller generates and injects tokens onto the network. Advantages over the previous approach: - No per-PE interrupt hardware needed - I/O controller centralises all external event handling - Destination PE is configurable, not hardwired - Same mechanism works for all I/O devices See `io-and-bootstrap.md` for the unsolicited token generation model. ### Potential: Compiler-Assigned ISR PEs + Interrupt Token Injection - ISR is a dataflow subgraph mapped to specific PEs at compile time - External interrupt signal injects a token into that PE's input FIFO - ISR runs concurrently with main program, no context switch ### Alternative A: Dedicated Control Core Handles All Interrupts - **How it works**: a conventional CPU (6502, small RISC core, etc.) handles all interrupts in the traditional way. pushes ISR context onto its own stack, runs the handler, communicates results to the dataflow fabric. - **Advantages**: - Well-understood interrupt model - Can handle complex ISR logic (nested interrupts, priority levels, etc.) - Isolates interrupt complexity from the dataflow design - **Disadvantages**: - Requires a full conventional CPU — significant hardware - Communication between control core and dataflow fabric needs a bridge - ISR execution speed limited by the control core's performance - Defeats the goal of "not locking in to having a normal CPU" - **Why rejected**: explicitly a non-goal to depend on a conventional control core for runtime operations. but **a tiny microsequencer for bootstrap is accepted** — the distinction is bootstrap-only vs runtime-active. ### Alternative B: Interrupt Tokens with Priority Routing - **How it works**: interrupt generates a special high-priority token that pre-empts normal token flow in the network. dedicated priority lanes or priority bits cause routing nodes to fast-track it. - **Advantages**: - Minimum interrupt latency - Any PE can handle interrupts (not just designated ones) - Dynamic: runtime decides which PE handles based on load - **Disadvantages**: - Priority routing adds complexity to every routing node - Risk of priority inversion (high-priority token blocked by full FIFO) - "Any PE" means the ISR subgraph must be loaded everywhere, or you need dynamic code loading at interrupt time - Much more complex than designated-PE approach - **Why rejected**: over-engineered for v0. the designated-PE approach is simpler and the compiler already handles PE assignment. priority can be added later (a priority bit + FIFO bypass is ~3 chips per PE). ### Alternative C: Polling (No Hardware Interrupt Support) - **How it works**: a PE periodically checks I/O status via structure memory reads. no hardware interrupt mechanism at all. - **Advantages**: - Zero additional hardware - Entirely in the dataflow paradigm (it's just a program) - Deterministic timing (no async interrupts) - **Disadvantages**: - Interrupt latency = polling interval (potentially very high) - Wastes PE cycles on polling when no interrupt is pending - Ties up an SM bank for I/O status reads - Unsuitable for time-critical events - **Why rejected for general use**: bad latency characteristics. BUT this is actually a viable approach for non-time-critical I/O (checking if serial data is available, reading sensors). **could coexist with hardware interrupt support for different priority levels.** --- ## 7. Bootstrap / Program Loading ### Chosen: Layered Approach (microcontroller -> I/O controller) **UPDATED**: previous design specified a dedicated hardwired microsequencer with a separate config bus. this has been superseded by a layered approach: - **Phase 0-2**: external microcontroller as test fixture and bootstrap source - **Phase 4+**: I/O controller handles bootstrap via type-11 config writes No separate config bus. bootstrap traffic travels the normal network as type-11 subtype-01 packets. this eliminates a dedicated bus and means the bootstrap path is also the runtime reprogramming path. See `io-and-bootstrap.md` for the full bootstrap sequence. ### Previous Approach: Hardwired Microsequencer + Config Bus (superseded) - ROM state machine + UART + dedicated config bus - ~20-30 TTL chips - **Why superseded**: the type-11 config write mechanism eliminates the need for a separate config bus. the I/O controller (or external microcontroller during development) injects config writes onto the normal network. simpler architecture, fewer buses, and the same mechanism enables runtime reprogramming. ### Alternative A: Bootstrap PE (hardwired to run loader from ROM) - **Status**: deferred but not rejected. the I/O controller bootstrap model is essentially a simplified version of this — a fixed-function device that reads from storage and emits config writes. evolving the I/O controller toward a full PE with boot ROM is a natural future step. the architecture doesn't prevent it. ### Alternative B: External Host (6502, Z80, RP2040, etc.) - **Status**: the RP2040/Arduino IS the external host during Phase 0-2. it's a development tool, not part of the architecture. the long-term goal remains self-hosted bootstrap via the I/O controller. --- ## 8. Data Width ### Chosen: 16-bit Data, 16-bit External Bus (RESOLVED) **UPDATED**: data width resolved to 16-bit. External bus resolved to 16-bit with flit-based token encoding. See `bus-architecture-and-width-decoupling.md` for the three independent width domains. - 16-bit is the native word size for SM, ALU, and matching store data - All standard tokens carry full 16-bit data in flit 2 (no more 14-bit dyadic limitation) - IRAM width decoupled: 32-bit effective (two-half read), independently sized - PE pipeline registers are wider (~64-68 bits) but purely internal ### Alternative: 8-bit Data - **Advantages**: narrower everything — fewer chips, traces, board area. more period-authentic (6502/Z80 era). simpler ALU. - **Disadvantages**: 8-bit intermediates overflow constantly in real computation. need multi-word operations for anything >255. not enough bits in flit 1 for meaningful routing + addressing after type field. - **Status**: rejected. 16-bit is the minimum for practical computation. ### Alternative: Mixed 8/16 (8-bit bus, 16-bit operations via double-pump) - **Disadvantages**: token transmission takes 4 flit-cycles (32-bit logical token / 8-bit bus). throughput quartered. every pipeline stage needs double-pump logic. complexity in exchange for saving a few bus traces. - **Status**: rejected. the 16-bit bus with 2-flit tokens is the right balance between physical simplicity and throughput. --- ## 9. Clocking ### Chosen: Three-Mode Progression (A → B → C) **UPDATED**: see `network-and-communication.md` and `bus-architecture-and-width-decoupling.md` for full details. Three modes form a progression, not mutually exclusive alternatives: **Mode A (chosen for v0): Globally synchronous, locally gated.** One master clock, stages stall independently via gated clocks. simplest TTL implementation. with a 16-bit bus and 2-flit tokens, effective inter-module bandwidth is half the PE token rate. adequate for v0 where most traffic is PE-internal. **Mode B: Bus at 2x PE clock.** The external bus runs at double the PE clock rate. bus critical path (wires + latches + comparators) is much shorter than PE pipeline stages. ser/deser at PE boundaries run in the fast domain; dual-clock FIFOs handle the crossing. effective bandwidth equals PE token rate — full throughput recovery on the narrower bus. transition from Mode A requires bus clock PLL/divider + dual-clock FIFOs. **Mode C: Fully asynchronous.** No global clock, req/ack handshaking on every flit. each module runs at its own speed. theoretically ideal for dataflow but painful to design and debug in TTL. transition from Mode B requires replacing clocked FIFOs with async FIFOs and bus clock with handshake signals. Neither transition changes any module interface — this is the payoff of the FIFO-based decoupling discipline. the architecture preserves Mode C by mandating ready/valid handshaking at every inter-module boundary. ### Previous Alternative: Mesochronous Same frequency, no phase alignment. dual-clock FIFOs at boundaries. **Subsumed by Mode B**, which provides the same dual-clock FIFO infrastructure but with the additional benefit of 2x bus bandwidth. The inter-PE network is the highest-value target for early async adoption, even while PEs themselves stay synchronous. --- ## 10. Miscellaneous Ideas Not Yet Integrated ### SM as Coprocessor for Complex Operations - SM could potentially handle operations beyond memory access: matrix multiply, FFT butterfly, etc. by embedding specialised functional units in SM banks alongside the data they operate on. - Very Amamiya-inspired (he embedded list operators in structure memory). - Deferred: v0 SM has only read/write/fetch-and-add/CAS. ### Using FPGA for Matching Store Prototyping - Before committing to a TTL matching store design, prototype it in a small FPGA (iCE40, etc.). validate the addressing scheme, test with real token streams, measure collision rates. - Doesn't compromise the "discrete logic" goal — it's a prototyping step. - The FPGA gets replaced with TTL once the design is validated. - **Strongly recommended** before building boards. ### 4x4 CAM Chips (100142) for Small Associative Lookups - Too tiny for matching store (4 words x 4 bits per chip) - Potentially useful for: - Routing table entries at network nodes (4-8 entries) - Context slot free-list (but bitmap + priority encoder is cheaper) - Small tag-based lookups in special-purpose logic - Keep in the parts bin. don't design around them. ### Compile-Time Token Route Scheduling - The E1 does fully static routing. we could do partially static: compiler pre-computes common token routes and configures routing tables, but the network still handles dynamic routing for runtime-generated tokens (new activations, interrupt responses). - This is essentially what we've already landed on but worth noting explicitly as a design point on the static-dynamic spectrum. ### Vector / SIMD-Style Parallel Operations Explored in the context of the EM-4 analysis. How to engage multiple PEs on a data-parallel operation (e.g. vec_add across array elements). **Option A: SM Scatter/Gather (recommended)** SM holds arrays. A CM issues a burst of SM reads, SM returns elements as tokens to assigned PEs, each PE does its operation locally, results write back to SM or forward as tokens. The "vector instruction" is really a small program fragment that generates the scatter/read pattern. - Most dataflow-native: no new hardware, no new instruction types - Latency depends on SM access path: - If SM-CM transfers use the main bus: every element is bus traffic. At 4 PEs this is fine; at scale it saturates. - If SM-CM has a dedicated interconnect (direct connection, or separate AN/DN fabrics as in Amamiya's DFM): much better. SM reads don't compete with inter-CM token traffic. This is the strongest argument for dedicated SM-CM paths. - Strongly connected blocks (deferred) would help amortise the per- element dispatch overhead — a block could issue a burst of SM reads as a tight loop without re-entering the token pipeline. - The compiler generates the scatter/gather pattern statically. **Option B: Broadcast Token** A token type that routes to all PEs matching a prefix mask (or all PEs in a group). Each PE combines broadcast data with locally-held data. - On a shared bus, broadcast is free (everyone sees every flit) - On point-to-point fabric, requires tree-structured forwarding — routing nodes duplicate the packet - Falls naturally out of prefix-based hierarchical routing: broadcast to prefix `01xx` hits all PEs in that group - Useful for distributing loop invariants, control signals, reduction operands - Doesn't replace scatter/gather for element-wise access — it's complementary (broadcast the operation, scatter the data) - Deferred: needs prefix routing infrastructure not present in v0 **Option C: Wide Tokens (multi-element payload)** Pack multiple data elements into a single multi-flit token. PE unpacks and processes sequentially (or in a strongly connected block). - Amortises network/matching overhead: 1 token vs N tokens - Already supported by multi-flit token format - But PE ALU is 8/16-bit, so N elements = N cycles internally. No actual parallelism, just reduced network overhead. - Most useful as a micro-optimisation within Option A. **Option D: Paired-PE Lockstep (true SIMD)** Two PEs receive the same instruction stream but different data. Requires synchronisation or broadcast instruction trigger. - Alien to the dataflow model (PEs are supposed to be independent) - Compiler must ensure identical IRAM contents at matching addresses - Synchronisation mechanism needed — unclear how to do this without violating dataflow semantics - **Rejected**: fights the architecture. If you want SIMD, use Option A where each PE independently processes its element. The parallelism comes from the graph structure, not from lockstep execution. **Decision**: Option A (SM scatter/gather) is the primary approach. Option B (broadcast) is a natural extension when prefix routing is implemented. Options C and D are rejected or subsumed. **Key implication**: dedicated SM-CM paths become more valuable when vector operations are common, because the per-element SM traffic is the bottleneck. This is a strong argument for eventually separating AN/DN from the main CN, even at small scale. --- ## 11. Matching Store Entry Addressing ### Chosen: Unified Offset (dyadic-first IRAM layout) The token's offset field serves as both the IRAM instruction address and (for dyadic instructions at offsets < M) the matching store entry within the context slot. The compiler packs dyadic instructions at low IRAM offsets and monadic above. Single cycle, no extra token bits, no lookup table. See `pe-design.md` §Instruction Address vs Matching Store Address for the chosen design. ### Alternative A: Separate Token Fields The token carries both an instruction offset AND a separate match entry index. Costs token bits — the offset field would need to be split or the match_entry packed into spare bits. Rejected because the unified offset approach achieves the same result with zero bit cost. ### Alternative B: Instruction Word Contains Match Entry The instruction word fetched from IRAM in Stage 3 would contain the match_entry field. Initially considered as the "simplest v0 approach." **Rejected** because Stage 2 (matching) happens BEFORE Stage 3 (instruction fetch) — the match_entry must be known before the instruction word is available. This ordering constraint makes the approach impossible without adding a pipeline stall or lookup table. ### Alternative C: Lookup ROM/SRAM A small lookup ROM/SRAM alongside the matching store maps instruction offset → match_entry. Adds either a serial read before the match SRAM access (extra latency) or requires a second SRAM port (extra hardware). Rejected as unnecessary given that the compiler can enforce the dyadic-first layout constraint. --- ## 12. Matching Store Overflow: CAM-Based Buffer An early design considered using National Semiconductor 100142 CAM chips (4×4-bit, content-addressable memory) for a small overflow buffer alongside the matching store. Tokens that couldn't fit in the direct- indexed store would spill to the CAM for associative lookup. **Why abandoned:** the 100142 is tiny (4 words × 4 bits per chip) and expensive. Building a useful overflow buffer requires many chips for minimal capacity. The TLB/LUT fallback to external RAM or SM RAM (described in `pe-design.md` §Overflow) is more scalable and uses commodity SRAM. The 100142 chips remain potentially useful for other small associative lookups (routing tables, free-list management) but are not a good fit for matching store overflow. --- ### Instruction Memory as Write-Back Cache - Future idea: if instruction memory is writable at runtime, could it function as a write-back cache for a larger backing store? PE fetches function bodies on demand from SM or flash, caches them in local instruction SRAM. evicts on capacity pressure. - Very speculative. would require significant additional hardware (tag memory, eviction logic, demand-fetch state machine). probably not worth it for v0-v4. but the writable instruction memory path means the hardware foundation exists. ### ROM-Mapped IRAM Banks (Execute in Place) - The '610 memory mapper doesn't care whether the physical backing store is SRAM or ROM. Some logical IRAM banks could map to shared ROM (parallel EPROM/flash on the address bus) instead of per-PE SRAM. Shared library code lives in ROM once, every PE fetches from it directly — no bootstrap loading needed for that code. - **Appeal**: standard library or runtime support code is write-once/read-many. ROM-mapping avoids loading it into every PE's SRAM at bootstrap time and frees those SRAM banks for user code. - **Timing mismatch**: parallel ROMs of the era (27C256, AT28C256) run 150-250ns access time. if IRAM SRAM is at the fast end (~55-100ns), ROM-banked fetches need wait states — 3-4 cycles instead of the normal 2-cycle two-half read. the PE pipeline would need to stall differently depending on which bank is active. Solvable with wait-state insertion keyed to the active bank's backing store type (ROM vs SRAM flag per '610 mapping entry, or a separate register). - **Fan-out**: each PE has its own IRAM data bus. sharing a single ROM across PEs requires either multiplexed access (contention, arbitration) or ROM per PE (defeats the sharing benefit). on a shared bus this is less of an issue, but with per-PE IRAM buses it's a real constraint. - **Write protection**: IRAM write tokens targeting a ROM-backed bank must be rejected or ignored. needs write-protect logic per bank mapping (a flag bit in the '610 mapping register or a separate WP register). - **Status**: back-burner. the bootstrap EXEC approach handles v0 fine. ROM-mapped banks become interesting at scale where bootstrap loading time or SRAM capacity per PE is a real constraint. the '610 infrastructure makes it a relatively cheap upgrade path if the timing issues are solved.