# Lab1: RV32I Simulator
[TOC]
###### tags: `RISC-V` `computer architure 2021`
## Introduction
This question comes from [leetcode 119](https://leetcode.com/problems/pascals-triangle-ii/).
Given an integer `rowIndex`, return the `rowIndex`^th^ (**0-indexed**) row of the **Pascal's triangle**. In **Pascal's triangle**, each number is the sum of the two numbers directly above it as shown:
The original question required the answerer to use the vector data structure, but when I convert c/c++ code to RISC-V assembly code, I changed it to a fixed-size array.
## C++ code([PascalsTriangleII.cpp](https://github.com/newyear2580/computer_architecture_hw1/blob/main/PascalsTriangleII.cpp))
```cpp=
#include<vector>
vector<int> getRow(int rowIndex) {
vector<int> result ;
if ( rowIndex == 0 ) {
result = { 1 } ;
return result ;
} // if
else if ( rowIndex == 1 ) {
result = { 1, 1 } ;
return result ;
} // else if
else { // rowIndex > 1
vector<int> temp ;
result = { 1, 1 } ;
for ( int i = 2 ; i <= rowIndex ; i ++ ) {
temp.push_back( 1 ) ;
for ( int j = 1 ; j < result.size() ; j ++ ) {
temp.push_back( result[j - 1] + result[j] ) ;
} // for
temp.push_back( 1 ) ;
result = temp ;
temp.clear() ;
} // for
return result ;
} // else
} // getRow()
```
## C code([PascalsTriangleII.c](https://github.com/newyear2580/computer_architecture_hw1/blob/main/PascalsTriangleII.c))
```c=
#include<stdio.h>
void swap(int res[34], int temp[34]) {
int a ;
for ( int i = 0 ; i < 34 ; i ++ ) {
a = res[i] ;
res[i] = temp[i] ;
temp[i] = a ;
} // for
} // swap
int main() {
int result[34] = {0} ;
int temp[34] = {0} ;
int rowIndex = 5 ;
int limit = 33 ;
if ( rowIndex < 0 || rowIndex > 33 ) { // error
printf("Input is out of range!\n") ;
return ;
} // if
else if ( rowIndex == 0 ) {
result[0] = 1 ;
} // else if
else if ( rowIndex == 1 ) {
result[0] = 1 ;
result[1] = 1 ;
} // else if
else { // rowIndex > 1
result[0] = 1 ;
result[1] = 1 ;
for ( int i = 2 ; i <= rowIndex ; i ++ ) {
temp[0] = 1 ;
for ( int j = 1 ; j < i ; j ++ ) {
temp[j] = result[j-1] + result[j] ;
} // for
temp[i] = 1 ;
swap(result, temp) ;
} // for
} // else
printf("[%d", result[0]) ;
for ( int k = 1 ; k <= rowIndex ; k ++ ) {
printf(",%d", result[k]) ;
} // for
printf("]\n") ;
} // main()
```
## RISC-V code([PascalsTriangleII.s](https://github.com/newyear2580/computer_architecture_hw1/blob/main/PascalsTriangleII.s))
**1. Store arrays**
- There are two arrays named result array and temporary array.
- The size of both arrays is 34(cell) * 4(size of integer) = 136 bytes.
- I stores arrays in the stack and use register`s1` and register`s2` to point to result array and temporary array.
**2. Input out of the range handling**
- `s3 = rowIndex`.
- When `rowIndex` out of the range, it will print the error message.
- `0 <= rowIndex <= 33`
**3. Conditional branch**
- There will be special cases when `rowIndex == 0` or `rowIndex == 1`.
- When `rowIndex == 0`, output is [1].
- When `rowIndex == 1`, output is [1, 1].
- If it is not for these two special cases, it needs to be handled by loop.
**4. Loop**
- There is a nested loop, an inner loop within an outer loop.
- The outer loop uses *i*(register `s4`) to verify whether to end itself.
- The inner loop uses *j*(register `s5`) to verify whether to end itself.
```clike=
.data
str1: .string "["
str2: .string ","
str3: .string "]\n"
str4: .string "Input is out of range!\n"
# input limit is 0~33, rowIndex is the input number
# Use stack to store result array and a temporary array
# the largest case of the array is 34 cells
# Because of the size of int is 4 bytes, the array's size is 34*4 = 136 bytes
# s0: input limit
# s1: address of result array in the stack
# s2: address of temporary array in the stack
# s3: rowIndex
# s4: outerLoop i
# s5: innerLoop j
.text
main:
addi sp, sp, -272 # initialize the space of the two arrays
addi s1, sp, 136 # address of result array
add s2, sp, zero # address of temporary array
addi s3, zero, 5 # rowIndex = 5
li s0, 33 # input limit is 33
blt s3, zero, error # if ( rowIndex < 0 ) goto error
bgt s3, s0, error # if ( rowIndex > 33 ) goto error
add t0, zero, zero # t0 = 0
beq s3, t0, input0 # if ( rowIndex == 0 ) goto input0
addi t0, zero, 1 # t0 = 1
beq s3, t0, input1 # if ( rowIndex == 1 ) goto input1
j other # rowIndex > 1
input0:
addi t0, zero, 1 # t0 = 1
sw t0, 0(s1) # result array = {1}
j printArr
input1:
addi t0, zero, 1 # t0 = 1
sw t0, 0(s1) # result array = {1}
sw t0, 4(s1) # result array = {1,1}
j printArr
other:
addi t0, zero, 1 # t0 = 1
sw t0, 0(s1) # result array = {1}
sw t0, 4(s1) # result array = {1,1}
li s4, 2 # s4 = i, initialize to 2
outerLoop:
bgt s4, s3, printArr # if ( i <= rowIndex ) then loop, else goto printArr
sw t0, 0(s2) # temporary array = {1}
add t1, zero, t0 # t1 is index of temporary array start from 1
add s5, zero, t0 # s5 = j, initialize to 1
innerLoop:
bge s5, s4, outerIncre # if ( j < i ) then loop, else goto outerIncre
slli t2, t1, 2 # t2 is the offset to access temporary array
add t2, t2, s2 # t2 is the address of temp[j]
addi t3, s5, -1 # t3 = j - 1
slli t3, t3, 2 # t3 is the offset
add t3, t3, s1 # t3 is the address of result[j - 1]
lw t3, 0(t3) # t3 = result[j - 1]
add t4, s5, zero # t4 = j
slli t4, t4, 2 # t4 is the offset
add t4, t4, s1 # t4 is the address of result[j]
lw t4, 0(t4) # t4 = result[j]
add t3, t3, t4 # t3 = result[j - 1] + result[j]
sw t3, 0(t2) # temp[j] = result[j - 1] + result[j]
addi t1, t1, 1 # t1 = t1 + 1, t1 is index of temporary array
addi s5, s5, 1 # j = j + 1
j innerLoop # goto innerLoop
outerIncre:
add t2, s4, zero # t2 = i
slli t2, t2, 2 # t2 is the offset
add t2, t2, s2 # t2 is the address of temp[i]
sw t0, 0(t2) # temp[i] = 1
add t2, s1, zero # exchange the addresses of
add s1, s2, zero # result array and temporary array
add s2, t2, zero
addi s4, s4, 1 # i = i + 1
j outerLoop # goto outerLoop
printArr:
add t0, zero, zero # k = 0, index of print loop
la a0, str1 # load label str1, which is "["
li a7, 4 # a7 = 4, which means ecall will print a string
ecall
slli t1, t0, 2 # t1 is the offset
add t1, t1, s1 # t1 is the address of result[0]
lw t1, 0(t1) # t1 = result[0]
add a0, t1, zero # a0 = result[0]
li a7, 1 # a7 = 1, which means ecall will print a integer
ecall
addi t0, t0, 1 # k = 1
printLoop:
bgt t0, s3, printStr3 # if ( k <= rowIndex ) then loop, else goto printStr3
la a0, str2 # load label str2, which is ","
li a7, 4 # a7 = 4, which means ecall will print a string
ecall
slli t1, t0, 2 # t1 is the offset
add t1, t1, s1 # t1 is the address of result[k]
lw t1, 0(t1) # t1 = result[k]
add a0, t1, zero # a0 = result[k]
li a7, 1 # a7 = 1, which means ecall will print a integer
ecall
addi t0, t0, 1 # k = k + 1
j printLoop
printStr3:
la a0, str3 # load label str3, which is "]\n"
li a7, 4 # a7 = 4, which means ecall will print a string
ecall
j exit # goto exit
error:
la a0, str4 # load label str4, which is the error message
li a7, 4 # a7 = 4, which means ecall will print a string
ecall
exit:
addi sp, sp, 272 # release stack space
```
## Result
The following figure shows the case where the input is 0, 1, ..., 5.
The following figure shows the case where the input is 10 and the maximum value is 33.
## How to use ?
Change the immediate value on line 23 and change it to the number you want to test. This action is to change the value of rowIndex.
## RISC-V assembly code works on Ripes
**Ripes provides a 5-stage RISC-V pipeline processor.**
***
**1. Store arrays**
- The stack segment is near the top of memory with high address. If you use the stack space, you need to subtract the stack pointer from the space you want to use.
- `addi sp, sp, -272` use to initialize the space in the stack for result array and temporary array.
- Register`sp` will be written when instruction at `addi sp, sp, -272` WB stage. RegWrt signal will be enable by setting to 1.
***
**2. Input out of the range handling**
- For example, `rowIndex == -1`, branch to label`error` and then print the error message.
- When instruction`blt s3, zero, error` at EXE stage, BRANCH signal will be enable by setting to 1.
- Because of the **control hazard**, it need to flush two cycles to get correct address of next instruction.
***
**3. Conditional branch**
- Similar to the second point.
***
**4. Loop**
- Use innerloop as an example, instruction `bge x21 x20 64` means `if ( j < i ) then innerLoop, else goto outerIncre`.
***
**5. Load word**
- If the source register of the next instruction of instruction`lw` uses the destination register of instruction`lw`, data hazard will occur. At this time, a nop should be used to avoid it.
Sign in with Wallet
Connect another wallet