---
# System prepended metadata

title: 'Lab3:SoftCPU'
tags: [RISC-V, 2022 Computer Architecture]

---

# Lab3:SoftCPU
######  tags:`RISC-V` `2022 Computer Architecture`
###### contributed by <[YongDa Su](https://github.com/YongDaSu/2022ComputerArchitecture/tree/main/Lab02)>
## Pre-work
step1. [environment build](https://hackmd.io/@2gMSvG25RxKj2-N_rAY6zg/HkKaA_qUs)
step2. create a folder in `srv32/sw/HW3-1`
step3. copy `makefile` in `hello` to `HW3-1`
step4. modify `makefile`
```
SRC = HW3-1.c
TARGET = HW3-1
```
![](https://i.imgur.com/ORBiTCC.jpg)
step5. back to `~/srv32`
```linux=
$ make HW3-1  #folder name
```
## Leetcode medium
### [Leetcode 19.](https://leetcode.com/problems/remove-nth-node-from-end-of-list/) Remove Nth Node From End of List
Given the `head` of a linked list, remove the `nth` node from the end of the list and return its `head`.

example:
![](https://i.imgur.com/0gAQnt8.jpg)

### C code
```c=
/*** Leetcode 19. Remove Nth Node From End of List ***/ 

#include<stdio.h>
#include<stdlib.h>
struct ListNode {
	int val;
	struct ListNode *next;
};
typedef struct ListNode Node;

void add_node(Node **start, int value);
void print_list(Node *node);
void free_list(Node *node);

struct ListNode* removeNthFromEnd(Node *node, int n){
    int i=0;
    int j;
    struct ListNode *cur;
    cur = node;
    while(cur != NULL){
        i++; 
        cur = cur->next;
    }
    //printf("i = %d", i);
    //special condition
    //1.i=1
    if(i == 1){
    	node = NULL;
    	return node;
    }
    //2.if n = i (means delete first node)
    if(i == n){
        node = node->next;
        return node;
    }
    
    //loop until meet the delete target
    cur = node;
    for(j=0;j<i-n-1;j++){
        cur = cur->next;
    }
    //skip the target
    cur->next = cur->next->next;
    return node;
}



int main(int argc, char* argv[])
{
	// create first list
	Node *head = NULL;
	add_node(&head, 1);
	add_node(&head, 2);
	add_node(&head, 3);
	add_node(&head, 4);
	add_node(&head, 5);

	printf("\noriginal list = ");
	print_list(head);
	printf("delete 2 node from end.");
	//removeNthFromEnd(head,2);
	printf("\nresult = ");
	print_list(removeNthFromEnd(head,2));
	free_list(head);
	
	//create second list
	Node *head2 = NULL;
	add_node(&head2, 1);

	printf("\noriginal list = ");
	print_list(head2);
	printf("delete 1 node from end.");
	//removeNthFromEnd(head2,1);
	printf("\nresult = ");
	print_list(removeNthFromEnd(head2,1));
	free_list(head2);
	
	//create third list
	Node *head3 = NULL;
	add_node(&head3, 1);
	add_node(&head3, 2);
	add_node(&head3, 3);
	add_node(&head3, 4);
	add_node(&head3, 5);
	add_node(&head3, 6);

	printf("\noriginal list = ");
	print_list(head3);
	printf("delete 6 node from end.");
	//removeNthFromEnd(head3,6);
	printf("\nresult = ");
	print_list(removeNthFromEnd(head3,6));
	free_list(head3);
	
	return 0;	
}

void add_node(Node **start, int value)
{
	Node *new_node = (Node*)malloc(sizeof(Node));
	new_node->val = value;
	new_node->next = NULL;
	
	if(*start == NULL) {
		*start = new_node;
		return;
	}
	else {
		Node *cur;	
		cur = *start;
		while(cur->next != NULL) {
			cur = cur->next;
		}
		cur->next = new_node;
		return;
	}
}

void print_list(Node *node)
{
	if (node == NULL){
		printf("NULL");
	}
	while(node != NULL) {
		printf("%d ", node->val); 
		node = node->next;
	}
	printf("\n");
}

void free_list(Node *node)
{
	Node *cur, *tmp;
	cur = node;
	while(cur != NULL) {
		tmp = cur;
		cur = cur->next;
		free(tmp);
	}
}
```
### Part1 - RTL & ISS result
#### **RTL SIM**
```linux=
Excuting 30166 instructions, 40136 cycles, 1.330 CPI
Program terminate
- ../rtl/../testbench/testbench.v:434: Verilog $finish

Simulation statistics
=====================
Simulation time  : 0.408 s
Simulation cycles: 40147
Simulation speed : 0.0983995 MHz
```

#### **ISS**
```linux=
Excuting 30166 instructions, 40136 cycles, 1.331 CPI
Program terminate

Simulation statistics
=====================
Simulation time  : 0.030 s
Simulation cycles: 40136
Simulation speed : 1.327 MHz
```

### Part2 - waveform analysis
Input following command under directory `srv32/sim`
```linux=
$ make HW3-1.run
$ gtkwave wave.fst
```
![](https://i.imgur.com/fRer0J0.jpg)

* **data hazard**
RAW data hazard
```
5f8:	8b498993          	addi    s3,s3,-1868
5fc:	00d986b3          	add	    a3,s3,a3
```
|Instruction||||
|-|-|-|-|
|addi	s3,s3,-1868|IF/ID	|EX⬂|WB|
|addi	a3,s3,a3||IF/ID⬃	|EX|WB|

![](https://i.imgur.com/d1sFVA4.jpg)

* **Load-use hazard**
In srv32, 3-stage pipeline will not lead to stall that wasting cycle when load-use.
A single MUX is used to classify 2 operands, which sloves the problem of load-use hazard.

```
76c:	00442783          	lw	    a5,4(s0)
770:	ffc7fb13          	andi	s6,a5,-4
```
![](https://i.imgur.com/TPX8xdt.jpg)

* **control hazard**
```
28:	    fe62ece3          	bltu	t0,t1,20
2c:	    00040117          	auipc	sp,0x40
30:	    fd410113          	addi	sp,sp,-44
```
The timing diagram of the above instruction sequence is as follow:
|Instruction|||||
|-|-|-|-|-|
|bltu	t0, t1, 20 < memset ><font color=red>(taken)</font>|IF/ID	|EX|WB||
|auipc	sp, 0x40 <font color=blue>(flush)</font>||nop|nop|nop||
|addi	sp, sp, -44 < numJewelsInStones+0x50 > <font color=blue>(flush)</font>|||nop|nop|nop|

![](https://i.imgur.com/vL49rI3.jpg)

## From Lab2
### C code
```c=
/* Lab02 c code
   leetcode1550. Three Consecutive Odds
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool threeConsecutiveOdds(int *arr, int arrSize)
{
	int i;
    int count = 0;
    if (arrSize < 3)
        return false;
    for (i = 0; i < arrSize; i++)
    {
        if (*(arr + i) & 1)
        {
            if (++count == 3)
                return true;
        }
        else
        {
            count = 0;
        }
    }
    return false;
}

int main(int argc, char *argv[])
{
    int test1[2] = {2, 6};
    int test2[9] = {1, 2, 34, 3, 4, 5, 7, 23, 25};
    int test3[6] = {1, 3, 4, 7, 9, 12};
    bool answer1 = threeConsecutiveOdds(test1, sizeof(test1) / sizeof(test1[0]));
    bool answer2 = threeConsecutiveOdds(test2, sizeof(test2) / sizeof(test2[0]));
    bool answer3 = threeConsecutiveOdds(test3, sizeof(test3) / sizeof(test3[0]));
    printf("The answer1 is %d\n", answer1);
    printf("The answer2 is %d\n", answer2);
    printf("The answer3 is %d\n", answer3);

    return 0;
}

/*** terminal output
The answer1 is 0
The answer2 is 1
The answer3 is 0
--------------------------------
Process exited after 0.02739 seconds with return value 0
Press any key to continue . . .
***/
```
### Part1 - RTL & ISS result
#### **RTL SIM**
```linux=
Excuting 5683 instructions, 7807 cycles, 1.373 CPI
Program terminate
- ../rtl/../testbench/testbench.v:434: Verilog $finish

Simulation statistics
=====================
Simulation time  : 0.095 s
Simulation cycles: 7818
Simulation speed : 0.0822947 MHz
```
#### **ISS**
```linux=
Excuting 5683 instructions, 7807 cycles, 1.374 CPI
Program terminate

Simulation statistics
=====================
Simulation time  : 0.005 s
Simulation cycles: 7807
Simulation speed : 1.580 MHz
```
## reference
* [Lab3: srv32 - RISCV RV32IM Soft CPU](https://hackmd.io/@sysprog/S1Udn1Xtt)
* [srv32](https://github.com/sysprog21/srv32)
* [verilator](https://verilator.org/guide/latest/files.html#files-read-written)
* [建置範例](https://hackmd.io/@eecheng/B1fEgnQwF)