xh1-research-fork/research/.xh1/responses/20260825T180300Z_mul-div-unit.md

# MUL/DIV Unit

## Status

DRAFT — initial research document. No architectural decision has been made for XH-1.

## Abstract

This document investigates the design of the multiplication and division unit (MUL/DIV) for a single core inside the XH-1 128-core RISC-V processor. It surveys existing approaches for integer multiplication and division, identifies alternative implementations, and analyzes trade-offs in performance, area, power, latency, verification complexity, and scalability across 128 cores. The document focuses on the base integer extensions (RV64I/M) and explicitly defers floating-point and vector multiply/accumulate topics, which belong to separate units.

## Research Question

What is the most appropriate microarchitectural implementation of the MUL/DIV unit for a single XH-1 core, given that 128 identical cores will be instantiated on die, and given that the MUL/DIV unit must implement at minimum RV64M (MUL, MULH, MULHU, MULHSU, DIV, DIVU, REM, REMU)?

Sub-questions:

- Should multiplication be iterative (shift-and-add) or fully combinational (array/Wallace/Booth)?
- Should division use a restoring, non-restoring, SRT, or Newton–Raphson scheme?
- Should the unit be pipelined, multi-cycle, or variable-latency?
- How does the MUL/DIV unit interact with the surrounding pipeline (depth, bypass, in-order vs out-of-order issue)?
- How does the unit scale when replicated 128 times on die?
- Should fused MAC operations (MUL + ADD) or fused multiply-add be considered?

## Background

The RISC-V "M" extension specifies eight integer multiply/divide instructions (MUL, MULH, MULHSU, MULHU, DIV, DIVU, REM, REMU) on 64-bit values producing either 64-bit or 128-bit results. Division is defined to round toward zero and is required to complete even for overflow cases (e.g., `INT64_MIN / -1`), as specified in the RISC-V Unprivileged ISA.

Key properties of the workload that influence the design:

- **Result width asymmetry.** MUL produces a 128-bit result, but only the low 64 bits are written to `rd` for `MUL`. MULH-family instructions write the high 64 bits. The datapath therefore needs at least a 64×64→128 multiplier followed by a selector.
- **Sign handling.** Three signed/unsigned combinations (signed×signed, signed×unsigned, unsigned×unsigned) must be supported. Sign correction is required for MULH/MULHSU.
- **Division latency and throughput.** RISC-V does not require division to retire in a single cycle, but the ISA mandates deterministic behavior for overflow.
- **Rarity in many workloads.** Empirical studies (e.g., Hennessy & Patterson, *Computer Architecture: A Quantitative Approach*) report that integer divide and remainder instructions are uncommon (typically <1% of dynamic instructions), while multiplies are more frequent in HPC and crypto workloads.

For XH-1, the unit sits on the execution path of every core. With 128 cores, area and per-core energy dominate; raw single-thread latency of division matters less than aggregate throughput, die-area cost, and ease of verification.

## Existing Approaches

### Multiplication

1. **Iterative shift-and-add multiplier**
   - One 64-bit adder reused across 64 cycles.
   - Smallest area, lowest energy per multiplication, but very long latency.

2. **Array multiplier (combinational)**
   - 64×64 array of full adders producing a 128-bit result.
   - Single-cycle result, large area, high fan-out, and a long critical path.
   - Historically too slow for one cycle at high clock frequencies.

3. **Wallace / Dadda tree**
   - Tree of carry-save adders reducing partial products to two 128-bit vectors, then a final carry-propagate adder.
   - Logarithmic depth; commonly used in high-performance cores.
   - Larger area than array, but shorter critical path.

4. **Booth-encoded Wallace / Dadda**
   - Radix-4 or higher Booth recoding reduces the number of partial products by ~2×.
   - Common in modern cores (e.g., reported in implementations of ARM and x86 multipliers).

