Cache window management
AssigneeLSI Corporation
InventorVinay Bangalore Shivashankaraiah
Life of this patent
Estimating the term…
Abstract
A method of managing a plurality of least recently used (LRU) queues having entries that correspond to cached data includes ordering a first plurality of entries in a first queue according to a first recency of use of cached data. The first queue corresponds to a first priority. A second plurality of entries in a second queue are ordered according to a second recency of use of cached data. The second queue corresponds to a second priority. A first entry is selected in the first queue based on the order of the first plurality of entries in the first queue. A recency property associated with the first entry is compared with a recency property associated with a second entry in the second queue. Based on a result of this comparison, the first entry and the second entry may be swapped.
Claims18
A method of managing a cache, comprising:
- maintaining a lowest priority least recently used (LRU) queue;
- maintaining a plurality of higher priority (LRU) queues, each of said higher priority LRU queues having a maximum number of entries, each of said lowest priority LRU queue and said higher priority LRU queues having a least used entry;
- determining a first entry in a first one of said plurality of higher priority LRU queues is eligible for promotion to a second one of said plurality of higher priority LRU queues;
- comparing a first hit count value associated with said first entry to a second hit count value associated with a second entry of said second one of said plurality of higher priority LRU queues, said second entry being a least used entry of said second one of said plurality of higher priority LRU queues;
- and,
- if said first hit count value is greater than said second hit count value, swapping said first entry in said first one of said plurality of higher priority LRU queues with said second entry of said second one of said plurality of higher priority LRU queues.
A method of managing a plurality of least recently used (LRU) queues having entries that correspond to cached data, comprising:
- ordering a first plurality of entries in a first queue according to a first recency of use of cached data corresponding to the respective first plurality of entries, the first queue corresponding to a first priority;
- ordering a second plurality of entries in a second queue according to a second recency of use of cached data corresponding to the respective second plurality of entries, the second queue corresponding to a second priority, the second priority being greater than the first priority;
- selecting a first entry in said first queue based on the order of said first plurality of entries in said first queue;
- and,
- comparing a recency property associated with said first entry with a recency property associated with a second entry in said second queue and based on a result of said comparison, swapping said first entry and said second entry.
A non-transitory computer readable medium having instructions stored thereon for managing a cache that, when executed by a computer, at least instruct the computer to:
- maintain a lowest priority least recently used (LRU) queue;
- maintain a plurality of higher priority (LRU) queues, each of said higher priority LRU queues having a maximum number of entries, each of said lowest priority LRU queue and said higher priority LRU queues having a least used entry;
- determine a first entry in a first one of said plurality of higher priority LRU queues is eligible for promotion to a second one of said plurality of higher priority LRU queues;
- compare a first hit count value associated with said first entry to a second hit count value associated with a second entry of said second one of said plurality of higher priority LRU queues, said second entry being a least used entry of said second one of said plurality of higher priority LRU queues;
- and,
- if said first hit count value is greater than said second hit count value, swap said first entry in said first one of said plurality of higher priority LRU queues with said second entry of said second one of said plurality of higher priority LRU queues.
Dependencies are inferred from the claim text.