12. 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?

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