Probabilistic associative cache

摘要

A computer cache memory organization called Probabilistic Set Associative Cache (PAC) has the hardware complexity and latency of a direct-mapped cache but functions as a set-associative cache for a fraction of the time, thus yielding better than direct mapped cache hit rates. The organization is considered a (1+P)—way set associative cache, where the chosen parameter called Override Probability P determines the average associativity, for example, for P=0.1, effectively it operates as if a 1.1-way set associative cache.

主权项

1. A computer cache memory
physically organized as a direct mapped cache; configured to be accessed with a cache tag search policy of a set-associative cache, in which one or more extra bits in cache directory entries are employed in addition to a direct mapped cache tag in order to implement N-way associative cache behavior, wherein the one or more extra bits indicate a home location node from a plurality of nodes within a given set, wherein the cache tag search policy searches the home location node prior to a remainder of the plurality of nodes when searching the given set; and configured to be modified by a replacement algorithm which implements two different replacement algorithms in one, namely a direct mapped replacement algorithm and a N-way set associative replacement algorithm, where N is 2 or greater, wherein each node of said plurality of nodes is usable to cache only a single address at a time, wherein a home location node is only a portion of cache memory, wherein the one or more extra bits must allow designating a location storing a single address within a set, wherein a directory entry of said computer cache memory is updated on cache misses such that an oracle decides whether to employ the direct mapped replacement algorithm or the N-way set associative replacement algorithm, and wherein said oracle comprises a random number generator and a parameter that is an override probability P, where on a miss if a generated random number is less than or equal to the override probability P, then the N-way replacement algorithm is employed, otherwise, if the generated random number is greater than the override probability P, then the direct mapped replacement algorithm is employed.