Lab1: RV32I Simulator

contributed by < MatthewChen >

tags: RISC-V,Computer Architecture 2022

Find Pivot Index

This problem is based on LeetCode 724.

Given an array of integers nums, calculate the pivot index of this array.

• The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.
• If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.
• Return the leftmost pivot index. If no such index exists, return -1.
  

Implementation

C++

I use 2 variables to track the accumulations of the left-side and right-side. Once the values matches, we find the pivot element.

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int leftSum=0,rightSum=0;
        for(int i=0; i<nums.size(); i++)
            rightSum += nums[i];

        for(int i=0; i<nums.size(); i++){
            rightSum -= nums[i];
            if(leftSum == rightSum){
                return i;
            }else{
                leftSum += nums[i];
            }
        }

        return -1;
    }
};

Assembly

.data
input: .word 1,7,3,6,5,6   #Input array
len:   .word 6             #Length
str:   .string "The answer is "
.text


main:
    lw   s1, len
    la   s2, input
    add  t0, zero,zero     #i=0
    add  t1, zero,zero     #Left sum
    add  t2, zero,s3       #Right sum
    add  s3, zero,s2
sumLoop:
    lw   t3, 0(s3)         #nums[i]
    add  t2, t2,t3         #rightSum += nums[i]
    addi s3, s3, 4         #Pointer sheft
    addi t0, t0, 1         #i++
    blt  t0, s1, sumLoop

    add  t0, zero,zero     #i=0
    add  s3, zero,s2
findLoop:
    lw   t3, 0(s3)         #nums[i]
    sub  t2, t2, t3        #rightSum -= nums[i]
    beq  t1, t2, foundPI   #leftSum == rightSum
    add  t1, t1, t3        #leftSum += nums[i]
    addi t0, t0, 1         #i++
    addi s3, s3, 4         #Pointer sheft
    blt  t0, s1, findLoop

    addi s4, zero, -1      #Not found
    j printAns
    
foundPI:
    add  s4, t0, zero
    j printAns
    
printAns:
    la a0, str             #String
    li a7, 4               #Print string
    ecall
    add a0, s4, zero       #Load answer
    li a7, 1               #Print answer
    ecall
    li a7, 10              #End program
    ecall

This is the basic conversion of C++ program. The register t1 and t2 are the parameter “leftSum” and “rightSum” in C++ code, respectively. If t1 and t2 are equal then jump to foundPI function.

In comarision to C++, only one index increased for each iteration, in the assembly implementation we use two : t0(index) and s3(address).

Analysis

Processing Pipeline

Executions in processor can be divided in to five stages. They are :

1. IF: Instruction fetch
2. ID: Instruction Decode
3. EX: Exceute
4. MEM: Memory read/write
5. WB: Write Back

IF

The instruction is fetched from memory and placed in the instruction register according to the program counter(PC).

add  t2, t2,t3  #x7:t2   x28:t3

This currently loading instruction is at the memory location 0x000024 (marked as red). As shown in picture below, the next instruction is also prepared.

ID

The current instruction are decoded into control signals.
It also moves operands from registers or immediate fields to working registers.
For branch instructions, the branch condition is tested and the corresponding branch address computed.
Interestingly, jump to a function has been translated into the PC deviation.

EX

Where Arithmetic Logic Unit(ALU) locate. Compute according to opcode and get the answer. Include (+ - * / << >> & | …).
For blt intruction, the ALU takes in 2 values (not registers) , original PC and distance.

As a result of hit failure, it turns out to flush some instuctions after that.

MEM

Write data to memory or Read data from memory.

WB

The multiplexer got 0x10000004 (0x10000000 + 4) from ALU and saved it into s3.

Reference

The RISC-V Instruction Set Manual