# Lab1: R32I Simulator
This is a permutations with recursive method.
It is just a simple implemention of assembly code. The main purpose here is to understand the concept of pipelining and hazard.

# This example shows an implementation of the
# mathematical combintation formula.
.data
argument: .word 7 5

.text 
main:                       # Initialize the register of argument
	addi a2, zero, 0x7   # The n of nCk
	addi a3, zero, 0x5   # The k of nCk
	addi a0, zero, 0     # The return value of nCk
	jal comb             # Begin the routine of comb
	j end                # After finished, goto end:
comb:
	addi sp, sp, -12     # Create stack
	sw ra, 8(sp)         # Save return address
	sw a2, 4(sp)         # Save caller argument $a2(The n of nCk)
	sw a3, 0(sp)         # Save caller argument $a3(The k of nCk)
	beq a2, a3, if       # Jump if nCn == 1
	beq a3, zero, if     # Jump if nC0 == 1
	addi a2, a2, -1      # Sub 1 from $a2
	addi a3, a3, -1      # Sub 1 from $a3
	jal comb             # The recursion of (n-1)C(k-1)
	lw a3, 0(sp)         # Restore $a3 to $a3 + 1
	jal comb             # The recursion of (n-1)C(k) 
	lw ra, 8(sp)         # Restore $ra, $a2, $a3
	lw a2, 4(sp)         # ''
	lw a3, 0(sp)         # ''
	addi sp, sp, 12      # Pop the stack
	jr ra                # Return to ${ra}
if:
	addi sp, sp, 12      # Pop the stack
	addi a0, a0, 1       # Add 1 to ${a0}
	jr ra                # Return to ${ra}
end:

## The Recursion of combination
We all know the combination with recursion can be represented by the following expression.
\begin{split}C^{n}_{m} = C^{n-1}_{m-1} + C^{n-1}_{m}\end{split}

## Pipeline
Pipeline consists of main five stages, IF, ID, EX, MEM and WB, these stages have the following works.
- `IF` (Instruction Fetch) :
- The stage to fetch the instructions. The instruction will be fetched depending on the PC (Program Counter), which points the address of the instruction.
- PC (Program Counter) typically will plus 4 after fetching a instruction. Sometimes, however, PC will be forced to change to some specific address because of some instructions like `jal`, `j`, `bne` and `beq`,etc.

- `ID` (Instruction Decode) :
- Instructions are represented in a 4 bytes, that is 32 bit, and it has three types of instructioin.
- R series
- Register base instruction
- I Series
- Immediate base instruction
- J Series
- Jump base instruction
- Each instructions have some info to be decoded, this stage is doing such job to extract the information out.
- Each series of instruction will encounter some sitution when they are in successive order.

- ==Hazard==
- `RAR` (Read after Read)
- It will not occurred neither `Hazard`.
- `WAR`
- It will encounter some `Hazard` , when some register are been read immediately after it write back by the previous instruction.
- `RAW`
- It will not encounter `Hazard` & `Stall`.
- `WAW`
- It will not encounter `Hazard`
- In order to handle the problems above, designers make a series `control signal` to detect the problems before the `EX` stage.
- `Register Dst`
- Control the write back target(`rs, rd`).
- `ALU Control`
- Control the ALU which operation to execute.
- `PC Src`
- Control whether to jump or just plus 4 to next instruction address.
- `ALU Src`
- Control the input of value is immediate value (I series) or in register (R series).
- `Zero`
- Which is a signal to handle the branch instruction whether tell PC to jump or not. It can be optimized to the ID stage.
- `Mem Write`
- Control whether overwrite the memory
- `Mem Read`
- Control whether read from memory or not.
- `Mem Reg`
- Control the source of WB in memory or ALU.

- The above signals are been defined well. Then ID will decode the instruction into these signals to control the behavior of components and be used to detect `Hazard`.

- `EX` (Execution)
- This stage will execute the operation when encounter `R series` instructions, such like `Add`, `Sub`, `mul`, `mov`, `beq` and `jal`, etc. Such instruction will need `ALU` to finish the tasks.
- `add` - `ALU` will execute the add operation.
- `beq` - `ALU` will check whether the condition is true or not in order to control the PC with `zero` flag.
- However, such jobs can be decided before `EX` stage, that is ,it can be implemented in `ID` stage.
- `jal` - `ALU` will calculate the final address then send it to PC.

- `MEM` (Mem structure)
- `MEM` store the data and some address information. Then, instructions can decided to load the content from memory or store some values to memory.
- We need `MemWrite` & `MemRead` to control whether writting or reading to or from memory, respectively.

- `WB` (Write Back)
- The important stage to return the result of some instruction back to specfic register.
- Especially in pipeline, we need to store the info of which register to be written back.
- And, it has a signal, called `MemReg`,to control the source from `MEM` or `ALU`.

## Description

- `addi a2, zero, 0x7`, `addi a3, zero, 0x5` and `addi a0, zero, 0`
- which will set the value to 7 into register `$a2`
- ID
- `ALU Src` signal will be set to receive the imme value, `0x7`.
- EX
- `ALU` will receive the value from imme.


- MEM
- `nop`
- WB
- Write back to the register `$a2`
- Write signal is `true`

-
- The same as above
-
- The same as above

- `jal comb`
- After compile this, ripes will translate the `comb` label to a absolute address.
- This instruction will store the next the address of itself plus 4 and then jump to the specified address.
- ID
- It will be known that it is a jump instruction.
- It calculate the address with an add ALU.
- WB
- Write back the itsel plus 4 address back to `$ra` register.

- `sw ra, 8(sp)`, `sw a2, 4(sp)`, `sw a3, 0(sp)
- ID
- The MemWrite will be set
- EX
- Calculate the address.
- MEM
- Then it store the

- `beq a2, a3, if`, `beq a3, zero, if`
- ID
- It will be compared in this stage
- EX
- This is optimized to nothing to do with this instruction.