Published Articles >> Table of Contents >> Abstract

10th International Symposium on High Performance Computer Architecture (HPCA'04)   p. 288
Using Prime Numbers for Cache Indexing to Eliminate Conflict Misses
Mazen Kharbutli, North Carolina State University
Keith Irwin, North Carolina State University
Yan Solihin, North Carolina State University
Jaejin Lee, Seoul National University

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/HPCA.2004.10015
Send link to a friend

Abstract
Using alternative cache indexing/hashing functions is a popular technique to reduce conflict misses by achieving a more uniform cache access distribution across the sets in the cache. Although various alternative hashing functions have been demonstrated to eliminate the worst case conflict behavior, no study has really analyzed the pathological behavior of such hashing functions that often result in performance slowdown. In this paper, we present an in-depth analysis of the pathological behavior of cache hashing functions. Based on the analysis, we propose two new hashing functions: prime modulo and prime displacement that are resistant to pathological behavior and yet are able to eliminate the worst case conflict behavior in the L2 cache. We show that these two schemes can be implemented in fast hardware using a set of narrow add operations, with negligible fragmentation in the L2 cache. We evaluate the schemes on 23 memory intensive applications. For applications that have non-uniform cache accesses, both prime modulo and prime displacement hashing achieve an average speedup of 1.27 compared to traditional hashing, without slowing down any of the 23 benchmarks. We also evaluate using multiple prime displacement hashing functions in conjunction with a skewed associative L2 cache. The skewed associative cache achieves a better average speedup at the cost of some pathological behavior that slows down four applications by up to 7%.
Back to Top Additional Information
Citation:  Mazen Kharbutli, Keith Irwin, Yan Solihin, Jaejin Lee, "Using Prime Numbers for Cache Indexing to Eliminate Conflict Misses," hpca, p. 288,  10th International Symposium on High Performance Computer Architecture (HPCA'04),  2004