Column-associative Caches: A Technique for Reducing the Miss Rate of Direct-mapped Caches

Abstract

Direct-mapped caches are a popular design choice for high-performance processors; unfortunately, direct-mapped caches suffer systematic interference misses when more than one address map into the same cache set. This paper describes the design of column-associative caches, which minimize the conflicts that arise in direct-mapped accesses by allowing conflicting addresses to dynamically choose alternate hashing functions, so that most of the conflicting data can reside in the cache. At the same time, however, the critical hit access path is unchanged. The key to implementing this scheme efficiently is the addition to each cache set of a rehash bit, which indicates whether that set stores data that is referenced by an alternate hashing function. When multiple addresses map into the same location, these rehashed locations are preferentially replaced. We demonstrate using trace-driven simulations and an analytical model that a column-associative cache removed virtually all interference misses for large caches, without altering the critical hit access time.