# Dynamic Dataflow CPU — Bus Architecture & Width Decoupling Design document covering the separation of external bus width, internal PE data path width, and instruction memory width. See `architecture-overview.md` for module taxonomy and overall architecture. See `network-and-communication.md` for routing topology and clocking discipline. See `pe-design.md` for PE pipeline and frame-based matching. See `iram-and-function-calls.md` for instruction encoding and output modes. See `bus-interconnect-design.md` for the physical bus implementation (arbitration, node interfaces, loopback, backpressure). ## Core Principle: Three Independent Width Domains The architecture separates into three width domains, each sized for its own constraints. There is no requirement that they match. | Domain | Width | Driven By | |--------|-------|-----------| | External bus (inter-module) | 16-bit | routing trace count, physical buildability | | Token format (logical) | variable-length flits | encoding needs per token type | | IRAM (instruction memory) | 16-bit single-half read | opcode + mode + frame reference; see `iram-and-function-calls.md` | | Frame store entries | 16-bit data (or 32-bit with wide=1) | operand, constant, and destination storage | | PE pipeline registers | wide, decomposed | parallel data path + control path | | SM internal datapath | 16-bit | SRAM word size | Width conversion occurs at FIFO boundaries between domains, using serializers/deserializers (shift register + toggle). This is cheap in TTL and naturally integrates with the clock domain crossing FIFOs that already exist in the GALS clocking design. --- ## External Bus: 16-bit Physical ### Rationale 32 data lines plus control signals is at the edge of practical breadboard construction and remains a significant routing burden on PCBs. Halving the bus width to 16 bits: - Halves data traces (16 data + handful of control vs 32 + control) - Halves routing node width (comparators, latches, muxes all narrower) - Halves FIFO storage width at network boundaries - Dramatically simplifies physical interconnect for v0 and beyond ### Flit Structure All inter-module communication is serialized into 16-bit flits. The first flit of any packet contains the type field and routing information, enabling routing nodes to make forwarding decisions after receiving only the first flit. Tokens are 1-2 flits for compute traffic, 2 flits for SM operations and PE-local writes, and 2-3 flits for some SM operations (CAS, EXT). The number of flits is determined by the prefix bits in flit 1 — routing nodes and receivers can predict packet length from the first flit alone. ### Impact on Throughput Inter-module token transfer takes 1-2 flit-cycles depending on token type. Inline monadic tokens (1 flit) are the fastest path; standard compute and structure tokens take 2 flit-cycles. This is acceptable because: 1. Most token traffic in a well-compiled program stays PE-local (tokens circulate through the ring pipeline without touching the external bus) 2. The external bus is already the slow path - SM access latency and cross-PE routing latency dominate over bus serialization 3. Clock mode B (2x bus clock) recovers full bandwidth on the narrower bus when needed (see Clock Discipline below) --- ## Token Format: Opcodes Don't Travel **Critical architectural point: tokens do not carry opcodes.** A token is pure data-in-motion — it carries a destination instruction address, activation identity, and a data value. It does not know what operation will be performed on it. The execution flow for a dyadic instruction (pipeline-reversed order: IFETCH before MATCH): 1. Token arrives at PE: `[offset, port=L, act_id, data_L]` 2. IRAM fetch at `offset` begins; 670 act_id resolution begins in parallel 3. act_id resolves to frame_id; presence check for `(frame_id, offset)` — no partner, so store `data_L` in frame and set presence bit 4. Token 2 arrives: `[offset, port=R, act_id, data_R]` 5. IRAM fetch and act_id resolution again in parallel 6. Presence bit set — extract `data_L` from frame, clear presence 7. Now have `(offset, data_L, data_R)` — instruction already fetched from IRAM 8. IRAM returns: `[type, opcode, mode, wide, fref]` 9. ALU executes opcode on data_L, data_R 10. Read destination(s) from frame at fref; form output token(s) using pre-formed flit 1 from frame + ALU result This means: - **Frame entries hold operand data, constants, and pre-formed destination flits.** No opcode, no instruction metadata per activation — the instruction template is shared. - **IRAM width is completely independent of bus width.** Instruction words are fetched from PE-local SRAM, never serialized onto the external bus (except during program loading via PE-local write tokens, which is a slow-path operation). - **The opcode is an implementation detail of the PE.** It gets loaded into IRAM during program initialization and sits there until replaced. From the network's perspective, it doesn't exist. ### Instruction Deduplication Because IRAM entries are templates and frames provide per-activation state, many activations can share the same physical instruction. A series of comparisons against different thresholds uses one `cmp` instruction at a single IRAM offset — each activation provides different operand pairs and constants via different frames. The number of IRAM entries a fragment needs is the number of **unique operation shapes**, not the total number of operations executed. This keeps IRAM small even for moderately complex function fragments. ### Implications for Program Loading Loading a program means: 1. Write IRAM entries via PE-local write tokens (prefix 011+01, region=0) 2. Allocate frames via frame control tokens (prefix 011+00, op=ALLOC) 3. Write constants and destinations into frame slots via PE-local write tokens (prefix 011+01, region=1) 4. Inject initial tokens (constants, inputs) via I/O 5. The graph executes itself Replacing instructions at runtime is a PE-local write token to the target PE. See **IRAM Valid-Bit Protection** below for safe swap protocol. --- ## Flit-1 Bit Allocation: Routing vs Endpoint Decode Flit 1 is 16 bits. The hard routing requirement is minimal: **Network routing nodes** inspect only `bit[15]` (SM/CM split) plus the 2-bit destination ID. These 3 bits determine where the flit goes. The remaining bits are opaque payload - the network forwards them blindly. **The destination endpoint** (PE or SM) decodes the full 16 bits to determine token format, how many further flits to clock in, and how to begin processing. ### Routing Field ``` Flit 1 bit [15] — SM/CM discriminator: 0 = CM token → route to PE identified by PE_id 1 = SM token → route to SM identified by SM_id For CM tokens (bit[15]=0): bits [13:12] = PE_id for dyadic wide (prefix 00) bits [12:11] = PE_id for monadic normal and misc bucket (prefix 01x) For SM tokens (bit[15]=1): bits [14:13] = SM_id (0-3) ``` Everything below the destination ID is endpoint-decoded, not network-decoded. The routing node's job is to extract the destination ID from the appropriate bit position based on bit[15]. ### Flit-1 Field Alignment Invariants Several field positions are architecturally fixed across CM token formats, enabling shared decode hardware: - **PE_id** is always at bits [12:11] for monadic normal and misc bucket tokens (prefix 01x), and at bits [13:12] for dyadic wide (prefix 00). The routing node extracts PE_id from the appropriate position based on the prefix. - **act_id** is always bits [2:0] on dyadic wide and monadic normal tokens. This allows the 670-based act_id-to-frame_id lookup to begin immediately from the low 3 bits of flit 1, regardless of token type. - **offset** is bits [10:3] for both dyadic wide and monadic normal tokens (8 bits). This allows the IRAM address latch to wire directly to flit 1 bits [10:3] for the two hot-path formats. For the misc bucket formats (011+xx), field positions vary by subtype. These are decoded after the 5-bit prefix, not on the hot path. --- ## CM Token Formats (bit[15]=0) The prefix encoding uses variable-length bit patterns to give the hot path (dyadic wide) the shallowest decode and the most generous field allocation. ### Dyadic Wide (prefix 00) — 2 flits, 16-bit data, HOT PATH ``` Flit 1: [0][0][port:1][PE:2][offset:8][act_id:3] = 16 bits Flit 2: [data:16] = 16 bits ``` The dominant token format. Port lives in flit 1 alongside routing. - **offset:8** -> 256 IRAM entries addressable by dyadic tokens - **act_id:3** -> 8 unique activation IDs (4 concurrent frames with 4 IDs of ABA distance) - **port:1** -> L/R operand discriminator - Full 16-bit data in flit 2 The PE begins the IRAM read on `offset[7:0]` and the 670 act_id-to-frame_id resolution on `act_id[2:0]` the instant flit 1 is latched. Both proceed in parallel. Decode: bit[15]=0 AND bit[14]=0 — two gates. ### Monadic Normal (prefix 010) — 2 flits, 16-bit data ``` Flit 1: [0][1][0][PE:2][offset:8][act_id:3] = 16 bits Flit 2: [data:16] = 16 bits ``` Standard monadic token. No matching — the arriving token IS the sole input. - **offset:8** -> 256 IRAM entries addressable by monadic tokens - **act_id:3** -> 8 unique activation IDs - Full 16-bit data in flit 2 Decode adds one more gate at bit[13]. ### Misc Bucket (prefix 011) — infrequent formats The 2-bit sub field after the 011 prefix discriminates four formats: **Frame Control (sub=00) — 2 flits, activation lifecycle:** ``` Flit 1: [0][1][1][PE:2][00][op:1][spare:3][act_id:3] = 16 bits Flit 2: [payload:16] = 16 bits ``` Manages activation lifecycle on the target PE. - **op=0 (ALLOC):** associate act_id with next free frame. Flit 2 = return routing for confirmation/error token. - **op=1 (FREE):** release frame associated with act_id. Flit 2 = unused (or diagnostic). **PE-Local Write (sub=01) — 2 flits, IRAM and frame loading:** ``` Flit 1: [0][1][1][PE:2][01][region:1][spare:1][slot:5][act_id:3] = 16 bits Flit 2: [data:16] = 16 bits ``` Writes to PE-local storage. The `region` bit selects the target: - **region=0 (IRAM write):** act_id ignored. slot = IRAM address (within current bank). - **region=1 (frame write):** act_id resolved to frame_id by PE's tag store. slot = frame slot index within that activation's frame. **Monadic Inline (sub=10) — 1 flit, trigger only:** ``` Flit 1: [0][1][1][PE:2][10][offset:7][spare:2] = 16 bits No flit 2. ``` Single-flit token. Carries no data payload, just a trigger. Constants for the instruction come from the frame (via fref in the instruction word). - **offset:7** -> 128 IRAM entries addressable by inline tokens - **spare:2** - reserved Use cases: synchronization signals, barrier tokens, loop iteration triggers, SWITCH not-taken triggers. Note: monadic inline does not carry an act_id. The instruction at the target offset must not require frame access (mode 4 CHANGE_TAG with no constant, or a dedicated control opcode). Alternatively, the spare bits could carry a reduced act_id in a future revision. **Spare (sub=11) — reserved:** Candidates: extended monadic with wider offset, broadcast/multicast, debug/trace injection, bus-level AN forwarding hint (for split-bus SM-to-SM routing). ### CM Token Summary | Format | Prefix | Flits | Data | Offset | Act ID | Port | |--------|--------|-------|------|--------|--------|------| | Dyadic wide | 00 | 2 | 16-bit | 8 (256) | 3 | flit1 | | Monadic normal | 010 | 2 | 16-bit | 8 (256) | 3 | -- | | Frame control | 011+00 | 2 | 16-bit payload | -- | 3 | -- | | PE-local write | 011+01 | 2 | 16-bit | -- | 3 | -- | | Monadic inline | 011+10 | 1 | none | 7 (128) | -- | -- | | (spare) | 011+11 | ? | ? | ? | ? | ? | ### Hot Path Decode Summary - bit[15] splits SM/CM: one gate - bit[14] splits dyadic-wide from everything else: one gate - bit[13] splits monadic normal from misc bucket: one more gate - the misc bucket is three gates deep, but nothing there is latency-critical On the hot path (dyadic wide, prefix 00), the PE begins the IRAM read on `offset[7:0]` and the 670 act_id-to-frame_id resolution on `act_id[2:0]` simultaneously with decode. By the time the prefix is fully resolved (2 gates, ~10 ns), both lookups are already in flight. ### Spare Bits and Future Use The spare bits are explicitly reserved, not accidentally unused: - **Frame control spare:3** - future candidates: extended op field (up to 4 lifecycle operations), diagnostic flags, priority level. - **Monadic inline spare:2** - future candidates: reduced act_id (2 bits), extended interpretation flag. - **Misc bucket sub=11** - entire format reserved for future use. The spare bits provide escape hatches for architectural evolution without changing the base format. v0 should treat them as must-be-zero on transmit, ignored on receive. --- ## SM Token Format (bit[15]=1) ``` SM token (2 flits, standard): flit 1: [1][SM_id:2][op:3-5][addr:8-10] = 16 bits flit 2: [data:16] or [return_routing:16] = 16 bits ``` 15 bits available after the SM discriminator. SM_id (2 bits) selects one of 4 SMs. The remaining 13 bits are split between opcode and address using variable-width encoding: ``` op[2:1] != 11: 3-bit opcode, 10-bit addr (1024 cells) read, write, alloc, free, exec, ext op[2:1] == 11: extends to 5-bit opcode, 8-bit payload (256 cells or inline data) rd_inc, rd_dec, cas, raw_rd, clear, set_pg, write_im, (spare) ``` One decode gate on op[2:1] discriminates the two tiers. See `sm-design.md` for the full opcode table, extended addressing, and `cas` handling. **Return routing in flit 2:** for `read` and other result-producing ops, flit 2 carries a **pre-formed CM token template**. The SM's result formatter latches the template, prepends it as flit 1, and appends the read data as flit 2. **IO is memory-mapped SM:** IO devices are mapped into SM address space (typically SM00 at v0). IO operations use the standard SM token format. I-structure semantics provide natural interrupt-free IO: a `read` from an IO device that has no data defers until data arrives. --- ## Variable-Length Token Summary | Token Type | Prefix | Flits | Total Bits | Contents | |-----------------|---------|-------|------------|------------------------------------------------| | Dyadic wide | 00 | 2 | 32 | offset + act_id + port + 16-bit data | | Monadic normal | 010 | 2 | 32 | offset + act_id + 16-bit data | | Frame control | 011+00 | 2 | 32 | op + act_id + 16-bit payload | | PE-local write | 011+01 | 2 | 32 | region + slot + act_id + 16-bit data | | Monadic inline | 011+10 | 1 | 16 | offset only, no data | | SM standard | 1 | 2 | 32 | SM_id + op + addr + 16-bit data or ret routing | The common case is 2 flits. Inline monadic (1 flit) is the fast path for control-flow tokens. PE-local writes are 2 flits and infrequent during execution. --- ## IRAM Valid-Bit Protection ### The Problem IRAM is written via PE-local write tokens (prefix 011+01, region=0) that share the PE's input path with compute tokens. When IRAM contents are replaced at runtime (swapping function fragments in and out), tokens in flight may target IRAM addresses that have been or are being overwritten. Because tokens do not carry instruction identity information, the PE cannot distinguish "right instruction" from "wrong instruction" — it just sees an offset into IRAM. This is an **instruction identity problem**, not a presence problem. The dangerous case is not "IRAM is empty" but "IRAM contains a different instruction than the token expects." ### The Mechanism: Per-Page Valid Bits IRAM is logically divided into pages (e.g. 8 pages of 32 instructions for 256-entry IRAM, or 16 pages of 16). Each page has a 1-bit valid flag, stored in a small TTL register alongside IRAM. Total hardware cost: one register chip for all page valid bits. The valid bit is checked during the IFETCH pipeline stage, in parallel with the IRAM SRAM read. The top bits of the token's `offset` field select the page; the valid bit for that page gates whether the token proceeds or is rejected. ``` Token arrives at IFETCH: page = offset[high bits] if valid_bit[page] == 0: -> reject token (see rejection policy below) else: -> proceed with instruction fetch and act_id resolution ``` ### IRAM Swap Protocol Because config writes and compute tokens share the input path, the swap sequence is naturally ordered: ``` 1. Loader sends drain signal (implementation TBD — could be a PE-local write "quiesce" flag, or the PE back-pressures via handshake/ready signal) 2. PE processes remaining compute tokens in pipeline (natural drain) 3. PE-local write token (prefix 011+01, region=0) arrives: a. PE clears valid bit for target page b. PE writes instruction word to IRAM at specified address c. If more write tokens follow (burst), keep writing 4. Load-complete marker arrives (PE-local write with load-complete flag): a. PE sets valid bit for target page b. PE resumes accepting compute tokens for that page ``` During steps 3-4, any compute token that arrives targeting an invalid page is rejected. The shared input path ordering guarantees that tokens from the *new* code epoch cannot arrive until after the loader has sent them, which is after the load completes. Rejected tokens are therefore late arrivals from the old epoch — work that is being abandoned. **Presence-bit optimisation:** the frame's presence metadata (in the 670 register files) can be checked before step 1 to determine if any tokens are pending for offsets in the target page. If all presence bits for matchable offsets in that page are clear, the drain step can be skipped entirely — no tokens are waiting for those instructions. This enables targeted IRAM replacement without stalling the entire PE. ### Rejection Policy **v0: discard silently + diagnostic.** Late-arriving tokens targeting an invalid IRAM page are dropped. The PE sets a sticky flag (directly driving a diagnostic LED) to indicate that a discard occurred. This is a "should never happen if the loader protocol is correct" safety net. The LED makes it visible during debugging without adding any pipeline complexity. If the flag lights up, something is wrong with the drain timing. **Future: NAK response.** The PE could form a NAK token from the rejected compute token and emit it to a coordinator. The output stage already exists (forms tokens from frame destinations + ALU results); a bypass path from IFETCH to the output would enable this. Estimated cost: a mux and some control logic, ~5-8 TTL chips. Deferred until the runtime is sophisticated enough to act on NAKs. ### What This Does NOT Protect Against The valid-bit mechanism catches tokens that arrive **during** an IRAM swap (page is invalid). It does **not** catch tokens that arrive after a swap completes and the page is re-validated with different code. Preventing that case requires the drain protocol to be correct — all tokens from the old epoch must have been processed or discarded before the new code is marked valid. For v0, this is a software/loader invariant enforced by the drain protocol. Future hardening options: - **Per-page epoch counter (2-3 bits):** incremented on each page reload. Checked against an expected epoch stored per-activation or derived from spare token bits. Catches post-swap stale tokens at the cost of a comparator + epoch storage. - **Fragment ID register per page:** similar to epoch but identifies the fragment by name rather than sequence number. More expensive (wider comparator) but more debuggable. Both options fit in the spare bits reserved in the token formats above. The valid-bit mechanism is forward-compatible with either. --- ## IRAM: Decoupled Width, Sized for Encoding Needs Instruction memory word width is driven entirely by what needs to be encoded per instruction, with no pressure from bus width. ### IRAM Physical Organisation - 256 entries (8-bit address) per PE per IRAM bank, 512 bytes total (two 8-bit-wide SRAM chips) - Address format: `[offset:8]` = 8 bits (direct from token flit 1 bits [10:3]) - Single-cycle 16-bit read: both SRAM chips addressed in parallel, full instruction word available in one cycle - Instruction word format: `[type:1][opcode:5][mode:3][wide:1][fref:6]` = 16 bits. See `iram-and-function-calls.md` for detailed field definitions and mode table. - Dyadic and monadic tokens both address the same 256-entry range (8-bit offset on both formats) - Written only during program loading (PE-local write tokens, prefix 011+01, region=0) with valid-bit protection - **Bank switching:** the 8-bit offset addresses 256 entries within the current IRAM bank. With 8Kx8 SRAM, higher address bits select between banks (up to 16 banks of 256 = 4096 instruction templates per PE). Bank selection is a PE-local register, changed by loader control tokens. ### Destinations and Constants in Frames, Not IRAM The original 32-bit two-half IRAM design packed destination addresses and inline constants into the instruction word. The revised 16-bit instruction contains only the operation template (opcode, mode, frame reference). All per-activation data — destinations, constants, accumulators — lives in the frame. This has several consequences: - **IRAM density doubles:** 256 instructions per bank in the same SRAM capacity that previously held 128 entries of 32-bit words. - **Read cycles halve:** one SRAM read per fetch instead of two sequential half-reads. - **Template sharing increases:** the same instruction at a single IRAM offset can serve many activations with different destinations and constants, because all variable data is in the per-activation frame. --- ## Matching: Frame-Based with 670 Register Files The matching store is no longer a rectangular `[ctx_slot:offset]`-indexed SRAM. Match operand data lives in the per-activation frame (SRAM), and match metadata (presence, port) lives in 74LS670 register files for combinational access. ### How Matching Works When a dyadic token arrives, the PE performs two parallel lookups: 1. **IRAM fetch:** `offset[7:0]` addresses the instruction SRAM. Returns the 16-bit instruction template. 2. **670 act_id resolution:** `act_id[2:0]` indexes the act_id-to-frame_id 670 lookup table. Returns `{valid, frame_id}` in ~35 ns (combinational). With frame_id resolved, the PE checks presence and port metadata for the target matchable offset via additional 670 chips indexed by `[frame_id:2]`. The matchable offset range is constrained to offsets 0-7 (8 dyadic-capable slots per frame). The assembler packs dyadic instructions at low offsets; offsets 8-255 are monadic-only. On a match miss (first operand), the PE writes the arriving data into the frame SRAM at the match slot and sets presence in the 670. On a match hit (second operand), the PE reads the stored data from the frame, clears presence, and proceeds to execute. ### Hardware Cost | Component | Chips | Notes | |-----------|-------|-------| | act_id -> frame_id lookup | 2 | 74LS670, indexed by act_id | | Presence + port metadata | 4 | 74LS670, indexed by frame_id | | Bit select mux | 1-2 | offset-based selection of presence/port | | **Total match metadata** | **~8** | | All reads are combinational (~35 ns). All resolve during the IFETCH stage in parallel with the IRAM read. By the time the MATCH stage begins, the PE knows frame_id, presence, and port — the only SRAM access in MATCH is reading/writing the actual operand data in the frame. See `pe-pipelining-and-multiplexing.md` for the full design of the 670-based matching system, including the set-associative SRAM fallback (Approach A) and full register-file pool (Approach B) alternatives. --- ## PE Internal Pipeline: Wide but Decomposed The pipeline is reversed from the original design: IFETCH occurs before MATCH. After the instruction is fetched and matching completes, the pipeline carries both operand data and instruction control information in parallel but logically separate paths. ### Data Path ``` 16-bit mode: data_L: 16 bits (from frame match slot or arriving token) data_R: 16 bits (from arriving token or frame match slot) | ALU (16-bit) | result: 16 bits ``` The data path is uniformly 16-bit. The 8-bit narrow data mode from the original design is removed — all compute tokens carry 16-bit data. The frame-based architecture makes 8-bit a software concern (mask and extend in the ALU) rather than a hardware data path width. ### Control Path (16-bit instruction word + frame reads) ``` From IRAM (16 bits): type: 1 bit (CM/SM operation select) opcode: 5 bits (consumed by ALU / SM opcode mapper) mode: 3 bits (output routing, frame access pattern) wide: 1 bit (16/32-bit frame value select) fref: 6 bits (frame slot base index) From frame SRAM (read during output stage): dest1: 16 bits (pre-formed flit 1 for output token) dest2: 16 bits (pre-formed flit 1 for fan-out, if mode requires) const: 16 bits (constant value, if mode requires) ``` ### Total Pipeline Register Width Between the instruction fetch and execute stages, the pipeline register holds ~48 bits (2x 16-bit operands + 16-bit instruction word). Between execute and output, it holds ~48+ bits (16-bit ALU result + 16-bit destination from frame + control bits). These bits arrive from different sources (frame SRAM for operands, IRAM for control, frame again for destinations) and leave to different destinations (ALU for data+opcode, bus output for destinations). They are latched at the same time but never need to pass through a single bus. The key simplification over the original design: destination flits are pre-formed in the frame. The output stage reads a 16-bit frame slot and puts it directly on the bus as flit 1 — almost zero token formation logic. --- ## SM Internal Data path: 16-bit SM (Structure Memory) operates on 16-bit data words in SRAM. Its internal data path naturally matches this width: - Tokens arrive as 2 flits on the 16-bit bus, deserialized at the SM input FIFO - Operation decoding extracts opcode, address, data from the reassembled 32-bit logical token - SRAM access is 16-bit (one data word per operation) - Result tokens are assembled from the read data + return routing info, then serialized into 2 flits on the output The SM never needs an internal data path wider than 16 bits for data operations. The 32-bit logical token is assembled/disassembled at the FIFO boundaries. --- ## Companion Documents - `pe-design.md` — PE architecture, pipeline stages, frame-based matching, 670 register file design - `pe-pipelining-and-multiplexing.md` — pipeline analysis, stall analysis, matching store alternatives - `iram-and-function-calls.md` — 16-bit instruction encoding, output modes, SM operation mapping, function call primitives - `bus-interconnect-design.md` — physical bus implementation: shared and split AN/CN/DN topologies, node interfaces, arbitration, loopback, backpressure, chip counts - `architecture-overview.md` — module taxonomy, overall system architecture - `network-and-communication.md` — routing topology, clocking discipline - `sm-design.md` — SM opcode table, extended addressing, CAS handling - `alu-and-output-design.md` — ALU operation set - `sram-availability.md` — component availability for period-appropriate SRAMs