Method of varying the amount of data prefetched to a cache memory in dependence on the history of data requests

• US 5,146,578 A
• Filed: 04/12/1991
• Issued: 09/08/1992
• Est. Priority Date: 05/01/1989
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Zenith Data Systems Corp. (Acer, Inc.)
• Inventors: Zangenehpour, Saied
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): Ray, Gopal C.
• Application Number:
  US07/685,157
• Time in Patent Office: 515 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 364/200 MS File, 364/900 MS File, 395/425, 395/800
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.