Conflict Avoiding Caches Invite New Data Layout Optimizations
Bavo Nootaert, Hans Vandierendonck, Koen De Bosschere · Ghent University Academic Bibliography (Ghent University) · 2006
Cache performance can be seriously degraded by conflict misses, which occur when too many addresses in the working set are mapped to the same sets of the cache.Past research has investigated a myriad techniques to remove conflict misses.Software-driven optimizations (e.g.padding and blocking) reorganize data or statements in a program in order to improve locality.Hardware optimizations include hashed indexing, i.e. the set index is computed using a XOR-based hash function instead of the conventional modulo indexing.It has been repeatedly shown that both software and hardware optimizations can effectively remove conflict misses.We confirm on a set of numerical kernels that hashing removes most conflict misses and that it avoids unusually high miss rates, which occur for pathological data layouts.Second, we show that data layout optimizations such as intra-variable padding do not consistently outperform caches with hashing.Furthermore, these optimizations provide only marginal improvements for caches with hashing.Caches with hashed set index functions allow new data layout optimizations which are meaningless in modulo-indexed caches.This paper introduces base address optimization and shows that the number of conflict misses can be reduced by over 15% on average for numerical kernels.Optimizing the base address is at least as powerful as intra-variable padding and it removes additional misses when applied together with intra-variable padding or blocking.