| # Bit-String Hardware Accelerator ISA Specification |
|
|
| ## 1. ISA Overview |
|
|
| **Architecture**: RISC-style bit-manipulation ISA |
| **Operand Width**: 64-bit integer registers |
| **Word Size**: 64 bits |
| **Addressing**: Bit-addressed linear address space |
|
|
| --- |
|
|
| ## 2. Register File |
|
|
| ``` |
| Registers: R0-R31 (32 × 64-bit GPRs) |
| Special Registers: |
| - R0: Hard-wired zero |
| - R31: Return value / implicit accumulator |
| ``` |
|
|
| --- |
|
|
| ## 3. Instruction Format |
|
|
| ### 3.1 R-Type (Register-Register) |
| ``` |
| ┌─────────┬─────┬─────┬─────┬────────────┐ |
| │ Opcode │ Rd │ Rs1 │ Rs2 │ Reserved │ |
| │ 6 bits │ 5 │ 5 │ 5 │ 13 bits │ |
| └─────────┴─────┴─────┴─────┴────────────┘ |
| ``` |
|
|
| ### 3.2 I-Type (Register-Immediate) |
| ``` |
| ┌─────────┬─────┬─────┬──────────────┐ |
| │ Opcode │ Rd │ Rs1 │ Immediate │ |
| │ 6 bits │ 5 │ 5 │ 18 bits │ |
| └─────────┴─────┴─────┴──────────────┘ |
| ``` |
|
|
| ### 3.3 L-Type (Load Immediate) |
| ``` |
| ┌─────────┬─────┬──────────────────────┐ |
| │ Opcode │ Rd │ Immediate │ |
| │ 6 bits │ 5 │ 53 bits (sign-ext) │ |
| └─────────┴─────┴──────────────────────┘ |
| ``` |
|
|
| --- |
|
|
| ## 4. Opcode Assignments |
|
|
| | Mnemonic | Opcode | Type | Semantics | |
| |----------------|--------|------|-----------| |
| | BITLOAD | 0x01 | R | rd ← mem[rs1 + rs2 bit offset] & 1 | |
| | BITSTORE | 0x02 | R | mem[rs1 + rs2 bit offset] ← rs3 & 1 | |
| | BITFIELD | 0x03 | R | rd ← (mem[rs1 + rs2] >> rs3) & ((1 << rs4) - 1) | |
| | BITTEST | 0x04 | R | flag ← (mem[rs1 + rs2] >> bit_offset) & 1 | |
| | BITCOUNT | 0x05 | R | rd ← popcount(mem[rs1]) | |
| | BITSCANFWD | 0x06 | R | rd ← first_set_bit(rs1) | |
| | BITSCANREV | 0x07 | R | rd ← last_set_bit(rs1) | |
| | LOADIMM64 | 0x08 | L | rd ← immediate (53-bit sign-extended) | |
| | BITEXTRACT | 0x09 | R | rd ← extract_field(rs1, rs2, rs3) | |
| | BITINSERT | 0x0A | R | rd ← insert_field(rs1, rs2, rs3, rs4) | |
| | BITROTL | 0x0B | R | rd ← rotate_left(rs1, rs2) | |
| | BITROTR | 0x0C | R | rd ← rotate_right(rs1, rs2) | |
| |
| --- |
| |
| ## 5. Instruction Semantics |
| |
| ### 5.1 BITLOAD (Single-Bit Load) |
| |
| **Encoding**: `BITLOAD Rd, Rs1, Rs2` |
| |
| **Operation**: |
| ``` |
| effective_bit_address = Rs1 + Rs2 |
| word_index = effective_bit_address / 64 |
| bit_index = effective_bit_address mod 64 |
| Rd ← (memory[word_index] >> bit_index) & 1 |
| ``` |
| |
| **Constraints**: |
| - `Rs1`: Bit base address (64-bit) |
| - `Rs2`: Bit offset (64-bit) |
| - `Rd`: Destination register (bit 0 set, bits [63:1] = 0) |
| - No privilege required |
| - May fault: page fault if effective address invalid |
| |
| **Latency**: 3 cycles (address generation + memory access + extract) |
| |
| --- |
| |
| ### 5.2 BITSTORE (Single-Bit Write) |
| |
| **Encoding**: `BITSTORE Rs1, Rs2, Rs3` |
| |
| **Operation**: |
| ``` |
| effective_bit_address = Rs1 + Rs2 |
| word_index = effective_bit_address / 64 |
| bit_index = effective_bit_address mod 64 |
| bit_value = Rs3 & 1 |
| old_word = memory[word_index] |
| mask = 1 << bit_index |
| new_word = (old_word & ~mask) | (bit_value << bit_index) |
| memory[word_index] ← new_word |
| ``` |
| |
| **Constraints**: |
| - `Rs1`: Bit base address |
| - `Rs2`: Bit offset |
| - `Rs3`: Bit value (only bit 0 is meaningful) |
| - No destination register |
| - Requires write permission on target memory |
| - May fault: segmentation fault, write-protect fault |
| |
| **Latency**: 3 cycles (address generation + RMW cycle) |
| |
| --- |
| |
| ### 5.3 BITFIELD (Multi-Bit Extract) |
| |
| **Encoding**: `BITFIELD Rd, Rs1, Rs2, Rs3, Rs4` |
| |
| **Operation**: |
| ``` |
| effective_bit_address = Rs1 + Rs2 |
| word_index = effective_bit_address / 64 |
| bit_index = effective_bit_address mod 64 |
| field_width = Rs3 |
| bit_offset_in_word = Rs4 |
| |
| word = memory[word_index] |
| extracted = (word >> bit_offset_in_word) & ((1 << field_width) - 1) |
| Rd ← extracted |
| ``` |
| |
| **Constraints**: |
| - `field_width` must be in range [1, 64] |
| - If `bit_offset + field_width > 64`, behavior is undefined (may trap) |
| - No cross-boundary extraction in this instruction (use software loop) |
| |
| **Latency**: 3 cycles |
| |
| --- |
| |
| ### 5.4 BITTEST (Test and Branch) |
| |
| **Encoding**: `BITTEST Rs1, Rs2` |
| |
| **Operation**: |
| ``` |
| effective_bit_address = Rs1 + Rs2 |
| word_index = effective_bit_address / 64 |
| bit_index = effective_bit_address mod 64 |
| condition_flag ← (memory[word_index] >> bit_index) & 1 |
| ``` |
| |
| **Latency**: 3 cycles |
| |
| **Conditional Execution**: Sets zero flag (ZF) in status register: |
| - `ZF = 0` if bit is set |
| - `ZF = 1` if bit is clear |
| |
| --- |
| |
| ### 5.5 BITCOUNT (Population Count) |
| |
| **Encoding**: `BITCOUNT Rd, Rs1` |
| |
| **Operation**: |
| ``` |
| Rd ← popcount(Rs1) |
| ``` |
| |
| **Latency**: 2 cycles (specialized hardware) |
| |
| --- |
| |
| ### 5.6 BITSCANFWD (Find First Set Bit) |
| |
| **Encoding**: `BITSCANFWD Rd, Rs1` |
| |
| **Operation**: |
| ``` |
| If Rs1 = 0: |
| Rd ← 64 (or undefined, behavior determined by hardware) |
| Else: |
| Rd ← position of rightmost set bit (0-indexed) |
| Range: Rd ∈ [0, 63] |
| ``` |
| |
| **Latency**: 2-3 cycles |
| |
| --- |
| |
| ### 5.7 BITSCANREV (Find Last Set Bit) |
| |
| **Encoding**: `BITSCANREV Rd, Rs1` |
| |
| **Operation**: |
| ``` |
| If Rs1 = 0: |
| Rd ← 64 (or undefined) |
| Else: |
| Rd ← position of leftmost set bit (0-indexed) |
| Range: Rd ∈ [0, 63] |
| ``` |
| |
| **Latency**: 2-3 cycles |
| |
| --- |
| |
| ### 5.8 LOADIMM64 (Load 53-Bit Immediate) |
| |
| **Encoding**: `LOADIMM64 Rd, immediate` |
| |
| **Operation**: |
| ``` |
| Rd ← sign_extend(immediate[52:0], 64) |
| ``` |
| |
| **Latency**: 1 cycle |
| |
| --- |
| |
| ### 5.9 BITEXTRACT (Field Extraction with Width) |
| |
| **Encoding**: `BITEXTRACT Rd, Rs1, Rs2, Rs3` |
| |
| **Operation**: |
| ``` |
| value = Rs1 |
| start_bit = Rs2 |
| field_width = Rs3 |
|
|
| extracted = (value >> start_bit) & ((1 << field_width) - 1) |
| Rd ← extracted |
| ``` |
| |
| **Latency**: 1 cycle (register-only, no memory) |
| |
| --- |
| |
| ### 5.10 BITINSERT (Field Insertion) |
| |
| **Encoding**: `BITINSERT Rd, Rs1, Rs2, Rs3, Rs4` |
| |
| **Operation**: |
| ``` |
| dest_value = Rs1 |
| source_value = Rs2 |
| start_bit = Rs3 |
| field_width = Rs4 |
|
|
| mask = ((1 << field_width) - 1) << start_bit |
| shifted_source = (source_value & ((1 << field_width) - 1)) << start_bit |
| Rd ← (dest_value & ~mask) | shifted_source |
| ``` |
| |
| **Latency**: 2 cycles |
| |
| --- |
| |
| ### 5.11 BITROTL (Rotate Left) |
| |
| **Encoding**: `BITROTL Rd, Rs1, Rs2` |
| |
| **Operation**: |
| ``` |
| value = Rs1 |
| rotate_amount = Rs2 mod 64 |
| Rd ← (value << rotate_amount) | (value >> (64 - rotate_amount)) |
| ``` |
| |
| **Latency**: 2 cycles |
| |
| --- |
| |
| ### 5.12 BITROTR (Rotate Right) |
| |
| **Encoding**: `BITROTR Rd, Rs1, Rs2` |
| |
| **Operation**: |
| ``` |
| value = Rs1 |
| rotate_amount = Rs2 mod 64 |
| Rd ← (value >> rotate_amount) | (value << (64 - rotate_amount)) |
| ``` |
| |
| **Latency**: 2 cycles |
| |
| --- |
| |
| ## 6. Memory Semantics |
| |
| ### 6.1 Byte Ordering (Little-Endian) |
| |
| All operations assume little-endian byte ordering: |
| ``` |
| Memory layout (64-bit word at address 0x00): |
| Bit 0 at byte 0, bit 0 |
| Bit 7 at byte 0, bit 7 |
| Bit 8 at byte 1, bit 0 |
| Bit 63 at byte 7, bit 7 |
| ``` |
| |
| ### 6.2 Alignment Requirements |
| |
| - No alignment requirement for bit addresses |
| - Memory accesses are naturally granular to 64-bit words |
| - Unaligned word access: hardware loads containing word, extracts bits |
| |
| ### 6.3 Virtual Memory Integration |
| |
| - Bit addresses translate to physical addresses via TLB |
| - `word_address = bit_address >> 6` (divide by 64) |
| - `word_address` is then translated through MMU |
| - Page boundaries: if `bit_address` and `bit_address+63` span different pages, may require two memory accesses |
| - Hardware handles transparently for single-bit operations |
| - Multi-word operations may trap if boundary conditions not met |
| |
| ### 6.4 Cache Coherency |
| |
| - Follows processor's existing cache coherency protocol |
| - BITSTORE is treated as a regular write for coherency purposes |
| - No special coherency instruction needed |
| |
| --- |
| |
| ## 7. Exception Behavior |
| |
| | Exception | Opcode | Trigger | Action | |
| |-----------|--------|---------|--------| |
| | PAGE_FAULT | Any memory op | Address not in TLB | Interrupt handler, retry | |
| | PROTECTION_FAULT | BITSTORE | Page not writable | Interrupt handler | |
| | INVALID_ADDRESS | Any memory op | Address > max physical | Trap | |
| | UNDEFINED_FIELD_WIDTH | BITFIELD | width = 0 or width > 64 | Trap | |
| |
| --- |
| |
| ## 8. Status Register (Implicit) |
| |
| ``` |
| Bit Name Meaning |
| 0 ZF Zero Flag (set by BITTEST) |
| 1 CF Carry Flag (unused in this ISA) |
| 2-63 Reserved |
| ``` |
| |
| --- |
| |
| ## 9. Privilege Levels |
| |
| All bit-string instructions are **user-mode executable**. No privilege escalation. |
| |
| Exception: Bit addresses pointing to kernel memory may trigger protection faults. |
| |
| --- |
| |
| ## 10. Formal Semantics (First-Order Logic) |
| |
| ### Correctness Property: Single-Bit Load |
| |
| ``` |
| ∀ base, offset ∈ ℕ : |
| let eff_addr = base + offset |
| let word_idx = eff_addr >> 6 |
| let bit_idx = eff_addr mod 64 |
| BITLOAD base offset = (mem[word_idx] >> bit_idx) & 1 |
| ``` |
| |
| ### Correctness Property: Single-Bit Store |
| |
| ``` |
| ∀ base, offset, value ∈ ℕ : |
| let eff_addr = base + offset |
| let word_idx = eff_addr >> 6 |
| let bit_idx = eff_addr mod 64 |
| let mask = 1 << bit_idx |
| |
| after BITSTORE base offset value: |
| mem[word_idx] = (mem[word_idx] & ~mask) | ((value & 1) << bit_idx) |
| ∀ j ≠ word_idx : mem[j] unchanged |
| ``` |
| |
| ### Correctness Property: Field Extraction |
|
|
| ``` |
| ∀ value, start, width ∈ ℕ, width ≤ 64 : |
| BITEXTRACT value start width = (value >> start) & ((1 << width) - 1) |
| ``` |
|
|
| --- |
|
|
| ## 11. Implementation Constraints |
|
|
| - **Max memory size**: 2^64 bits (addressable) |
| - **Max single extraction**: 64 bits per instruction |
| - **Max rotation**: Full 64-bit rotation with any offset |
| - **Frequency**: Target 1+ GHz (1-3 cycle latency operations) |
| - **Power**: < 2mW per operation (estimated) |
| - **Area**: ~100-200k gates (estimates as sub-module) |
|
|
| --- |
|
|
| ## 12. Future Extensions (Out of Scope) |
|
|
| - SIMD bit-parallel operations |
| - GPU integration |
| - Vector bit strings |
| - Conditional bit operations |
| - Atomic bit operations (hardware locks) |
|
|
|
|
