---
# System prepended metadata

title: 'Assignment1: RISC-V Assembly and Instruction Pipeline'

---

# 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/)
![](https://i.imgur.com/2rO2nHb.png)

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**
    ![](https://i.imgur.com/IwMoEf6.png)
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
```


![](https://i.imgur.com/nz1OJRw.png)

                                             
# 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
![](https://i.imgur.com/uLtnvo0.png)
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
![](https://i.imgur.com/xdgj3u4.png)
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
![](https://i.imgur.com/J7ckfPP.png)
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
![](https://i.imgur.com/QbXcjMV.png)
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
![](https://i.imgur.com/caHi53T.png)
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.
![](https://i.imgur.com/9XqGAf7.png)
Ripes show in nop
![](https://i.imgur.com/lX1iYcX.png)


# Branch prediction
## Two-bit saturation counter
![](https://i.imgur.com/fTIi3nE.png)
**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.**