bit_accelerator/docs/DATAPATH.md

# Bit-Accelerator Datapath Architecture

## 1. High-Level Datapath Diagram

```
┌─────────────────────────────────────────────────────────────────────┐
│                     BIT ACCELERATOR DATAPATH                         │
└─────────────────────────────────────────────────────────────────────┘

Stage 0: DECODE & OPERAND FETCH
┌──────────────┐
│   Opcode     │──────────► Opcode Decoder (6-to-12 decoder)
│   Operands   │──────────► Register File (3R1W)
│              │
└──────────────┘
     │
     ▼
Stage 1: ADDRESS GENERATION
┌──────────────────────────────────────────┐
│  Adder (Rs1 + Rs2)  ◄─── 64-bit Carry    │
│  eff_bit_address = base + offset         │
│                                          │
│  Output: 64-bit effective bit address    │
└──────────────────────────────────────────┘
     │
     ▼
Stage 2: WORD & BIT INDEX CALCULATION
┌──────────────────────────────────────┐
│  Divider / Shifter (÷64 & mod 64)    │
│  word_index = eff_addr >> 6          │  Combinational or pipelined
│  bit_index  = eff_addr & 0x3F        │
│                                      │
│  Output: (word_index[57:0], bit_idx) │
└──────────────────────────────────────┘
     │
     ▼
Stage 3: MEMORY ACCESS & TLB LOOKUP
┌──────────────────────────────────────────┐
│  TLB Lookup (word_index → phys_address)  │
│  L1 Cache Tag/Index Match                │
│  Memory Request to Load/Store Queue      │
│                                          │
│  Output: 64-bit word from L1/L2/Memory   │
└──────────────────────────────────────────┘
     │
     ▼
Stage 4: BIT EXTRACTION
┌──────────────────────────────────────┐
│  Barrel Shifter                      │
│  (word >> bit_index)                 │
│                                      │
│  AND Gate (extract LSB)              │
│  result = shifted_word & 1           │
│                                      │
│  Output: 1-bit result                │
└──────────────────────────────────────┘
     │
     ▼
Stage 5: WRITEBACK
┌──────────────────────────────────────┐
│  Register File Write                 │
│  result ──► Rd                       │
└──────────────────────────────────────┘
```

---

## 2. Component Specifications

### 2.1 Address Generator (Stage 1)

**Component**: 64-bit Ripple-Carry Adder or Kogge-Stone Parallel-Prefix Adder

**Inputs**:
- `base_address[63:0]` from Rs1 register
- `bit_offset[63:0]` from Rs2 register
- `carry_in` = 0

**Outputs**:
- `effective_bit_address[63:0]`

**Latency**: 1 cycle (Kogge-Stone) or 2 cycles (simpler adder)

**Control Signals**:
- `enable_add`: 1 if instruction requires address computation
- `select_operand`: 0 = Rs1+Rs2, 1 = Rs3+Rs4 (for multi-register ops)

---

### 2.2 Word and Bit Index Calculator (Stage 2)

**Component**: Fixed-Point Divider (÷ 64) and Modulo-64 Unit

**Inputs**:
- `effective_bit_address[63:0]` from Address Generator

**Outputs**:
- `word_index[57:0]` = `effective_bit_address >> 6`
- `bit_index[5:0]` = `effective_bit_address[5:0]`

**Hardware Implementation**:
```
word_index[i] = effective_bit_address[i+6], for i = 0 to 57
bit_index[i]  = effective_bit_address[i],   for i = 0 to 5
```
(This is purely combinational wiring - no logic!)

**Latency**: 0 cycles (combinational)

---

### 2.3 TLB & Cache Lookup (Stage 3)

**Component**: TLB (Translation Lookaside Buffer) + L1 Cache Controller

**Inputs**:
- `word_index[57:0]` (virtual word address, 6-bit aligned = 6 bits from effective address)
- Control: `is_load`, `is_store`

**Outputs**:
- `cache_hit` (1-bit flag)
- `data_word[63:0]` (from L1 cache on hit)
- `phys_address[40:0]` (for miss → L2/Memory)

**Behavior**:

**On Hit** (L1 cache, TLB translate):
- Return data directly from cache (fastest path)
- Latency: 1 cycle

**On Miss** (TLB or L1 cache miss):
- Initiate memory request to L2
- Stall pipeline until data returns
- Latency: variable (10+ cycles to L2, 50+ to main memory)

**Special Case: Page Boundary**:
- If `bit_address` and `(bit_address + 63)` span different pages:
  - Hardware may need two memory accesses
  - OR: Load both words and merge results (dual-load architecture)

---

### 2.4 Barrel Shifter (Stage 4)

**Component**: 64-bit Logarithmic Shifter

