> [!note] AI Tools Usage > I used Gemini for researching, brainstorming and proofreading. # Why must branches be resolved early in the pipeline? > Reference: [Lectures 21-23: RISC-V 5-Stage Pipeline ](https://docs.google.com/presentation/d/1v-Squx8lK-oOrflFOwBZh-ue94seVHZudqDOgJmFf5Q/edit?slide=id.g30cd39f6c3e_86_146#slide=id.g30cd39f6c3e_86_146) ![image](https://hackmd.io/_uploads/r1rCi39Hbe.png) In the Lecture, the 5-stage pipeline CPU resolves in the **EX stage**. Branch Resolution consists of two tasks: determine the branch outcome (taken or not taken) and calculate the branch target address. **Branch Comp**: A Branch Comparator in EX stage is used to determine whether branch condition is met (e.g., `beq`, `bge`, `blt`). **Branch Target Address**: This can be calculated by the ALU (or a separate adder). However, branches can be optimized by resolving earlier in the **ID stage**. In the following section, I'll introduce the concept of ID-stage resolution. ```text KEY Concept: Why resolve branch early? -> To reduce branch penalties. Trade-off: Early resolution introduces more hazards. -> The earlier branch resolution, the more hazards. ``` ## Trade-off: Hazards and Penalties ### Control Hazard In a 5-stage pipeline CPU, branch resolution typically occurs in one of two stages (ID and EX). * Resolution in **EX stage**: The branch decision is known at the end of EX stage. - If mispredicted, need to flush `IF` and `ID`. - Penalty: **2 cycles**. For example, ```asm= 0x10: beq t0, t1, LABEL_if # Assume Branch Taken 0x14: add t2, t3, t4 # Fetched (in ID) -> FLUSHED! 0x18: sub t5, t6, t7 # Fetched (in IF) -> FLUSHED! ``` * Resolution in **ID stage**: The branch decision is known at the end of ID stage. - If mispredicted, need to flush `IF`. - Penalty: **1 cycle**. For example, ```asm= 0x10: beq t0, t1, LABEL_if # Assume Branch Taken 0x14: add t2, t3, t4 # Fetched (in IF) -> FLUSHED! 0x18: sub t5, t6, t7 # Not Fetched ``` ### Data Hazard As mentioned, earlier branch resolution introduces more hazards. Here, we analyze the data hazards when branch resolution is moved to **ID** stage. **Load-Use Data Hazard** * Resolution in EX stage: ```asm= 0x10: lw t0, 0(sp) # Producer (In MEM stage) 0x14: beq t0, t1, LABEL_if # Consumer (In EX stage) ``` **Analysis:** There is a **LOAD-USE data hazard** on register `t0`. Since the `lw` instruction retrieves data at the end of **MEM** stage, even if there is full forwarding, the `beq` instruction can not get the required data at the beginning of **EX** stage for comparison. Therefore, the pipeline must **stall for 1 cycle** (or insert a NOP) to wait for the data become available. * Resolution in ID stage: Use the same example, ```asm= 0x10: lw t0, 0(sp) # Producer (In EX stage) 0x14: beq t0, t1, LABEL_if # Consumer (In ID stage) ``` **Analysis:** There is a **LOAD-USE data hazard** on register `t0`. The `beq` instruction requires `t0` in **ID** stage to determine whether the branch is taken or not. However, `lw` is currently in **EX** stage, and it is impossible to access memory in `EX` stage. Therefore, **2 stalls** (or insert NOPs) are needed. * Stall 1: Since `lw` is in EX stage, we must insert a NOP to wait for `lw` to reach **MEM** stage. * Stall 2: Even when `lw` is in MEM stage, `lw` retrieves data at the **end** of this cycle. The `beq` instruction (now stalled in ID) needs data at the **beginning** of the cycle. Thus, a second NOP is required to wait for the `lw` reach **WB** stage. **Conclusion:** Only when `lw` reaches **WB** stage can we forward the data from `lw` to `beq` to resolve the branch. ```asm= lw t0, 0(sp) nop # Stall (Wait for EX -> MEM) nop # Stall (Wait for MEM -> WB) beq t0, t1, LABEL_if ``` However, what happens if it is merely a **RAW data hazard**, not a LOAD-USE hazard? **RAW Data Hazard** Consider the below code snippet, where a **RAW data hazard** occurs: ```asm= 0x10: addi t0, t1, 0x7F # Producer 0x14: beq t0, t2, LABEL_else # Consumer ``` The same situation happens. Even though `addi` is not a memory instruction, it calculates the result in the **EX** stage. Since the `beq` instruction needs the data in **ID** stage, the result is not yet ready. Therefore, the `beq` instruction must **stall for 1 cycle**. ## Verification ### Branch Resolution in ID stage * Control Hazard: ```asm= .text .globl main main: li t0, 1 li t1, 1 beq t0, t1, Label_Taken # To be flushed addi t2, x0, 0x11 addi t3, x0, 0x22 j Test_Fail Label_Taken: addi t4, x0, 0x33 li t5, 0xCAFE j Exit Test_Fail: li t5, 0xDEAD Exit: li a0, 0 ``` ![image](https://hackmd.io/_uploads/rkzd_o2HWl.png) * `beq t0, t1, Label_Taken` = `0x00628863` * `addi t2, x0, 0x11` = `0x01100393` * `addi t4, x0, 0x33` = `0x03300E93` `0x00628863` corresponds to `beq t0, t1, Label_Taken`. Since the branch is taken and **resolved is in ID stage**, the intruction fetched in IF stage (`0x01100393`, namely `addi t2, x0, 0x11`)is flushed. Consequently, a NOP (`0x00000013`) appears in the ID stage in the following cycle, therefore, the penalty is 1 cycle. :::success Control Hazard Verified ::: * LOAD-USE Data Hazard ```asm= .text .globl main main: addi t1, x0, 5 addi t2, x0, 5 sw t2, 0(sp) lw t0, 0(sp) # LOAD-USE Data Hazard beq t0, t1, Label_Taken # To be flushed addi t2, x0, 0x11 addi t3, x0, 0x22 j Test_Fail Label_Taken: addi t4, x0, 0x33 li t5, 0xCAFE j Exit Test_Fail: li t5, 0xDEAD Exit: li a0, 0 ``` ![image](https://hackmd.io/_uploads/H19I3CnBZg.png) * `lw t0, 0(sp)` = `0x00012283` * `beq t0, t1, Label_Taken`: `0x00628863` * `addi t2, x0, 0x11`: `0x01100393` When the `beq` instruction is in ID stage, it depends on the `lw` instructions (currently in EX stage). Since `lw` retrieves data at the end of **MEM** stage, but `beq` needs to resolve the branch condition with ID stage, the data is not yet available. Consequently, `beq` must stall for **two cycles** in ID stage to wait for `lw` complete. :::success LOAD-USE Hazard Verified ::: * RAW Data Hazard ```asm= .text .globl main main: addi t1, x0, 5 addi t2, x0, 6 addi t0, t1, 1 # RAW Data Hazard beq t0, t2, Label_Taken # To be flushed addi t2, x0, 0x11 addi t3, x0, 0x22 j Test_Fail Label_Taken: addi t4, x0, 0x33 li t5, 0xCAFE j Exit Test_Fail: li t5, 0xDEAD Exit: li a0, 0 ``` ![image](https://hackmd.io/_uploads/BJrsCT2rZe.png) * `addi t0, t1, 1` = `0x00130293` * `beq t0, t2, Label_Taken` = `0x00728863` * `addi t2, x0, 0x11` = `0x01100393` * `addi t4, x0, 0x33` = `0x03300E93` when the `beq` instruction is in ID stage, a RAW data hazard occurs on register `t0`. Consequently, `beq` must stall for **one** cycle in ID stage. This allows the required data to be forwarded from **MEM** stage in the next cycle. Since the branch is taken, `addi t2, x0, 0x11` is flushed. :::success RAW Data Hazard Verified ::: # How can compressed \(C) instructions affect pipeline fetch? ## RVC (RISC-V Compressed Instruction) [Compressed Instruction Set](https://en.wikipedia.org/wiki/Compressed_instruction_set) > Quote from [Chapter 26. "C" Extension for Compressed Instructions, Version 2.0 ](https://docs.riscv.org/reference/isa/v20240411/_attachments/riscv-unprivileged.pdf) > This chapter describes the RISC-V standard compressed instruction-set extension, named "C", which reduces static and dynamic code size by adding short 16-bit instruction encodings for common operations. The C extension can be added to any of the base ISAs (RV32I, RV32E, RV64I, RV64E), and we use the generic term "RVC" to cover any of these. Typically, 50%-60% of the RISC-V instructions in a program can be replaced with RVC instructions, resulting in a 25%-30% code-size reduction. RISC-V Compressed Instruction introduces **short 16-bit** instructions, RVC allows **common** (namely, frequently used) 32-bit instructions to encode into 16-bit. > Note: RVC does not add any new instructions, each 16-bit instruction maps one-to-one to an existing 32-bit instruction. Furthermore, 32-bit and 16-bit instructions can be intermixed. The benefits of RVC is that the same I-cache can store more instructions, which reduces instruction cache misses (**spatial locality**). > Quote from [Chapter 26. "C" Extension for Compressed Instructions, Version 2.0 ](https://docs.riscv.org/reference/isa/v20240411/_attachments/riscv-unprivileged.pdf) > The C extension is compatible with all other standard instruction extensions. The C extension allows 16-bit instructions to be freely intermixed with 32-bit instructions, with the latter now able to start on any 16-bit boundary, i.e., IALIGN=16. With the addition of the C extension, no instructions can raise instruction-address-misaligned exceptions. ## How RVC Compress? RVC does not employ complex compression algorithm. Instead, it utilizes the **regularity** of code. It achieves the 16-bit target by mixing and matching specific constraints: 1. Small Immediates: Standard instructions allocate 12 bits for immediates. RVC shrinks this to 5~6 bits. 2. The registers `x0` (Zero), `x1` (ra) and `x2` (sp) are used most frequently. Since these three registers are essential for control flow and stack, RVC hard-codes them into the OPCode. The Opcode implies these registers, saving the 5 bits usually required for register addressing. 3. The destination register and the first source register are identical. Many instructions are of this type, for example, `addi s0, s0, 1`. In this case, RVC encodes the register index only once. 4. Popular Register Only: Many RVC instructions can only access the 8 most frequently used registers (`x8`-`x15`, namely `s0-s1` and `a0`-`a5`). This allows the register to be specified using only 3 bits instead of 5. > Note: These conditions are **strategies**, not simultaneous requirements. An instruction usually needs to use 1 or 2 of these strategies to fit into 16 bits. ```text // Compressed 16-bit RVC instruction formats _________________________________________________________________________________ |Format| Meaning |15 14 13 12 |11 10 9 8 7 | 6 5 4 3 2 | 1 0 | --------------------------------------------------------------------------------- | CR | Register | funct4 | rd/rs1 | rs2 | op | | CI | Immediate |funct3| imm | rd/rs1 | imm | op | | CSS | Stack-relative Store |funct3| imm | rs2 | op | | CIW | Wide Immediate |funct3| imm | rd' | op | | CL | Load |funct3| imm | rs1' | imm | rd' | op | | CS | Store |funct3| imm | rs1' | imm | rs2' | op | | CA | Arithmetic | fucnt6 |rd'/rs1'|funct2| rs2' | op | | CB | Branch/Arithmetic |funct3| offset |rd'/rs1'|offset | op | | CJ | Jump |funct3| jump target | op | --------------------------------------------------------------------------------- -> rd/rs1: Standard 5-bit register field (Can access x0-x31) -> rd'/rs1': Compressed 3-bit register field (Can only access x8-x15) -> imm: Immediate values that are less than 12 bits ``` ## My Thoughts ### Effects on Instruction Fetch Since the length of instructions have two different sizes(32-bit and 16-bit), there will have two impact on instruction fetch stage: 1. The PC update logic requires a additional **MUX** to select between `PC + 4` and `PC　+ 2`. Originally, the PC always incremented by 4, but now the amount of increment depends on the current instruction's length. 2. We must determine the instruction length in **IF** stage. While the hardware doesn't need to fully decode the instruction here, it only has to check the the **lower 2 bits** to decide the length. In conclusion, RVC increases the hardware complexity of the **IF** stage. ## Analysis ### Spatial Locality Assume a Direct-mapped L1 Instruction Cache size of **32 KB** with a cache block size of **64 Bytes**. * In standard RISC-V (Worst Case), a 64-byte cache block can store: $$ 64 \ \text{Bytes} / 4 \ \text{Bytes} = 16 \ \text{instructions} $$ * In RVC (Best Case), if all instructions were compressed to 16-bit, a 64-byte cache block can store: $$ 64 \ \text{Bytes} / 2 \ \text{Bytes} = 32 \ \text{instructions} $$ * In reality, programs are a mix. Assume that one 32-bit instruction is mixed with two 16-bit instructions (1:2 ratio). - Size of these 3 instructions: $4 + 2 + 2 = 8 \ \text{Bytes}$ - A 64-byte cache block can store: $$(64 \ \text{Bytes} / 8 \ \text{Bytes}) \times 3 \ \text{instructions} = 24 \ \text{instructions}$$ ### Miss Rate Based on the calculation above, we can analyze the cache miss rate (assuming instruction are sequentially executed): * **Standard RISC-V:** The CPU has to fetch a new cache block from main memory once every 16 instructions. $$ \text{Miss Rate} = \frac{1 \ \text{Miss}}{16 \ \text{Instructions}} = 6.25\% $$ * **RVC (Mixed):** The CPU has to fetch a new cache block from main memory once every 24 instructions. $$ \text{Miss Rate} = \frac{1 \ \text{Miss}}{24 \ \text{Instructions}} \approx 4.17\% $$ ### How to validate? To validate the my analysis, we can implement the RVC on 4-SoC MyCPU: 1. Modify the **IF** stage: Add a **MUX** to select between `PC+4` and `PC+2`, controlled by decoding the **lower 2 bits** (Opcode for RVC instructions) of the current instruction. 2. Compilation: Use `riscv-none-elf-gcc` toolchain with the `-march=rv32ic` flag to get the assembly binaries (`.asmbin`). 3. Simulation: Run the simulation and use `gtkwave` to analyze the waveforms. Calculate the total duration of IF stage stalls. # Reference [Debunking CISC vs RISC code density](https://www.bitsnbites.eu/cisc-vs-risc-code-density/) ["C" Extension for Compressed Instructions, Version 2.0](https://github.com/riscv/riscv-isa-manual/blob/main/src/c-st-ext.adoc) # AI Usage [Gemini - RISC-V Compressed Instructions Explained](https://gemini.google.com/share/c2a851e7e5a2)