$[20]$ B$.3>$ Increasing a cache's associativity $($with all other parameters kept con$-$

stant$)$ statistically reduces the miss rate. However, there can be pathological cases

where increasing a cache's associativity would increase the miss rate for a partic$-$

ular workload.

Consider the case of direct$-$mapped compared to a two$-$way set associative

cache of equal size. Assume that the set associative cache uses the LRU replace$-$

ment policy. To simplify, assume that the block size is one word. Now, construct a

trace of word accesses that would produce more misses in the two$-$way associative

cache.

$($Hint: Focus on constructing a trace of accesses that are exclusively directed to

a single set of the two$-$way set associative cache, such that the same trace would

exclusively access two blocks in the direct$-$mapped cache.$)$