final-Fa2021-solution

HONOR CODE I have not used any online resources during the exam. I have not obtained any help either from anyone in the class or outside when completing this exam. No sharing of notes/slides/textbook between students. CANVAS ANSWERS MAY BE LOCKED AFTER 1ST TRY. Questions Sheet. Read all of the following information before starting the exam: For each question fill out the appropriate choice or write text on page. Also type clearly on in the exam on the appropriate text. IF THE MULTIPLE CHOICE ANSWER IS WRONG WE WILL MARK THE ANSWER WRONG. IF THE MULTIPLE-CHOICE ANSWER IS CORRECT, WE WILL READ THE WRITTEN PORTION. 1 pt Qs (0 or 1). 2 or 3pt Qs (if no explaination only 1 pt.) Show all work, clearly and in order, if you want to get full credit. We reserve the right to take off points if we cannot see how you logically got to the answer (even if your final answer is correct). 1 or 2 sentences atmost. I will take points off for rambling and for incorrect or irrelevant statements.

HONOR CODE Questions Sheet. Section A Virtual Memory 15 points. Canvas Q1-Q28 Common questions. Canvas Q1-Q2 For the virtual address 0x15957 answer the following Canvas Q3-Q12. All in hex. (0.5 pt each) For the virtual address 0x2ee19 answer the following. Canvas Q13-Q22. All in hex (0.5 pt each) For the virtual address 0x1a344 answer the following. All in hex (Canvas: 23-28) (0.5 pt each) B. Easy. RISCV Blackbox. [10 Points] Answer questions below for the code shown. 29. _____ bytes are stored to memory? [1] 30. The string result is "_______" ? [1] Answer questions below for the code shown. 31. _____ bytes are stored to memory? [1] 32. The string result is "_______" ? [2] Answer questions below for the code shown. 33. _____ bytes are stored to memory? [2] 34. The string result is _______ ? [3] C. Lets Cache I (14pts) 35. The hit ratio of loop 1 for Cache A is ---- ? (1 pts) 36. The hit ratio of loop 1 for Cache B is ---- ? (1 pts) 37. The hit ratio of loop 2 for Cache A is ---- (assume loop 1 has already run) ? (1 pts) 38. The hit ratio of loop 2 for Cache B is ---- (assume loop 1 has already run) ? (1 pts) 39. The hit ratio of loop 3 for Cache A is ---- (assume loop 1 and 2 has already run) ? (2 pts) 40. The hit ratio of loop 3 for Cache B is ---- (assume loop 1 and 2 has already run) ? (2 pts) 41. What is the hit ratio if loop 3 changes to the one below (on Cache A) ? (2 pts) 42. What is the hit ratio if loop 3 is same as Q41 for lines 7-10. (on Cache B) ? (2 pts) 43. What is hit ratio for the code below. Assume Cache B ? (2 pts) D. RISC-V Single Cycle Datapath [15 points] 44. What is the logic for badd signal ? (1) 45. _____ is the number of registers badd needs to access in a single cycle ? (1) 46. What is the RegWen signal for badd ? (1) 47. What is the comparison logic we are interested in ? (2) 48. Consider the following modifications to the Reg[] register file. (2) 49. What is ASel and BSel (2) 50. What are the changes to mux-A ? (2) 51. What are the changes to mux-B ? (2) 52. The WBsel select is _____ ? (2) F. RISC-V Pipeline 17 points. Part I

Section A Virtual Memory 15 points. Canvas Q1-Q28 Refer slide deck L21-VM-III Week 8 if you need to. The chart below shows how memory accesses are treated in a system. The table below describes the parameters int he memory system. Please use the data below to answer question groups Q1,Q2,Q3,Q4 on canvas. CAUTION 1: When converting from binary to hex you can always pad the MSB e.g., 10 1010 (6 bit field) in hex is 0010 1010 (2 0s padded in MSB) is 0x2a . always use lower case and prefix 0x for hex . Correct: 0xabcdef Incorrect: 0xABCDEF Flowchart Parameter Value Physical address bits 18 Size of page 64 bytes Virtual address bits 18 ------------------------- --------------------- TLB Sets 8 TLB Ways 2 ----------------------- ------------------- Cache size 256 bytes Cache Sets 16 Cache Ways 2 VPN - Virtual page number Index (Set index of cache or TLB) PPN - Physical page number INVALID. TLB entry is invalid TLB-T (TLB Tag)

TLB Way 0 TLB-T PPN Set 0 [0x1cb] 0x958 Set 1 [0x1be] --- Set 2 [0xa4] 0xe76 Set 3 [0x74] ---- Set 4 [0x11d] 0x2b5 Set 5 [0xbc] 0xa36 Set 6 [0x1fb] --- Set 7 [0xf1] 0xfea Way 0 TLB-T PPN Set 0 [0x177] 0x47b Set 1 [0x24] --- Set 2 [0x12] 0x84a Set 3 [0x16c] --- Set 4 [0x192] 0xe76 Set 5 [0xd1] --- Set 6 [0xab] 0xec3 Set 7 [0xc6] ---

