# Lab1: RV32I Simulator
##### tags: `computer architecture`
## Fibonacci number ([Leetcode509](https://leetcode.com/problems/fibonacci-number/))
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.
## Implementation
You can find the source code [here](https://github.com/airpodspro/computr-architecture)
### C code

#include <stdio.h>

void F(int);

int main(){
    num = 5;
    fib = F(num);
    printf("the number of F("%d") ="%d, num, fib);
}

F(int n){
    fibpre = 0, fib = 1, temp;
    for(int i = 2; i <= num; i++){
        temp = fib;
        fib += fibpre;
        fibpre = temp;
    }
    return fib;
}

#### **Code explain:**
Give a number of n in function F(n), at first we define the initial number of fibpre and fib as F(0) and F(1) in the function, then we start calculating the F(n) we wanted by the loop, it will first keep the original number of *fib* in the `temp` ( Ex : keep F(1) in `temp` ), then calculate the new `fib` by using `fib` += `fibpre` ( Ex : `fib` = F(0) + F(1) ), its also the define of calculating Fibonacci number ( sum of the two preceding ones ), so now we get the number of F(2) in `fib`, then we replace the value of `fibpre` as the original `fib` we kept in `temp` ( know as F(1) ), we now get the F(2) in `fib` and the F(1) in `fibpre` for the next loop of calculating F(3).

### Assembly code
We can change the number of n in F(n) by replacing the number behind num, in the latter case we take 5 as an example

.data
        num: .word 5
.text

main:
        la  s0, num            # s0 = num address
        lw  s0, 0(s0)          # load in the number at the address
        li  s1, 1              # load immediate 1 in s1
        blt  s0, s1, end       # see if the answer is fib[0] or fib[1]
        sub s1, s0, s1         # get number of doing loop
        li  t0, 0              # set initiall prefib
        li  s0, 1              # set initial fib
        
loop: 
        mv  t1, s0             # keep original fib
        add  s0, s0, t0        # calculate next fib
        mv  t0, t1             # replace prefib by original fib 
        addi  s1, s1, -1       # count how many times left
        bgt  s1, zero, loop    # if s1 > 0 go back loop
        
end:
        mv  a0, s0             # print result
        li  a7, 1
        ecall
        
exit:

## Analysis
We run the code by using [Ripes](https://github.com/mortbopet/Ripes) simulator
### Pseudo instruction
When we write the assembly code in Ripes, it will automatically generate the pseudo instuctions

00000000 <main>:
	0:		10000417		auipc x8 0x10000
	4:		00040413		addi x8 x8 0
	8:		00042403		lw x8 0 x8
	c:		00100493		addi x9 x0 1
	10:		02944263		blt x8 x9 36 <end>
	14:		409404b3		sub x9 x8 x9
	18:		00000293		addi x5 x0 0
	1c:		00100413		addi x8 x0 1

00000020 <loop>:
	20:		00040313		addi x6 x8 0
	24:		00540433		add x8 x8 x5
	28:		00030293		addi x5 x6 0
	2c:		fff48493		addi x9 x9 -1
	30:		fe9048e3		blt x0 x9 -16 <loop>

00000034 <end>:
	34:		00040513		addi x10 x8 0
	38:		00100893		addi x17 x0 1
	3c:		00000073		ecall

### 5-stage RISC-V processor


There are 5 stages in RISC-V processor
* Instruction fetch(IF)
* Instruction decode(ID)
* Execute(EX)
* Memory access(MEM)
* Register write back(WB)

each stages are seperated by pipeline register.

We take instruction `lw s0, 0(s0)` as an example to explain what will it actually do in these 5 stages.

#### **1. Instruction fetch (IF)**
In this stage, it will fetch the machine code of instruction in the insruction memory, also plus 4 to get the next pc


* The address of the insruction is `0x0000002c`
* We input the address and get `instr` as `0xfff48493`
* We plus 4 to the address then we got the address of the next instruction as`0x00000030`

#### **2. Instruction decode (ID)**
In this stage, it will decode the machine code, and also find out the value of in need register


* Instruction `0xfff48493` is decoded to 4 parts
* `opcode` = `ADDI`
* `Wr idx` = `0x09`
* `R1 idx` = `0x09`
* `R2 idx` = `0x1f`
* `0x0000002c` and `0x00000030` are send to this stage to make sure there is no flush to this stage, if it occures, then we will need them. In this case, they are not using.
* `Reg 1 ` and `Reg 2` is the value of `R1 idx` and `R2 idx`, `Reg 1` = `0x0000004`, `Reg 2` = `0x00000000`
* There is also an immediate -1 in the instruction, so we get `0xffffffff` by the `imm.`
*
#### **3. Execution (EX)**
In this stage, we will execute things using ALU and also decide if it will jump when it is a branch instruction


* The ID/EX pipeline register provides `0x00000004`, `0x00000000`, and `0xffffffff` for ALU
* We will chose the two inputs of ALU `Op1` and `Op2`, in this case
`Op1` = `0x00000004`,`Op2` = `0xffffffff`
* ALU will do math to calculae `Res`, `Res` = `0x00000004` + `0xffffffff` = `0x00000003`.
* This instruction isn't a branch instruction, so we don't use Branch

#### **4. Memory access (MEM)**
In this stage we will access the memory if it need the value in data memory.


We don't need the value in data memory in this instruction, but it will still pass MEM stage.

There is another example that will access data memory


This is the instruction `lw x8 0 x8` in MEM stage, it gets the value`0x00000005` by input address `0x10000000`
#### **5. Register write back (WB)**
In this stage we will write the register value if needed


* We pass the value in `Res` to `Wr data`, `0x09` to `Wr idx`
* `Wr data` = `0x00000003`, `Wr idx` = `0x09`
* We write `0x00000003` back to `0x09` as an update of looping number

After all these stage are done, the register is updated like this:


After executing the whole program, the registers are updated like this:


The result is in console


This is the pipeline diagram of the code


We can see there are few places with unfinish instructions


it is because there is a branch instruction in front of them, when the branch decided to jump, it will flush the instructions which execute after it.

## Reference
[Classic RISC pipeline - Wikipedia](https://en.wikipedia.org/wiki/Classic_RISC_pipeline)