# Lab1: RV32I Simulator
###### tags: `Computer Architecture 2020`
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:
$\ \ \ \ \ \ F_0=0,\ F_1=1$
and
$\ \ \ \ \ \ F_n=F_{n-1} + F_{n-2}$
for $n>1$

## Inplement in C code

#include<stdio.h>

int fib(int n){
    if(n <= 1){
        return n;
    }
    else{
        return fib(n - 1) + fib(n - 2);
    }
}

int main(void){
    int n = 12;
    printf("Fibonacci(%d) = %d", n, fib(n));
    return 0;
}

## RISC-V asm with recursion

.data
argument: .word    12
str1:     .string "Fibonacci("
str2:     .string ") = "

.text
main:                          # initial value
        lw    a0, argument     # n = 12
        li    s0, 1            # for comparison with n (n <= 1)
        jal   ra, fib          # call fib(12)

        mv    a1, a0           # a1 : final falue
        lw    a0, argument     # a0 : argument
        jal   ra, printResult  # print result

        j     exit             # go to exit

fib:
        ble   a0, s0, L1       # if(n <= 1)
        addi  sp, sp, -12      # push the stack
        sw    ra, 8(sp)        # store return address
        sw    a0, 4(sp)        # store argument n
        addi  a0, a0, -1       # argument = n - 1
        jal   ra, fib          # call fib(n - 1)
        sw    a0, 0(sp)        # store return value of fib(n - 1)
        lw    a0, 4(sp)        # load argument n
        addi  a0, a0, -2       # argument = n - 2
        jal   ra, fib          # call fib(n - 2)
        lw    t0, 0(sp)        # load return value of fib(n - 1)
        add   a0, a0, t0       # fib(n - 1) + fib(n - 2)
        lw    ra, 8(sp)        # load return address
        addi  sp, sp, 12       # pop the stack
        ret                    # return
	
L1:
        ret                    # return

printResult:                   # Fibonacci(12) = 89
        mv    t0, a0
        mv    t1, a1
        la    a0, str1
        li    a7, 4
        ecall                  # print string str1
        mv    a0, t0
        li    a7, 1
        ecall                  # print int argument n
        la    a0, str2
        li    a7, 4
        ecall                  # print string str2
        mv    a0, t1
        li    a7, 1
        ecall                  # print int result
        ret

exit:
        li   a7, 12
        ecall                  # exit

After running the code, it will print `Fibonacci(10) = 55` on the console,
with argument = 10.

## 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`.

## 問題