Cache Way 0 Tag 0 1 2 3 4 5 6 7 Set 0 [0x322] 0x13 0xc8 0xce 0xc6 0x76 0x7c 0xde 0xf3 Set 1 [0x45a] 0xbc 0x0f 0xd8 0x93 0xe7 0x69 0xea 0xb1 Set 2 [0x6f6] 0x56 0xf3 0x3d 0xd6 0x7b 0x2c 0x98 0x34 Set 3 [0x276] 0xf3 0x8c 0x94 0x8d 0xaf 0x5c 0x02 0x3b Set 4 [0x23c] 0x3a 0x09 0x3c 0x3b 0x35 0x3f 0x85 0x1e Set 5 [0x425] 0x19 0x65 0xaf 0x3e 0xb4 0x8a 0x8a 0xcf Set 6 [0x62e] 0x88 0x87 0xad 0x73 0xac 0x70 0xeb 0x77 Set 7 [0x4ac] 0x0c 0x02 0x16 0xfe 0x7b 0x34 0xd6 0x91 Set 8 [0x761] 0xc9 0x97 0x01 0x6d 0xea 0x55 0x59 0x73 Set 9 [0x242] 0xe2 0x55 0x38 0xd0 0x84 0x6c 0x16 0x5b Set 10 [0x494] 0x76 0x78 0x19 0x6b 0xb6 0xf3 0xa4 0xfb Set 11 [0x23d] 0xf5 0xac 0x7f 0xf5 0x1f 0xb8 0x03 0x20 Set 12 [0x7b9] 0x11 0x9a 0xd4 0x8d 0x85 0xe8 0xb3 0xb1 Set 13 [0x15a] 0x4e 0xaa 0x51 0x0f 0x61 0xc3 0x8f 0x0e Set 14 [0x739] 0x77 0x71 0x3b 0xb8 0xa7 0x70 0x18 0x15 Set 15 [0x627] 0x7f 0x65 0xe0 0x34 0x1a 0x90 0xb5 0x19 Way 1 Tag 0 1 2 3 4 5 6 7 Set 0 [0x7f5] 0x11 0xbf 0xe8 0x3e 0xad 0x26 0x2e 0xaa Set 1 [0x73b] 0xe3 0x08 0x0b 0x3a 0xc6 0x98 0x67 0x17 Set 2 [0x31b] 0x39 0x16 0x2e 0xbc 0xde 0x90 0xb5 0x61 Set 3 [0x755] 0x2b 0x39 0x46 0xf5 0x95 0xb7 0x43 0x6d Set 4 [0x627] 0x51 0x8f 0x28 0xb4 0x1d 0xac 0x8c 0x3d Set 5 [0x2af] 0xf5 0x49 0x67 0x1d 0xcb 0x75 0x8e 0x05

Way 1 Tag 0 1 2 3 4 5 6 7 Set 6 [0xf2] 0xc1 0xcd 0x99 0xce 0x27 0xb1 0x9b 0xaf Set 7 [0x236] 0xbb 0xe4 0xda 0xcd 0x43 0xa6 0xa0 0x11 Set 8 [0x1c1] 0x02 0x29 0xe3 0x33 0xa9 0x24 0x89 0x1e Set 9 [0x335] 0x32 0x44 0x68 0x76 0x7b 0xfb 0x7d 0xc9 Set 10 [0x64] 0x3c 0x84 0x70 0x27 0x98 0x88 0x96 0x73 Set 11 [0x51] 0x50 0x82 0x6c 0xda 0x93 0x3a 0x77 0x8b Set 12 [0x56f] 0x9c 0xd1 0xc7 0xba 0x62 0xde 0x1e 0x37 Set 13 [0x654] 0xd5 0x9c 0x66 0x8f 0x95 0xa6 0x3f 0x4c Set 14 [0x1e4] 0xc9 0x96 0xb0 0x3b 0xfb 0x76 0xa3 0x77 Set 15 [0x5d8] 0xb3 0x4f 0x91 0xe9 0x6e 0xa5 0x91 0x8a

0x7 Is it a cache hit or miss Hit What is the data byte 0x61 For the virtual address 0x2ee19 answer the following. Canvas Q13-Q22. All in hex (0.5 pt each) What is the VPN 0xbb8 What is the TLB tag. 0x177 Is it a TLB hit or miss Hit Is it a page fault No What is the PPN ? 0x47b what is the cache tag ? 0x23d what is the cache index 0xb What is the byte offset 0x1 Is it a cache hit or miss

Hit What is the data byte 0xac For the virtual address 0x1a344 answer the following. All in hex (Canvas: 23-28) (0.5 pt each) 00110 1000 1101 000100 What is the VPN 0x68d What is the TLB tag. 0xd1 Is it a TLB hit or miss hit Is it a page fault yes What is the PPN ? N/A Is it a cache hit ? No

