Andrew login ID:Full Name:CS 15-213, Fall 2003Exam 2November 18, 2003Instructions: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 66 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 (10):2 (10):3 (12):4 (11):5 (09):6 (08):7 (06):TOTAL (66):Page 1 of 16Problem 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 indexfor each set of 4 lines. The Tag columns contain the tag value for each line. The V column contains thevalid bit for each line. The Bytes 0–3 columns contain the data for each line, numbered left-to-right startingwith byte 0 on the left.The contents of the cache are as follows:4-way Set Associative CacheIndex Tag V Bytes 0–3 Tag V Bytes 0–3 Tag V Bytes 0–3 Tag V Bytes 0–30 F0 1 ED 32 0A A2 8A 1 BF 80 1D FC 14 1 EF 09 86 2A BC 0 25 44 6F 1A1 0C 0 03 3E CD 38 A0 0 16 7B ED 5A 8A 1 8E 4C DF 18 E4 1 FB B7 12 022 8A 1 54 9E 1E FA B6 1 DC 81 B2 14 00 1 B6 1F 7B 44 74 0 10 F5 B8 2E3 BE 0 2F 7E 3D A8 C0 1 27 95 A4 74 C4 0 07 11 6B D8 8A 1 C7 B7 AF C24 7E 1 32 21 1C 2C 8A 1 22 C2 DC 34 BE 1 BA DD 37 D8 DC 0 E7 A2 39 BA5 98 0 A9 76 2B EE 54 0 BC 91 D5 92 98 1 80 BA 9B F6 8A 1 48 16 81 0A6 38 1 5D 4D F7 DA 82 1 69 C2 8C 74 8A 1 A8 CE 7F DA 3E 1 FA 93 EB 487 8A 1 04 2A 32 6A 9E 0 B1 86 56 0E CC 1 96 30 47 F2 06 1 F8 1D 42 30Part 1The box below shows the format of a physical address. Indicate (by labeling the diagram) the fields thatwould be used to determine the following:CO The block offset within the cache lineCI The cache indexCT The cache tag12 11 10 9 8 7 6 5 4 3 2 1 0Page 2 of 16Part 2For 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: 0x1314Physical address format (one bit per box)12 11 10 9 8 7 6 5 4 3 2 1 0Physical memory referenceParameter ValueCache Offset (CO) 0xCache Index (CI) 0xCache Tag (CT) 0xCache Hit? (Y/N)Cache Byte returned 0xPhysical address: 0x08DFPhysical address format (one bit per box)12 11 10 9 8 7 6 5 4 3 2 1 0Physical memory referenceParameter ValueCache Offset (CO) 0xCache Index (CI) 0xCache Tag (CT) 0xCache Hit? (Y/N)Cache Byte returned 0xPage 3 of 16Part 3For the given contents of the cache, list all of the hex physical memory addresses that will hit in Set 3. Tosave space, you should express contiguous addresses as a range. For example, you would write the fouraddresses 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 012 11 10 9 8 7 6 5 4 3 2 1 012 11 10 9 8 7 6 5 4 3 2 1 0Part 4For the given contents of the cache, what is the probability (expressed as a percentage) of a cache hit whenthe physical memory address ranges between 0x1140 - 0x115F. Assume that all addresses are equallylikely to be referenced.Probability = _________%The following templates are provided as scratch space:12 11 10 9 8 7 6 5 4 3 2 1 012 11 10 9 8 7 6 5 4 3 2 1 012 11 10 9 8 7 6 5 4 3 2 1 0Page 4 of 16Problem 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 tablefor the first 32 pages are as follows:TLBIndex Tag PPN Valid0 003 EB 1007 46 01 028 D3 1001 2F 02 031 E0 1012 D3 03 001 5C 000B D1 14 02A BA 0011 F1 05 01F 18 1002 4A 16 007 63 103F AF 07 010 0D 0032 10 0Page TableVPN PPN Valid VPN PPN Valid00 37 1 10 16 001 58 1 11 37 002 19 1 12 28 003 2A 1 13 53 004 56 0 14 1D 005 33 0 15 4A 106 61 0 16 49 007 28 0 17 26 008 42 0 18 0C 109 63 0 19 04 10A 31 1 1A 1F 00B 5C 0 1B 22 10C 5A 1 1C 40 00D 2D 0 1D 0E 10E 4E 0 1E 35 10F 1D 1 1F 03 1Page 5 of 16A. Part 1(a) The box below shows the format of a virtual address. Indicate (by labeling the diagram) thefields (if they exist) that would be used to determine the following: (If a field doesn’t exist, don’tdraw it on the diagram.)VPO The virtual page offsetVPN The virtual page numberTLBI The TLB indexTLBT The TLB tag21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0(b) The box below shows the format of a physical address. Indicate (by labeling the diagram) thefields that would be used to determine the following:PPO The physical page offsetPPN The physical page number17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0Page 6 of 16B. Part 2For the given virtual addresses, indicate the TLB entry accessed and the physical address. Indicatewhether the TLB misses and whether a page fault occurs.If there is a page fault, enter “-” for “PPN” and leave part C blank.Virtual address: 0x005EEC(a) Virtual address format (one bit per box)21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0(b) Address translationParameter ValueVPN 0xTLB Index 0xTLB Tag 0xTLB Hit? (Y/N)Page Fault? (Y/N)PPN 0x(c) Physical address format (one bit per box)17 16 15 14 13 12 11 10 9 …
View Full Document
Unlocking...