Given a byte-addressable memory with 256 bytes, suppose a memory dump yields the results shown below. The address of each memory cell is determined by its row and column. For example, memory address 0x97 is in the 9th row, 7th column, and contains the hexadecimal value 43. Memory location 0xA3 contains the hexadecimal value 58

The system from which this memory dump was produced contains 4 blocks of cache, where each block consists of 8 bytes. Assume that the following sequence of memory addresses takes place: 0x2C, 0x6D, 0x86, 0x29, 0xA5, 0x82, 0xA7, 0x68, 0x80, and 0x2B. 

a) How many blocks of main memory are there? 

b) Assuming a direct-mapped cache  

i. Show the format for a main memory address, assuming that the system uses direct-mapped cache. Specify field names and sizes. 

ii. What does cache look like after the 10 memory accesses have taken place? Draw the cache and show contents and tags. 

iii. What is the hit rate for this cache on the given sequence of memory accesses?

c) Assuming a fully associative cache 

i. Show the format for a main memory address. Specify field names and sizes. 

ii. Assuming that all cache blocks are initially empty, blocks are loaded into the first available empty cache location, and cache uses a first-in, first-out replacement policy, what does cache look like after the 10 memory accesses have taken place? 

iii. What is the hit rate for this cache on the given sequences of memory accesses?  

d) Assuming a 2-way set-associative cache 

i. Show the format for a main memory address. Specify field names and sizes. 

ii. What does cache look like after the 10 memory accesses have taken place? 

iii. What is the hit ratio for this cache on the given sequence of memory accesses? 

iv. If a cache hit retrieves a value in 5ns, and retrieving a value from main memory requires 25ns, what is the average effective access time for this cache, assuming that all memory accesses exhibit the same hit rate as the sequence of 10 given, and assuming that the system uses a nonoverlapped (sequential) access strategy?

Transcribed Image Text:

0 1 2 3 4 5 6 7 8 9 A B C D E F 0 DC D5 9C 77 C1 99 90 AC 33 D1 37 74 B5 82 38 EO 1 86 E5 2 49 E2 23 FD DO A6 98 BB DE 9A 9E EB 04 AA 6D 18 3C 9D 1F 2F 78 44 1E C5 CE BF 93 20 85 88 3A 14 F3 59 5C 41 B2 4E B7 29 E7 87 3D B8 E1 3 39 7F EF DA 2A 76 89 CB 72 92 E9 4 6B 69 02 56 7E 5B 5 B9 16 A8 FA AE 68 21 25 34 24 B6 48 17 83 75 0A 6 40 2B C4 1D 08 03 0E OB B4 C2 53 FB E3 8C OC 9B 7 60 4F D7 D9 97 2E 6C 94 BC 31 AF 30 9F A4 FE 09 CD 80 64 B3 8D 81 A7 DB F1 BA 66 BE 11 1A A1 D2 8 9 A B C D E F 61 28 5D D4 4A 10 A2 43 CC 07 7D 5A CO 52 57 A3 58 55 OF E8 F6 91 F0 C3 19 F9 26 51 1C C6 3B 22 OD F5 2C 62 B0 50 35 A9 D3 CF 67 BD 8B 47 ED 7B EE 95 12 7C DF B1 4D EC 42 8E 96 A0 C8 27 3E EA 01 13 F4 F8 46 71 5F 7A FF CA 45 65 73 79 C9 FC A5 C7 05 D8 F2 AD 15 32 06 5E DD 4C 6A 00 8A D6 6E F7 63 3F 36 6F 1B 4B 70 84 AB E6 2D 54 E4 8F Description