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?

In this exercise, we will examine how replacement policies impact miss rate. Assume a 2-way set associative cache with 4 blocks. You may find it helpful to draw a table like those found on page 482 to solve the problems in this exercise, as demonstrated below on the address sequence "0, 1, 2, 3, 4."

Transcribed Image Text:

Address of Memory| Hit or Block Accessed Miss a. 0 1 2 3 4 b. Miss Miss Miss Miss Miss Evicted Block 0, 2, 4, 8, 10, 12, 14, 16, 0 1, 3, 5, 1, 3, 1, 3, 5, 3 0 Contents of Cache Blocks after Reference The following table shows address sequences. Set 0 Mem[0] Mem[0] Mem[0] Mem[0] Mem[4] Set 0 Mem[2] Mem[2] Mem[2] Address Sequence Set 1 Mem[1] Mem[1] Mem[1] Mem[1] Set 1 Mem[3] Mem[3]