**Inputs**:
- `word[63:0]` from memory/cache
- `bit_index[5:0]` from Index Calculator
- `shift_direction` (0=right, 1=left, from decoder)
- `rotate_mode` (0=shift, 1=rotate)

**Implementation** (Rotating 64-bit barrel shifter):
```
Level 0: Shift by 32: word[i] ← (shift_by_32 ? word[(i+32)%64] : word[i])
Level 1: Shift by 16: word[i] ← (shift_by_16 ? word[(i+16)%64] : word[i])
Level 2: Shift by  8: word[i] ← (shift_by_8  ? word[(i+8)%64]  : word[i])
Level 3: Shift by  4: word[i] ← (shift_by_4  ? word[(i+4)%64]  : word[i])
Level 4: Shift by  2: word[i] ← (shift_by_2  ? word[(i+2)%64]  : word[i])
Level 5: Shift by  1: word[i] ← (shift_by_1  ? word[(i+1)%64]  : word[i])

bit_index[5:0] is decoded into 6 control signals: {shift_by_32, ..., shift_by_1}
```

**Outputs**:
- `shifted_word[63:0]`

**Latency**: 1 cycle (combinational through 6 levels of muxes)

---

### 2.5 Bit Extractor (Stage 4, after shifter)

**Component**: AND gate + optional sign-extension logic

**Inputs**:
- `shifted_word[63:0]` from Barrel Shifter
- `mask[63:0]` (computed from field width)
  - Single bit: `mask = 64'h0000_0000_0000_0001`
  - Multi-bit (width w): `mask = (1 << w) - 1`

**Outputs**:
- `extracted_field[63:0]` = `shifted_word & mask`

**For BITLOAD** (single-bit extract):
- Output: `result[63:0]` with `result[0] = extracted_field[0]`, `result[63:1] = 0`

**For BITFIELD** (multi-bit extract):
- Output: `result[63:0]` = extracted field, zero-extended

**Latency**: 1 cycle (combinational AND + logic)

---

### 2.6 Control Unit (Combinational + Sequential)

**Combinational Decoder**:
```
Opcode[5:0] → 12 control signals:
  - enable_addr_gen
  - enable_mem_load
  - enable_mem_store
  - enable_shift
  - enable_extract
  - enable_writeback
  - shift_direction (L/R)
  - rotate_mode
  - field_width[5:0]
  - is_signed_extend
```

**Sequential State Machine** (for cache misses, exceptions):
```
State 0: IDLE → await instruction
State 1: EXECUTE → run datapath
State 2: MEMORY_WAIT → stall on L1 miss
State 3: EXCEPTION → handle fault
State 4: WRITEBACK → commit result
```

---

### 2.7 Register File (3-Read, 1-Write Port)

**Capacity**: 32 × 64-bit registers

**Read Ports**:
- Port A: Rs1 (base address)
- Port B: Rs2 (offset/secondary operand)
- Port C: Rs3 (value to write for BITSTORE)

**Write Port**:
- Port W: Rd (destination register)

**Access Time**: 1 cycle (combinational read, synchronous write)

---

## 3. Data Flow for BITLOAD Instruction

**Instruction**: `BITLOAD R5, R10, R15`

```
Clock | Stage | Operation
------|-------|-------------------------------------------
  0   |   0   | Decode BITLOAD, fetch R10=0x1000, R15=0x42
      |       | 
  1   |   1   | Address generator: eff_addr = 0x1000 + 0x42 = 0x1042
      |       | 
  2   |   2   | Index calc (combinational): 
      |       |   word_idx = 0x1042 >> 6 = 0x41
      |       |   bit_idx = 0x1042 & 0x3F = 0x02
      |       |
  3   |   3   | TLB lookup: word_index → phys_addr = 0x41000
      |       | L1 cache hit: word = 0xABCD_EF01_2345_6789
      |       |
  4   |   4   | Shifter: shifted = word >> 2 = 0x2AF37_BC04_8D15_9E
      |       | Extractor: result = shifted & 1 = 0
      |       |
  5   |   5   | Writeback: R5 ← 0
```

---

## 4. Pipeline Depth Analysis

**Best Case** (L1 hit):
- Stage 0: Decode (1 cycle)
- Stage 1: Address gen (1 cycle)
- Stage 2: Index calc (0 cycles, combinational)
- Stage 3: Memory access (1 cycle hit)
- Stage 4: Extract (1 cycle)
- Stage 5: Writeback (committed)
- **Total: 4 cycles latency**

**Worst Case** (L2 miss, then main memory):
- Stages 0-3: same as above
- Stage 3: Memory miss, initiate L2 request (10+ cycles)
- Stage 4: Extract (1 cycle)
- **Total: 15+ cycles latency**

---

## 5. Throughput Analysis

**Instruction Issue Rate**: 1 instruction per cycle (assuming no structural hazards)

