Patent ID: 7133971

Claim:
A method allowing a choice of Least Frequently Used (LFU) or Most Frequently Used (MFU) cache line replacement the method comprising the steps of: determining new state information for at least two given cache lines of a plurality of cache lines in a cache, the new state information based at least in part on prior state information for the at least two given cache lines, wherein the state information comprises a plurality of line use counters, each line use counter corresponding to one of the plurality of cache lines; and wherein the step of determining new state information further comprises the steps of: incrementing a given line use counter when a cache line corresponding to the given line use counter is referenced; inverting a predetermined number of line use counters; selecting, based on the step of selecting either LFU or MFU replacement criteria, either values of the predetermined number of line use counters or the inverted versions of the predetermined number of line use counters, wherein the values of the predetermined number of line use counters are selected for an LFU calculation and the inverted versions of the predetermined number of line use counters are selected for an MFU calculation; and determining which of the values of the predetermined number of line use counters or the inverted versions of the predetermined number of line use counters is smallest in value; and when an access miss occurs in one of the at least two given lines: selecting either LFU or MFU replacement criteria, wherein said selection is based on a selection signal; and replacing one of the at least two given cache lines based on the new state information and the selected replacement criteria.