Systems and methods for managing cache pre-fetch

Patent metadata

Field	Value
Publication number	US-10489295-B2
Application number	US-201313829152-A
Country	US
Kind code	B2
Filing date	Mar 14, 2013
Priority date	Oct 8, 2012
Publication date	Nov 26, 2019
Grant date	Nov 26, 2019

Abstract

A system includes a data store and a memory cache subsystem. A method for pre-fetching data from the data store for the cache includes determining a performance characteristic of a data store. The method also includes identifying a pre-fetch policy configured to utilize the determined performance characteristic of the data store. The method also includes pre-fetching data stored in the data store by copying data from the data store to the cache according to the pre-fetch policy identified to utilize the determined performance characteristic of the data store.

First claim

What is claimed is:

1. A system comprising:
a data store configured to store data on a storage medium; and
a memory cache subsystem configured to connect to the data store, wherein the memory cache subsystem comprises:
a plurality of memory elements configured to store cached data; and
a pre-fetch controller configured to:
determine a characteristic of the data store, the determined characteristic indicating a physical arrangement of data stored on the storage medium of the data store;
select a pre-fetch process for the data store from a plurality of pre-fetch processes based on associations between the determined characteristic of the data store and the pre-fetch processes, the associations identifying one or more pre-fetch processes configured to efficiently pre-fetch data stored in the indicated physical arrangement of the data stored on the storage medium of the data store;
change a memory access bandwidth limit for the pre-fetch process for pre-fetching data from the data store based on an amount of bandwidth used by an application for at least one memory access operation to the plurality of memory elements associated with the application accessing data in the data store; and
execute the selected pre-fetch process to retrieve pre-fetch data corresponding to a designated logical address from the data store for storage in one or more of the memory elements, wherein:
a first pre-fetch process associated with a sequential physical data arrangement is configured to pre-fetch additional data physically proximate to the pre-fetched data on the storage medium of the data store; and
a second pre-fetch process associated with one or more of a random physical data arrangement and a pseudo-random physical data arrangement is configured to pre-fetch the data corresponding to the designated logical address without pre-fetching the additional data.

2. The system of claim 1 , wherein the physical arrangement of the data stored on the storage medium of the data store is one of: the sequential data arrangement, the random data arrangement, and the pseudo random data arrangement.

3. The system of claim 1 , wherein:
the pre-fetch controller is further configured to receive a read operation initiated external to the memory cache subsystem; and
the first pre-fetch process is further configured to pre-fetch data from sequential physical locations on the storage medium of the data store in response to the read operation.

4. The system of claim 1 , wherein:
the pre-fetch controller is further configured to receive a pre-fetch operation pertaining to the designated logical address initiated external to the memory cache subsystem; and
the first pre-fetch process is configured to pre-fetch the additional data from sequential physical locations of the storage medium of the data store in response to the pre-fetch operation initiated external to the memory cache subsystem.

5. The system of claim 4 , wherein the pre-fetch controller is further configured to receive the pre-fetch operation from the application, the application running external to the memory cache subsystem.

6. The system of claim 4 , wherein the pre-fetch controller is further configured to receive the pre-fetch operation from an external utility of a computing device communicatively coupled to the pre-fetch controller.

7. The system of claim 1 , wherein:
the determined characteristic of the data store further indicates a size of an output buffer of the data store; and
the pre-fetch controller is further configured to retrieve the pre-fetch data from surplus buffer content in the output buffer of the data store by use of the selected pre-fetch process.

8. The system of claim 1 , wherein the pre-fetch controller is further configured to autonomously initiate a pre-fetch operation in response to a determination that at least some of the plurality of memory elements of the memory cache subsystem are available and ready to be written with the pre-fetch data.

9. The system of claim 1 , wherein the pre-fetch controller is further configured to initiate a plurality of pre-fetch operations to fill up the plurality of memory elements of the memory cache subsystem during an initial operation period after startup of the memory cache subsystem.

10. The system of claim 9 , further comprising an address translation layer configured to connect to the memory cache subsystem, wherein the pre-fetch controller is further configured to receive a cache status indication from the address translation layer, wherein the cache status indication indicates whether the plurality of memory elements are full with cached data.

11. The system of claim 1 , wherein the pre-fetch controller is further configured to limit usage of processing resources allocated to pre-fetch operations in response to a memory access operation initialized by a software application.

12. The system of claim 11 , further comprising an address translation layer configured to connect to the memory cache subsystem, wherein the pre-fetch controller is further configured to receive an instruction from the address translation layer to limit the usage of the processing resources allocated to the pre-fetch operations.

13. A method, comprising:
determining a characteristic of a storage device, the determined characteristic indicating a physical arrangement of data stored on a storage medium of the storage device;
selecting a pre-fetch process for the storage device from a plurality of pre-fetch processes based on associations between the determined characteristic and respective pre-fetch processes, the associations identifying pre-fetch processes configured to efficiently pre-fetch data stored in the physical arrangement indicated by the determined characteristic;
changing a memory access bandwidth limit for the pre-fetch process for pre-fetching data from the storage device based on an amount of bandwidth used for at least one memory access operation to a cache associated with an application accessing data on the storage device; and
implementing the selected pre-fetch process to admit pre-fetch data of the storage device into the cache, wherein:
implementing a first pre-fetch process associated with a sequential physical data arrangement comprises retrieving designated data from the storage device with additional data physically proximate to the designated data within the storage device; and
implementing a second pre-fetch process not associated with the sequential physical data arrangement comprises retrieving the designated data from the storage device without retrieving the additional data.

14. The method of claim 13 , wherein implementing the first pre-fetch process further comprises:
receiving a read operation to read data from the storage device, wherein the read operation specifies at least one block of data;
admitting the specified block of data into the cache; and
pre-fetching at least one additional block of data to admit into the cache in response to the read operation.

15. The method of claim 13 , further comprising:
receiving a pre-fetch request from an external application, wherein the pre-fetch request identifies a sequence of blocks on the storage device; and
admitting the sequence of blocks identified in the pre-fetch request into the cache in response to the pre-fetch request.

16. The method of claim 15 , further comprising designating the sequence of blocks as high priority for populating the cache from an initial state following startup of the cache.

17. The method of claim 15 , further comprising designating the sequence of blocks identified in th

Assignees

• Sandisk Technologies Llc

Inventors

• Nellans David
• Mathiasen Torben
• Flynn David
• Talagala Nisha

Classifications

• G06F12/0862 Primary

  with prefetch · CPC title

• G06F2212/602

  Details relating to cache prefetching · CPC title

• G06F2212/6022

  Using a prefetch buffer or dedicated prefetch cache · CPC title