US5146578A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of varying the amount of data prefetched to a cache memory in dependence on the history of data requests
Assignee: RPX Corp
•
Filing: 1991-04-12
•
Granted: 1992-09-08
•
Expires: 2011-04-12
Abstract
Abstract A method of dynamically prefetching data for a cache memory is controlled by the past history of data requests. If the previous fetch and current fetch request are not sequential, no data is prefetched. If the previous fetch and current fetch request are sequential and less than all of the current fetch request is already in the cache, two blocks of data sequentially beyond the current fetch request are prefetched. If the previous two blocks fetched and current fetch request are sequential and less than all of the current fetch request is already in the cache, four blocks of data sequentially beyond the current fetch request are prefetched. If the previous three blocks fetched and the current fetch request are sequential and less than all of the current fetch request is already in the cache, eight blocks of data sequentially beyond the current fetch request are preferred. The prefetch algorithm is limited at eight blocks. Each additional sequential request less than all of which is already in the cache will cause eight blocks to be prefetched.
Inventors
- 👤 Saied Zangenehpour
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 14:30
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0866; G06F12/0862; G06F2212/00; G06F2212/60; G06F2212/6026
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
105 words
A method of prefetching data for a cache memory from a mass-storage device in response to a fetch request generated by a requesting circuit, comprising the steps of: checking whether a previous fetch and a current fetch request are for data with sequential addresses, and prefetching data with sequential addresses beyond the current fetch request if the previous fetch and the current fetch request are for data with sequential addresses; and keeping track of the number of successive fetches with sequential addresses, and progressively increasing the amount of said data with sequential addresses prefetched as the number of successive fetches with sequential addresses progressively increases.
Claim 2
Independent Claim
105 words
A method of prefetching data for a cache memory from a mass-storage device in response to a fetch request generated by a requesting circuit, comprising the steps of: checking whether a previous fetch and a current fetch request are for data with sequential addresses, and prefetching data with sequential addresses beyond the current fetch request if the previous fetch and the current fetch request are for data with sequential addresses; and keeping track of the number of successive fetches with sequential addresses, and progressively increasing the amount of said data with sequential addresses prefetched as the number of successive fetches with sequential addresses progressively increases.
Claim 3
Dependent Claim
69 words
The method according to claim 1, further comprising the steps of writing an address of the previous fetch in a sector field of a register; comparing the sector field to an address of the current fetch request; and determining from the comparison of the sector field with the address of the current fetch request whether the previous fetch and the current fetch request are for data with sequential addresses.
Claim 4
Dependent Claim
62 words
The method according to claim 2, further comprising the steps of: incrementing a count field in the register in response to each successive request at sequential addresses; setting the count field to zero in response to a request at a non-sequential address; and carrying out said progressively increasing step using the value from the count field as said number of successive fetches.
Claim 5
Dependent Claim
46 words
The method according to claim 1, including the step of: treating a current fetch request for data that is already contained in the cache memory as a request which does not result in a prefetch of sequential data beyond the address of the currently requested data.
Claim 6
Independent Claim
142 words
A method of prefetching blocks of data from a first memory to a second memory in response to a fetch request generated by a requesting circuit, comprising the steps of: checking whether a previous fetch and a current fetch request are for data with sequential addresses, and keeping track of the number of successive fetches with sequential addresses; prefetching the next two sequential blocks beyond an address of the current fetch request if the previous fetch and the current fetch request are for data with sequential addresses; prefetching the next four sequential blocks beyond the current fetch request if the previous two fetches and the current fetch request are for data with sequential addresses; and prefetching the next eight sequential blocks beyond the current fetch request if the previous three fetches and the current fetch request are for data with sequential addresses.
Claim 7
Independent Claim
142 words
A method of prefetching blocks of data from a first memory to a second memory in response to a fetch request generated by a requesting circuit, comprising the steps of: checking whether a previous fetch and a current fetch request are for data with sequential addresses, and keeping track of the number of successive fetches with sequential addresses; prefetching the next two sequential blocks beyond an address of the current fetch request if the previous fetch and the current fetch request are for data with sequential addresses; prefetching the next four sequential blocks beyond the current fetch request if the previous two fetches and the current fetch request are for data with sequential addresses; and prefetching the next eight sequential blocks beyond the current fetch request if the previous three fetches and the current fetch request are for data with sequential addresses.
Claim 8
Independent Claim
180 words
A method of prefetching data for storage in a cache memory from a mass-storage device in response to a fetch request generated by a requesting circuit, comprising the steps of: checking whether a previous fetch and a current fetch request are for data with sequential addresses, and maintaining a record representative of the number of successive fetches with sequential addresses; prefetching the next two sequential blocks beyond an address of the current fetch request if the previous fetch and the current fetch request are for data with sequential addresses and the cache memory lacks a portion of the currently requested data; prefetching the next four sequential blocks beyond the current fetch request if the previous two fetches and the current fetch request are for data with sequential addresses and the cache memory lacks a portion of the currently requested data; and prefetching the next eight sequential blocks beyond the current fetch request if the previous three fetches and the current fetch request are for data with sequential addresses and the cache memory lacks a portion of the currently requested data.
Claim 9
Independent Claim
180 words
A method of prefetching data for storage in a cache memory from a mass-storage device in response to a fetch request generated by a requesting circuit, comprising the steps of: checking whether a previous fetch and a current fetch request are for data with sequential addresses, and maintaining a record representative of the number of successive fetches with sequential addresses; prefetching the next two sequential blocks beyond an address of the current fetch request if the previous fetch and the current fetch request are for data with sequential addresses and the cache memory lacks a portion of the currently requested data; prefetching the next four sequential blocks beyond the current fetch request if the previous two fetches and the current fetch request are for data with sequential addresses and the cache memory lacks a portion of the currently requested data; and prefetching the next eight sequential blocks beyond the current fetch request if the previous three fetches and the current fetch request are for data with sequential addresses and the cache memory lacks a portion of the currently requested data.
Claim 10
Dependent Claim
65 words
The method according to claim 6 further comprising the steps of: providing a register containing a sector field; writing the address of the last sector of the previous fetch in eh sector field; comparing the sector field to an address of the current fetch request; and determining from the comparison whether the previous fetch and the current fetch request are for data with sequential addresses.
Claim 11
Dependent Claim
49 words
The method according to claim 7 further comprising the steps of: providing a count field in the register; incrementing the count field in response to each sequential request; setting the count field to zero with each non-sequential request; and determining the number of sequential requests from the count field.
Claim 12
Independent Claim
239 words
A method of transferring data from a first memory to a second memory in response to successive requests which are issued by a requesting circuit and which each specify a segment of data having sequential addresses, comprising the steps of: detecting each said fetch request; fetching from said first memory to said second memory in response to detection of each of a first and a second of said requests a respective quantity of data which includes a fetch portion at sequential addresses and a prefetch portion at sequential addresses, said prefetch portion following and being contiguous to said fetch portion; and dynamically varying the size of said prefetch portion, wherein the respective prefetch portions, which are fetched in response to each of said first and second requests, are of different size, said dynamically varying step including the steps of checking whether the quantity of data to be fetched in response to a current execution of said fetching step is contiguous to the quantity of data fetched in response to the immediately preceding execution of said fetching step, keeping track of the number of successive executions of said fetching step, including the current execution thereof, in which said quantities of data fetched are all contiguous, and selecting the size of said prefetch portion in dependence on the number of successive executions of said fetching step, including the current execution thereof, in which said quantities of data fetched are all contiguous.
Claim 13
Independent Claim
239 words
A method of transferring data from a first memory to a second memory in response to successive requests which are issued by a requesting circuit and which each specify a segment of data having sequential addresses, comprising the steps of: detecting each said fetch request; fetching from said first memory to said second memory in response to detection of each of a first and a second of said requests a respective quantity of data which includes a fetch portion at sequential addresses and a prefetch portion at sequential addresses, said prefetch portion following and being contiguous to said fetch portion; and dynamically varying the size of said prefetch portion, wherein the respective prefetch portions, which are fetched in response to each of said first and second requests, are of different size, said dynamically varying step including the steps of checking whether the quantity of data to be fetched in response to a current execution of said fetching step is contiguous to the quantity of data fetched in response to the immediately preceding execution of said fetching step, keeping track of the number of successive executions of said fetching step, including the current execution thereof, in which said quantities of data fetched are all contiguous, and selecting the size of said prefetch portion in dependence on the number of successive executions of said fetching step, including the current execution thereof, in which said quantities of data fetched are all contiguous.
Claim 14
Dependent Claim
76 words
The method according to claim 9, including immediately following said detecting step the step of determining whether all data in the specified segment is already in said second memory, and thereafter carrying out said fetching step only if said determining step results in a determination that a portion of the specified segment is missing from said second memory, the segments specified by said first and second requests each including a portion missing from said second memory.
Claim 15
Dependent Claim
42 words
The method according to claim 9, wherein said selecting step is carried out by progressively increasing the size of said prefetch portion in response to a progressive increase in said number of successive fetches of said quantities of data which are contiguous.
Claim 16
Dependent Claim
29 words
The method according to claim 11, wherein said selecting step is carried out by doubling the size of said prefetch portion each time said number of successive fetches increases.
Claim 17
Dependent Claim
74 words
The method according to claim 12, wherein said fetching step includes the steps of using an integer multiple of a predetermined data block size for each said fetch portion and each said prefetch portion, and progressively increasing said prefetch portion rom two blocks to four blocks to eight blocks in successive said fetching steps in response to successive increases in said number of successive fetching steps fetching said quantities of data which are contiguous.
Claim 18
Dependent Claim
35 words
The method according to claim 9, including the steps of using as said second memory a cache memory, and using as said first memory a mass storage device which is slower than said cache memory.
References Cited (Backward Citations)
US3898624A
Cited
US4157587A
Cited
US4489378A
Cited
US4807110A
Cited
US4691277A
Cited
US4860192A
Cited
US4882642A
Cited
US4956803A
Cited
US4918587A
Cited
US4888679A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-09-08 | 1996-03-09 | 1996-09-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-09-08 | 2000-03-09 | 2000-09-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-09-08 | 2004-03-09 | 2004-09-08 | $7700.00 | Window Closed / Lapsed |