System and method for hierarchical approximation of least recently used replacement algorithms within a cache organized as two or more super-ways of memory blocks
View Patent ↗A system for approximating a least recently used (LRU) algorithm for memory replacement in a cache memory. In one system example, the cache memory comprises memory blocks allocated into sets of N memory blocks. The N memory blocks are allocated as M super-ways of N/M memory blocks where N is greater than M. An index identifies the set of N memory blocks. A super-way hit/replacement tracking state machine tracks hits and replacements to each super-way and maintains state corresponding to an order of hits and replacements for each super-way where the super-ways are ordered from the MRU to the LRU. Storage for the state bits is associated with each index entry where the state bits include code bits associated with a memory block to be replaced within a LRU super-way. LRU logic is coupled to the super-way hit/replacement tracking state machine to select an LRU super-way as a function of the super-way hit and replacement history. Block selection logic then selects a memory block to be replaced within the LRU super-way as a function of predefined selection criteria.
1. A system for cache memory management, the system comprising:
a cache memory, wherein the cache memory comprises memory blocks allocated into sets of N memory blocks, and wherein the N memory blocks are allocated as M super-ways of N/M memory blocks, wherein N is greater than M;
an index, wherein the index identifies the set of N memory blocks;
a super-way hit/replacement tracking state machine, wherein the super-way hit/replacement tracking state machine tracks hits and replacements to each super-way and maintains state corresponding to an order of hits and replacements to each super-way, wherein the state orders the super-ways from the MRU to the LRU;
state bit storage associated with each index entry, wherein the state bits include code bits associated with a memory block to be replaced within a LRU super-way;
LRU logic coupled to the super-way hit/replacement tracking state machine, wherein the LRU logic selects an LRU super-way as a function of the super-way hit and replacement history; and
block selection logic coupled to the LRU logic, wherein the block selection logic selects a memory block to be replaced within the LRU super-way as a function of predefined selection criteria.
2. The system of claim 1 , wherein the block selection logic includes a log2(N/M)-bit random number generator, and wherein the block selection logic selects a memory block to be replaced as a function of a random number generated by the random number generator.
3. The system of claim 1 , wherein the block selection logic selects a memory block to be replaced as a function of an approximately randomly generated number.
4. The system of claim 1 , wherein the block selection logic includes a priority encoder that uses log2(N/M) bits for each of the M super-ways to track the history of memory block replacement within each M super-way.
5. The system of claim 4 , wherein tracking the history of memory block replacement within each M super-way includes recording the most recent used way within the super-way.
6. The system of claim 4 , wherein the block selection logic selects the LRU memory block within the super-way for replacement.
7. The system of claim 1 , wherein the block selection logic includes LRU logic to select an LRU way as a function of the way hit and replacement history within each M super-way.
8. The system of claim 1 , wherein the state bits are stored in a RAM array.
9. In a cache memory having memory blocks allocated into sets of N memory blocks, a method of selecting a memory block to be replaced on a cache miss, the method comprising:
placing the N memory blocks into M groups of N/M memory blocks, wherein N is greater than M;
determining a least recently used (LRU) group of memory blocks; and
selecting a memory block to be replaced within the LRU group of memory blocks, wherein selecting includes randomly selecting the memory block;
wherein determining the LRU group of memory blocks includes ordering the M groups of memory blocks from a most recently used (MRU) group to the LRU group, wherein ordering the groups includes tracking, via a state machine, an order of hits and replacements to each group such that a state of the state machine corresponds to an order of hits.
10. In a cache memory having memory blocks allocated into sets of N memory blocks, a method of selecting a memory block to be replaced on a cache miss, the method comprising:
placing the N memory blocks into M groups of N/M memory blocks, wherein N is greater than M;
determining a least recently used (LRU) group of memory blocks, wherein determining the LRU group of memory blocks includes ordering the M groups of memory blocks from a most recently used (MRU) group to the LRU group, wherein ordering the groups includes tracking, via a state machine, an order of hits and replacements to each group such that a state of the state machine corresponds to an order of hits;
determining an LRU block within the LRU group, wherein determining includes ordering memory blocks within the groups by tracking hits to memory blocks within each group; and
selecting the LRU memory block as the memory block to be replaced within the LRU group of memory blocks.