Customizing Cache Indexing Through Entropy Estimation

Modern computers heavily rely on caches as one of the means to achieve higher performance. As a result, cache management has been the topic of extensive research. Compared to cache replacement and prefetching, cache indexing has re-ceived far less interest over the years. Being in the critical path, a good cache index function must exhibit a high performance while having a minimal computational delay. Previous indexing schemes fall short of these requirements, having either moderate performance or a prohibitively expensive delay. We propose ENTROPyINDEX, an entropy-based cache indexing scheme that can deliver superior performance while maintaining a minimal computational cost. ENTROPyINDEX is based on the idea of constructing the index function dynamically at runtime using the address bits with the highest entropy (randomness) to maximize the balance of the cache access distribution. The entropy of the address bits is measured by determining which bits change between two subsequent cache misses. ENTROPyINDEX periodically compares the entropy of different bits and selects the ones that change the most. This dynamic selection scheme allows ENTROPyINDEX to adapt to different types of applications. Our experimental results show that ENTROPyINDEX outper-forms previous indexing schemes both with and without hardware prefetching. For SPEC 2006, SPEC 2017, PARSEC 3.0 and GAP benchmarks without prefetching, ENTROPyINDEX delivers a geometric mean IPC improvement of 3.39% (with the highest being 52.2%), compared to a 1.74% improvement of the state-of-the-art index function (PRIME) and a 1.76% improvement of a commercialized indexing scheme (XORHASH) over the baseline power-of-two modulo scheme. With prefetching, ENTROPyINDEX is the only indexing scheme with a substantial performance gain of 1.42% (with the highest being 30.1 %), compared to a 0.41 % improvement of Prime and a 0.49% improvement of Xorhash over the same baseline. For non-uniform applications and no-prefetching, ENTROPyINDEX gives an IPC speed up of 5.58%, compared to a 2.26% speed up of Prime and a 2.23% speed up of Xorhash. For non-uniform applications with prefetching, the IPC speed up of ENTROPyINDEX is 2.08%, compared to a 0.35% speed up of Prime and a 0.53% speed up of Xorhash. For CVP workloads without prefetching, ENTROPyINDEX delivers a speed up of 3.04% over the baseline compared to a 1.52% of Prime and a 2.04% of Xorhash. For CVP workloads with prefetching, ENTROPyINDEX improves the IPC by 1.60%, compared to 0.63% of Prime and 1.07% of Xorhash.