Evaluating Associativity in CPU Caches

Abstract

Because of the infeasibility or expense of large fully-associative caches, cache memories are often designed to be set-associative or direct-mapped. This paper presents (1) new and efficient algorithms for simulating alternative direct-mapped and set-associative caches, and (2) uses those algorithms to quantify the effect of limited associativity on the cache miss ratio. We introduce a new algorithm, forest simulation, for simulating alternative direct-mapped caches and generalize one, which we call all-associativity simulation, for simulating alternative direct-mapped, set-associative and fully-associative caches. We find that while all-associativity simulation is theoretically less efficient than forest simulation or stack simulation (a commonly-used simulation algorithm), in practice, it is not much slower and allows the simulation of many more caches with a single pass through an address trace. We also provide data and insight into how varying associativity affects the miss ratio,. We show: (1) how to use the simulations of alternative caches to isolate the cause of misses; (2) that the principle reason why set-associative miss ratios are larger than full-associative ones is (as one might expect) that too many active blocks map to a fraction of the sets even when blocks map to sets in a uniform random manner; and (3) that reducing associativity from eight-way to four-way, from four-way to two-way, and from two-way to direct-mapped causes relative miss ratio increases in our data of about 5, 10, and 30 percent respectively, regardless cache size.