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

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

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]