---
###### tags: `Computer Architecture 2022`
---

# Assignment1: RISC-V Assembly and Instruction Pipeline
contributed by < [poweifeng0](https://github.com/poweifeng0) >
## Find the Highest Altitude [LeetCode 1732]

>There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.
>You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i​​​​​​ and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

## Implementaion
You can find the source code [here](https://github.com/poweifeng0/NCKU-RISC-V/tree/main/homework1).

### C code
<!-- Before assembly language, it is better for us to first implement the problem in some high level language. I selected C programming language for my first attemp to implement. -->

The following is my implementation:

#include<stdio.h>
#define gainsize(gain)  sizeof(gain)/sizeof(int)

int largestAltitude(int* gain, int gainSize){
    int i, max, arti;
	arti = 0;
	max=arti;
    for(i=0;i<gainSize;i++){
        arti=arti+gain[i];
        if(arti>max){max = arti;}    
    }
    return max;   
}

int main(){
    
    int gain[]={-1,5,4};
    int gainSize = 3;
    int max = largestAltitude(gain,gainSize);
    printf("max1=%d\n",max);

    int gain2[]={-5,1,5,0,-7};
    gainSize = 5;
    max = largestAltitude(gain2,gainSize);
    printf("max2=%d\n",max);

    int gain3[]={-5,1,3};
    gainSize = 3;
    max = largestAltitude(gain3,gainSize);
    printf("max3=%d\n",max);

    return 0 ;
}

### assembly code

.data
gain: .word -1,5,4
gainsize: .word 3
gain2: .word -5,1,5,0,-7
gainsize2: .word 5
gain3: .word -5,1,3
gainsize3: .word 3

.text
main:
		la s0, gain 	#load gain address
		lw s1, gainsize
		jal func
		la s0, gain2 	#load gain2 address
		lw s1, gainsize2
		jal func
		la s0, gain3 	#load gain3 address
		lw s1, gainsize3
               jal func
		li a7 10
		ecall
func:
		mv t1, x0		#int i = 0
		mv a2, x0		#arti = 0
		mv a3, a2		#max=arti
loop:
               lw a1, 0(s0)           #load gain[i]
		addi s0, s0, 4
		add a2, a2 a1     	#arti=arti+gain[i]
		blt a2, a3 conti       #if arti[i]<max
		mv  a3, a2
conti:
		addi t1, t1 1	        # i++
		blt t1, s1, loop	# i<gainsize jump to loop conti
		mv a0 a3
		li a7 1 
		ecall
		jr ra

### 5-stage pipelined processor
Using the 5-stage pipelined processor to run this code, and observed the format go through different pipleline.
The 5-stage are IF, ID, EX, MEM and WB. There is one pipeline register between two stage.

---
## Analysis
Using the U-type format to analysis each stage. The U-type instruction is designed to put the immediates to the highest and implement the
te 32-bit operate.

### Instruction fetch (IF)
- addr of PC is equal to `0x00000000`, and the represent the first address.
- Next address will increase 4bit, so the first multiplexer is equal to `0x00000004`

### Instruction decode and register fetch (ID)
- the `0x10000417` is decoded.
- first, we can lookup the U-type encoding variants
- according to the above format, U-type includes the 20bit imm., rd and opcode.
- Put the imm. to the first 20 bit, and put zero to fill up last 12 bit, so the output in the imm. block is `0x10000000`.
- The output of the decode includes the `rd`=`0x08`, `opcode` = `aupic`, and two address.
(`auipc rd imm20` will add the PC address and the first 20 bit of immediates to the rd registers )
### Execute (EX)
- ALU unit in this stage is used to calculate the Op1 and Op2 by using AND, OR, add or subtract.
<!-- - But U-type don't have the control signal to the ALU, so the RES is eqal to the Op2. -->
<!-- - Just R-type instruction have the control signal to the ALU. -->

### Memory access (MEM)
- This stage read the value through the addr
- we can lookup the picture below, `0x10000000` in the memory have the word `0xffffffff`.

### Register write back (WB)
- In this stage, the multiplexer will choose a output, and decided by the control block from the ID stage.
- In the above picture, multiplexer choose `0x10000000` and send back to the register block.

### Control hazard
- Control hazard occurs when the branch and jump condition happend.
- In first picture, `jal` instruction get the next address after finishing the EXE stage.
- At the same time, the multiplexer in the IF stage has already get the next PC address. This address is the `func` address.
- In the second picture, after forwarding the next PC address to the ID stage and EXE stage, CPU need to discard the current instruction.
- Finally, the nop in these two stage happened.