Andrew login ID Full Name CS 15 213 Spring 2004 Exam 2 April 8 2004 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 79 points and a total of 17 pages 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 not use a calculator laptop or other wireless device Good luck 1 16 2 10 3 8 4 12 5 9 6 10 7 14 TOTAL 79 Page 1 of 17 Problem 1 16 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 84 18 84 92 84 A7 8B 84 V 1 1 0 0 1 1 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 9E E4 84 9F FA 73 29 96 V 0 0 1 0 1 0 1 0 4 way Set Associative Cache Bytes 0 3 Tag V BF 80 1D FC 10 0 16 7B ED 5A 02 0 DC 81 B2 14 48 0 27 95 A4 74 57 1 22 C2 DC 34 73 0 BC 91 D5 92 28 1 69 C2 8C 74 B5 1 B1 86 56 0E CC 0 EF 8E B6 07 BA 80 A8 96 Bytes 0 3 09 86 2A 4C DF 18 1F 7B 44 11 FF D8 DD 37 D8 BA 9B F6 CE 7F DA 30 47 F2 Tag E8 E4 89 93 28 6B BF 91 V 0 1 1 1 1 0 0 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 O I T The block offset within the cache line The cache index The cache tag 12 11 10 9 8 7 6 5 Page 2 of 17 4 3 2 1 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 0x0D74 Physical address format one bit per box 12 11 10 9 8 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 0 Physical memory reference Parameter Cache Offset CO Value 0x Cache Index CI 0x Cache Tag CT 0x Cache Hit Y N Cache Byte returned 0x Physical address 0x0AEE Physical address format one bit per box 12 11 10 9 Physical memory reference Parameter Cache Offset CO Value 0x Cache Index CI 0x Cache Tag CT 0x Cache Hit Y N Cache Byte returned 0x Page 3 of 17 Part 3 For the given contents of the cache list all of the hex physical memory addresses that will hit in Set 7 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 0x1080 0x109F 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 Page 4 of 17 Problem 2 10 points This problem requires you to analyze the behavior of the program below which transposes the N N int matrix A For this problem N 4 For this problem you should assume that the loop variables x and y are kept in registers and do not cause memory accesses Likewise the temporary variable t which is used to exchange two array elements is also stored in a register and does not cause any load store from to the memory system or the caches 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 define N 4 Array size int A N N 0 int x y for y 0 y N y for x y 1 x N x int t t A y x A y x A x y A x y t You are supposed to analyze how this program will interact with a simple cache The cache line size is 2 sizeof int The cache is cold when the program starts Further more the array A is aligned so that the first two elements are stored in the same cache line You are supposed to fill out the tables below For each load ld and store st operation to an element of the array A you should indicate if this operation misses M or hits H in the cache Note that this program does not touch the diagonal array elements 1 The cache is direct mapped and has two 2 lines ld ld ld st st st ld st ld ld st st ld ld st st ld st ld ld ld st st st 2 The cache is 2 way set associative and has one set It uses the least recently used LRU replacement policy ld ld ld st st st ld st ld ld st st ld ld st st ld st Page 5 of 17 ld ld ld st st st Problem 3 8 …
View Full Document
Unlocking...