Managing a prefetch buffer with probabilistic access predictions

Patent metadata

Field	Value
Publication number	US-9239794-B1
Application number	US-201313873682-A
Country	US
Kind code	B1
Filing date	Apr 30, 2013
Priority date	Jun 11, 2012
Publication date	Jan 19, 2016
Grant date	Jan 19, 2016

Abstract

A method for managing data items retrieved for storage in a prefetch memory buffer includes determining a probability that a first data item will be requested for retrieval. The method includes estimating a first request time at which the new data item will be requested. The method also includes determining a time differential for the first data item, wherein the time differential is determined based on current time and the first request time. The method includes calculating a first prefetch priority value for the first data item based on the first data item probability and the time differential. The method includes randomly comparing the first prefetch priority value of the first data item to the prefetch priority values of the one or more stored data items to identify at least one stored data item having a prefetch priority value lower than the first prefetch priority value.

First claim

The invention claimed is:

1. A method for managing data items retrieved for storage in a prefetch memory buffer, the method comprising:
a) determining a probability that a first data item will be requested for retrieval;
b) estimating a first request time at which the new data item will be requested;
c) determining a time differential for the first data item, wherein the time differential is determined based on current time and the first request time;
d) calculating a first prefetch priority value for the first data item based on the first data item probability and the time differential;
e) calculating prefetch priority values for one or more stored data items stored in the prefetch memory buffer; and
f) comparing the first prefetch priority value of the first data item to the prefetch priority values of the one or more stored data items to identify at least one stored data item having a prefetch priority value lower than the first prefetch priority value.

2. The method of claim 1 , further comprising grouping the one or more stored data items stored in the prefetch memory buffer into subsets of based on probability.

3. The method of claim 2 , wherein calculating the prefetch priority values for one or more stored data items includes calculating the prefetch priority values for each stored data item identified as having the largest time differential in each subset.

4. The method of claim 1 , further comprising replacing the at least one stored data item identified as having a prefetch priority value lower than the first prefetch priority value with the first data item in the prefetch memory buffer.

5. The method of claim 1 , further comprising analyzing one or more properties for requests of one or more subsequent data items to determine a probability that a new data item will be requested.

6. The method of claim 1 , further comprising analyzing one or more properties for request of one or more subsequent data items to estimate a time at which a new data item will be requested.

7. The method of claim 1 , comprising recalculating prefetch priority values for one or more data items stored in the prefetch memory buffer until a new request is received for a data item or until it is determined a new data item will probably be requested.

8. The method of claim 1 , comprising assigning a highest prefetch priority value to a new data item actually requested by a user.

9. A system for managing data items retrieved for storage in a prefetch buffer, the system comprising:
a processor, and;
a memory, the memory including code representing instructions that when executed cause the processor to:
determine a probability that a first data item will be requested for retrieval;
estimate a first request time at which the new data item will be requested;
determine a time differential for the first data item, wherein the time differential is determined based on current time and the first request time;
calculate a first prefetch priority value for the first data item based on the first data item probability and the time differential;
calculate prefetch priority values for one or more stored data items stored in the prefetch memory buffer; and
compare the first prefetch priority value of the first data item to the prefetch priority values of the one or more stored data items to identify at least one stored data item having a prefetch priority value lower than the first prefetch priority value.

10. The system of claim 9 , wherein the memory includes code representing instructions that when executed cause the processor to group the one or more stored data items into subsets based on probability.

11. The system of claim 10 , wherein the memory includes code representing instructions that when executed cause the processor to calculate the prefetch priority values for each stored data item identified as having the largest time differential in each subset.

12. The method of claim 9 , wherein the memory includes code representing instructions that when executed cause the processor to replace the at least one stored data item identified as having a prefetch priority value lower than the first prefetch priority value with the first data item in the prefetch memory buffer.

13. The system of claim 9 , wherein the memory includes code representing instructions that when executed cause the processor to analyze one or more properties for requests of one or more subsequent data items to determine a probability that a new data item will be requested.

14. The system of claim 9 , wherein the memory includes code representing instructions that when executed cause the processor to analyze one or more properties for request of one or more subsequent data items to estimate a time at which a new data item will be requested.

15. The system of claim 9 , wherein the memory includes code representing instructions that when executed cause the processor to recalculate prefetch priority values for one or more data items stored in the prefetch memory buffer until a new request is received for a data item or until it is determined a new data item will probably be requested.

16. The system of claim 9 , wherein the memory includes code representing instructions that when executed cause the processor to assign a highest prefetch priority value to a new data item actually requested by a user.

17. A computer program product, tangibly embodied on non-transitory computer-readable media, the computer program product being configured to cause a data processing apparatus to:
determine a probability that a first data item will be requested for retrieval;
estimate a first request time at which the new data item will be requested;
determine a time differential for the first data item, wherein the time differential is determined based on current time and the first request time;
calculate a first prefetch priority value for the first data item based on the first data item probability and the time differential;
calculate prefetch priority values for one or more stored data items stored in the prefetch memory buffer; and
compare the first prefetch priority value of the first data item to the prefetch priority values of the one or more stored data items to identify at least one stored data item having a prefetch priority value lower than the first prefetch priority value.

18. The computer program product of claim 17 , further comprising being configured to cause a data processing apparatus to group the one or more stored data items into subsets based on probability.

19. The computer program product of claim 18 , further comprising being configured to cause a data processing apparatus to calculate the prefetch priority values for each stored data item identified as having the largest time differential in each subset.

20. The computer program product of claim 17 , further comprising being configured to cause a data processing apparatus to replace the at least one stored data item identified as having a prefetch priority value lower than the first prefetch priority value with the first data item in the prefetch memory buffer.

Assignees

• Google Inc

Inventors

• Merchant Arif

Classifications

• G06F12/0862 Primary

  with prefetch · CPC title

• G06F12/0868

  Data transfer between cache memory and other subsystems, e.g. storage devices or host systems · CPC title

• G06F2212/1016

  Performance improvement · CPC title

• G06F2212/6026

  Prefetching based on access pattern detection, e.g. stride based prefetch · CPC title