**Bottlenecks**:
- Memory bandwidth: If high % of instructions are BITLOAD/BITSTORE
- Cache behavior: Working set fit in L1 cache is critical
- Register contention: Low (3 reads, 1 write per cycle is feasible)

**Optimization**: Dual-issue for independent bit operations:
- Issue BITLOAD + BITCOUNT in same cycle (different functional units)

---

## 6. Critical Path (for clock frequency)

The critical path is the longest combinational delay in the pipeline:

```
TDC = T_mux(operand select) + T_adder(64-bit) + T_setup(register)
    ≈ 0.3ns + 1.2ns + 0.2ns = 1.7ns
    ≈ 588 MHz (f_clock ≤ 1/1.7ns)
```

For 1+ GHz target, require pipelined adder (Kogge-Stone):
```
T_KS_adder ≈ 0.8ns → allows ~1.2 GHz
```

---

## 7. Physical Implementation Details

### 7.1 Gate Counts (Estimates)

| Component | Gates |
|-----------|-------|
| 64-bit Adder (Kogge-Stone) | 1,500 |
| Barrel Shifter (6 levels) | 4,000 |
| TLB (16-32 entries) | 5,000 |
| L1 Cache Interface | 10,000 |
| Register File (32×64) | 20,000 |
| Control Decoder + FSM | 3,000 |
| Data Muxes, AND gates, misc | 5,000 |
| **Total estimate** | **~50k gates** |

### 7.2 Area Estimate

- Technology: 7nm FinFET
- Gate density: ~80M gates/mm²
- **Area ≈ 50k / 80M ≈ 0.6 mm²** (sub-mm² functional unit)

### 7.3 Power Estimate

- Dynamic power: ~2mW (1 GHz, 1.2V, 50k gates, 80% switching activity)
- Static power: ~0.5mW (leakage)
- **Total: ~2.5mW** (idle or active, instruction-dependent)

---

## 8. Memory System Integration

### 8.1 Memory Hierarchy

```
CPU Pipeline
    ↓
L1 I-Cache (32 KB)  ←── 1 cycle (instructions)
L1 D-Cache (32 KB)  ←── 1 cycle (data for BITLOAD)
    ↓ (miss)
L2 Cache (256 KB)   ←── 10 cycles
    ↓ (miss)
L3 Cache (8 MB)     ←── 30 cycles
    ↓ (miss)
Main Memory (DDR4)  ←── 50+ cycles
```

### 8.2 TLB Integration

```
Virtual Bit Address (64-bit)
    ↓
Extract word_index[57:0] = bit_address[63:6]
    ↓
TLB lookup (16-entry, 4-way associative)
    ├─► Hit: phys_word_addr = phys_base[40:0] | word_index[13:0]
    ├─► Miss: page walk (25+ cycles)
    ↓
L1 Cache tag lookup
```

### 8.3 Boundary Conditions

**Case 1**: Bit 0-63 fit in single 64-bit word
- Single memory access (normal path)

**Case 2**: Extract bits spanning two words (e.g., bits 60-65)
- Hardware loads both words
- Shifts, masks, combines
- Transparent to ISA

**Case 3**: Bits span two pages (e.g., word 0x1FFFF to 0x20000)
- May require two separate TLB lookups + memory accesses
- Hardware handles by stalling until both words available
- Or: Software constraint to avoid (less common)

---

## 9. Write-Path (BITSTORE)

```
BITSTORE Rs1, Rs2, Rs3

Stage 1: Address gen → eff_addr = Rs1 + Rs2
Stage 2: Index calc → word_idx, bit_idx
Stage 3: TLB lookup + load current word
Stage 4: Bit mask & merge:
         mask = 1 << bit_idx
         new_word = (old_word & ~mask) | ((Rs3 & 1) << bit_idx)
Stage 5: Store new_word back to memory (writeback cache)
```

**Read-Modify-Write**:
- Load old word: 3 cycles
- Compute new value: 1 cycle
- Store: pipelined (doesn't wait for commit)
- **Total latency: 4-5 cycles**

---

## 10. Register Transfer Language (RTL) Skeleton

```verilog
// Stage 1: Address Generation
reg [63:0] eff_addr;
always @(posedge clk)
  eff_addr <= rs1_data + rs2_data;

// Stage 2: Index Calculation (combinational)
wire [57:0] word_index = eff_addr[63:6];
wire [5:0] bit_index = eff_addr[5:0];

// Stage 3: Memory Access
wire [63:0] memory_word = l1_cache_read(word_index);

// Stage 4: Bit Extraction
wire [63:0] shifted = memory_word >> bit_index;
wire [63:0] extracted = shifted & 64'h1;

// Stage 5: Writeback
always @(posedge clk)
  rd_data <= extracted;
```