Full Name CS 15 213 Spring 2002 Exam 2 March 28 2002 Instructions Make sure that your exam is not missing any sheets then write your full name and Andrew login ID on the front Write your answers in the space provided below the problem If you make a mess clearly indicate your 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 easy points 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 but no laptops or other wireless devices Good luck 1 4 2 12 3 13 4 7 5 6 6 12 TOTAL 54 Page 1 of 14 In this problem you will compare the performance of direct mapped and way associative caches for the initialization of 2 dimensional array of data structures Both caches have a size of bytes The direct mapped cache has byte lines while the way associative cache has byte lines You are given the following definitions typedef struct float irr 3 short theta short phi photon t photon t surface 16 16 register int i j k Also assume that sizeof short 2 sizeof float 4 surface begins at memory address 0 Both caches are initially empty The array is stored in row major order Variables i j k are stored in registers and any access to these variables does not cause a cache miss A 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 14 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 14 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 addressable Virtual Addresses are 26 bits wide Physical Addresses are 12 bits wide Pages are 512 bytes Each Page Table Entry contains Physical Page Number Valid Bit A The box below shows the format of a virtual address Indicate the bits used for the VPN Virtual Page Number and VPO Virtual Page Offset 24 20 16 12 8 4 0 B The box below shows the format for a physical address Indicate the bits used for the PPN Physical Page Number and PPO Physical Page Offset 8 4 0 C Note For the questions below answers of the form are acceptable Also please note the units of each answer How much virtual memory is addressable bytes How much physical memory is addressable bytes How many bits is each Page Table Entry bits How large is the Page Table bytes Page 4 of 14 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 maintains each process view that it has full control of the virtual address space To the programmer the amount of physical memory used by the two processes together is twice that which is used by a single process NOTE Read both questions below before answering A How can the operating system conservatively save physical memory when creating the new process image 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 saved in part A in this case Hint 1 Note that the child doesn t change my array but the operating system has to be prepared for such an event since it doesn t know the future Hint 2 Think about protection bits and page faults Page 5 of 14 The following problem concerns the way virtual addresses are translated into physical addresses The memory is byte addressable and memory accesses are to 1 byte not 4 byte words 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 table for the first 32 pages and the cache are as follows Index 0 1 2 3 TLB Tag PPN 55 6 48 F 00 C 77 9 01 4 32 A 02 F 73 0 02 3 0F B 04 3 26 C 00 8 7A 2 21 1 17 E Valid 0 1 0 1 1 1 0 1 1 0 0 0 1 1 0 0 Page Table VPN PPN Valid VPN PPN Valid 000 C 0 010 1 1 001 7 1 011 8 1 002 3 1 012 3 0 003 8 1 013 E 1 004 0 0 014 6 0 005 5 0 015 C 0 006 C 1 016 7 0 007 4 1 017 2 1 008 D 1 018 9 1 009 F 0 019 A 0 00A 3 1 01A B 0 00B 0 1 01B 3 1 00C 0 0 01C 2 1 00D F 1 01D 9 0 00E 4 0 01E 5 0 00F 7 1 01F B 1 2 way Set Associative Cache Index Tag Valid Byte 0 Byte 1 Byte 2 Byte 3 Tag Valid Byte 0 Byte 1 Byte 2 Byte 3 0 7A 1 09 EE 12 64 00 0 99 04 03 48 1 02 0 60 17 18 19 38 1 00 BC 0B 37 2 55 1 30 EB C2 0D 0B 0 8F E2 05 BD 3 07 1 03 04 05 06 5D 1 7A 08 03 22 4 12 0 06 78 07 C5 05 1 40 67 C2 3B 5 71 1 0B DE 18 4B 6E 0 B0 39 D3 F7 6 91 1 A0 B7 26 2D F0 0 0C 71 …
View Full Document
Unlocking...