Simulate a random replacement policy by lipping 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?

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 Evicted Block Accessed Miss Block a. 0 1 2 3 4 b. Miss Miss Miss Miss Miss 0 0, 2, 4, 8, 10, 12, 14, 16, 0 1, 3, 5, 1, 3, 1, 3, 5, 3 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]