LRU-based column-associative caches

ABSTRACT

The column-associative cache is a direct-mapped cache that may be accessed more than once, each time with a different hash function, to satisfy a memory request. In the column-associative cache, the possible locations that a line can reside in defines the column. The original scheme relies on a rehash bit array to guide the replacement policy within the column. A subsequent proposal uses an index vector to speed up the cache search within the column. In this paper, we consider the idea of using the Least-Recently-Used (LRU) information to guide both the replacement policy and the search order. Results from trace-driven simulations using the SPEC95 benchmark suite show that the LRU-based scheme can achieve better or at least comparable performance.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Design, Measurement, Performance, Theory