Cache line replacement techniques allowing choice of LFU or MFU cache line replacement

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 step of incrementing a given line use counter when a cache line corresponding to the given line use counter is referenced;
• 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 that indicates a type of replacement criteria;
• and
• replacing one of the at least two given cache lines based on the new state information and the selected replacement criteria,
• 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 comprises a plurality of congruence class use counters;
• the step of determining new state information further comprises the step of incrementing a given one of the plurality of congruence class use counters when a congruence class corresponding to the given congruence class use counter is referenced, wherein each of the plurality of congruence class use counters corresponds to one of the congruence classes;
• 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
• the step of determining new state information further comprises the step of, when one or more of the line use counters corresponding to a given congruence class exceeds a maximum line use counter limit, dividing all of the line use counters corresponding to the given congruence class by an integer.