AB\0B Answer questions below for the code shown. 33. _____ bytes are stored to memory? [2] 16 (5 letters 3 + null character) 34. The string result is _______ ? [3] "AAABBBCCCDDDEEE" C. Lets Cache I (14pts) Assume we are working in a 4GB physical address space. We will be studying the behavior of different loops on two different caches. Cache-A Direct-mapped, 4KB, 64 sets Cache-B Set-associate, 4KB, 2 ways, 32 sets Both caches use write-back and write-allocate policies. Hit ratio is written as #Hits:#Accesses Hit-Miss ratio is: #Hits:#Misses Hit % : #Hits:#Accesses * 100. Answer questions below .text BLACKBOX: lbu s0 0 (a0) beq s0 x0 End slli s1 s0 8 add s1 s1 s0 sh s1 0 (a1) sb s0 2 (a1) addi a0 a0 1 addi a1 a1 3 j BLACKBOX end: sb x0 0 (a1) 1 2 3 4 5 6 7 8 9 10 11 12 13 ×

int size = 4096 ; // int is 4 bytes int a[size]; // long long int is 8 bytes long long int a_long[size]; /* loop 1 */ for ( int i = 0 ; i < size; i ++ ) { a[i] = i; } /* loop 2 */ for ( int i = 0 ; i < size; i ++ ) { a_long[i] = i; } /* loop 3 */ for ( int i = 0 ; i < size / 2 ; i += 1 ) { a[(size / 2 + i] = a[i]; } 35. The hit ratio of loop 1 for Cache A is ---- ? (1 pts) Write it as Hits:Accesses 15:16 36. The hit ratio of loop 1 for Cache B is ---- ? (1 pts) 15:16 37. The hit ratio of loop 2 for Cache A is ---- (assume loop 1 has already run) ? (1 pts) 7:8 38. The hit ratio of loop 2 for Cache B is ---- (assume loop 1 has already run) ? (1 pts) 7:8 39. The hit ratio of loop 3 for Cache A is ---- (assume loop 1 and 2 has already run) ? (2 pts) 0 MM

struct int_and_long { int a_int; long long int a_long; }; int size = 4096 ; // int is 4 byte aligned // long long int is 8 byte aligned /* loop 1 */ for ( int i = 0 ; i < size / 2 ; i += 1 ) { s[size - 1 - i].a_int = s[i].a_int } Struct has to add 4 byte padding to a_int so total size of struct is 16 bytes. Each cache line in A can hold 4 structs or 4 a_ints. 3:4 hits. e.g, s[0] and s[4095] M,M,H,H,H,H,H,H D. RISC-V Single Cycle Datapath [15 points] We wish to introduce a new instruction into our RISC-V datapath. badd (branch and add). This instruction is a conditional add instruction. The instruction works as follows. The instruction is encoded as follows. Add instruction Opcode f7 rs2 rs1 0x0 f3 rd 0110011 new badd instruction 0x10 rs2 rs1 0x0 f3 rd 0001011 It combines the semantics of branch and R-type instruction. if (R[rs1] > R[rs2]) { R[rd] ++ } else { R[rd] = R[rd] } 1 2 3 4 5

Like a branch it performs a comparison. If comparison succeeds it increments rd. rd is destination and source. If comparison fails, it simply retains the value in R[rd]. We have a new control signal badd which is 1 if the instruction being decoded is a badd. Given the single cycle datapath below, select the correct modifications in parts such that the datapath executes correctly for this new instruction (and all other instructions!). You can make the following assumptions: Caution 2: Pay careful attention to which input line is 1 and which line is 0 in the muxes. Some muxes choose top-most input as 0, some choose bottom-most input as 0 Hint: YOU DO NOT REQUIRE TRUTH TABLES Try writing down in plain english or reading out the logic to yourself e.g, !(A<=B) is A is not equal to B and A is not LT (less than) B

47. What is the comparison logic we are interested in ? (2) !(EQ OR L T) 48. Consider the following modifications to the Reg[] register file. (2) Which configuration will allow this instruction to execute correctly without breaking the execution of other instructions in our instruction set? 49. What is ASel and BSel (2) Don't care 50. What are the changes to mux-A ? (2) Which configuration will allow this instruction to execute correctly without breaking the execution of other instructions in our instruction set? B 51. What are the changes to mux-B ? (2) (d)

Which configuration will allow this instruction to execute correctly without breaking the execution of other instructions in our instruction set? B 52. The WBsel select is _____ ? (2) ALU F. RISC-V Pipeline 17 points. Refer slide deck L29-Hazard Week 11 if you need to. Consider a typical 5-stage (Fetch,Decode,EXecute,Memory,WriteBack) pipeline.Assume pipeline registers exist where the dotted lines are. READ RULES BELOW Forwarding/Bypassing is implemented.