EM-4 Architecture Analysis#

Deep-dive reference on the EM-4 (Electrotechnical Laboratory, Japan) and its single-chip processor EMC-R, based on the ISCA '89 and IPPS '91 papers. Captures architectural details for reference even where our design diverges.

Source papers:

• Sakai, Yamaguchi, Hiraki, Kodama, Yuba. "An Architecture of a Dataflow Single Chip Processor." Proc. ISCA '89, pp. 46–53, 1989.
• Sakai, Kodama, Yamaguchi. "Prototype Implementation of a Highly Parallel Dataflow Machine EM-4." Proc. IPPS '91, pp. 278–286, 1991.

See Prior_Art_Reference_Guide_for_a_Discrete-Logic_Dynamic_Dataflow_CPU.md for full bibliography including the network paper (Parallel Computing 1993), synchronisation paper (IEICE 1991), successor chip EMC-Y, and EM-X system papers.

1. Project Context and Design Objectives#

The EM-4 is a successor to SIGMA-1 (128-PE dataflow supercomputer, ETL, operational 1988, >100 MFLOPS). SIGMA-1 PEs were multi-chip (several gate arrays + large memory); direct scaling to 1000+ PEs was impractical due to hardware volume and architectural complexity.

EM-4 design objectives:

1. 1000+ PE machine for general use (numerical, symbolic, simulation)
2. Single-chip PE (the EMC-R) to make scaling feasible
3. O(N) interconnection network (vs O(N log N) for multi-stage networks)
4. Improve dataflow execution efficiency via new computation model

The 80-PE prototype was the first step toward a 1024-PE target. The EMC-R chip was designed with a 1024-PE global address space even though the prototype only used 80 PEs.

2. Identified Defects of Prior Dataflow Architectures#

The EM-4 papers explicitly list six defects of "conventional" (i.e. Manchester-style) dataflow machines. These are worth documenting because several of them drove design choices in our architecture too.

D1. Circular pipeline underutilisation at low parallelism. When fewer tokens are in flight than N×S (N = PEs, S = pipeline stages), the circular pipeline has bubbles. A single token going round the loop achieves throughput < 1 instruction per pipeline circulation time. No advanced control mechanism exists to fill the gap.

D2. Packet-based architecture cannot exploit registers. If every intermediate result becomes a packet and re-enters the PE through the input queue, there is no way to keep frequently-used values in fast local storage. This also prevents fine-grained pipelining within a single computation thread.

D3. High matching overhead (colored token style). Associative memory or hashing for color matching requires complex control logic and significant time per match operation.

D4. Excessive packet traffic. Every inter-node communication is a packet, even between nodes that always execute on the same PE. The network becomes the bottleneck.

D5. No resource management primitives. Mutual exclusion (test-and-set, compare-and-swap) requires serialisation, which is difficult in a pure dataflow model where any node can fire at any time.

D6. Garbage token cleanup overhead. Conditional branches (switches) produce garbage tokens on the not-taken path. Collecting these at program end is expensive.

Relevance to Our Design#

