# Lab1: RV32I Simulator
The lab is to understand how instructions work along with Ripes simulator. It starts from the small program, Factorial number, with recursion, and go on to study each stage of 5-stage-pipeline and hazards.

## Factorial Number
The Factorial number sequence is a recursive method to define:
$\ \ \ \ \ \ N_0=0,\ N_1=1$
and
$\ \ \ \ \ \ N_n=N_{n-1 }* n$
for $n>1$

## Implement in C code

#include<stdio.h>

long int Factorial(int n);
int main() {
    int n = 6;
    printf("Factorial of %d = %ld", n, Factorial(n));
    return 0;
}

long int Factorial(int n) {
    if (n>=1)
        return n*Factorial(n-1);
    else
        return 1;
}

## RISC-V asm with recursion

.data
argument: .word   6
str1:     .string "Factorial of "
str2:     .string " = "

.text
main:
        lw  a0, argument   # n = 6
        jal ra, fact       


        mv  a1, a0
        lw  a0, argument
        jal ra, printResult


        li a7, 10
        ecall

fact:
        addi sp, sp, -16
        sw   ra, 8(sp)
        sw   a0, 0(sp)
        addi t0, a0, -1
        bge  t0, zero, nfact

        addi a0, zero, 1
        addi sp, sp, 16
        jr x1

nfact:
        addi a0, a0, -1
        jal  ra, fact
        addi t1, a0, 0
        lw   a0, 0(sp)
        lw   ra, 8(sp)
        addi sp, sp, 16
        mul a0, a0, t1
        ret


# a0: Value which factorial number was computed from
# a1: Factorial result
printResult:
        mv t0, a0
        mv t1, a1
        la a0, str1
        li a7, 4
        ecall
        mv a0, t0
        li a7, 1
        ecall
        la a0, str2
        li a7, 4
        ecall
        mv a0, t1
        li a7, 1
        ecall
        ret

After running the code, it will print `Factorial(6) = 720` on the console,
with argument = 6.

## Ripes simulator

### Pipeline
The pipeline architecture consists of 5 stages (IF, ID, EX, MEM, WB) in the simulator, the following is the function of each stage:

* **IF (Instruction fetch)**
In IF stage, we can get PC (program counter), which comes from either the last instruction addr. (PC) plus 4 or Arithmetic Logic Unit (ALU) if there is a branch instr. in EX stage like beq jal ,and so on. Then, instruction will be fetched depending on the PC from the instr. memory.
<br>
We can see PC = 0x04, and fetches 0x0052503 in instr. memory, which means
`lw x10 0(x10)` in asm. After fetching instr. PC will plus 4 = 0x08.
<br>

If instr. in the EX stage is branch instr., PC will come from the result of ALU, and change the MUX (multiplexer) input.

* **ID (Instruction decode)**
In ID stage, the decoder will decode the instruction, determine the input of each MUX, and then the register file will be read to prepare for the next stage.

* **EX (Execute)**
EX stage is where the computation occurs. The stage consists of ALU and Branch.
* The ALU is responsible for computing the math operation, the boolean operation, and even the PC of the branch instruction.
* The Branch will use data from register to determine if the Branch taken or not.


The `addi` instruction, the two operand 0x000002d0 and 0x00000000 come from Reg1 and Imm data, respectively, and get the result 0x000002d0.

<br>

This is `bge` instruction. Because Reg1 is greater than Reg2, set Branch taken = true, and change the PC.

* **MEM (Memory access)**
In MEM stage, we can access memory through instruction such as sw, lw, etc.


This is `sw` instruction, it will set MemWrite = true and then store 0xc ， into addr. 0x7fffffe8.

<br>


This is `lw` instruction, it will get value from 0x7fffff98 and then write the value back to the register.

* **WB (Writeback)**
After the instruction `lw x10 0(x2)` mentioned in the above picture, the data 0x00000001 will write back to the register x10(t0).


### Pipeline Hazards & Solutions
Pipeline hazards are the problems that it cannot execute the next instruction in the next cycle. There are three kinds of hazards, data hazards, structural hazards, and control hazards. Here, I will use the simultor to show about data hazards and control hazards and how the simulator solves the problems.
* **Data Hazard**
Data hazards typically result from data dependency. In this architecture, RAW (Read after Write) is the main reason that causes data hazards. The following are two examples.
* `addi x2 x2 -16`
`sw x1 8(x2)`
In this case, CPU will write data back to x2 in WB stage, but x2 is needed in EX stage of the next instruction. So, it is too late to wait for data write back to register. To solve the problem, the simulator use forwarding from EX/MEM directly to ALU.


The yellow line is the path of forwarding.


We can see that x2 in the register file hasn't been changed, it still maintains 0x7ffffff0 because the data hasn't written back yet. But, the Op1 of ALU has already changed to 0x7fffffe0

* **Control Hazard**
Control hazards happen when there is a branch instruction like beq, bne, etc. The next instruction can be determined only after the EX stage of the branch instruction.

To solve the problem, the simulator use a static prediction that always predicts no branch happens. By this way, the pipeline can successfully do without any stall if the prefiction is correct.

However, it sometimes make an incorrect prediction like the following two picture.



In the EX stage, if the branch happens, CPU will set Branch taken signaal into true, and the next two instructions it predicts should be discarded. So if prediction is not correct, the pipeline still has to undergo 2-cycle `nop`.

###### tags: `Computer Architecture (Fall 2020)`RV32I Simulator`