Patent Number: 6,490,654

Title: Method and apparatus for replacing cache lines in a cache memory

Abstract: A cache memory replacement algorithm replaces cache lines based on thelikelihood that cache lines will not be needed soon. A cache memory inaccordance with the present invention includes a plurality of cache linesthat are accessed associatively, with a count entry associated with eachcache line storing a count value that defines a replacement class. Thecount entry is typically loaded with a count value when the cache line isaccessed, with the count value indicating the likelihood that the contentsof cache lines will be needed soon. In other words, data which is likelyto be needed soon is assigned a higher replacement class, while data thatis more speculative and less likely to be needed soon is assigned a lowerreplacement class. When the cache memory becomes full, the replacementalgorithm selects for replacement those cache lines having the lowestreplacement class. Accordingly, the cache lines selected for replacementcontain the most speculative data in the cache that is least likely to beneeded soon.

Inventors: Wickeraad; John A. (Loomis, CA), Lyle; Stephen B. (Rocklin, CA), Voge; Brendan A. (Granite Bay, CA)


International Classification: G06F 12/12 (20060101); G06F 1/00 (20060101); G06F 012/12 ()

Expiration Date: 12/02015