prelim2-19fa

Fall 2019 CS 3410 Prelim 2 December 3, 2019 Please turn off and stow away all electronic devices. You may not use them for any reason during the exam. Do not bring them with you if you leave the room temporarily. This is a closed book and notes examination. You may use the 4-sided reference sheet. There are 7 problems . Make sure you have the whole exam. You have 90 minutes to complete 90 points. Use your time accordingly. Question Points Score 1 12 2 8 3 21 4 9 5 4 6 24 7 12 Total: 90 It is a violation of the Academic Integrity Code to look at any exam other than your own, to look at any other reference material, or to otherwise give or receive unauthorized help. We also ask that you not discuss the exam with anyone who has not yet taken it. Academic Integrity is expected of all students of Cornell University at all times, whether in the presence or absence of members of the faculty. Understanding this, I declare I shall not give, use or receive unauthorized aid in this examination. Signature: Date Name: NetID

1. [12 points] C is for... Calling Conventions Consider the code below: 11 int set1( int val, int *vptr) { 12 val++; 13 *vptr += val + 6; 14 set2(val, vptr); 15 return *vptr + val; 16 } First, where it says BODY , convert only lines 12-14 into RISC-V assembly, using the instruc- tions and pseudo-instructions on your reference sheet. Use the label set2 for the location of the function call. Next, where it says PROLOGUE , write the RISC-V assembly that corresponds to the Prologue that supports the Body you wrote. Follow the calling conventions you learned in class. Comment your code explaining what each line does. PROLOGUE: BODY: Page 2

3. C is for... Computer Games. The code below is a part of a hypothetical C program that plays PacMan. It will be compiled to RISC-V using CS 3410 calling conventions. 5 #define NUM_GHOSTS 4 6 7 enum {pacman, blinky, pinky, inky, clyde}; // 0, 1, 2... 8 9 bool paused = false; 10 11 /* integer arrays, storing the x,y coordinates of pacman (in 12 * x_coord[pacman]) and ghosts (starting at x_coord[blinky]) */ 13 int *x_coord; 14 int *y_coord; 15 16 /* Changes coordinates of ghost t. Each ghost thread moves only itself. 17 * (For example: the thread for blinky only ever calls move(blinky)) */ 18 void move( int t) { 19 if (!paused) { 20 x_coord[t]++; 21 y_coord[t]++; 22 } 23 } (a) [3 points] Allocate the x coordinate array. Write C code that initializes the variable x coord by calling malloc . The array should have enough room to store the integer x coordinates of pacman and the ghosts. There will always be one pacman, but your code should work for any number of ghosts and integers on any machine. (b) [10 points] What goes where? Where are these program components located when the program runs? Your Choices are: A the Heap B the Global Data Segment C a Register D the Stack E the Text Segment F System Reserved G None of the Above NUM GHOSTS Circle One: A B C D E F G x coord Circle One: A B C D E F G x coord[10] Circle One: A B C D E F G move Circle One: A B C D E F G t Circle One: A B C D E F G Page 4

C is for... Consulting. The code from the previous page will be multi-threaded, with a dedicated thread for PacMan and each ghost. Each thread calls move(t) , where t identifies the ghost thread to be moved. Assume all data types (pointers, int s and bool s) are 4 bytes, and global variables are 8-byte aligned. The code runs on a multi-core system; each thread runs on its own core. Each core’s cache has 4-byte cache lines. IMPORTANT: you must explain your answers below referencing the code and using CS 3410 terminology when appropriate. (c) [2 points] Give one reason why the MSI coherence protocol is preferable to the VI protocol. For the next questions, assume you use the MSI coherence protocol on your system. (d) [2 points] Explain what happens if you increase the cache line to larger than 4 bytes? (e) [2 points] If the cache lines were 8 bytes, name one specific change you would make to the code to improve the performance of your game. Do not write code; do not modify the code on the previous page. Describe the change and explain why it would be an improvement. (f) [2 points] Explain a possible benefit of having ghost threads run on the same core. Page 5

5. Excuse the interruption (a) [2 points] When a system call occurs, does the prologue of the system call need to save all the registers or just the callee-saved registers? Explain. (b) [2 points] When a page fault occurs for an instruction at address PC , what is the first instruction of user code that will be executed after the page fault is handled? A. control never returns back to user code that experiences a page fault B. it depends on whether the page fault is synchronous or asynchronous C. PC-4 D. PC E. PC+4 Your Answer Page 7

6. Take the Red Pill. Consider a system with byte-addressed memory that has a virtual address size of 24-bits. Pages in memory are 1KB in size. Page Table Entries are 4 bytes. Physical memory is 8 MB total and takes 50 ns to access. The frequency of the processor is 1 GHz. There is a single two-way set associative cache that is 4KB in size. It has a hit rate of 90% and takes 1 cycle to access. Cache lines are 32B wide. There is a fully-associative TLB that holds 64 translations across 64 blocks. (a) [2 points] How large (in B/KB/MB/ etc. ) is the virtual address space? Your Answer: (b) [2 points] How large (in B/KB/MB/ etc. ) is a Page Table? Your Answer: (c) [2 points] How large (in pages ) is a Page Table? Your Answer: (d) [2 points] How many page offset bits are there? Your Answer: (e) [2 points] How large (in bits) is the physical page number? Your Answer: (f) [2 points] What is the tag of a TLB entry? A. the virtual address B. the physical address C. the VPN D. the PPN E. the page offset F. None of these Your Answer: Page 8

7. [12 points] Miss Congeniality 3: A Missed Opportunity Consider a dual core processor with 4-bit addresses. Each core has a private 4B cache with 1 byte cache lines. Core 0’s cache is 2-way associative. Core 1’s cache is direct mapped. The caches use an MSI coherence protocol. (The MSI protocol is on your reference handout.) The diagram below shows the 4-bit address of the data in the cache. The caches were filled from left to right, as shown by the small number in each box. The diagram also shows two more memory references at times 9 and 10. Each reference has format X:ABCD:Y where X indicates the Core that the reference originated from and Y indicates whether it is a read or a write. CORE 0 Cache state prior to access Way 0 Way 1 Way 0 Way 1 Memory Reference 0000:S 0001:S 0010:S 0011:M 0:1000:R 1000:S Set 0 Set 1 Set 2 Set 3 1010:S 1110:M 0011:I 1111:M CORE 1 Cache state prior to access t 9 2-way set associative direct mapped 1 2 3 4 5 6 7 8 X 1101:S 11 1:1101:R 10 Set 0 Set 1 0 L 1 0 L This question asks you to categorize the results of different proposed Memory References at time 11 . An example has been done for you. Note that the references do not happen one after the other. They represent 6 possible references for time 11 only. Possible answers are: Hit, Cold Miss, Conflict Miss, Capacity Miss, Coherence Miss, Upgrade Miss. t=11 Memory Reference Categorization (Hit or Miss? What Kind of Miss?) 0:1000:R Hit 1:1000:W 0:1000:W 0:1010:R 0:0011:R 1:0011:R 1:0001:R Page 10