5. **Pipelined iterative multiplier**
   - Splits the 64-cycle iterative multiplier into pipeline stages (commonly 2–4 stages).
   - Used in many in-order RISC-V cores (e.g., the Rocket Chip generator's `MulDiv`).

6. **Dedicated single-cycle fused multiply-add (FMA) for integers**
   - Rare for integer-only M-extensions; usually belongs to the F/D extensions.

### Division

1. **Restoring division**
   - Classical shift-subtract. One bit per cycle, 64 cycles for 64-bit operands.
   - Simple, easy to verify.

2. **Non-restoring division**
   - Similar latency, but allows a single add/subtract per bit without explicit restore.
   - Used in many textbook implementations.

3. **SRT division**
   - Radix-4 or higher; produces 2+ bits per cycle using a small redundant quotient-digit table.
   - Significantly faster (16–32 cycles for 64-bit) at higher area cost.
   - Common in high-performance OoO cores (e.g., POWER, Itanium, recent x86).

4. **Newton–Raphson reciprocal + multiply**
   - Iteratively refines an approximation of 1/d, then multiplies.
   - Very high throughput once the reciprocal is available.
   - Worst-case latency is higher than SRT; best for repeated divisions by the same divisor.
   - Rare in integer pipelines due to initial latency.

5. **Goldschmidt division**
   - Similar to Newton–Raphson; iteratively scales numerator and denominator toward 1.
   - Same usage profile as Newton–Raphson.

6. **Lookup-table based constant dividers**
   - For known small constant divisors, the compiler/runtime can replace DIV with a multiply-by-reciprocal.
   - Microarchitectural implication: the DIV unit need not be heavily optimized if software frequently replaces division by constants.

## Alternative Designs

For the XH-1 MUL/DIV unit, four credible microarchitectural templates are considered.

### Design A: Shared iterative multi-cycle unit (Rocket-style)

- One 64-bit datapath reused for both MUL and DIV.
- MUL: 1 cycle/partial product (radix-2 Booth optional).
- DIV: 1 bit/cycle, restoring or non-restoring.
- MUL latency: ~33–35 cycles (radix-2 Booth) or ~64 cycles (plain shift-add).
- DIV latency: ~64 cycles.
- Throughput: 1 MUL or DIV per ~32 cycles (shared); MUL and DIV cannot execute concurrently.
- Plausible canonical reference: the `MulDiv` module in the BOOM/Rocket Chip generator (UC Berkeley).

### Design B: Pipelined iterative multiplier + iterative divider

- Multiplier: 2–4 stage pipelined radix-2/radix-4 iterative unit.
- Divider: separate 64-bit iterative datapath (non-restoring or SRT-radix-2).
- MUL throughput: 1 per cycle once pipeline is full.
- DIV throughput: 1 per ~32 cycles.
- Independent issue of MUL and DIV is possible.

### Design C: Pipelined Wallace/Booth multiplier + SRT-radix-4 divider

- Multiplier: 3-stage pipelined radix-4 Booth → Wallace tree → CPA. Produces full 128-bit result.
- Divider: radix-4 SRT producing 2 bits/cycle; ~17 cycles for 64-bit DIV.
- DIV/REM can be produced simultaneously since quotient digits are known.
- Area: significantly larger than Designs A and B.
- Latency: MUL ~3–4 cycles, DIV ~17–20 cycles.
- Used in many modern superscalar cores.

### Design F: Fused integer MAC / FMA

- Add an integer fused multiply-add returning low 64 bits (a*b)+c in one operation.
- This is non-standard for RV64M and would require custom opcodes or being staged behind a regular MUL+ADD sequence.
- Documented here for completeness, not recommended without strong workload evidence.

## Comparison

| Property | A: Iterative shared | B: Pipelined iterative MUL + iterative DIV | C: Wallace/Booth MUL + SRT-4 DIV |
|---|---|---|---|
| MUL latency | ~33–64 cycles | 3–5 cycles | 3–4 cycles |
| MUL throughput | 1 / 32 cycles | 1 / cycle | 1 / cycle |
| DIV latency | ~64 cycles | ~32 cycles | ~16–20 cycles |
| DIV throughput | 1 / 64 cycles | 1 / 32 cycles | 1 / 16 cycles |
| 64×64→128 datapath | Yes (shared) | Yes (MUL only) | Yes (Wallace) |
| MUL+DIV concurrency | No (shared) | Yes (separate datapaths) | Yes (separate datapaths) |
| Estimated relative area | 1.0× | ~1.5–2.0× | ~3.0–5.0× |
| Estimated critical path | Short | Short | Longest (CPA final stage) |
| Verification complexity | Low | Medium | High |
| Fits "small in-order" model | Excellent | Good | Marginal |

ASSUMPTION: Area estimates above are rough order-of-magnitude relative numbers based on typical RISC-V implementations and the cited textbooks. They have not been measured for XH-1.

## Advantages

### Design A (iterative shared)

- Smallest area per core, which directly reduces die cost across 128 cores.
- Lowest per-core dynamic energy for the rare case of an actual MUL/DIV.
- Easiest to verify formally (small state space, one datapath).
- Matches the "many small cores" scaling philosophy.
- Canonical reference: Rocket Chip `MulDiv`.

### Design B (pipelined iterative MUL + iterative DIV)

- MUL throughput is high enough to support HPC and crypto workloads where 64-bit multiplies are common.
- DIV remains simple.
- Area increase over A is bounded.
- Two independent datapaths simplify scheduling in the issue stage.

### Design C (Wallace/Booth + SRT-4)

- Best raw latency and throughput for both operations.
- Suitable for single-core-bound workloads or for cores that need to hide memory latency behind fast arithmetic.
- DIV+REM can be produced together with little extra hardware.

## Disadvantages

### Design A

- DIV latency of 64 cycles is long; if the surrounding pipeline is short (e.g., 5–7 stages), the unit will dominate total execution time for any divide.
- Back-to-back MULs serialize.
- Under HPC or cryptography kernels, MUL throughput becomes a bottleneck.

### Design B

- More area than A.
- Pipelined MUL increases register pressure in the issue queue and requires more bypass paths in the surrounding execution stage.
- DIV still slow.

### Design C

- Largest area per core, replicated 128 times.
- Highest per-core power.
- Wallace tree and SRT have long critical paths that may limit clock frequency for the whole core.
- Verification complexity is significantly higher: partial-product reduction, Booth recoding, SRT quotient-digit selection tables, and divider corner cases (e.g., `INT64_MIN / -1`) all need separate coverage.
- Wall-clock design and verification cost may delay the whole project.

## XH-1 Considerations

PROPOSAL: For XH-1, an in-order core with 128 instances on die, the dominant design constraint is **per-core area, energy, and verification cost**, not single-thread peak performance. The MUL/DIV unit should therefore favor small, simple, well-trodden implementations.

Specific implications for XH-1:

- The 128-core factor means the MUL/DIV unit's area is multiplied by 128. Even a 2× area difference per core translates to a substantial absolute area delta.
- The energy of 128 MUL/DIV datapaths, even at low utilization, contributes to total socket power.
- A long-latency MUL/DIV unit is acceptable if the surrounding pipeline is deep enough or if it can be overlapped with other in-flight instructions in the same core.
- Single-cycle MUL would impose a critical path on the whole core; for a 128-core design, sustained high clock frequency across all cores is critical to total throughput.

## 128-Core Scalability

Scalability dimensions to consider:

- **Wiring and layout.** A 128-core die has a complex interconnect. A small MUL/DIV unit is easier to place and route within each core tile. Designs with large irregular adder trees (Wallace/SRT) complicate physical design at high core counts.
- **Verification replication.** Bugs in the MUL/DIV unit, if present, propagate to 128 cores. A simpler, formally verifiable design (Design A) is safer for replication.
- **Yield.** Smaller per-core area improves yield and binning flexibility; large per-core area reduces the number of cores that fit on a reticle at the target process node.
- **Power delivery.** 128 simultaneous MUL/DIV operations are unlikely, but worst-case power events (e.g., SIMD-style vector MUL workloads scaled down to integer MUL) must be within the socket's power-delivery budget.
- **Frequency scaling.** A 128-core chip with modest per-core frequency but high aggregate throughput may benefit from a short critical path. A Wallace multiplier's critical path can limit fmax for the whole core.

## Performance Considerations

- MUL/DIV instructions are infrequent in general-purpose workloads (often <1% dynamic instructions) but can dominate kernels in cryptography (AES, ChaCha20, RSA), big-integer arithmetic (GMP-style libraries), and some HPC kernels.
- If XH-1 is intended for general-purpose server or desktop use, the MUL/DIV unit will rarely be on the critical path of a thread.
- If XH-1 targets HPC or cryptography, the MUL throughput becomes important. In this case, B or C should be reconsidered.
- Software can use compiler transformations to replace DIV by constants with multiply-by-reciprocal, reducing pressure on the DIV unit.

## Implementation Considerations

- **Sign handling.** The unit must correctly handle `MULH`, `MULHSU`, and `MULHU` as well as overflow cases of DIV (notably `INT64_MIN / -1`, which must produce `INT64_MIN` per RISC-V spec).
- **REM vs DIV.** Producing REM in parallel with DIV using the same datapath is standard in restoring/non-restoring designs; the unit should support issuing DIVU/REMU pairs in one operation.
- **Pipeline interface.** The unit must integrate with the core's issue, wakeup, and writeback stages. If in-order, the issue stage must stall in-order cores on multi-cycle MUL/DIV. If OoO, completion must wait for the unit's completion signal.
- **Bypassing.** Forwarding paths from the MUL/DIV pipeline registers to dependent instructions must be designed carefully to avoid structural hazards.
- **Early termination.** For DIV, the unit can terminate early when the remainder is zero, saving cycles. Implementation cost is low.

## Verification Considerations

- **Corner cases.** RV64M has well-defined corner cases: `INT64_MIN / -1`, division by zero, overflow in REM, sign interactions in MULH-family.
- **Directed + constrained-random.** A combination of directed tests for ISA corner cases and constrained-random for the rest is standard practice (e.g., as in the RISC-V architectural test framework, riscv-tests).
- **Formal verification.** A small iterative multiplier/divider (Design A) is amenable to formal proofs of correctness for a few-bit case and inductive scaling. A Wallace + SRT unit (Design C) is significantly harder to formally verify due to selector-table complexity.
- **Cross-core equivalence.** With 128 identical cores, regression in one core implies regression in all 128. A well-verified single-core design simplifies the chip-level verification effort.
- **Testbench reuse.** The RISC-V community maintains architectural compliance tests that should be run against the MUL/DIV unit regardless of the chosen design.

## Recommendation

PROPOSAL: Adopt a **Design B–leaning approach**: a small, simple, well-understood MUL/DIV unit similar in spirit to Rocket Chip's `MulDiv`, with the following characteristics:

- A **radix-4 Booth-encoded iterative multiplier** (or radix-2 if radix-4 proves too complex for the area budget) producing 64 bits of result per ~16 cycles, sharing partial datapath with the divider if needed.
- A **non-restoring (or radix-2 SRT) divider** completing in ~32 cycles.
- MUL and DIV on the same datapath with **shared state** but capable of being interleaved at issue time.
- Optional microarchitectural relaxation: a separate tiny **fast-MUL path for 32×32→64 results** (the low half of MUL where both operands are sign- or zero-extended from 32 bits) to accelerate common cases. This adds minimal area.

This recommendation is provisional and is the lightest-weight option that still keeps MUL throughput reasonable. It avoids the critical-path cost of Design C and the throughput limit of Design A, while remaining well within the verification budget of a 128-core project.

RECOMMENDATION: If workload analysis (not yet performed) shows MUL-heavy HPC/cryptography use, escalate to a pipelined radix-4 Booth multiplier with a 2–3 cycle latency, keeping the iterative divider. If workload analysis shows almost no MUL/DIV usage, drop to a plain Design A.

## Confidence

- **Low–Medium** for any specific microarchitectural recommendation. The document is at an early stage; the recommendation will be revised after:
  1. Workload analysis (target use cases of XH-1).
  2. Synthesis of representative MUL/DIV units in the target technology.
  3. Frequency, area, and power target constraints.
- **High** that the iterative, shared-datapath approach (Design A or B) is the appropriate starting point for a 128-core, area-constrained, verification-constrained design.

## Open Questions

- What is the target frequency of XH-1 cores, and what is the critical-path budget for the MUL/DIV unit?
- What process node is targeted, and what is the per-core area budget?
- What is the intended workload mix (server, HPC, embedded, ML)?
- Is the core in-order or out-of-order? The MUL/DIV interface and latency tolerance depend strongly on this.
- Will the F extension (floating-point) be present in the same core, and if so, should integer MUL be reused inside an FMA datapath?
- Will the V extension (vector) be present? If so, scalar integer MUL may be lightly used and the scalar MUL/DIV unit can be minimal.
- Are fused integer MAC operations required by any target workload?
- What level of formal verification is mandated for XH-1?

## Sources

Primary and authoritative references used or cited in this document:

- RISC-V International, *The RISC-V Instruction Set Manual, Volume I: Unprivileged Architecture* — official definition of RV64M (MUL, MULH, MULHSU, MULHU, DIV, DIVU, REM, REMU) and division overflow semantics.
- RISC-V International, *Architectural Compatibility Test Suite* (riscv-tests, riscv-arch-test) — official compliance test references.
- UC Berkeley Architecture Research, *Rocket Chip Generator* documentation — reference for the small iterative `MulDiv` module.
- UC Berkeley Architecture Research, *BOOM Out-of-Order Processor* documentation — reference for SRT-class dividers and pipelined multipliers in BOOM v2/v3.
- Hennessy & Patterson, *Computer Architecture: A Quantitative Approach* (recent editions) — workload frequency of MUL/DIV, energy/area considerations.
- Ercegovac & Lang, *Digital Arithmetic* — comprehensive treatment of shift-add, Booth, Wallace, SRT, and Newton–Raphson dividers.
- Parhami, *Computer Arithmetic: Algorithms and Hardware Designs* — additional reference for multiplier and divider architectures.

ASSUMPTION: Specific page numbers and edition identifiers for Hennessy & Patterson, Ercegovac & Lang, and Parhami have not been quoted above because the exact editions in the XH-1 research library have not been recorded in this document. They should be cited precisely when this document is finalized.

INSUFFICIENT EVIDENCE: No synthesis, layout, or PPA data for the target process node is yet available for any of the four design candidates. The relative area and energy figures are qualitative estimates only.