• D1: partially addressed by our monadic bypass (skip matching for single-input ops). Strongly connected blocks (deferred) would address it more completely.
• D2: we currently have no register file. The matching store SRAM serves as temporary operand storage. SM serves as shared scratch. A register file is deferred pending strongly connected block implementation.
• D3: solved — our direct-indexed matching with wire concatenation addressing has zero associative lookup overhead, same as the EM-4's direct matching.
• D4: partially addressed by static PE assignment (compiler places communicating nodes on the same PE to avoid network traffic). Strongly connected blocks would further reduce intra-PE packet overhead.
• D5: SM with RMW operations provides atomic primitives. I-structure semantics (deferred) will add synchronising memory.
• D6: generation counters handle stale token detection. The cancel bit approach (EM-4's C field in the data part) is noted as a potential addition. See open items.

3. Strongly Connected Arc Model#

The EM-4's most significant contribution. Arcs in the dataflow graph are classified into two types:

• Normal arcs: standard dataflow — token matching, packet formation, full pipeline traversal.
• Strongly connected arcs: local to a PE — sequential register-based execution without packet formation or matching.

A strongly connected block is a subgraph whose internal arcs are all strongly connected. The execution rule: once any node in a strongly connected block fires, the entire block executes to completion on that PE, exclusively. No other block can interrupt or interleave with it on that PE during execution.

Hardware Mechanism#

The EMC-R instruction format contains:

• M (mode) field (1 bit): if zero, the current strongly connected block ends with the next instruction.
• NF (next flag) (1 bit): controls continuation within the block.
• R0, R1 (4 bits each): strongly connected register references for the next instruction's operands. These index into a 16-entry register file in the EXU.
• OUT (1 bit): whether this instruction generates an output packet (1) or stores its result in a register (0, with result going to R2).

When executing within a strongly connected block:

1. Pipeline stages 3 (instruction fetch + decode) and stage 4 (execute) repeat in an overlapped loop.
2. Stage 4's execution overlaps with stage 3's fetch of the next instruction in the block.
3. Operands come from the register file (R0, R1) or from the matching store (first instruction only).
4. Results go to the register file (R2) or out as packets.
5. When the block ends (M=0), the last instruction's execution overlaps with stages 1-2 of the next incoming packet.

The register-based pipeline throughput is up to 6x the packet-based circular pipeline throughput.

Performance Example: Fibonacci#

The papers give a concrete comparison on a Fibonacci subgraph:

• Pure dataflow program: 23 clocks for the recursive-call subgraph
• Strongly connected program: 9 clocks for the same computation

The strongly connected version packs type checking, branching, subtraction, and MKPKT operations into a single block that executes sequentially using registers, rather than creating separate tokens for each intermediate.

Implications for Compiler#

The compiler must:

1. Identify valid strongly connected blocks (subgraphs that can execute sequentially without violating data dependencies).
2. Annotate instructions with M, NF, R0, R1, R2, OUT fields.
3. Construct blocks automatically (the papers mention a "block constructor" in their compiler).

This is non-trivial compiler work but is amenable to standard optimisation techniques (instruction scheduling, register allocation within blocks).

Advantages Summarised (from the paper)#

• A1: enables advanced control pipeline (deterministic execution within blocks)
• A2: register file for intra-block operands (no matching needed)
• A3: intra-block matching simplified (no color matching if block is within a single function instance)
• A4: no packet transfers within blocks (reduces network traffic)
• A5: indivisible instruction sequences enable resource management (test-and-set, etc.)
• A6: garbage token cleanup simplified (just reset register file flags)

4. Direct Matching Scheme#

The EM-4's matching mechanism, which is conceptually very close to our design and to Monsoon's Explicit Token Store.

Mechanism#

At function invocation, two memory regions are bound:

• Operand segment: storage for waiting/matching operands. One word per dyadic instruction in the function body.
• Template segment: compiled instruction codes for the function.

The address of an instruction in the template segment has a 1:1 simple correspondence with the matching location in the operand segment. No hashing, no associative lookup.

Matching operation:

1. Read the operand segment at the address corresponding to this instruction.
2. If partner data is present: match succeeds, clear the presence flag, proceed to instruction fetch.
3. If partner data is absent: write incoming data, set presence flag, token consumed.

The read-modify-write is completed in a single clock cycle (read in first half-clock, write/eliminate in second half-clock).

Comparison with Monsoon ETS#

The 1991 paper explicitly compares with Monsoon:

"Although the Explicit Token-Store scheme in the Monsoon Machine also uses the frame-based matching, the direct matching does not need an extra instruction field for data synchronization since a displacement of the matching place is in common with the instruction. This scheme realizes a much more efficient synchronization than Monsoon does and instructions and packets are fairly smaller, at the cost of memory space."

Key difference: EM-4 shares the address between instruction fetch and operand matching (they're at the same offset in their respective segments), so no additional "frame offset" field is needed in the instruction or token. Monsoon needs a separate frame-pointer + slot-offset in each token.

Comparison with Our Design#

Our matching store uses the same principle: SRAM_address = ctx_slot : match_entry, with match_entry derived from the token's addressing fields, giving 1:1 correspondence to instruction addresses.

The key differences:

5. EMC-R Chip Architecture#

Block Diagram (5 functional units + maintenance)#

              ┌──────────────┐
Network In ──►│ Switching    │──► Network Out (port A)
Network In ──►│ Unit (SU)    │──► Network Out (port B)
              └──────┬───────┘
                     │ to local PE
              ┌──────▼───────┐
              │ Input Buffer │
              │ Unit (IBU)   │
              └──────┬───────┘
              ┌──────▼───────┐     ┌──────────┐
              │ Fetch and    │◄───►│ Off-chip  │
              │ Matching     │     │ Memory    │
              │ Unit (FMU)   │◄──┐ │ (≤5 MB)  │
              └──────┬───────┘   │ └──────────┘
              ┌──────▼───────┐   │       ▲
              │ Execution    │   │       │
              │ Unit (EXU)   │───┘  ┌────┴────┐
              └──────┬───────┘     │ Memory  │
                     │             │ Control │
                     ▼             │ Unit    │
              Packet output       └─────────┘
              (back to SU)

Gate Counts and Pin Usage#

Notable: the FMU (matching + sequencing) is only ~3.5K gates — the direct matching scheme keeps it small. The SU (network switch) is ~10K gates because of the three-bank deadlock prevention buffers. The EXU dominates at ~20K gates due to the multiplier, barrel shifter, and 16- register file.

Chip Implementation#

• 1.5 μm CMOS gate array
• Inverter gate delay: 0.7 ns
• Clock: 80 ns (12.5 MHz)
• Peak performance: 12.5 MIPS per PE
• Package: 299-pin ceramic (43 power/ground, 255 signal, 1 unused)
• Fabricated from October 1989; no major bugs found in testing

6. Pipeline Organisation#

Four stages, some with sub-stages. Two pipeline modes that integrate:

Packet-Based Circular Pipeline (thin path)#

The standard dataflow pipeline for tokens arriving from the network:

Stage 1: TNF    Template segment # fetch from off-chip memory
                (bypassed for non-normal packets)

Stage 2: Match  - For matching with immediate: IMF (immediate fetch)
                - For matching with stored data:
                  RD (first half-clock): read matching store
                  EL/WR (second half-clock): eliminate flag if match,
                                              or write data if no match
                - Bypassed for single-operand (monadic) instructions

Stage 3: IF/DC  Instruction fetch (half-clock) + decode (half-clock)

Stage 4: EX     Execution + packet output (overlapped)

Register-Based Advanced Control Pipeline (thick path)#

For strongly connected block execution:

Stage 3 ◄──► Stage 4   (loop: fetch next instruction while executing
                         current instruction)

Stages 3 and 4 repeat until the strongly connected block ends. During this loop, stages 1 and 2 can process the next incoming packet concurrently.

Overlap Properties#

• Stage 4 (execution) overlaps with stage 3 (fetch) of the next instruction in a strongly connected block.
• When a block ends, stage 4 of the last block instruction overlaps with stages 1-2 of the next packet.
• The SU operates independently and concurrently with all PE stages.

Throughput#

• Packet-based circular pipeline: 1 instruction per 4 clocks (at best, with full pipeline)
• Register-based advanced control: 1 instruction per clock (within a strongly connected block)
• Ratio: up to 6× throughput improvement for strongly connected blocks (4 stages × pipeline effects, empirical)

7. Instruction Set Architecture#

RISC Characteristics#

• 26 instructions
• 4 instruction formats (2 base + 2 immediate variants)
• 2 memory addressing modes
• 16-entry register file
• No microcode
• Fixed packet size
• Few packet types
• Simple synchronisation (direct matching + register sequencing)

Instruction Set (26 instructions)#

Arithmetic and Logic (14): ADD, SUB, MUL, DIV0-2, DIVR, DIVQ (division pipeline), SHF (shift), AND, OR, EOR, NOT, ALUTST

Branch (6): BEQ (equal), BGT (greater), BGE (greater/equal), BTYPE (by data type), BTYPE2 (by 2 data types), BOVF (overflow). All implemented as delayed branches.

Memory or Register (4): L (load), S (store), LS (load-and-store), LDR (load from register)

Others (2): GET (remote operation — sends return address to operand destination), MKPKT (make packet — explicit packet construction from two operands)

Instruction Format#

38-bit instruction word (stored in off-chip memory).

Without packet output (OUT=0):

| OP | AUX | TRC | M | NF | R0 | R1 | OUT | R2 | BC | DPL |
|  5 |  7  |  1  | 1 |  1 |  4 |  4 |  1  |  4 |  2 |  8  |

With packet output (OUT=1):

| OP | AUX | TRC | M | NF | R0 | R1 | OUT | WCF | M2 | CA | DPL |
|  5 |  7  |  1  | 1 |  1 |  4 |  4 |  1  |  2  |  1 |  3 |  8  |

Field descriptions:

• OP (5 bits): opcode (26 instructions)
• AUX (7 bits): secondary opcode field (e.g. shift direction/amount)
• TRC (1 bit): trace control
• M (1 bit): mode — 0 = strongly connected block ends after next instruction
• NF (1 bit): next instruction flag (continuation within block)
• R0, R1 (4 bits each): register file addresses for operands
• OUT (1 bit): generate output packet (1) or store in register (0)
• R2 (4 bits): destination register (when OUT=0)
• BC (2 bits): branch condition (when OUT=0, branch instructions only)
• DPL (8 bits): displacement (branch target or packet address offset)
• WCF (2 bits): waiting condition flag for output packet matching type
• M2 (1 bit): output packet arc type (normal vs strongly connected)
• CA (3 bits): column address within PE group

Packet Format#

78 bits total: 39-bit address part + 39-bit data part (fixed size).

Address part (39 bits):

| HST | PT | WCF | M | GA  | CA | MA  |
|  1  |  5 |  2  | 1 |  7  |  3 | 20  |

• HST (1 bit): bound for host (vs normal destination)
• PT (5 bits): packet type
• WCF (2 bits): waiting condition flag (matching type)
• M (1 bit): arc type (normal=0, strongly connected=1)
• GA (7 bits): destination PE group address (supports 128 groups)
• CA (3 bits): column/member address within group (supports 8 per group; prototype uses 5 per group)
• MA (20 bits): memory address (matching address for normal data packets)

Data part (39 bits):

| C | * | DT | D  |
| 1 | 3 |  3 | 32 |

• C (1 bit): cancel bit (packet is nonsense/garbage — discard on arrival)
• * (3 bits): reserved
• DT (3 bits): data type tag
• D (32 bits): data value

Special Packets#

Non-data packets (function control, structure access, remote memory access) have special PT (packet type) values and are "colorless" (no operand segment number). Generated by MKPKT or GET instructions. Processed by a per-PE SP Monitor — a special strongly connected block that the system manager configures at initialisation. This makes special packet handling completely programmable.

Macro Instructions#

Complex operations (integer division, function call, complex structure ops) are implemented as strongly connected blocks containing simpler instructions, rather than as single complex instructions. The division pipeline (DIV0, DIV1, DIV2, DIVR, DIVQ) is a good example: five simple instructions that chain via registers to implement non-restoring division.

8. Interconnection Network#

Processor Connected Omega Network#

Topology: each PE contains a 3×3 packet switch (the SU) as an element of the network. PEs are directly interconnected; there are no separate switching nodes.

Properties:

• Average distance from any PE to any other: O(log N)
• Connection links per PE: small constant (3 input, 3 output in the SU)
• Total switching elements: O(N) — smaller than O(N log N) for multi- stage omega networks
• Routing is self-routing based on destination address

Deadlock Prevention#

Store-and-forward deadlock is prevented by a three-bank buffer at each SU input port. Packets entering the network start in the lowest bank. When a packet reaches stage 0 of the network (one hop), it is promoted to the next bank level. Because the circular omega topology guarantees no packet ever needs more than two rounds through the network, three bank levels prevent circular buffer dependencies.

Load Balancing#

The SU contains a Packet Rewriting Controller (PRC) that implements function-level dynamic load balancing. Special MLPE (Minimum Load PE) packets circulate through the network. The PRC in each SU rewrites these packets so they always contain the address and load of the least-loaded PE encountered so far. PEs preparing to make function calls read MLPE packets from a local FIFO to determine where to place new function instances.

This is done within normal packet transfer time (no overhead) using the PRC, which operates in parallel with normal routing.

Prototype Network Implementation#

• Intra-group (5 PEs per group): traces on the PE group board
• Inter-group (same rack half): mother board connections
• Inter-rack-half: shielded cables
• Each network path: 44 signal lines (5 control + 39 data)
• Transfer rate: 60.9 MB/s per port; 14.63 GB/s total
• Transfer delay: 80 ns between adjacent nodes; ~410 ns average

9. EM-4 Prototype Details#

Organisation#

• 80 PEs in 16 groups of 5 (group size determined by omega network topology)
• Each PE: EMC-R + Memory Address Register (MAR) + off-chip SRAM
• Off-chip memory per PE: 1.31 MB SRAM (max 5.25 MB)
• Host computer: SUN3/260 + VME bus
• Packet interface processor: controls system clock, power, packet I/O
• Packet interface switch: connects host to PE groups

Physical Implementation#

• Single rack: 60.0 cm × 92.0 cm × 140.5 cm
• 16 PE group boards (4-layer multi-wire, 50.8 cm × 47.0 cm each)
• 8 boards in upper rack, 8 in lower rack + interface switch
• Single synchronisation clock: 12.5 MHz
• Power: 3-phase 200V supply; ~2.6 KW total (PEs ~2.42 KW)

Memory Organisation (per PE)#

The off-chip memory is a unified address space partitioned into:

• Secondary packet buffer (overflow from 32-word on-chip FIFO)
• Matching store (operand segments)
• Instruction store (template segments)
• SP Monitor area
• Structure store
• Working area

All accessible from the EXU as a single address space via the MCU.

Program Execution Flow#

1. Initialisation: host + maintenance circuits reset system, set PE numbers, configure memory segment linkages, load monitor routines.
2. Program loading: assembled code sent via packets using "broadcasting" — each PE loads function codes into its memory and forwards to uninitialised PEs.
3. Execution start: host sends input packets to appropriate matching addresses via the packet interface processor.
4. Execution: function instances invoke other functions. Results flow back to parent functions or to the packet interface.
5. Termination: resultant packets sent to packet interface processor.

Performance Results (80 PEs)#

Note: EM-4 programs were in assembly language; comparison programs were compiled C (SPARC, VAX) or FORTRAN (CRAY) with maximum optimisation.

The CRAY/X-MP outperforms the EM-4 only on matrix multiplication, where the CRAY's vector pipeline dominates (2-3 instructions per inner loop vs EM-4's 12). The EM-4 is 6-21× faster on everything else.

PI calculation achieves the highest MIPS (824, vs 1000 theoretical peak) because all operations can be statically scheduled with local-only communication. Fibonacci achieves the lowest (223) due to heavy packet traffic causing IBU FIFO overflow.

10. Analysis: Relevance to Our Architecture#

Validated Design Choices#

1. Direct matching with ordinary SRAM. The EM-4 confirms this works in real hardware. Their FMU is only ~3.5K gates with direct matching. Our matching store should be similarly simple.

2. Static PE assignment reduces matching hardware. Though the EM-4 still does dynamic function-to-group allocation, their acknowledgment that compiler-directed allocation reduces matching overhead supports our more aggressive static assignment approach.

3. RISC instruction philosophy. 26 instructions, no microcode, simple formats. Validates our EEPROM-decoded instruction approach.

4. Single-cycle matching via half-clock read-modify-write. The EM-4 achieves this in their 80 ns clock. We should be able to do the same with modern async SRAM (~15-25 ns access) within our target clock period.

Features We Should Adopt or Plan For#

1. Instruction format continuation bit. Reserve 1 bit in the instruction encoding for "next instruction follows sequentially" (EM-4's NF flag). Even without strongly connected block execution in v0, this preserves the option. Zero hardware cost — it's just an IRAM bit that the v0 pipeline ignores.

2. Cancel bit in token format. The EM-4's C bit in the data part marks garbage tokens for discard. Consider adding this to our token format (1 bit in flit 2 or flit 3) to handle not-taken branch cleanup without relying solely on generation counters. Generation counters catch stale matches; the cancel bit catches tokens still in flight.

3. IBU overflow to off-chip SRAM. The EM-4's two-level buffering (32-word on-chip FIFO + 8K-word off-chip SRAM) is pragmatic. We need an explicit overflow/backpressure strategy for PE input FIFOs.

4. SP Monitor concept. Special packet handling as a programmable strongly connected block rather than fixed-function hardware. Interesting for our I/O and system packet handling — rather than a fixed I/O controller state machine, a configurable handler built from normal instructions.

Features Evaluated and Deferred#

1. Strongly connected blocks. The performance benefit is clear (up to 6× throughput within blocks, 2.5× on Fibonacci subgraph). The hardware cost is moderate (16-register file + sequencing logic). But it requires significant compiler infrastructure (block identification, register allocation within blocks). Deferred to post-v0. The instruction format should reserve the continuation bit to enable future implementation.

2. PE-embedded network switch. The EMC-R's SU (~10K gates) operates independently alongside the PE. Relevant only if we move from shared bus to point-to-point topology. Not applicable to v0 shared-bus design.

3. Dynamic load balancing (MLPE). Makes sense at 80-1000 PEs, not at 4. Static compiler assignment is sufficient for our scale.

4. 16-register file. Closely tied to strongly connected blocks. The EM-4 uses it for intra-block operand passing (R0, R1, R2 fields). Without strongly connected execution, there's no register file traffic pattern. The matching store SRAM and SM handle all operand staging for v0. If/when strongly connected blocks are added, a small register file (using SRAM with dedicated address lines, or a 74670- style register file chip) should be added simultaneously.

Features Not Applicable#

1. Processor connected omega network. O(N) hardware, O(log N) distance. Irrelevant for a 4-PE shared bus. Worth revisiting if scaling to 16+ PEs.

2. Template segment number fetch (pipeline stage 1). The EM-4 needs this because operand segments are dynamically bound to template segments at function invocation. Our static PE assignment with compiler-fixed IRAM contents eliminates this stage entirely, saving one pipeline stage.

3. 78-bit fixed-size packets. Our variable-length multi-flit tokens on a 16-bit bus are better suited to discrete logic where wide buses are physically expensive. The EM-4 could use fixed-size packets because everything was on-chip or on a custom bus.

4. Macro instructions via strongly connected blocks. Complex operations (division, function call) are decomposed into simple instruction sequences within strongly connected blocks. Without strongly connected execution in v0, we handle complex operations differently (multi-token graph fragments or SM operations).

11. Open Items Arising from EM-4 Analysis#

1. Cancel bit in token format: evaluate adding 1 bit to type-00/01 tokens for garbage token discard. Requires: format change in flit 2, discard logic in PE input (check cancel bit before entering matching pipeline). Low hardware cost, potentially useful for conditional branch cleanup.

2. IBU overflow strategy: decide between backpressure (stall the bus — simple but blocks all traffic) vs local overflow SRAM (more hardware but non-blocking). For v0 shared bus at 4 PEs, backpressure may be acceptable.

3. I-structure semantics in SM: confirmed as wanted. The EM-4 puts structure storage in per-PE off-chip memory; we're keeping it in a dedicated SM module with synchronising memory semantics. Design the deferred-read queue.

4. Instruction format bit reservation: when finalising IRAM encoding, reserve 1 bit for continuation flag (NF equivalent) and 1 bit for output-mode flag (OUT equivalent). These cost nothing in v0 (pipeline ignores them) and enable strongly connected blocks later.

5. Strongly connected block feasibility study: before implementing, compile some representative programs (fibonacci, simple parallel computations) and measure what percentage of instructions could be placed in strongly connected blocks. This determines the practical performance benefit and justifies (or not) the compiler complexity.