# Assignment1: RISC-V Assembly and Instruction Pipeline
###### tags: `RISC-V` `computer architure 2021`
# Problem
[70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)

You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
# Problem Analysis
n=1 =>1(1)
n=2 =>2(1,1),(2,0)
n=3 =>3(1,1,1),(1,2)(2,1)
n=4 =>5(1,1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)
n=5 =>8(1,1,1,1,1),(1,1,1,2),(1,1,2,1),(1,2,1,1),(2,1,1,1),(2,2,1),(2,1,2),(1,2,2)

We can see the regular pattern from the above that the current climbing stairs are the sum of the previous one and the one that keeps up with the previous.
So we can write the code as:

#a[i] is the current climbing stairs
#a[i-1] is the previous climbing stairs
#a[i-2] is the climbing stairs that keeps up with the previous
include<stdio.h>
int i,n;
int* arr=(int *)malloc((n)*sizeof(int));
arr[0]=1;
arr[1]=2;
if (n==1)
    return 1;
if (n==2)
    return 2;
for(i=2;i<n;i++)
    {
        a[i]=a[i-1]+a[i-2];
    }
return a[n-1];

and a[i-1] is the answer of this question.

# C Code
I took n=5 as a testbench,and the upper one is my C code.

include<stdio.h>

int main(void)
{

int n=5;
int i=2;
int a=1;
int b=2;
int c;
for(i=2;i<n;i++)
    {
        c=a+b;
        a=b;
        b=c;
    }
printf("%d",b);
}

# Assembly Code

.data
n:     .word 5
.text
main:
    lw s1,n
    addi s3,zero,2 #int i=2
    addi s4,zero,1 #a=1
    addi s5 ,zero,2 #b=2 
for: 
    addi s3,s3,1 #i++
    add s6,s4,s5 #c=a+b
    mv s4,s5   #a=b
    mv s5,s6   #b=c
    beq s3,s1,print #if i==n,print arr[n-1] 
    j for #else do for loop
print:
    mv a0,s5 #equal to addi a0,s5,0
    li a7,1
    ecall  
    

# Pipeline Hazard
There are three types of hazards in pipeline:
1.Structural hazard:
* It occur when hardware resource is not enough in pipeline

2.Data hazard:
* Read after write(RAW)
* Write after write(WAW)
* Write aftre read(WAR)
It occur when the source data of current instruction is come from previous instruction, but previous instruction has not yet write back to register file. As consequence, the current instruction will get incorrect data. It will result in huge problem in pipeline ,so it needed to be solved.

    add s6,s4,s5 
    mv s4,s5   
    mv s5,s6   

In theory,when the program executed mv s5,s6 was encountered into RAW hazard.
Fortunately,there is a line that connect with WB and EXE,so we can forward the result from the WB to EXE.

3.Control hazard:
* The pipelined processor does not know what instruction to fetch next, because the branch decision has not been made by the time the next instruction is fetched.

    blt s3,s1,for 
    j print

In spite of the forwarding line from ALU to PC,there is still two nops after beq.If we want to discrease the delay,maybe we can try to put the comparer after the Register in the ID.So we can discrease one nop and speed up the program operation.