Andrew login ID:Full Name:CS 15-213, Spring 2002Exam 2March 28, 2002Instructions:Make sure that your exam is not missing any sheets, then write your full name and Andrew login IDon the front.Write your answers in the space provided below the problem. If you make a mess, clearly indicateyour final answer.The exam has a maximum score of 54 points.The problems are of varying difficulty. The point value of each problem is indicated. Pile up the easypoints quickly and then come back to the harder problems.This exam is OPEN BOOK. You may use any books or notes you like. You may use a calculator, butno laptops or other wireless devices. Good luck!1 (4):2 (12):3 (13):4 (7):5 (6):6 (12):TOTAL (54):Page 1 of 14Problem 1. (4 points):In this problem, you will compare the performance of direct mapped and-way associative caches for theinitialization of 2-dimensional array of data structures. Both caches have a size of bytes. The directmapped cache has-byte lines while the-way associative cache has-byte lines.You are given the following definitionstypedef struct{float irr[3];short theta;short phi;} photon_t;photon_t surface[16][16];register int i, j, k;Also assume thatsizeof(short) = 2sizeof(float) = 4surface begins at memory address 0Both caches are initially emptyThe array is stored in row-major orderVariables i,j,k are stored in registers and any access to these variables does not cause a cache missA. What fraction of the writes in the following code will result in a miss in the direct mapped cache?for (i = 0; i < 16; i ++){for (j = 0; j < 16; j ++){for(k = 0; k < 3; k ++){surface[i][j].irr[k] = 0.;}surface[i][j].theta = 0;surface[i][j].phi = 0;}}Miss rate for writes to surface:____________%B. Using code in part A, what fraction of the writes will result in a miss in the 4-way associative cache?Miss rate for writes to surface: ____________%Page 2 of 14C. What fraction of the writes in the following code will result in a miss in the direct mapped cache?for (i = 0; i < 16; i ++){for (j = 0; j < 16; j ++){for (k = 0; k < 16; k ++){surface[j][i].irr[k] = 0;}surface[j][i].theta = 0;surface[j][i].phi = 0;}}Miss rate for writes to surface:____________%D. Using code in part C, what fraction of the writes will result in a miss in the 4-way associative cache?Miss rate for writes to surface:____________%Page 3 of 14Problem 2. (12 points):The following problem concerns various aspects of virtual memory.Part I.The following are attributes of the machine that you will need to consider:Memory is byte addressableVirtual Addresses are 26 bits widePhysical Addresses are 12 bits widePages are 512 bytesEach Page Table Entry contains:– Physical Page Number– Valid BitA. The box below shows the format of a virtual address. Indicate the bits used for the VPN (Virtual PageNumber) and VPO (Virtual Page Offset).24 20 16 12 8 4 0B. The box below shows the format for a physical address. Indicate the bits used for the PPN (PhysicalPage Number) and PPO (Physical Page Offset)8 4 0C. Note: For the questions below, answers of the formare acceptable. Also, please note the units ofeach answerHow much virtual memory is addressable? bytesHow much physical memory is addressable? bytesHow many bits is each Page Table Entry? bitsHow large is the Page Table? bytesPage 4 of 14Part II(4 points)Application images for the operating system used on the machine in part I are formed with a subset of ELF.They only contain the .text and .data regions.When a process uses fork() to create a new process image in memory, the operating system maintainseach process’ view that it has full control of the virtual address space. To the programmer, the amount ofphysical memory used by the two processes together is twice that which is used by a single process.**NOTE** Read both questions below before answeringA. How can the operating system conservatively save physical memory when creating the new processimage during a call to fork() with respect to the .text and .data regions?B. Imagine a process that acts in the following fashion:int my_array[HUGE_SIZE];int main() {/* Code to initialize my_array */if(fork() == 0) {exit(0);} else {/* Code that calculates and prints* the sum of the elements in my_array*/}}How could the operating system be aggressive by temporarily saving memory beyond what was savedin part A in this case? Hint 1: Note that the child doesn’t change my array, but the operating systemhas to be prepared for such an event since it doesn’t know the future. Hint 2: Think about protectionbits and page faults.Page 5 of 14Problem 3. (13 points):The following problem concerns the way virtual addresses are translated into physical addresses.The memory is byte addressable, and memory accesses are to 1-bytenot 4-bytewords.Virtual addresses are 17 bits wide.Physical addresses are 12 bits wide.The page size is 256 bytes.The TLB is 4-way set associative with 16 total entries.The cache is 2-way set associative, with a 4-byte line size and 64 total entries.In the following tables, all numbers are given in hexadecimal. The contents of the TLB and the page tablefor the first 32 pages, and the cache are as follows:TLBIndex Tag PPN Valid0 55 6 048 F 100 C 077 9 11 01 4 132 A 102 F 073 0 12 02 3 10F B 004 3 026 C 03 00 8 17A 2 121 1 017 E 0Page TableVPN PPN Valid VPN PPN Valid000 C 0 010 1 1001 7 1 011 8 1002 3 1 012 3 0003 8 1 013 E 1004 0 0 014 6 0005 5 0 015 C 0006 C 1 016 7 0007 4 1 017 2 1008 D 1 018 9 1009 F 0 019 A 000A 3 1 01A B 000B 0 1 01B 3 100C 0 0 01C 2 100D F 1 01D 9 000E 4 0 01E 5 000F 7 1 01F B 12-way Set Associative CacheIndex Tag Valid Byte 0 Byte 1 Byte 2 Byte 3 Tag Valid Byte 0 Byte 1 Byte 2 Byte 30 7A 1 09 EE 12 64 00 0 99 04 03 481 02 0 60 17 18 19 38 1 00 BC 0B 372 55 1 30 EB C2 0D 0B 0 8F E2 05 BD3 07 1 03 04 05 06 5D 1 7A 08 03 224 12 0 06 78 07 C5 05 1 40 67 C2 3B5 71 1 0B DE 18 4B 6E 0 B0 39 D3 F76 91 1 A0 B7 26 2D F0 0 0C 71 40 107 46 0 B1 0A 32 0F DE 1 12 C0 88 37Page 6 of 14Part 11. The box below shows the format of a virtual address. Indicate (by labeling the diagram) the fields (ifthey exist) that would be used to determine the following: (If a field doesn’t exist, don’t draw it onthe diagram.)VPO The virtual page offsetVPN The virtual page numberTLBI The TLB indexTLBT The TLB tag16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 02. The box below shows the format of a physical address. Indicate (by labeling
View Full Document
Unlocking...