# R32I Simulator
contributed by < `eddie9712` >
## Testing environment:

eddie@eddie-V5-591G:~$uname -a 
Linux eddie-V5-591G 4.15.0-118-generic #119~16.04.1-Ubuntu SMP Tue Sep 8 14:54:40 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

eddie@eddie-V5-591G:~$gcc --version
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609

## Download and Install Ripes simulator
* Download the simulator which simulate the behavior on risc-v pipeline
* Download [here](https://github.com/mortbopet/Ripes/releases)
* Choose the file `Ripes-v2.1.0-linux-x86_64.AppImage`
* After download the file ,run `sudo ./Ripes-v2.1.0-linux-x86_64.AppImage`
* When I execute thed command above,I ran into an issue of `.../libstdc++.so.6:version 'GLIBCXX_3.4.22' not found(...)`
* **solved**:Followed the steps from [here](https://github.com/lhelontra/tensorflow-on-arm/issues/13) ,because the version of `libstdc++.so.6` is too old , so I ran the commands below to upgrade:

  sudo add-apt-repository ppa:ubuntu-toolchain-r/test
  sudo apt-get update
  sudo apt-get install gcc-4.9
  sudo apt-get upgrade libstdc++

## Using riscv-gnu-toolchain

Reference [here](https://github.com/riscv/riscv-gnu-toolchain)

1.(terminal)After download and install the Risc-v and c cross-compiler ,We can use this tool to compile our C code:
(with the architecture rv32ima)

e.g.
We have a program `hello.c`:

void main() 
{ 
  int a=3; 
  int b=4; 
  int c; 
  c=a*b; 
}

So we can use riscv-gnu-toolchain to compile this program like:
` riscv32-unknown-linux-gnu-gcc -S hello.c`
>-S means Compile only; do not assemble or link.(If you would like to know more about the `riscv32-unknown-linux-gnu-gcc` command,run the command `riscv32-unknown-linux-gnu-gcc --help`)

then we can get the result `hello.s`(assembly code):

        .file   "hello.c"
        .option nopic
        .text
        .align  2
        .globl  main
        .type   main, @function
main:
        addi    sp,sp,-32
        sw      s0,28(sp)
        addi    s0,sp,32
        li      a5,3
        sw      a5,-20(s0)
        li      a5,4
        sw      a5,-24(s0)
        lw      a4,-20(s0)
        lw      a5,-24(s0)
        mul     a5,a4,a5
        sw      a5,-28(s0)
        nop
        lw      s0,28(sp)
        addi    sp,sp,32
        jr      ra
        .size   main, .-main
        .ident  "GCC: (GNU) 10.2.0"
        .section        .note.GNU-stack,"",@progbits

However, we can't use this assembly code directly in the Ripes simulator(will get some errors),so we need to adjust the code after compiling

2.(In Ripes simulator)We can add the path for installing toolchain into the Ripes simulator:

Edit->Settings->Editor

After we add the path to the compiler we have downloaded berfore ,we can compile the C code and run in the Ripes simulator directly.

## Illustrate IF, ID, IE, MEM, and WB stages
Take the first instruction(`mat_modify.s`) for example:
**addi x2 x2 -80**
=>0xfb010113 at address 0x00000000 in text section

So the -80=>b0 and sign-extended to fb0
x2=>0x02 (rs1)
x2=>0x02 (rd)
* IF(Instruction fetch)
The instruction being read from memory(address in PC) ,and the PC address is incremented by 4 and written back to PC
(The first instruction is at address 0X00000000)
* ID(Instruction decode)
At this stage the instruction will be decoded for different purpose ,and the immediate field will be extended to 32 bits

We can see the picture below:

We get **0x7ffffff0** for reading the Rs1 register(X2) ,and get **0xffffffb0** for sign-extending -80

* IE(EX)
At the IE stage ,there are many actions being taken. It will check whether the instruction is branch or not ,and it will decide the branch target address ,calculate the arithmetic result...etc.In this case ,we can see the multiplexer is enabled which make the sign-extended result(0xfffffb0) pass. And the result will add to the content of X2(0x7fffff0) ,here we can also find that the number 0x02(X2 register) is passing simutaneously.
* MEM
If the memory relation instructions(lw,sw...) are at this stage ,the data memory will be enabled ,It will use the adress and the data to load or store the data .In this case we get the result(0x7fffffa0) pass through the MEM stage
* WB
At this stage ,It will write the results might from arithmetic calculating,or memory accessing or PC+4(hazard detection) to the specific register or mutliplexer. Here we get (0x7fffffa0) from arithmetic calculating ,and write it back to the register X2(display 0x02).
## Matrix multiplication
To find the result of the multiplication of 2 $\times$ 2 martix ,so I hold the two matrices for example:

$$
\begin{bmatrix}
1 & 2 \\
3 & 4 \\
\end{bmatrix}
\times
\begin{bmatrix}
5 & 6 \\
7 & 8 \\
\end{bmatrix}=?
$$

### C code

There is a program of matrix multiplication `mat.c`:

#include<stdio.h>
int main()
{
   int matrix[2][2]={1,2,3,4};   //an 2*2 square matrix
   int matrix2[2][2]={5,6,7,8};
   int new[2][2]={0};
   int i,j,k;
   for(i=0;i<2;i++){
    for(j=0;j<2;j++){
      for(k=0;k<2;k++)
        new[i][j]+=matrix[i][k]*matrix2[k][j];
     }
  }
   
}

### Assembly code:
And then we can run the command ` riscv32-unknown-linux-gnu-gcc -S mat.c` to get the assembly code [here](https://github.com/eddie9712/Computer_Architecture/blob/main/riscv/Lab1/mat.s). However,to execute the program on the Ripes simulator correctly ,We need to simplify and adjust the code:[modified version](https://github.com/eddie9712/Computer_Architecture/blob/main/riscv/Lab1/mat_modify.s)

## assembly code illustrate(with memory updating):

1. The code is put into the text section of memory ,and it starts from the address 0x00000000

2. The data of the program is put into the data section. As you can see,the string `"The result is:"` is stored into `0x10000000-0x1000000c` ,and the initial values of two matrix are stored into `0x10000014-0x1000002c`:

3. When the processor starts to execute main function ,it sets the stack pointer for program and stores the original value of S0:
(sp initial value 0x7ffffff0)

    addi sp,sp,-80                   
    sw s0,76(sp)
    addi s0,sp,80 

4. Load the data from data section to program's stack memory ,so we get `a2=1,a3=2,a4=3,a5=4`,stack memory `s0-44=1,s0-40=2,s0-36=3,s0-32=4` ,and the second matrix same as the first matrix.

    la a5,.LC0                    #load the memory from address .LC0
    lw a2,0(a5)
    lw a3,4(a5)
    lw a4,8(a5)
    lw a5,12(a5)
    sw a2,-44(s0)                 #store the value 1,2,3,4 from LC0 to stack(matrix1 2*2)
    sw a3,-40(s0)
    sw a4,-36(s0)
    sw a5,-32(s0)

5. Declare a new matrix to store the result, and initialize its values to zero

 sw zero,-76(s0)                  #initialize the space of the new matrix(result 2*2)
 sw zero,-72(s0)
 sw zero,-68(s0)
 sw zero,-64(s0)

6. After that ,we can observe in C code we have three variables(i,j,k) to control loops ,so in assembly code we can find three memory spaces in stack ,which are used for controlling loops:
`s0-20 => i`,`s0-24 => j`,`s0-28 => k` ,they all use the same control method :

.L2:                                     #the outermost loop (variable i) 
	lw a4,-20(s0) 
	li a5,1
	ble a4,a5,.L7 

=>load the varaible to a4=>if variable <= 1 than jump

7. Then we go to the innermost loop L5 ,In C code ,we have `new[i][j]+=matrix[i][k]*matrix2[k][j];` ,so we should get the address of the specific subscripts. Therefore ,the assembly code below calclates the address
of the `new[][]` matrix.

        lw a5,-20(s0)                    #calculate the address of the subscripts in new matrix  
	slli a4,a5,1 
	lw a5,-24(s0) 
	add a5,a4,a5 
	slli a5,a5,2 
	addi a4,s0,-16 
	add a5,a4,a5  
	lw a4,-60(a5)                    #a4 = value of the selected subscripts in new matrix

When I have a deep look at the address calculating ,I find it will do:
$$s0-16+4\times(2i+j)$$

Because of the fact that the data is stored for "row-major order" ,so it will calculate the subscripts with this formula ,and the assembly code use the same way to find the specific subscripts in `matrix` and `matrix2` ,and load the values into `a3`,`a4`,`a5`
>In row-major order, the consecutive elements of a row reside next to each other

8. After that ,we can get the results in matrix :

        mul a5,a3,a5     
	add a4,a4,a5     
	lw a5,-20(s0)    
	slli a3,a5,1
	lw a5,-24(s0)
	add a5,a3,a5
	slli a5,a5,2
	addi a3,s0,-16
	add a5,a3,a5    
	sw a4,-60(a5)        

9. When it leave the loops ,it will find the address of results and print them ,So I Insert `"jal ra printReslt"` for printing result ,here is the print function part:

 la a0,str1
        li a7,4
        ecall
     
     	li a0 10                         #go to next line
     	li a7 11
     	ecall

     	lw t1,-76(s0)                    #first element
     	mv a0,t1
     	li a7,1
     	ecall
     
     	li a0 32                         #space character
     	li a7 11
     	ecall

I use the environment calls provided by [here](https://github.com/mortbopet/Ripes/wiki/Environment-calls) ,printing the string ,space characters(ascii code number) ,and last issue I need to solve is print the result in memory ,so I observe that the s0 hasn't been changed during the loop which means that I can use the address `s0-16-60` directly ,so I specify the addresses `s0-76`,`s0-72`,`s0-68`,`s0-64`
(it access the address in the loop)

        addi a4,s0,-16 
	add a5,a4,a5  
	lw a4,-60(a5)  

The memory look:

## Optimize the assembly code
At the assembly program generated by cross-compiler ,I find the section here:

        lw a5,-20(s0)                    #calculate the address of the subscripts in new matrix  
	slli a4,a5,1 
	lw a5,-24(s0) 
	add a5,a4,a5 
	slli a5,a5,2 
	addi a4,s0,-16 
	add a5,a4,a5  
	lw a4,-60(a5)                    #a4 = value of the selected subscripts in new matrix

It is executed two times in the program ,because the function of this section is for calculating the `"new"` matrix's address(which means it must be changed during execution) ,so I store the address (with instructions `mv t1 a5`) ,load the address from t1 (with instructions `sw a4,-60(t1)` ,and delete the redundant part .

* Result:
* **Before**: We have **623** cycles for the whole program:
* **After** :We have just **559** cycles
* Because there is forwarding mechanism inside the processor ,so I can insert these instructions without `nop` insert.

## Reference list
[environment calls of Ripes](https://github.com/mortbopet/Ripes/wiki/Environment-calls)
[Row- and column-major order
](https://en.wikipedia.org/wiki/Row-_and_column-major_order)[matrix multiplication](https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm)