# Assignment1: RISC-V Assembly and Instruction Pipeline
contributed by < [`linson`](https://github.com/??????) >
###### tags: `RISC-V`, `jserv`
## Question Description
[Majority Element](https://leetcode.com/problems/majority-element)
> 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.
>
> So inputs like `[2,2,1,3]` the majority element is not exists, since no element's quantity is greater than `2`. i.e. do not satifies the definition of majority element. Below is what Leetcode will show up.
> 
> Follow-up: Could you solve the problem in linear time and in $\mathcal{O}(1)$ space?
:::warning
:warning: I think the assumption in Leetcode is too strong which I think that's the reason why it suggest to answer it in $\mathcal{O}(n)$ time but for now I will working on optimize the assembly rather than generalize the solution.
:notes: linson
:::
## Implementation
### C code
* As we know floor function that takes as input a real number x, and gives as output the greatest integer less than or equal to x.
* So in our case
* $$\frac{2k}{2} = k, k\ \in \mathbb{Z} \\
\frac{2k+1}{2} = k, k\ \in \mathbb{Z}$$
* i.e $\frac{6}{2} = \frac{5}{2} = 3$
* According to the definition of Majority the number of the element
* e.g `[3,2,3]`
* consider the iterator `i` as a length cutter.
* when `i` points to 0. It means array length is 1, i.e in order to be the majority. the number of the element must greater than floor(1/2) = 0.
* when `i` points to 1. It means array length is 2，i.e To become the majority the number of the element must greater than floor(2/2) = 1 。
* In this case `[3,2]` do not contains any element that its quantitiy is greater equal than 2, therefore the array with this length so far do not provides any useful information. So next `i` can be viewed as a whole new array to find majority element.
```clike=
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];
}
```
### Assembly code
#### Testdata
```clike=
.data # the assemble directives, to allocate the space for input variable
nums1: .word 3,2,3 # arr1 = [3,2,3]
numsSize1: .word 3 # arr1 length 3
nums2: .word 2,2,1,1,1,2,2 # arr2 =[2,2,1,1,1,2,2]
numsSize2: .word 7
nums3: .word 2,2,2,5
numsSize3: .word 4
# below is for print function use.
str: .string "The majority element of the array is "
no_str: .string "There is no majority element."
```
#### Main Logic
##### Registers to variables
* `t0 : i`
* `t1 : nums[i]`
* `t2 : nums[index]`
* `s0 : count`
* `s1 : *nums[i]`
* `s2 : numsSize`
* `s3 : *nums[index]`
* `s4 : indexs11 : *nums[0]`
```clike=
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:
```
#### Print
* The `ECALL` instruction is used to make a request to the supporting execution environment, which is usually an operating system. The ABI for the system will define how parameters for the environment request are passed, but usually these will be in defined locations in the integer register file.
* When calling Linux, `a7` is where to ++specify the Linux function number from `unistd.h`++ and registers from `a0` to `a6` contain any parameters.
```clike=
print:
la a0, str #a0 is return value register
li a7,4 # print string by specifiy the value of a7 register t0 4
ecall
add a0, t2, x0 # return value
li a7, 1 # print integer
ecall
```
* 
## Analysis
* By the help of **Ripes**, It is easy to check the performance of the program by cycles per Instruction(CPI)
* The closer CPI toward 1 the better performance.
* Below is performance of mine(under `nums3`).
* 
* It sucks !!.
### Load-use hazard
#### Description
* Load-use hazard means a subsequent instruction read value from a register which sould be written by the memory value read from previous instruction.
* There is no forwarding ability under this pipeline architecture so inserting a `nop(stall)` is needed to solve this issue.
#### Load-use hazard happend in my code
* In this cycle the result of `lw x7(t2) 0 x19` will be write back later, however the `beq` use `x7` right after it.
* So an extra cost of the cycle(`nop`) is insert to keep the logic correct.
#### Find out
* I find out since the definition of majority element, so the propability to run `count++` is higher(since `count[index]` is likely to keep the same). the same concept happens to update which leads to my modifications.
* `if(count == 0) {
index = i;
count = 1;
}`
### Modification
#### Before modification
* 
* 
#### After modification (Note: `arr` is `nums`)
* Change the `beq` to `bne` in the first if-esle( `if(nums[index] == nums[i])`)
* 
* load-use hazard solved, and less unconditional jump
* Change the `bne` to `beq` in the second if-else (`if(count == 0)`)
* 
* 
* The CPI decreases to 1.53 (under *nums3*)
## Reference
* [RISC-V Instruction Set Manual](https://riscv.org//wp-content/uploads/2017/05/riscv-spec-v2.2.pdf)
* [Environmental Calls](https://github.com/mortbopet/Ripes/wiki/Environment-calls)
* [Stephen Smith Blog - Risc-V Assembly Language Hello World](https://smist08.wordpress.com/2019/09/07/risc-v-assembly-language-hello-world/)
Sign in with Wallet
Connect another wallet