Exercise 5.12 In this exercise, we will examine how replacement policies impact miss rate.

Assume a two-way set-associative cache with four blocks. You may fi nd it helpful to draw a table like those found on page 483 to solve the problems in this exercise, as demonstrated below on the address sequence “0, 1, 2, 3, 4”.

Address of memory block accessed Hit or miss Evicted block Contents of cache blocks after reference Set 0 Set 0 Set 1 Set 1 0 Miss Mem[0]

1 Miss Mem[0] Mem[1]

2 Miss Mem[0] Mem[2] Mem[1]

3 Miss Mem[0] Mem[2] Mem[1] Mem[3]

4 Miss 0 Mem[4] Mem[2] Mem[1] Mem[3]

…

The following table shows address sequences.

Address sequence

a. 0, 2, 4, 0, 2, 4, 0, 2, 4

b. 0, 2, 4, 2, 0, 2, 4, 0, 2 5.12.1 [5] <5.3, 5.5> Assuming an LRU replacement policy, how many hits does this address sequence exhibit?

5.12.2 [5] <5.3, 5.5> Assuming an MRU (most recently used) replacement policy, how many hits does this address sequence exhibit?

5.12.3 [5] <5.3, 5.5> Simulate a random replacement policy by fl ipping a coin. For example, “heads” means to evict the fi rst block in a set and “tails” means to evict the second block in a set. How many hits does this address sequence exhibit?

5.12.4 [10] <5.3, 5.5> 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.12.5 [10] <5.3, 5.5> Describe why it is diffi cult to implement a cache replacement policy that is optimal for all address sequences.
5.12.6 [10] <5.3, 5.5> 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?