Patent ID: 7870341

Claim:
A cache allowing a choice of Least Frequently Used (LFU) or Most Frequently Used (MFU) cache line replacement, the cache comprising: a plurality of cache lines; state information for at least two given cache lines of the plurality of cache lines; LFU/MFU circuitry adapted: to determine 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; when a cache miss occurs in one of the at least two given lines: to select either LFU or MFU replacement criteria, wherein said selection is based on a selection signal that indicates a type of replacement criteria; to determine which one of the at least two given cache lines should be replaced based on the new state information and the selected replacement criteria; and replacement circuitry coupled to the LFU/MFU circuitry and to the plurality of cache lines, the replacement circuitry adapted to replace the selected given cache line; wherein the state information comprises a plurality of line use counters, each line use counter corresponding to one of the cache lines; and the LFU/MFU circuitry is further adapted to increment a given line use counter when a cache line corresponding to the given line use counter is referenced; wherein the plurality of cache lines are assigned to a plurality of congruence classes, each congruence class assigned to at least two of the plurality of cache lines, whereby at least two of the line use counters corresponds to a congruence class, the state information further comprising a plurality of congruence class use counters, each of the congruence class use counters corresponding to one of the congruence classes, and wherein the LFU/MFU circuitry is further adapted to increment a given congruence class use counter when a congruence class corresponding to the given congruence class use counter is referenced; and wherein the plurality of line use counters are also assigned to the plurality of congruence classes, one line use counter per cache line assigned to a congruence class, and wherein the LFU/MFU circuitry is further adapted, when one or more of the line use counters corresponding to a given congruence class exceeds a maximum line use counter limit, to divide all of the line use counters corresponding to the given congruence class by an integer.