Cache mapping exercises

getting started exercises
direct mapping
fully associative mapping
set associative mapping

1. Cache mapping

2. Number of blocks in main memory= Main memory size/ block size = 2 20 Bytes/ 2 4 Bytes

3. Main memory = 2 20 Bytes number of bits in physical address= 20 bits. Block size= 16 Bytes = 2 4 Bytes number of bits in block offset = 4 bits.

4. Cache memory contains 32 blocks = 2 5 blocks Number of bits in cache index = 5 bits Number of bits in tag : the remaining = 20 – (5+4) =11 bits

5. ODB63 = 0000 1101 101 1 0110 0011 The first least significant bits are for the offset The next 5 bits are for cache index. 10110 is 22 in decimal ODBC will map (22 Mod 32) = 22 cache block that is the block number 23 (blocks start from 0)

6. In the figure below, the physical address in only divided into offset and tag. A block in the main memory can map any address in the cache memory. It is the fully associative mapping. When the cache is searched, all entries (block in cache) are searched in parallel to retrieve the data.

7. Main memory size= 2 14 words number of bits in physical address = 14 bits Block size= 8 words = 2 3 words  number of bits in offset = 3 bits

8. Number of lines in cache memory = 16 blocks 2-way set associative mapping means each set contains 2 blocks  16/2 = 8 sets = 2 3 sets That is 3 bits for the set index The tag bits are the remaining tag= 14 – (3+3) = 8 bits

9. Direct mapping case: Block size = 32 Bytes = 2 5 Bytes 5 bits offset Cache Memory size =64 Kbytes = 2 6 * 2 10 Bytes Number of lines = CM size/ Block size  2 16 Bytes / 32 Bytes = 2 11 Bytes  11 bits for index Tag 8 bits Index 11 bits Offset 5 bits

10. Tag bits = the remaining = 24- (11+5) = 8 bits

11. Fully associative case: Block size = 32 Bytes = 2 5 Bytes 5 bits offset In full associative, all the rest of bits is for the tag since a block in Main Memory can be mapped to any cache b lock Tag 19 bits Offset 5 bits

12. 4-way set associative : Block size = 32 Bytes = 2 5 Bytes 5 bits offset Cache Memory size =64 Kbytes = 2 6 * 2 10 Bytes Number of lines = CM size/ Block size  2 16 Bytes / 32 Bytes = 2 11 lines Each set contains 4 blocks = 2 2 blocks

13. So the number of sets is : 2 11 /2 2 =2 9  9 bits for set Tag bits = the remaining = 24- (9+5) = 10 bits Tag 10 bits Index 9 bits Offset 5 bits

14. Step 1 : read 30 30 Mod 5 = 0 So we go to address zero and map the memory block  miss Step 2 : read 31 31 Mod 5 = 1 So we go to address one and map the memory block again miss

15. Step 3 : read 30 It already exists at this position  hit Step 4 : read 26 26 Mod 5 = 1 (address location busy, we will replace and we no longer have 31 in cache) So we go to address one and replace the memory block  miss

16. Step 5 : read 25 25 Mod 5 = 0 (address location busy, we will replace and we no longer have 30 in cache) So we go to address zero and replace the memory block  miss Step 6 : read 28 28 Mod 5 = 3 So we go to address three and map the memory block  miss

17. Step 7 : read 23 23 Mod 5 = 3 (address location busy, we will replace and we no longer have 28 in cache) So we go to address three and replace the memory block  miss Step 7 : read 25 Already in cache memory  hit

18. Step 8: read 28 28 Mod 5 = 3 (address location busy, we will replace and we no longer have 23 in cache) So we go to address three and replace the block 23 by 28  miss