# Assignment1: RISC-V Assembly and Instruction Pipeline
contributed by < [509](https://github.com/cicero884) >
###### tags: `computer architure 2021`
[TOC]
## Program
Monotonic Array[(LeetCode 896)](https://leetcode.com/problems/monotonic-array/)
An array is monotonic if it is either monotone increasing or monotone decreasing.
Given an integer array nums, return true if the given array is monotonic, or false otherwise.
### program main logic
Checking the array is increasing or decreasing by comparing the first and the last element, and start to compare whether each element are smaller than or equal to next element in increasing array, or larger than or equal to next element in decreasing array.
If not, store the result with or operation in S4.
### write in C

#include<stdio.h>
#define MAX_ARRAY 100
#define true 1
#define false 0
int input_data[MAX_ARRAY];
int input_size;
_Bool isMonotonic(int* nums, int numsSize){
	if(numsSize<3) return true;
	int i=1,prev=nums[0],now=nums[1];
	_Bool result=false;
	if(prev>nums[numsSize-1]){
		while(i<numsSize){
			result|=(prev < now);
			prev=now;
			++i;
			now=nums[i];
		}
	}
	else{
		while(i<numsSize){
			result|=(prev > now);
			prev=now;
			++i;
			now=nums[i];
		}
	}
	return !result;
}

int main(){
	for(input_size=0;input_size<MAX_ARRAY && scanf("%d",&input_data[input_size])!=EOF; ++input_size);
	//for(int i=0;i<input_size;++i) printf("%d ",input_data[i]);
	//input_data[0]=1;
	//input_data[1]=2;
	//input_data[2]=2;
	//input_data[3]=1;
	//input_size=4;

	if(isMonotonic(input_data,input_size)) printf("true");
	else printf("false");
}

### rewrite in Assembly
search risc-v [isa](https://riscv.org/wp-content/uploads/2017/05/riscv-spec-v2.2.pdf) and [RISC-V Assembly Programmer's Manual](https://github.com/riscv-non-isa/riscv-asm-manual/blob/master/riscv-asm.md) to understand pseudoinstruction and label then write assembly code

.data
input:		.word 1,3,3,4,5
input_size: .word 5
trueStr:	.string "true\n"
falseStr:	.string "false\n"

.text
main:
la		a0, input  
lw		a1, input_size
jal		isMonotonic

#set message
bnez	a0, trueMsg
la 		a1, falseStr 	#false
j		print	
trueMsg:
la 		a1, trueStr 	#true

print:
li 	a0, 1	# 1 = StdOut
li  	a2, 13	# length of our string
li  	a7, 64	# linux write system call
ecall           # Call linux to output the string

#exit
li  a0, 0   # Use 0 return code
li  a7, 93  # Service command code 93 terminates
ecall       # Call linux to terminate the program


isMonotonic:
addi	t0, a1, -3	
bgez	t0 sizeOver3	# jump if input_size > 3
li 	a0, 0		# return true
ret

sizeOver3:
addi	s0, a0, 4	# i(count in address)
lw	s1, 0(a0)	# prev(init with first element)
lw	s2, 4(a0)	# next(init with second element)
slli	s3, a1, 2
add 	s3, s3, a0 	# max_address(&input_data+input_size)
li	s4, 0		# result

lw	t0, -4(s3) 	#l ast element
bgt	s1, t0, decreaseCheckLoop

increaseCheckLoop:
ble	s3, s0, return	# while(i<input_size)(count in address)
slt 	t0, s2, s1 	# next<prev
or 	s4, s4, t0	# result|=next<prev

mv 	s1, s2		# prev=next
addi 	s0, s0, 4	# ++i(count in address)
lw 	s2, 0(s0)	# next=input_data[i]
j increaseCheckLoop

decreaseCheckLoop:
ble	s3, s0, return	# while(i<input_size)(count in address)
slt 	t0, s1, s2 	# prev<next
or 	s4, s4, t0	# result|=(prev<next)

mv 	s1, s2		# prev=next
addi	s0, s0, 4	#++i(count in address)
lw 	s2, 0(s0)	# next=input_data[i]
j decreaseCheckLoop

return:
seqz 	a0, s4	# return !return
ret

## Explaination
### ISA
I separate the pseudoinstructions which used in my program to 5 types
#### R-type
only reg_do_write being set to 1,the others set to zero.
So ALU will use register's data as op1 and op2, and wrte back data with result of ALU to register.
no memory read or memory write.
#### I-type
compare to R-type, alu_op2_ctrl also being set to 1
So ALU will use register's data as op1 and will use imm data as op2, and wrte back data with result of ALU to register.
no memory read or memory write.
#### I-type with memory read
compare to other I-type, mem_do_read also being set to 1
So ALU will use register's data as op1 and will use imm data as op2, output result to memory as address, and wrte back data in memory.
no memory write.
#### B-type
alu_op1_ctrl and alu_op2_ctrl is set to 1, so it will add PC(op1) and imm(op2) together.
do_br is set to 1 .So if the result of branch is set to 1, it will use alu's result as next PC
#### J-type
alu_op1_ctrl and alu_op2_ctrl is set to 1, so it will add PC(op1) and imm(op2) together.
do jump set to 1 .So it will use alu's result as next PC.
reg_do_write being set to 1, it will store PC+4 into memory
### pipeline
#### IF(instruction fetch)
the first mux will deside the next PC should come from PC+4 adder or from ALU(while branch or jump.
The pc will give to instruction memory to get instruction
this stage will send:
1. PC(to be add in ALU)
2. PC+4(write back to memory)
3. instruction
#### ID(instruction decode)
This stage will decode instruction to:
1. Control unit(read opcode then control mux and r&w memory and register)
2. register(get R1&R2 index then output data)
3. imm.(convert instruction to immidiate number)
#### EX(execute)
The two 3to1 mux are for forwarding data from MEM or WB stage
the tow 2to1 mux are for control unit to decide where ALU inputs are from.
||op1|op2|
|-|-|-|
|0|reg|reg|
|1|OP|imm|

ALU will calculate the result.
the branch will compare two value from register to decide whether to branch with the logic gate on the top

if((do_br && branch_taken) || do_jump) PC=alu_res

#### MEM
Get ALU_res as address and signal from control unit to decide memory read and write,wrte date from reg2
#### WB(write back)
The 3to1 mux will decide write back date come from
1. ALU result
2. PC+4
3. Data memory read

#### Other
to make sure data correct and increase efficiency, add Forwarding unit and Hazard control
##### Forwarding unit
This unit will compare reg1&reg2 address in EX state with MEM,WB states then forward data(control 3to1 mux in EX state)
##### Hazard control
There are three type of Hazard need to deal with
1. ALU's op1 or op2 in EX state need read data from MEM state(stall PC_counter&IF_ID and clear ID_EX)
2. jump or branch(clear IF_ID & ID_EX)(not direct draw wire in rips graph)
3. ECALL(request to the supporting execution environment), need to finish all write to register operation before execute it(stall PC_counter,IF_ID,ID_EX and clear EX_MEM)

## Reference
* [LeetCode 896. Monotonic Array](https://leetcode.com/problems/monotonic-array/)
* [Rips](https://github.com/mortbopet/Ripes)
* [The RISC-V Instruction Set Manual](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwibmYajttzzAhXkJKYKHa_4BgYQFnoECAoQAQ&url=https%3A%2F%2Friscv.org%2Fwp-content%2Fuploads%2F2017%2F05%2Friscv-spec-v2.2.pdf&usg=AOvVaw0XfoEuynO3lBpSbNNE0xhm)
* [riscv-asm-manual](https://github.com/riscv-non-isa/riscv-asm-manual)