Increasing a cache's associativity $($with all other parameters kept constant$)$ statistically reduces the miss rate. However, there can be pathological cases where increasing a cache's associativity would increase the miss rate for a particular workload.

Consider the case of direct$-$mapped cache compared to a two$-$way set associative cache of equal size. Assume that the set associative cache uses the LRU replacement 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.$)$