Less recently and frequently used (LRAFU) cache replacement policy
View Patent ↗Apparatuses, systems, methods, and program products are disclosed for cache replacement. An apparatus includes a cache memory structure, a processor, and memory that stores code executable by the processor. The code is executable by the processor to receive a value to be stored in the cache memory structure, identify, in response to determining that the received value is not currently stored in an entry of the cache memory structure, a least recently used (“LRU”) set of entries of the cache memory structure where the received value can be stored, and select a least frequently used (“LFU”) entry of the identified LRU set of entries for storing the received value.
1. An apparatus comprising:
a cache memory structure;
a processor; and
a memory that stores code executable by the processor to:
receive a value to be stored in the cache memory structure;
identify, in response to determining that the received value is not currently stored in an entry of the cache memory structure, a least recently used (“LRU”) set of entries of the cache memory structure where the received value can be stored, the LRU set of entries identified based on a recentness value that indicates which of a plurality of predefined sets of entries for the cache memory structure is the least recently used; and
select a least frequently used (“LFU”) entry of the identified LRU set of entries for storing the received value, the LFU entry selected based on a usage frequency count for the entries of the identified LRU set of entries, the usage frequency count indicating which entry of the identified LRU set of entries is the least frequently used.
2. The apparatus of claim 1 , wherein each of the plurality of predefined sets of entries for the cache memory structure is represented by one or more LRU bits, the recentness value comprising the one or more LRU bits that represent the identified LRU set of entries.
3. The apparatus of claim 2 , wherein the code is further executable by the processor to update the one or more LRU bits comprising the recentness value to identify a new LRU set of entries in response to storing the received value.
4. The apparatus of claim 2 , wherein the code is further executable by the processor to update the one or more LRU bits comprising the recentness value to identify a new LRU set replacement order in response to an entry outside of the current most recently used (“MRU”) set of entries being accessed.
5. The apparatus of claim 1 , wherein the usage frequency count for each entry of the plurality of predefined sets of entries comprises one or more LFU bits indicating which entry for each set of entries is the LFU entry.
6. The apparatus of claim 5 , wherein the code is further executable by the processor to update the one or more LFU bits of the usage frequency count for the identified LRU set of entries in response to storing the received value in the LFU entry such that the value of the one or more LFU bits corresponds to the LFU entry of the LRU set of entries.
7. The apparatus of claim 6 , wherein the code is further executable by the processor to set the usage frequency count for the identified LRU set of entries to a bit value that identifies the entry where the received value is stored as a most frequently used (“MFU”) entry and one or more other entries where the received value is not stored as LFU entries.
8. The apparatus of claim 1 , wherein the code is further executable by the processor to set, in response to determining that the received value is currently stored in an entry of the cache memory structure, the usage frequency count for a set of entries where the currently stored value is stored to a value that corresponds to how often the currently stored entry is accessed relative to one or more other entries of the set of entries.
9. The apparatus of claim 1 , wherein each of the plurality of predefined sets of entries comprises a pair of entries for storing values in the cache memory structure.
10. The apparatus of claim 1 , wherein the code is further executable by the processor to one of:
randomly select entries of the cache memory structure for generating each of the plurality of predefined sets of entries; and
sequentially select entries of the cache memory structure for generating each of the plurality of predefined sets of entries.
11. The apparatus of claim 1 , wherein the entries for each of the plurality of predefined sets of entries comprises memory addresses for the cache memory structure.
12. A method comprising:
receiving, by a processor, a value to be stored in a cache memory structure;
identifying, in response to determining that the received value is not currently stored in an entry of the cache memory structure, a least recently used (“LRU”) set of entries of the cache memory structure where the received value can be stored, the LRU set of entries identified based on a recentness value that indicates which of a plurality of predefined sets of entries for the cache memory structure is the least recently used; and
selecting a least frequently used (“LFU”) entry of the identified LRU set of entries for storing the received value, the LFU entry selected based on a usage frequency count for the entries of the identified LRU set of entries, the usage frequency count indicating which entry of the identified LRU set of entries is the least frequently used.
13. The method of claim 12 , wherein each of the plurality of predefined sets of entries for the cache memory structure is represented by one or more LRU bits, the recentness value comprising the one or more LRU bits that represent the identified LRU set of entries.
14. The method of claim 13 , further comprising updating the one or more LRU bits comprising the recentness value to identify a new LRU set of entries in response to storing the received value.
15. The method of claim 13 , further comprising updating the one or more LRU bits comprising the recentness value to identify a new LRU set replacement order in response to an entry outside of the current most recently used (“MRU”) set of entries being accessed.
16. The method of claim 12 , wherein the usage frequency count for each entry of the plurality of predefined sets of entries comprises one or more LFU bits indicating which entry for each set of entries is the LFU entry.
17. The method of claim 16 , further comprising updating the one or more LFU bits of the usage frequency count for the identified LRU set of entries in response to storing the received value in the LFU entry such that the value of the one or more LFU bits corresponds to the LFU entry of the LRU set of entries.
18. The method of claim 17 , further comprising setting the usage frequency count for the identified LRU set of entries to a bit value that identifies the entry where the received value is stored as a most frequently used (“MFU”) entry and one or more other entries where the received value is not stored as LFU entries.
19. The method of claim 12 , further comprising setting, in response to determining that the received value is currently stored in an entry of the cache memory structure, the usage frequency count for a set of entries where the currently stored value is stored to a value that corresponds to how often the currently stored entry is accessed relative to one or more other entries of the set of entries.
20. A program product comprising a computer readable storage medium that stores code executable by a processor, the executable code comprising code to perform:
receiving a value to be stored in a cache memory structure;
identifying, in response to determining that the received value is not currently stored in an entry of the cache memory structure, a least recently used (“LRU”) set of entries of the cache memory structure where the received value can be stored, the LRU set of entries identified based on a recentness value that indicates which of a plurality of predefined sets of entries for the cache memory structure is the least recently used; and
selecting a least frequently used (“LFU”) entry of the identified LRU set of entries for storing the received value, the LFU entry selected based on a usage frequency count for the entries of the identified LRU set of entries, the usage frequency count indicating which entry of the identified LRU set of entries is the least frequently used.