In this exercise, we will examine how replacement policies impact miss rate. Assume a 2-way set associative cache with 4 one word blocks.
Consider the following word address sequence: 0, 1, 2, 3, 4, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0.
1. Assuming an LRU replacement policy, which accesses are hits?
2. Assuming an MRU (most recently used) replacement policy, which accesses are hits?
3. Simulate a random replacement policy by flipping a coin. For example, “heads” means to evict the first block in a set and “tails” means to evict the second block in a set. How many hits does this address sequence exhibit?
4. Describe an optimal replacement policy for this sequence. Which accesses are hits using this policy?
5. Describe why it is difficult to implement a cache replacement policy that is optimal for all address sequences.
6. Assume you could make a decision upon each memory reference whether or not you want the requested address to be cached. What impact could this have on miss rate?