In this exercise, we will examine how replacement policies impact miss rate. Assume a 2-way set associative cache with 4 blocks. To solve the problems in this exercise, you may find it helpful to draw a table like the one below, as demonstrated for the address sequence €œ0, 1, 2, 3, 4.€

Consider the following address sequence: 0, 2, 4, 8, 10, 12, 14, 16, 0

1. Assuming an LRU replacement policy, how many hits does this address sequence exhibit?

2. Assuming an MRU (most recently used) replacement policy, how many hits does this address sequence exhibit?

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. Which address should be evicted at each replacement to maximize the number of hits? How many hits does this address sequence exhibit if you follow this €œoptimal€ 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?

Contents of Cache Address of Memory Blocks After Reference Evicted Set 1 Block Accessed Hit or MIss Set 1 Block Set o Set o Mem[0] Mem[0] Miss Mem[1] Mem[1] Mem[1] Mem[1] Miss Mem[2] Mem[2] Mem[2] Miss Mem[0] Mem[0] Mem[4] Mem[3] Mem[3] Miss Mis 4 2.