---
# System prepended metadata

title: 'Assignment1: RISC-V Assembly and Instruction Pipeline'

---

# Assignment1: RISC-V Assembly and Instruction Pipeline

## Two Sum II - Input array is sorted

### Intro
This problem is originally based on **Two Sum** ([LeetCode 1](https://leetcode.com/problems/two-sum/)) but with a spacial case that the input array is sorted. The objective of this problem is to find the exact two numbers in the given array whose sum equals to a specific target. 

### Solution
The brute-force solution is to use nested for loop to scan the whole array, but results in the time complexity of $O(n^2)$. A smarter way of solving this is to use a hash table with hash of an array element `num[i]` being `target - num[i]`. By doing so, we would solve the problem in linear time.

### Input array is sorted
The hashing way is generally the best method for the problem. However for the special case which the input array is sorted, doing so may be a waste of time and memory. Instead, we could utilize two pointers, one at the head of the array, another one at the tail of the array. Suming up the 2 numbers that has been pointed to, we compare it with the target. If the sum is larger than the target, we then move the tail pointer one step backward, and vice versa. This way, we could get to the target closer and closer every step until we found the solutions, and the overall time complexity would be $O(n)$.

### C code implementation
```c
#include <stdio.h>
#include <stdlib.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
    int *p = numbers, *q = &numbers[numbersSize - 1];
    while (1) {
        int sum = *p + *q;
        if (sum < target) {
            ++p;
        } else if (sum > target) {
            --q;
        } else {
            int *sol = malloc(2 * sizeof(int));
            sol[0] = p - numbers + 1;
            sol[1] = q - numbers + 1;
            *returnSize = 2;
            return sol;
        }
    }
}

int main(void) {
    int numbers[8] = {2, 3, 5, 7, 11, 13, 17, 19}, target = 12, returnSize, i;
    printf("numbers = ");
    for (i = 0; i < 8; ++i) {
        printf("%d ", numbers[i]);
    }
    printf("\ntarget = %d\n", target);
    int *sol = twoSum(numbers, 8, target, &returnSize);
    printf("sol = ");
    for (i = 0; i < returnSize; ++i) {
        printf("%d ", sol[i]);
    }
    printf("\n");
}
```
The function is straightfoward. It returns an integer array containing two indexes that points the solutions. Note that the [problem requirement](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/) says the array is **1-indexed**, so it's why we do `p + 1` and `r + 1`.

:::info
The implementation:
```c
#include <stdlib.h>

static inline int *mallocRes(int a, int b, int *returnSize)
{
    *returnSize = 2;
    int *res = (int *) malloc(sizeof(int) * 2);
    res[0] = a, res[1] = b;
    return res;
}

int *twoSum(int *numbers, int numbersSize, int target, int *returnSize)
{
    *returnSize = 2;
    int i = 0, j = numbersSize - 1;
    while (i < j) {
        if (numbers[i] + numbers[j] == target)
            return mallocRes(i + 1, j + 1, returnSize);
        numbers[i] + numbers[j] < target ? ++i : --j;
    }
    *returnSize = 0;
    return NULL;
}
```

:notes: jserv
:::

### RISC-V assembly code implementation
```asm
.data
num:    .word 2, 3, 5, 7, 11, 13, 17, 19
target: .word 12
str1:   .string "numbers = "
str2:   .string "\ntarget = "
str3:   .string "sol = "
lf:     .string "\n"
ws:     .string " "
sol:    .word 0, 0

.text
main:
        addi    sp, sp, -16
        sw      ra, 12(sp)      # save ra
        sw      s1, 8(sp)       # num
        sw      s0, 4(sp)       # i

        la      s0, num

        # print "numbers = "
        la      a0, str1
        jal     printStr

        # First for loop
        li      s1, 0           # i = 0
        li      a1, 8           # size = 8
        j       L_for0C
L_for0:
        # Calculate the address of numbers[i] and print the value
        slli    t1, s1, 2
        add     t1, s0, t1
        lw      a0, 0(t1)
        jal     printNum
        addi    s1, s1, 1       # ++i
L_for0C:
        blt     s1, a1, L_for0
L_for0E:

        # Print "target = "
        la      a0, str2
        jal     printStr

        # Print the value of target
        lw      a2, target
        mv      a0, a2
        jal     printNum

        # Print "\n"
        la      a0, lf
        jal     printStr

        # Call subroutine twoSum
        mv      a0, s0          # num
        addi    a3, sp, 0       # &returnSize = 0(sp)
        jal     ra, twoSum
        mv      s0, a0          # sol

        # Print "sol = "
        la      a0, str3
        jal     printStr

        # Second for loop
        li      s1, 0           # i = 0
        lw      t1, 0(sp)
        j       L_for1
L_for1:
        # Calculate the address of sol[i] and print the value
        slli    t2, s1, 2
        add     t2, s0, t2
        lw      a0, 0(t2)       # sol[i]
        jal     printNum

        addi    s1, s1, 1       # ++i
L_for1C:
        blt     s1, t1, L_for1
L_for1E:
        # Print "\n"
        la      a0, lf
        jal     printStr
        
        lw      ra, 12(sp)      # save ra
        lw      s1, 8(sp)       # num
        lw      s0, 4(sp)       # i
        addi    sp, sp, 16

        # Exit program
        li a7, 10
        ecall

# a0: numbers
# a1: numbersSize
# a2: target
# a3: &returnSize
twoSum:
        addi    sp, sp, -12
        sw      s0, 0(sp)       # reserve for p
        sw      s1, 4(sp)       # reserve for q
        sw      ra, 8(sp)

        # p = numbers, q = &number[numbersSize - 1]
        mv      s0, a0
        addi    t0, a1, -1
        slli    t0, t0, 2
        add     s1, a0, t0
L_while:
        lw      t2, 0(s0)
        lw      t3, 0(s1)
        add     t4, t2, t3      # sum = *p + *q
        bge     t4, a2, L_else0
        addi    s0, s0, 4       # ++p
        j       L_if0E
L_else0:
        bge     a2, t4, L_else1
        addi    s1, s1, -4      # --r
        j       L_if0E
L_else1:
        sub     t0, s0, a0      # p - numbers
        srai    t0, t0, 2
        addi    t0, t0, 1       # + 1
        sub     t1, s1, a0      # q - numbers
        srai    t1, t1, 2
        addi    t1, t1, 1       # + 1
        la      a0, sol         # fake malloc
        sw      t0, 0(a0)
        sw      t1, 4(a0)
        li      t0, 2
        sw      t0, 0(a3)       # *returnSize = 2

        # Returning from twoSum
        lw      s0, 0(sp)
        lw      s1, 4(sp)
        lw      ra, 8(sp)
        addi    sp, sp, 12
        jr      ra
L_if0E:
        j       L_while

printStr:
        li      a7, 4
        ecall
        ret

printNum:
        li      a7, 1
        ecall
        la      a0, ws
        li      a7, 4
        ecall
        ret
```

Note that the `malloc()` function is not actually called in my assembly implementation. Instead, I just give it a pre-allocated memory address with label `sol` which is 2 word wide in size. In the `twoSum` subroutine, it uses both `s0` and `s1` register, so it is a must to store the origin value for the caller before modifying the value in it.

:::warning
Can you use fewer instructions?

:notes: jserv
:::

:::info
I think if the index `i` and `j` are replaced with pointers, the codes for computing the memory address in the loop may be omitted. Instead of using indexes, we can just increase/decrease the value of pointers by 4. This way, it reduces instructions in the while loop and may thus speed up the computation.
Besides, since the subroutine `twoSum` is not calling any other subroutines, I think manipulating `sp` as well as storing `ra` and saved registers might be a waste of time? If I can make sure that I am not going to modify any values of these registers, perhaps these instruction could be omitted.
Thanks!
Yuyu
:::

### Output of the program
Both implementation would output the result in either terminal or Ripes' console.
```
numbers = 2 3 5 7 11 13 17 19
target = 12
sol = 3 4
```

## Analysis
Let's take a look at how the above assembly code is being executed with the 5-stage RISC-V CPU of Ripes'.

![](https://i.imgur.com/WiWQXrJ.png)

The following explaination will focus on the algorithm for solveing Two Sum, which starts from `<twoSum+0x10>`.

### IF stage
The upcoming instruction is `addi x8 x0 0`, which is to load the `s0` register with the initial value of zero.

![](https://i.imgur.com/EaUO9Or.png)

In the IF stage, the machine code of the instruction is going to be fetched from the instruction memory and be saved in the IFID register for the manipulation of further stages.

### IF - ID stages

For the next cycle, the instruction advanced to the ID stage, and a new instruction `addi x9 x11 -1` entered the IF stage.

![](https://i.imgur.com/3Ur0f0r.png)

In the ID stage, we can find that:
1. The decoded opcode is `ADDI`
2. The index of Rs1 is `0x00`, x0
3. The immediate value is zero.

### IF - ID - EX stages

All the instruction advanced, and a new one came in.

![](https://i.imgur.com/hgGeXfE.png)

In the EX stage, we can find that:
1. Rd of the instruction is `0x08`, s0
2. Op1 is `0x0`, the value of x0
3. Op2 is `0x0`, the immediate value
4. The multiplexer chooses the value from the previous stage, rather than the forwarded ones.

Also, in the ID stage:
1. The decoded opcode is also `ADDI`
2. The index of Rs1 is `0x0b`, x11, which is the size of the input array
3. The sign-extended value of the immediate value is `0xffffffff`, -1

### IF - ID - EX - MEM stages

![](https://i.imgur.com/FzYtghZ.png)

In the MEM stage, we can find that:
1. The `WrEn` is disabled, for `addi` is not to write the memory
2. The data read from the memory is garbage
3. The Rd is still `0x8`, passed from the previous stage

Also, in the EX stage:
1. Rd of the instruction is `0x09`, s1
1. Op1 is 0x8, which is the array size
2. Op2 is `0xffffffff`, which is to subtract 1 from it

In the ID stage:
1. The decoded opcode is `SLLI`, which is to multiply the array index by 4 to transform it into memory address displacement
2. The index of Rs1 is `0x8`, s0
2. The immediate value is `0x2`

### IF - ID - EX - MEM - WB stages

![](https://i.imgur.com/WcaSvaP.png)

In the WB stage, we can find that:
1. Finally, the result of first instruction is ready to write back
2. The `WrEn` signal of the register file is enabled
3. The destination register is `0x8`
4. The data to write is `0x0`

Also, there is nothing to do with memory for another `ADDI` instruction.

However, in the EX stage, the multiplexer for Op1 selects the forwarded data from WB stage due to data dependency. The mechanism behind this is that the hazard detection unit detected the dependency, or data hazard, which more detailedly is that it found the Rd of WB stage happened to be the same as the Rs in EX stage. Therefore it generates the signal to make the multiplexr select the proper source for ALU in order to ensure the correct result.
