Probabilistic associative cache
AssigneeInternational Business Machines Corporation
InventorsBulent Abali, John S. Dodson, Moinuddin K. Qureshi, Balaram Sinharoy
Life of this patent
Estimating the term…
Abstract
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.
Claims10
A computer cache memory organization called Probabilistic Set Associative Cache (PAC) physically organized as a direct mapped cache but employs a cache tag search policy of a set-associative cache, in which N−1 extra tag bits in the cache directory entries are employed in addition to the direct mapped cache tag in order to implement N-way associative cache behavior and a replacement algorithm which implements two different replacement algorithms in one, namely the direct mapped and the N-way set associative replacement algorithms.
A method of operation of a computer cache memory called Probabilistic Set Associative Cache (PAC) comprising the steps of:
- physically organizing the PAC as a direct mapped cache;
- employing a cache tag search policy of a set-associative cache in which N−1 extra tag bits in the cache directory entries are employed in addition to the direct mapped cache tag in order to implement N-way associative cache behavior;
- and
- employing a replacement algorithm which implements two different replacement algorithms in one, namely the direct mapped and the N-way set associative replacement algorithms.
Dependencies are inferred from the claim text.