$(8$ points$)$

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

$\backslash$table$[[\backslash$table$[[$Address of$],[$Memory$],[$Block Accessed$]],$Hit or Miss,$\backslash$table$[[$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]],[$dots$,,,,,,]]$

Consider the following address sequence: $1,3,5,7,11,13,15,5,1$

$4\mathrm{.}1-$ Assuming an LRU replacement policy, how many hits does this address sequence exhibit? Please show the status of the cache after each address is accessed.

$4\mathrm{.}2-$ Assuming an MRU $($most recently used$)$ replacement policy, how many hits does this address sequence exhibit? Please show the status of the cache after each address is accessed.

File Preview