# Lab2: RISC-V Toolchain
###### tags: `RISC-V` `Jserv` `Computer Architecture`
## Rewrite [Majority Element(Leetcode 169)](https://leetcode.com/problems/majority-element/) from [何坤霖](https://hackmd.io/@dgKSmDN0T_quhIoU9NVThA/BJapX2U-s)
- **Problem Description:**
Given an array nums of size n, return the majority element.The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
- **Motivation:**
I choose the problem because the problem is pretty easy ostensibly, but to meet the request it need some tricky skills.
- **What I understand and enhance the problem based on [何坤霖](https://hackmd.io/@dgKSmDN0T_quhIoU9NVThA/BJapX2U-s)'s method**
The problem request us to solve the problem in linear time and O(1) space.
The very fisrt thought of mine is use double loop to find frequency of every element brutly, but of course it cost(n^2) and didn't work(TLE).
Next I use map to enhance the thought above, and it work but cost O(N) space.
So I find a algorithm not so intiotive, but solve the problem in linear time and cost N(1) space named **Boyer–Moore majority vote algorithm**, and obviously the original C code used this to solve the problem.
The detail about the problem [何坤霖](https://hackmd.io/@dgKSmDN0T_quhIoU9NVThA/BJapX2U-s) has explained clearly, now I just want to show a tiny change I enhance from his code.
- **C code enhancement**
```C =
int majorityElement(int* nums, int numsSize){
int count = 1;
int index = 0;
for(int i = 0; i < numsSize; i++){
if(nums[index] == nums[i])
count++;
else
count--;
if(count == 0) {
index = i;
count = 1;
}
}
return nums[index];
}
```
Above is his C implementation about this problem.
We can see that:
```C =
int index = 0;
```
He let the index to be the first element in the input array,and:
```C =
for(int i = 0; i < numsSize; i++){
if(nums[index] == nums[i])
count++;
```
In this part he compare the first element with input array to the elements of input array from head.
Question is, he take the **First** element to compare with the whole input array, and **the loop start from 0 **. That means it should **start from i=1**
So the code I enhance is as below:
```C =
int majorityElement(int* nums, int numsSize){
int count = 1;
int index = 0;
for(int i = 1; i < numsSize; i++){
if(nums[index] == nums[i])
count++;
else
count--;
if(count == 0) {
index = i;
count = 1;
}
}
return nums[index];
}
```
(The change and enhancement are really tiny LUL)
```Assembly=
The corresponding RISC-V code is below:
main:
la s11, nums3 # *nums[0]
la s1, nums3 # *nums[i]
lw s2, numsSize3 # numsSize
add t0, x0, x0 # i = 0
add s4, x0, x0 # index = 0
add s3, s1, x0 # *nums[index]
addi s0, x0, 1 # count = 1
jalr ra, x0, forloop # jump to forloop 48
j print # jump to print to display result on console.
forloop:
lw t1, 0(s1) # t1 = nums[i]
lw t2, 0(s3) # t2 = nums[index]
beq t1, t2, countpp # nums[i] == nums[index], bracnch to count++
addi s0, s0, -1 # count--
j cont
countpp:
addi s0, s0, 1 # count++
cont:
bne s0, x0, else # if count == 0 jump to update
jal t4 update
else:
# for-loop control
addi t0, t0, 1 # ++i
addi s1, s1, 4 # nums[i++]
bltu t0, s2, forloop # if i < len, go to for loop
jalr x0, ra, 0 # return to main
update:
add s4, t0, x0 # index = i
slli t3, t0, 2 # i*4
add s3, s11, t3 # *nums[index] = *arr[0] + i*4
addi s0, x0, 1 # count = 1
jalr x0, t4, 0
exit:
```
## The bug in original RISC-V code
First I copy and paste the original RISC-V code into ripes and run it. Then I finded someting wrong soon.
I try different input data and I find the following case:
```Assembly=
nums: .word 5,1,6,5
```
will print:
```=
The majority element is 6
```
In normal case like
```Assembly=
nums: .word 1,1,6,1
``
will print:
```=
The majority element is 1
```
The reason of the difference is that the original code didn't set num[index] in the last part.
Take the first case for example, index = 0 initially, and then the index will change to 6 due to count equal to 0.
And then the count will equal to 1 and turn to be 0 because nums[2] (6) didn't equal to nums[3] (5), so index turn to be 3.
But next the original code didn't renew the riegister, it just print the old register value, which is nums[2].
So the result is 6.
The older nums[index] in the second case is equal to 1, though the code didn't renew the register, the result still be true.
So I modified it as below:
```Assembly=
main:
la s11, nums3 # *nums[0]
la s1, nums3 # *nums[i]
lw s2, numsSize3 # numsSize
add t0, x0, x0 # i = 0
add s4, x0, x0 # index = 0
add s3, s1, x0 # *nums[index]
addi s0, x0, 1 # count = 1
jalr ra, x0, forloop # jump to forloop 48
beq s0,x0,last_update # If count is equal to 0 and is in the end of the loop
last_update:
lw t2, 0(s3) # Set t2 to the newest nums[index]
j print # jump to print to display result on console.
forloop:
lw t1, 0(s1) # t1 = nums[i]
lw t2, 0(s3) # t2 = nums[index]
beq t1, t2, countpp # nums[i] == nums[index], bracnch to count++
addi s0, s0, -1 # count--
j cont
countpp:
addi s0, s0, 1 # count++
cont:
bne s0, x0, else # if count == 0 jump to update
jal t4 update
else:
# for-loop control
addi t0, t0, 1 # ++i
addi s1, s1, 4 # nums[i++]
bltu t0, s2, forloop # if i < len, go to for loop
jalr x0, ra, 0 # return to main
update:
add s4, t0, x0 # index = i
slli t3, t0, 2 # i*4
add s3, s11, t3 # *nums[index] = *arr[0] + i*4
addi s0, x0, 1 # count = 1
jalr x0, t4, 0
exit:
```
In line 165 to 167, I write a condition branch to let the final result to news nums[index].So the code works, the result is correct!
## Performance comparison
As I mentioned above, the for loop don't need to start with 1, so I compared the performance of the two version, of course in the correct version .
- i start from 0
- i start from 1
The total cycles are 1.2x lesser then original code!
## -O0 Optimized Assembly Code
compile hw2.C file
> riscv-none-elf-gcc -march=rv32i -mabi=ilp32 -O1 -o hw2.out hw2.c
Size
> riscv-none-elf-size hw2.out
ELF
> riscv-none-elf-readelf -h hw2.out
## -O1 Optimized Assembly Code
compile hw2.C file
> riscv-none-elf-gcc -march=rv32i -mabi=ilp32 -O0 -o hw2.out hw2.c
Size
> riscv-none-elf-size hw2.out
ELF
> riscv-none-elf-readelf -h hw2.out
## -O2 Optimized Assembly Code
compile hw2.C file
> riscv-none-elf-gcc -march=rv32i -mabi=ilp32 -O2 -o hw2.out hw2.c
Size
> riscv-none-elf-size hw2.out
ELF
> riscv-none-elf-readelf -h hw2.out
## -O3 Optimized Assembly Code
compile hw2.C file
> riscv-none-elf-gcc -march=rv32i -mabi=ilp32 -O3 -o hw2.out hw2.c
Size
> riscv-none-elf-size hw2.out
ELF
> riscv-none-elf-readelf -h hw2.out
Google Drive
Gist
Clipboard
Sign in with Wallet
