Computer Sciences Dept.

Evaluating Associativity in CPU Caches

Mark D Hill and Alan J Smith

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.

Download this report (PDF)

Return to tech report index

Computer Science | UW Home