Question

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”.

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]
…

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

(5.13.1) Assuming an LRU replacement policy, how many hits does this address sequence exhibit?

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

(5.13.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?

(5.13.4) Which address should be evicted at each replacement to maximize the number of hits? How many does this address sequence exhibit if you follow this “optimal” policy?

(5.13.5) Describe why it is difficult to implement a cache replacement policy that is optimal for all address sequences.

(5.13.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 the miss rate?

Short answer

(5.13.1)

With LRU replacement, there is 0 hit with the address sequence 0, 2, 4, 8, 10, 12, 14, 16, 0.

(5.13.2)

With MRU replacement, there is 1 hit with the address sequence 0, 2, 4, 8, 10, 12, 14, 16, 0.

(5.13.3)

With random replacement policy, there is 0 or 1 hit with the address sequence 0, 2, 4, 8, 10, 12, 14, 16, 0.

(5.13.4)

Any replacement policy is optimal if it gives 1 hit.

(5.13.5)

It is difficult to implement a cache replacement policy that is optimal for all address sequences because the cache doesn’t know the future address sequences.

(5.13.6)

The miss rate could decrease if an address with less temporal locality is replaced. Otherwise, the miss rate could increase too.

Step-by-step solution

Identify the number of hits using LRU replacement

(5.13.1)

In LRU replacement, the least recently used memory block is replaced. The address sequence is 0, 2, 4, 8, 10, 12, 14, 16, 0.

All these address sequences go in set 0. The table for the given address sequences is given below:

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]
2	Miss		Mem[0]	Mem[2]
4	Miss	0	Mem[4]	Mem[2]
8	Miss	2	Mem[4]	Mem[8]
10	Miss	4	Mem[10]	Mem[8]
12	Miss	8	Mem[10]	Mem[12]
14	Miss	10	Mem[14]	Mem[12]
16	Miss	12	Mem[14]	Mem[16]
0	Miss	14	Mem[0]	Mem[16]

Thus, there is no hit.

Identify the number of hits using MRU replacement

(5.13.2)

In MRU replacement, the most recently used memory block is replaced. The address sequence is 0, 2, 4, 8, 10, 12, 14, 16, 0.

All these address sequences go in set 0. The table for the given address sequences is given below:

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]
2	Miss		Mem[0]	Mem[2]
4	Miss	2	Mem[0]	Mem[4]
8	Miss	4	Mem[0]	Mem[8]
10	Miss	8	Mem[0]	Mem[10]
12	Miss	10	Mem[0]	Mem[12]
14	Miss	12	Mem[0]	Mem[14]
16	Miss	14	Mem[0]	Mem[16]
0	Hit		Mem[0]	Mem[16]

Thus, the number of hits is 1.

Identify the number of hits using a random replacement policy

(5.13.3)

The random replacement policy is flipping a coin. There is only one repeated memory address in the given sequence. Using a random replacement policy, the maximum number of hits could be 1 (for the memory address reference 0). Thus, the number of hits could be 0 or 1.

Identify the number of hits using optimal policy

(5.13.4)

Using any replacement policy, the maximum hits are 1. This is because of the reason that in the address sequence, only 0 is referenced again. Therefore, any address replacement is optimal if it gives one hit.

Identify the difficulty to implement an optimal replacement policy

(5.13.5)

The optimal replacement policy should cause a smaller number of misses. For a smaller number of misses, that block should be replaced which is not used in the future. But the future references of address are not known to the cache. So, only a good prediction can be made. The design of an optimal cache replacement policy is difficult to design.

Identify the impact of making a decision about caching a requested address or not on the miss rate

(5.13.6)

The miss rate can be improved by knowing the temporal locality of the memory block. If the temporal locality of the block is less, then it can be removed from the cache and this reduces the number of misses. On the other hand, one could choose the wrong addresses to replace and this could lead to high misses.