Least recently used-based hotness tracking mechanism enhancements for high performance caching

Patent metadata

Field	Value
Publication number	US-10599585-B2
Application number	US-201715466986-A
Country	US
Kind code	B2
Filing date	Mar 23, 2017
Priority date	Mar 23, 2017
Publication date	Mar 24, 2020
Grant date	Mar 24, 2020

Abstract

A method and apparatus for caching data accessed in a storage device, which include a selection of a list from a plurality of lists based on a cache block accessed from a cache memory, the cache memory being partitioned into a plurality of cache portions, each of the plurality of lists being assigned to a respective cache portion of the plurality of cache portions, each of the plurality of lists indicating an order in which cache blocks of the respective cache portion were accessed. Furthermore, a determination as to whether the accessed cache block meets a list update criteria, and an update the order in which cache blocks, assigned to the selected list, were accessed from the cache memory based on determining the accessed cache block meets the list update criteria may be included.

First claim

What is claimed is:

1. A method for caching data accessed in a storage device, the method comprising:
selecting a list from a plurality of lists based on a cache block accessed from a cache memory, the cache memory being partitioned into a plurality of cache portions, each of the plurality of lists being assigned to a respective cache portion of the plurality of cache portions, each of the plurality of lists indicating an order in which cache blocks of the respective cache portion were accessed;
determining whether the accessed cache block meets a list update criteria based on a count value of the selected list, a count value of the accessed cache block, and a threshold number of updates to the selected list;
updating the order in which cache blocks, assigned to the selected list, were accessed from the cache memory based on determining the accessed cache block meets the list update criteria; and
modifying the count value of the selected list only when the order of the selected list is updated,
wherein the count value of the selected list represents a number of times the selected list has been updated based on access to the cache blocks ordered by the selected list.

2. The method of claim 1 , wherein selecting the list from the plurality of lists comprises:
determining whether an address of the accessed cache block in the cache memory is associated with the selected list within a look-up table.

3. The method of claim 2 , wherein selecting the list from the plurality of lists further comprises:
selecting the list from the plurality of lists based on determining the address of the accessed cache block is associated with the selected list.

4. The method of claim 1 , further comprising:
setting the count value of the accessed cache block to the modified count value, when the accessed cache block causes the order of the selected list to be updated.

5. The method of claim 1 , further comprising:
determining the count value of the accessed cache block.

6. The method of claim 5 , wherein determining whether the accessed cache block meets the list update criteria comprises:
comparing the difference between the count value of the selected list and the count value of the accessed cache block to the threshold number of updates.

7. The method of claim 6 ,
wherein the count value of the selected list and the count value of the accessed cache block are timestamp values.

8. The method of claim 1 , wherein updating the order in which the cache blocks, assigned to the selected list, were accessed comprises:
updating a position of the accessed cached block to a head position within the order indicated by the selected list.

9. The method of claim 1 , further comprising:
returning a cache block from the cache memory based on the selected list indicating the updated order.

10. The method of claim 1 , further comprising:
determining a list for an eviction process from the plurality of lists based on an order of eviction.

11. The method of claim 10 , further comprising:
evicting a cache block from the determined list based on the order of eviction.

12. The method of claim 1 , further comprising:
triggering a control scheme in which the threshold number of updates to the selected list is dynamically adjusted in response to the detection of one or more events.

13. The method of claim 1 , further comprising:
triggering a control scheme in which a number of the plurality of cache portions is dynamically adjusted in response to the detection of one or more events.

14. A method for caching data accessed in a storage device, the method comprising:
selecting a list from a plurality of lists based on a cache block accessed from a cache memory, the cache memory being partitioned into a plurality of cache portions, each of the plurality of lists being assigned to a respective cache portion of the plurality of cache portions, each of the plurality of lists indicating an order in which cache blocks of the respective cache portion were accessed;
updating the order in which the cache blocks, assigned to the selected list, were accessed based on a count value of the selected list, a count value of the accessed cache block, and a threshold number of updates to the selected list;
modifying the count value of the selected list only when access to the respective cache portion causes the order of the selected list to be updated; and
returning a cache block from the cache memory based on the selected list indicating the updated order,
wherein the count value of the selected list represents a number of times the selected list has been updated based on access to the cache blocks ordered by the selected list.

15. The method of claim 14 , wherein selecting the list from the plurality of lists comprises:
determining an address of the accessed cache block in the cache memory.

16. The method of claim 14 , further comprising:
determining a list for an eviction process from the plurality of lists based on a sequential order of eviction.

17. The method of claim 16 , further comprising:
evicting a cache block from the determined list based on the sequential order of eviction.

18. A device for caching data, the device comprising:
a cache memory storing a plurality of cache blocks, the cache memory having assigned thereto a list indicating an order in which the cache blocks were accessed from the cache memory; and
a cache memory controller configured to:
determine whether a block to be accessed from a storage device is a cache block stored in the cache memory,
in response to determining the block is a cache block among the cache blocks stored in the cache memory, determine whether the block stored in the cache memory meets a list update criteria based on a count value of the list, a count value of the block stored in the cache memory, and a threshold number of updates to the list,
update the order, indicated by the list, in which the cache blocks were accessed from the cache memory in response to determining the block stored in the cache memory meets the list update criteria, and
modify the count value of the list only when the order of the list is updated,

wherein the count value of the list represents a number of times the list has been updated based on access to the cache blocks ordered by the list.

19. The device of claim 18 ,
wherein the cache memory controller is configured to return a cache block from the cache memory using one of a plurality of lists, and
the cache memory comprises a plurality of cache portions, each list of the plurality of lists being assigned to a respective cache portion of the plurality of cache portions, each list indicating an order in which cache blocks of the respective cache portion were accessed.

20. The device of claim 18 , wherein the cache memory controller is configured to:
partition the cache memory into a plurality of cache portions such that each of the cache portions are of equal size.

Assignees

• Intel Corp

Inventors

• Wysoczanski Michal
• Barczak Mariusz

Classifications

• G06F2212/604

  Details relating to cache allocation · CPC title

• G06F2212/1024

  Latency reduction · CPC title

• G06F12/123 Primary

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title

• G06F12/0893 Primary

  Caches characterised by their organisation or structure · CPC title