Andrew login ID Full Name CS 15 213 Fall 2003 Exam 2 November 18 2003 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 66 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 10 2 10 3 12 4 11 5 09 6 08 7 06 TOTAL 66 Page 1 of 16 Problem 1 10 points The following problem concerns basic cache lookups The memory is byte addressable Memory accesses are to 1 byte words not 4 byte words Physical addresses are 13 bits wide The cache is 4 way set associative with a 4 byte block size and 32 total lines In the following tables all numbers are given in hexadecimal The Index column contains the set index for each set of 4 lines The Tag columns contain the tag value for each line The V column contains the valid bit for each line The Bytes 0 3 columns contain the data for each line numbered left to right starting with byte 0 on the left The contents of the cache are as follows Index 0 1 2 3 4 5 6 7 Tag F0 0C 8A BE 7E 98 38 8A V 1 0 1 0 1 0 1 1 Bytes 0 3 ED 32 0A A2 03 3E CD 38 54 9E 1E FA 2F 7E 3D A8 32 21 1C 2C A9 76 2B EE 5D 4D F7 DA 04 2A 32 6A Tag 8A A0 B6 C0 8A 54 82 9E V 1 0 1 1 1 0 1 0 4 way Set Associative Cache Bytes 0 3 Tag V BF 80 1D FC 14 1 16 7B ED 5A 8A 1 DC 81 B2 14 00 1 27 95 A4 74 C4 0 22 C2 DC 34 BE 1 BC 91 D5 92 98 1 69 C2 8C 74 8A 1 B1 86 56 0E CC 1 EF 8E B6 07 BA 80 A8 96 Bytes 0 3 09 86 2A 4C DF 18 1F 7B 44 11 6B D8 DD 37 D8 BA 9B F6 CE 7F DA 30 47 F2 Tag BC E4 74 8A DC 8A 3E 06 V 0 1 0 1 0 1 1 1 25 FB 10 C7 E7 48 FA F8 Bytes 0 3 44 6F 1A B7 12 02 F5 B8 2E B7 AF C2 A2 39 BA 16 81 0A 93 EB 48 1D 42 30 Part 1 The box below shows the format of a physical address Indicate by labeling the diagram the fields that would be used to determine the following CO CI CT 12 The block offset within the cache line The cache index The cache tag 11 10 9 8 7 6 5 4 3 2 1 Page 2 of 16 0 Part 2 For the given physical address indicate the cache entry accessed and the cache byte value returned in hex Indicate whether a cache miss occurs If there is a cache miss enter for Cache Byte returned Physical address 0x1314 Physical address format one bit per box 12 11 10 9 8 7 6 5 4 3 2 1 0 4 3 2 1 0 Physical memory reference Parameter Cache Offset CO Cache Index CI Cache Tag CT Cache Hit Y N Cache Byte returned Value 0x 0x 0x 0x Physical address 0x08DF Physical address format one bit per box 12 11 10 9 8 7 6 5 Physical memory reference Parameter Cache Offset CO Cache Index CI Cache Tag CT Cache Hit Y N Cache Byte returned Value 0x 0x 0x 0x Page 3 of 16 Part 3 For the given contents of the cache list all of the hex physical memory addresses that will hit in Set 3 To save space you should express contiguous addresses as a range For example you would write the four addresses 0x1314 0x1315 0x1316 0x1317 as 0x1314 0x1317 Answer The following templates are provided as scratch space 12 11 10 9 8 7 6 5 4 3 2 1 0 12 11 10 9 8 7 6 5 4 3 2 1 0 12 11 10 9 8 7 6 5 4 3 2 1 0 Part 4 For the given contents of the cache what is the probability expressed as a percentage of a cache hit when the physical memory address ranges between 0x1140 0x115F Assume that all addresses are equally likely to be referenced Probability The following templates are provided as scratch space 12 11 10 9 8 7 6 5 4 3 2 1 0 12 11 10 9 8 7 6 5 4 3 2 1 0 12 11 10 9 8 7 6 5 4 3 2 1 0 Page 4 of 16 Problem 2 10 points The following problem concerns the way virtual addresses are translated into physical addresses The memory is byte addressable Memory accesses are to 4 byte words Virtual addresses are 22 bits wide Physical addresses are 18 bits wide The page size is 2048 bytes The TLB is 2 way set associative with 16 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 are as follows Index 0 1 2 3 4 5 6 7 TLB Tag PPN 003 EB 007 46 028 D3 001 2F 031 E0 012 D3 001 5C 00B D1 02A BA 011 F1 01F 18 002 4A 007 63 03F AF 010 0D 032 10 Valid 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 Page Table VPN PPN Valid VPN PPN Valid 00 37 1 10 16 0 01 58 1 11 37 0 02 19 1 12 28 0 03 2A 1 13 53 0 04 56 0 14 1D 0 05 33 0 15 4A 1 06 61 0 16 49 0 07 28 0 17 26 0 08 42 0 18 0C 1 09 63 0 19 04 1 0A 31 1 1A 1F 0 0B 5C 0 1B 22 1 0C 5A 1 1C 40 0 0D 2D 0 1D 0E 1 0E 4E 0 1E 35 1 0F 1D 1 1F 03 1 Page 5 of 16 A Part 1 a The box below shows the format of a virtual address Indicate by labeling the diagram the fields if they exist that would be used to determine the following If a field doesn t exist don t draw it on the diagram VPO The virtual page offset VPN The virtual page number TLBI The TLB index TLBT The TLB tag 21 20 19 18 17 …
View Full Document
Unlocking...