In this question you’re given a 16-byte memory segment and an 8-byte cache. Given the following series of memory accesses, complete the table below. Use the first Contents/Tag column to insert an item to the cache the first time and use the second Contents/Tag column if a cache entry is overwritten. Note: no index will have more than two blocks mapped to it. The first two examples have been provided.
Module 10 Assignment – Direct-mapped Cache Part 1: Calculating a Direct-Mapped Cache In this question you’re given a 16-byte memory segment and an 8-byte cache. Given the following series of memory accesses, complete the table below. Use the first Contents/Tag column to insert an item to the cache the first time and use the second Contents/Tag column if a cache entry is overwritten. Note: no index will have more than two blocks mapped to it. The first two examples have been provided. How many cache hits occurs given the memory accesses? How many cache misses are there? Additionally, what is the name of the cache eviction policy being used here? Namely, our strategy is to overwrite existing elements in the cache if cache slot is already full. In 1-2 paragraphs, discuss the performance implications (advantages/disadvantages) of using this eviction heuristic. Memory access: 0x48, 0x4C, 0x46, 0x4D, 0x42, 0x4B, 0x45, 0x41, 0x48, 0x4F, 0x4A, 0x47, 0x40, 0x43, 0x4C, 0x4E, 0x40, 0x49, 0x47 Memory Address Block Contents 0x40 3 0x41 a 0x42 9 0x43 R 0x44 ! 0x45 8 0x46 p 0x47 d 0x48 J 0x49 7 0x4A ? 0x4B V 0x4C s 0x4D A 0x4E T 0x4F 4 Index Contents Tag Contents Tag 000 J 1001 001 010 011 100 s 1001 101 110 111 Part 2: Implementing a Direct-Mapped Cache For this part of the assignment you will use the results from Part 1 to write a cache simulator in MIPS. Since you don’t have access to the cache controller on your system, we’ll simulate a cache by storing the elements in memory instead (but conceptually you can pretend data elements are being written to the cache). 1. Take the memory configuration from Part 1 and re-create the initial state in memory with the element at 0x40 being stored at the first byte in the data section, the element at 0x41 being stored at the second byte in the data sections, and so on. 2. Your “cache” (which is being stored in memory) should begin at the 32nd byte in the data section. That is, your cache should begin at 0x10010020. 3. Your cache size will be 8 bytes (so how many bits will your tag be?) 4. Create an array of words that stores the following memory addresses: 1. 10010008 2. 1001000C 3. 10010006 4. 1001000D 5. 10010002 6. 1001000B 7. 10010005 8. 10010001 9. 10010008 10. 1001000F 11. 1001000A 12. 10010007 13. 10010000 14. 10010003 15. 1001000C 16. 1001000E 17. 10010000 18. 10010009 19. 10010007 5. Iterate over each of the 19 memory accesses and compute: a. index/cache location (the offset from 0x10010020) b. tag value (remember how many bits must be in a tag for an 8-byte cache) i. Note: you will have to devise a simple scheme for storing the tag of the value currently being stored in the cache c. Use your tag scheme to determine if the element currently stored in the “cache” is the one being requested by the memory access i. If the element in the cache is the one being requested print “Cache hit!” to the console ii. If the element in the cache is not the one being requested print “Cache miss” to the console and update iii. Keep a running count of both the cache hits and cache misses d. Once the loop is complete print: i. “There were H cache hits” (where H is the number of hits) ii. “There were M cache misses” (were M is the number of misses)