Lab1: RV32I Simulator

contributed by < MatthewChen >

tags: RISC-V,Computer Architecture 2021

Fruits into Baskets

This problem is based on LeetCode 904.

Given a farm that has a single row of fruit trees arranged from left to right.

• You only have two baskets, and each basket can only hold a single type of fruit.
• Starting from any tree of your choice, you pick the fruit into your basket.
• There is no limit on the amount of fruit each basket can hold.
• However, once you reach a tree with fruit that cannot fit in your baskets, you must stop.
• Return the maximum number of fruits you can pick.

C++

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        if(fruits.size()<3)
            return fruits.size();
        
        int tempmax = 1, max = 1, cnum = 1;
        int temp1 = fruits[0], temp2 = fruits[1];

        for(int i=1; i<fruits.size(); i++){
            if (fruits[i] !=  temp1 && fruits[i] !=  temp2){
                temp1 = fruits[i-1];
                temp2 = fruits[i];
                tempmax = cnum + 1;
            }else
                tempmax += 1;
            if (tempmax > max)
                max = tempmax;
            if (fruits[i] !=  fruits[i-1])
                cnum = 1 ;
            else
                cnum += 1;
        }
        return max;
    }
};

Assembly code

.data
trees: .word 3,3,3,1,4   #Line of trees
len:   .word 5           #Length
str:   .string "The answer is "
.text


main:
    lw   s1, len
    addi t1, zero, 3
    blt  s1, t1, lessThanThree
    addi s2, zero, 1  #max
    addi s3, zero, 1  #tempMax
    addi s4, zero, 1  #cnum
    la   s5, trees
    lw   s6, 0(s5)    #temp1
    addi s5, s5, 4
    lw   s7, 0(s5)    #temp2
    la   s5, trees
    addi s9, zero, 1  #i? counter

loop:
    lw   t1, 0(s5)    #t1 = fruits[i-1]
    addi s5, s5, 4
    lw   t2, 0(s5)    #t2 = fruits[i]
    beq  t2, s6, oldFruit
    beq  t2, s7, oldFruit
    addi s6, t1, 0    #temp1 = fruits[i-1]
    addi s7, t2, 0    #temp2 = fruits[i]
    addi s3, s4, 1    #tempmax = cnum + 1
loop1:
    blt  s2, s3, maxUpdate
loop2:
    addi s9, s9, 1
    beq  s9, s1, finishP
    bne  t1, t2, newCounter
    addi s4, s4, 1
    j loop

oldFruit:
    addi s3, s3, 1    #tempmax += 1
    j loop1

newCounter:
    addi s4, zero, 1  #cnum reset
    j loop

maxUpdate:
    addi s2, s3, 0    #max = tempmax
    j loop2

lessThanThree:
    add a0, s1, zero
    li a7, 1          #print size
    ecall
    li a7, 10         #end program
    ecall

finishP:
    la a0, str        #string
    li a7, 4          #print string
    ecall
    add a0, s2, zero  #load answer
    li a7, 1          #print max
    ecall
    li a7, 10         #end program
    ecall

Compiled Memory

00000000 <main>:
	0:		10000497		auipc x9 0x10000
	4:		0144a483		lw x9 20 x9
	8:		00300313		addi x6 x0 3
	c:		0864c063		blt x9 x6 128 <lessThanThree>
	10:		00100913		addi x18 x0 1
	14:		00100993		addi x19 x0 1
	18:		00100a13		addi x20 x0 1
	1c:		10000a97		auipc x21 0x10000
	20:		fe4a8a93		addi x21 x21 -28
	24:		000aab03		lw x22 0 x21
	28:		004a8a93		addi x21 x21 4
	2c:		000aab83		lw x23 0 x21
	30:		10000a97		auipc x21 0x10000
	34:		fd0a8a93		addi x21 x21 -48
	38:		00100c93		addi x25 x0 1

0000003c <loop>:
	3c:		000aa303		lw x6 0 x21
	40:		004a8a93		addi x21 x21 4
	44:		000aa383		lw x7 0 x21
	48:		03638663		beq x7 x22 44 <oldFruit>
	4c:		03738463		beq x7 x23 40 <oldFruit>
	50:		00030b13		addi x22 x6 0
	54:		00038b93		addi x23 x7 0
	58:		001a0993		addi x19 x20 1

0000005c <loop1>:
	5c:		03394463		blt x18 x19 40 <maxUpdate>

00000060 <loop2>:
	60:		001c8c93		addi x25 x25 1
	64:		029c8e63		beq x25 x9 60 <finishP>
	68:		00731a63		bne x6 x7 20 <newCounter>
	6c:		001a0a13		addi x20 x20 1
	70:		fcdff06f		jal x0 -52 <loop>

00000074 <oldFruit>:
	74:		00198993		addi x19 x19 1
	78:		fe5ff06f		jal x0 -28 <loop1>

0000007c <newCounter>:
	7c:		00100a13		addi x20 x0 1
	80:		fbdff06f		jal x0 -68 <loop>

00000084 <maxUpdate>:
	84:		00098913		addi x18 x19 0
	88:		fd9ff06f		jal x0 -40 <loop2>

0000008c <lessThanThree>:
	8c:		00048533		add x10 x9 x0
	90:		00100893		addi x17 x0 1
	94:		00000073		ecall
	98:		00a00893		addi x17 x0 10
	9c:		00000073		ecall

000000a0 <finishP>:
	a0:		10000517		auipc x10 0x10000
	a4:		f7850513		addi x10 x10 -136
	a8:		00400893		addi x17 x0 4
	ac:		00000073		ecall
	b0:		00090533		add x10 x18 x0
	b4:		00100893		addi x17 x0 1
	b8:		00000073		ecall
	bc:		00a00893		addi x17 x0 10
	c0:		00000073		ecall

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 (Instruction fetch)

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

addi s2, zero, 1  #max

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

ID (Instruction Decode)

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.

EX (Exceute)

Where Arithmetic Logic Unit(ALU) locate. Compute according to opcode and get the answer. Include (+ - * / << >> & | …).

MEM (Memory read/write)

Write data to memory or Read data from memory.

lw   s1, len

Load the length of list into register s1.

WB (Write Back)

Write the result back to register.
The multiplexer add zero and 1 from ALU as final output. So the output value is 0x00000001.

Reference

The RISC-V Instruction Set Manual