Adaptive prefetching of data from a disk
First Claim
1. A method for adaptively selecting an optimal pre-fetch policy betweena first pre-fetch policy, in which a request for desired data from a data-set is satisfied by reading said desired data, and a second pre-fetch policy, in which a request for desired data from a data-set is satisfied by reading said data-set, said method comprising:
- collecting statistics on a number of avoidable read-misses;
on the basis of said statistics, defining a first threshold value;
upon detection of an unavoidable read-miss, generating a random number, and on the basis of a sign of a difference between said threshold value and said random number, selecting said optimal pre-fetch policy from said first and second pre-fetch policies.
9 Assignments
0 Petitions
Accused Products
Abstract
A method for adaptively selecting an optimal pre-fetch policy between a first pre-fetch policy, in which a request for desired data from a data-set is satisfied by reading the desired data, and a second pre-fetch policy, in which a request for desired data from a data-set is satisfied by reading the data-set. The method includes collecting statistics on a number of avoidable read-misses. On the basis of the statistics, a first threshold value is defined and frequently updated. Upon detection of an unavoidable read-miss, a random number is generated and the optimal pre-fetch policy is selected on the basis of a sign of a difference between the threshold value and the random number.
52 Citations
39 Claims
-
1. A method for adaptively selecting an optimal pre-fetch policy between
a first pre-fetch policy, in which a request for desired data from a data-set is satisfied by reading said desired data, and a second pre-fetch policy, in which a request for desired data from a data-set is satisfied by reading said data-set, said method comprising: -
collecting statistics on a number of avoidable read-misses;
on the basis of said statistics, defining a first threshold value;
upon detection of an unavoidable read-miss, generating a random number, and on the basis of a sign of a difference between said threshold value and said random number, selecting said optimal pre-fetch policy from said first and second pre-fetch policies. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
determining a threshold read-miss probability at which said optimal pre-fetch policy transitions from said first pre-fetch policy to said second pre-fetch policy;
changing said value of said random-walk variable by an amount dependent on said threshold read-miss probability.
-
-
8. The method of claim 1 wherein generating a random number comprises generating a random number having a uniform probability distribution over an interval defined by an upper bound and a lower bound.
-
9. The method of claim 1 wherein collecting statistics comprises classifying a read-miss as an avoidable-read miss or an unavoidable read-miss.
-
10. The method of claim 9 wherein classifying a read-miss comprises inspecting a flag associated with said data-set, said flag being indicative of whether data from said data-set has been previously requested.
-
11. The method of claim 10 wherein inspecting said flag comprises determining an identity of a system requesting said data from said data-set.
-
12. A mass-storage system for providing desired data to at least one host computer, said mass-storage system comprising:
-
a data-storage device having a data-set stored thereon, said data-set including said desired data;
a controller in communication with said data-storage device, said controller including a memory element for storage of statistics indicative of a number of avoidable read-misses;
a random-number generator for generating a random number in response to detection of an unavoidable read-miss;
a processor in communication with said memory element and said random-number generator for selecting an optimal pre-fetch policy on the basis of a sign of a difference between a threshold value defined on the basis of said statistics and said random number, said optimal pre-fetch policy being selected from a first pre-fetch policy in which a request for desired data from a data-set is satisfied by reading said desired data, and a second pre-fetch policy in which a request for desired data from a data-set is satisfied by reading said data-set. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A computer-readable medium having encoded thereon software for adaptively selecting an optimal pre-fetch policy between
a first pre-fetch policy, in which a request for desired data from a data-set is satisfied by reading said desired data, and a second pre-fetch policy, in which a request for desired data from a data-set is satisfied by reading said data-set, said software including instructions for: -
collecting statistics on a number of avoidable read-misses;
on the basis of said statistics, defining a first threshold value;
upon detection of an unavoidable read-miss, generating a random number, and on the basis of a sign of a difference between said threshold value and said random number, selecting said optimal pre-fetch policy from said first and second pre-fetch policies. - View Dependent Claims (30, 31, 32, 33, 34, 35, 36, 37, 38, 39)
determining a threshold read-miss probability at which said optimal pre-fetch policy transitions from said first pre-fetch policy to said second pre-fetch policy;
changing said value of said random-walk variable by an amount dependent on said threshold read-miss probability.
-
-
36. The computer-readable medium of claim 22 wherein said instructions for generating a random number comprise instructions for generating a random number having a uniform probability distribution over an interval defined by an upper bound and a lower bound.
-
37. The computer-readable medium of claim 22 wherein said instructions for collecting statistics comprise instructions for classifying a read-miss as an avoidable-read miss or an unavoidable read-miss.
-
38. The computer-readable medium of claim 37 wherein said instructions for classifying a read-miss comprise instructions for inspecting a flag associated with said data-set, said flag being indicative of whether data from said data-set has been previously requested.
-
39. The computer-readable medium of claim 38 wherein said instructions for inspecting said flag comprise instructions for determining an identity of a system requesting said data from said data-set.
-
23. A method for adaptively selecting an optimal pre-fetch policy between
a first pre-fetch policy, in which a request for desired data from a data-set is satisfied by reading said desired data, and a second pre-fetch policy, in which a request for desired data from a dataset is satisfied by reading said data-set, said method comprising: -
collecting statistics on a number of avoidable read-misses;
on the basis of said statistics, defining a first threshold value;
upon detection of an unavoidable read-miss, generating a random number, and on the basis of a sign of a difference between said threshold value and said random number, selecting said optimal pre-fetch policy from said first and second pre-fetch policies. - View Dependent Claims (24, 25)
determining a threshold read-miss probability at which said optimal pre-fetch policy transitions from said first pre-fetch policy to said second pre-fetch policy;
changing said value of said random-walk variable by an amount dependent on said threshold read-miss probability.
-
-
26. A mass-storage system for providing desired data to at least one host computer, said mass-storage system comprising:
-
a data-storage device having a data-set stored thereon, said data-set including said desired data;
a controller in communication with said data-storage device, said controller including a memory element for storage of statistics indicative of a number of avoidable read-misses;
a processor in communication with said memory element and said random number generator for selecting an optimal pre-fetch policy on the basis of said statistics, said optimal pre-fetch policy being selected from a first pre-fetch- policy in which a request for desired data from a data-set is satisfied by reading said desired data, and a second pre-fetch policy in which a request for desired data from a data-set is satisfied by reading said data-set. - View Dependent Claims (27, 28)
wherein said controller further comprises a random-number generator for generating a random number in response to detection of an unavoidable read-miss, and wherein said processor for selecting an optional pre-fetch policy on the basis of said statistics is a processor for selecting an optimal pre-fetch policy on the basis of a sign of a difference between a threshold value defined on the basis of said statistics and said random number. -
28. The mass-storage system of claim 26, wherein said statistics stored in said memory element comprise a random-walk variable having a value indicative of a likelihood of an avoidable read-miss.
-
-
29. A computer-readable medium having encoded thereon software for adaptively selecting an optimal pre-fetch policy between
a first pre-fetch policy, in which a request for desired data from a data-set is satisfied by reading said desired data, and a second pre-fetch policy, in which a request for desired data from a data-set is satisfied by reading said data-set, said software including instructions for: -
collecting statistics on a number of avoidable read-misses;
on the basis of said statistics, defining a first threshold value;
upon detection of an unavoidable read-miss, generating a random number, and on the basis of a sign of a difference between said threshold value and said random number, selecting said optimal pre-fetch policy from said first and second pre-fetch policies.
-
Specification