# 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)