# Assignment1: RISC-V Assembly and Instruction Pipeline
tag:jserv,hw1
contributed by [Re-Fu-Zhang](https://github.com/Chiwawachiwawa/traping-rain)
## Problem
[Trapping Rain Water (leetcode42)](https://leetcode.com/problems/trapping-rain-water/)
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
## Solution
:::warning
Redraw the graffiti with [Graphviz](https://graphviz.org/).
:notes: jserv
:::
I use two for loop to solve this problem,and it takes three steps to do.
step1.
find the greast value in array,and set it as the middle point.
step2.
After that I do the arr[0] to arr[max],here is the formula of the total rain in this step,how can we do that?
1.maxh=max value in array
2.maxhi=the location(middle point) in array
3.water_l=**it is the most important var in my solution**
if arr[i]>water_l,water_l=arr[i]
step3.
It is very resemblance as step2,we go from arr[i-1](i is the size of array)to arr[maxhi]
step4.
return rain
rain+=water_l-arr[i]
```c
#include<stdio.h>
#include<math.h>
void main(){
int arr[]={20,1,0,2,1,16,1,3,2,1,2,17};
int height=12;
int ans=trap(arr,height);
printf("%d\n",ans);
}
int trap(int* height, int heightSize){
int maxh=0,maxhi;
if(heightSize==0||heightSize==1)
return 0;
for(int i=0;i<heightSize;i++){
if(height[i]>maxh){
maxh=height[i];
maxhi=i;
}
}
int water_l=0;
int rain=0;
for(int i=0;i<maxhi;i++){
if(height[i]>water_l){
water_l=height[i];
}
rain+=water_l-height[i];
}
water_l=0;
for(int i=heightSize-1;i>maxhi;i--){
if(height[i]>water_l){
water_l=height[i];
}
rain+=water_l-height[i];
}
return rain;
}
```
ran on [onlineGDB](https://www.onlinegdb.com/) Sorry sir,I know it's a bad habbit.
# RV32I CODE
```
.data
arr: .word 20,1,0,2,1,16,1,3,2,1,2,17
size: .word 12
.text
main:
la s0 arr
lw s1 size
j findmax
add s2 zero zero #i=0
add s3 zero zero #maxh
add s4 zero zero #maxhi
add s5 zero zero #rain
add s6 zero zero #water_l
findmax:
bge s2 s1 leftmax
add t1 zero s2 #t1=i
add t1 t1 t1 #i*2
add t1 t1 t1 #i*4
add s7 t1 s0
lw t2 0[s7] #arr[i]=t2
blt s3 t2 process1
addi s2 s2 1 #i++
j findmax
process1:
add s4 zero s2 #maxhi=i
add s3 t2 zero #arr[i]=maxh
addi s2 s2 1 #i++
j findmax
leftmax:
mul s2 s2 zero
j process2
process2:
bge s2 s4 maxleft
add t1 zero s2 #t1=s2=i
add t1 t1 t1 #s2*2
add t1 t1 t1 #s2*4
add s7 s0 t1 #s2*4+address
lw t2 0[s7] #t2=arr[i]
blt s6 t2 changeprocess
add s5 s5 s6 #rain=rain+water_l
sub s5 s5 t2 #rain=rain+water_l-arr[i]
addi s2 s2 1 #i++
j process2
changeprocess:
add s6 t2 zero #water_l(s6)=arr[i](t2)
add s5 s5 s6 #rain=rain+water_l
sub s5 s5 t2 #rain=rain+water_l-arr[i]
addi s2 s2 1
j process2
maxleft:
mul s2 s2 zero
mul s6 s6 zero
addi s1 s1 -1
add s2 s2 s1
j process3
process3:
bge s4 s2 print
add t1 s2 zero
add t1 t1 t1
add t1 t1 t1
add s7 t1 s0
lw t2 0[s7]
blt s6 t2 changeprocess2
add s5 s5 s6 #=rain=rain+water_l
sub s5 s5 t2 #rain=rain+water_l-arr[i]
addi s2 s2 -1 #i--
j process3
changeprocess2:
add s6 t2 zero #water_l=t2
add s5 s5 s6 #rain=rain+water_l
sub s5 s5 t2 #rain=rain+water_l-arr[i]
addi s2 s2 -1 #i--
j process3
print:
addi a0 s5 0
li a7 1
ecall
li a7 10
ecall
```
:::warning
:warning: Can you use fewer instructions?
:notes: jserv
:::
:::info
Sure Sir,
The code below is the version I modifed.
I made a new loop called trap and useing register S3 as a tag to distinguish
the two similar loop in my C code!
sorry for the email,I know my question is stupid and rude :persevere:
:::
```
.data
arr: .word 20,1,10,2,1,161,1,3,2,1,2,17
size: .word 12
.text
main:
la t0 arr
lw t1 size
jal a0 findmax
add s1 zero zero
addi s3 zero 1 #tag=1
jal a0 trap
add s2 zero zero #water_l=0
addi s1 t1 -1 #i=size-1
addi s3 zero -1 #tag=-1
jal a0 trap
j print
findmax:
add t2 zero s1 #t2=i
slli t2 t2 2 #t2=4i
add t2 t2 t0 #t2=arr[i] address
lw t3 0(t2) #t3=content of arr[i]
blt t4 t3 change #if max_bar is less than arr[i]
addi s1 s1 1 #i++
blt s1 t1 findmax #if i is less than size,go back
jr a0
trap:
add t2 s1 zero
slli t2 t2 2
add t2 t2 t0
lw t3 0(t2) #t3=arr[i]
blt s2 t3 process #if water_l < arr[i] go process
sub s9 s2 t3 #s9=water_l-arr[i]
add s7 s7 s9 #rain=rain+s9
add s1 s1 s3 #i+tag
bne s1 t5 trap #if s1!=t1 do trap
jr a0
change:
add t4 t3 zero #t4=t3 t4=max_bar
add t5 zero s1 #t5=maxi
addi s1 s1 1 #i++
blt s1 t1 findmax
jr a0
process:
add s2 zero t3 #water_l=arr[i]
add s1 s1 s3 #i+tag
bne s1 t5 trap
jr a0
print:
addi a0 s7 0
li a7 1
ecall
li a7 10
ecall
```
# abi code
```
00000000 <main>:
0: 10000297 auipc x5 0x10000
4: 00028293 addi x5 x5 0
8: 10000317 auipc x6 0x10000
c: 02832303 lw x6 40 x6
10: 0240056f jal x10 36 <findmax>
14: 000004b3 add x9 x0 x0
18: 00100993 addi x19 x0 1
1c: 0380056f jal x10 56 <trap>
20: 00000933 add x18 x0 x0
24: fff30493 addi x9 x6 -1
28: fff00993 addi x19 x0 -1
2c: 0280056f jal x10 40 <trap>
30: 0700006f jal x0 112 <print>
00000034 <findmax>:
34: 009003b3 add x7 x0 x9
38: 00239393 slli x7 x7 2
3c: 005383b3 add x7 x7 x5
40: 0003ae03 lw x28 0 x7
44: 03cecc63 blt x29 x28 56 <change>
48: 00148493 addi x9 x9 1
4c: fe64c4e3 blt x9 x6 -24 <findmax>
50: 00050067 jalr x0 x10 0
00000054 <trap>:
54: 000483b3 add x7 x9 x0
58: 00239393 slli x7 x7 2
5c: 005383b3 add x7 x7 x5
60: 0003ae03 lw x28 0 x7
64: 03c94663 blt x18 x28 44 <process>
68: 41c90cb3 sub x25 x18 x28
6c: 019b8bb3 add x23 x23 x25
70: 013484b3 add x9 x9 x19
74: ffe490e3 bne x9 x30 -32 <trap>
78: 00050067 jalr x0 x10 0
0000007c <change>:
7c: 000e0eb3 add x29 x28 x0
80: 00900f33 add x30 x0 x9
84: 00148493 addi x9 x9 1
88: fa64c6e3 blt x9 x6 -84 <findmax>
8c: 00050067 jalr x0 x10 0
00000090 <process>:
90: 01c00933 add x18 x0 x28
94: 013484b3 add x9 x9 x19
98: fbe49ee3 bne x9 x30 -68 <trap>
9c: 00050067 jalr x0 x10 0
000000a0 <print>:
a0: 000b8513 addi x10 x23 0
a4: 00100893 addi x17 x0 1
a8: 00000073 ecall
ac: 00a00893 addi x17 x0 10
b0: 00000073 ecall
```
# Pipeline stage
## IF
The stage can do two things in parallel: from the catch instruction in memory to the IR (instruction register)
Medium.
add 4 to the PC (program counter), and store the added value in the NPC (next program counter).
## ID
The stage can do three things in parallel: decode the instruction; take the value out of the register; if
Immediate also needs to be read out, and sign-extension (that is, to expand 16bit to 32bit)
## EXE
It might do the following:
A. Do operations, such as: addition, subtraction, multiplication and division
B. Calculate the address of memory
C. If it is branch, calculate the target address and check the jump condition.
## MEM
A. Assign NPC to PC
B. If it is a memory reference (memory access), it is necessary to adjust the memory according to the memory address calculated in EX
Perform read and write operations, if it is load, read data from memory to LMD.
C. If it is a branch, you need to assign the target address calculated in EX to the PC according to the condition
## WB
A. Store the result of the operation back into the register
B. Write the value in LMD in MEM back to register
# Hazard is "danger" and "opportunity"
At the same time, there are data dependencies between multiple instructions executed. These data dependencies can be divided into three categories, namely Read After Write (RAW), Write After Read (WAR) and Write After Write (WAW). Below, we look at each of these situations.
EX:
add s1 s2 s3
add s4 s1 s2
# Pipeline Stall
If we find that the instructions executed later have data-level dependencies on the instructions executed earlier, the easiest way is to "wait again". When we decode the instruction, we will get the registers and memory addresses that the corresponding instruction needs to access. Therefore, at this time, we can judge whether this instruction will trigger a data risk.
If a data risk is triggered, we can decide to stall the entire pipeline for one or more cycles.
Ripes show in nop
# Branch prediction
## Two-bit saturation counter
**If the designer wants the counter to guess more times before changing his mind, we can increase the counter from two bits to three bits, or even more bits. However, a random increase in bits does not necessarily lead to better performance.**
Google Drive
Gist
Clipboard
Sign in with Wallet
