Method and apparatus to prefetch sequential pages in a multi-stream environment

• US 6,567,894 B1
• Filed: 12/08/1999
• Issued: 05/20/2003
• Est. Priority Date: 12/08/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Hsu, Windsor Wee Sun, Young, Honesty Cheng
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): CHACE, CHRISTIAN
• Application Number:
  US09/456,539
• Time in Patent Office: 1,259 Days
• Field of Search: 365/189.01, 365/230.01, 709/231, 711/137, 712/205, 712/206, 712/207
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

The present invention is system and method for determining information that is to be prefetched in a multi-stream environment which can detect sequential streams from among the aggregate reference stream and yet requires relatively little memory to operate, which is uniquely adapted for use in a multi-stream environment, in which multiple data accessing streams are performing sequential accesses to information independently of each other. A reference address referencing stored information is received. A matching run is found. A count corresponding to the run is updated. If the count exceeds a predetermined threshold, an amount of information to prefetch is determined. If a predetermined fraction of the determined amount of information to prefetch must still be retrieved, the determined amount of information is retrieved. A matching run may be found by searching a stack comprising a plurality of entries to find an entry corresponding to the reference address. Each of the plurality of entries may be associated with a maximum accessed address, a forward range, and a backward range, and the searching step may comprise searching the plurality of stack entries in one direction starting at an end of the stack and determining whether the reference address is between (maximum accessed address−backward range) and (maximum accessed address+forward range) for each stack entry until a matching stack entry is found.

Claims

1. A method for determining information that is to be prefetched in a multi-stream environment, comprising the steps of:

receiving a reference address referencing stored information;

finding a matching run;

updating a count corresponding to the run;

determining an amount of information to prefetch, if the count exceeds a predetermined threshold; and

retrieving the determined amount of information, if a predetermined fraction of the determined amount of information to prefetch must still be retrieved.

2. The method of claim 1, wherein the step of finding a matching run comprises the step of:

searching a stack comprising a plurality of entries to find an entry corresponding to the reference address.

3. The method of claim 2, wherein each of the plurality of entries is associated with a maximum accessed address, a forward range, and a backward range, and the searching step comprises the steps of:

searching the plurality of stack entries in one direction starting at an end of the stack; and

determining whether the reference address is between (maximum accessed address−

backward range) and (maximum accessed address+forward range) for each stack entry until a matching stack entry is found.

4. The method of claim 3, further comprising the step of:

rearranging the plurality of stack entries according to a replacement policy.

5. The method of claim 4, wherein the replacement policy is a least-recently used replacement policy.

6. The method of claim 5, further comprising the step of:

storing the retrieved information in a prefetch buffer, the prefetch buffer organized using a first-in, first-out replacement policy.

7. The method of claim 6, wherein the rearranging policy makes the referenced information eligible for immediate replacement.

8. The method of claim 3, wherein the step of determining an amount of information to prefetch comprises the step of:

determining an amount of information to prefetch based on the count corresponding to the run and on a size of the prefetch buffer.

9. The method of claim 3, wherein in the updating step comprises the step of:

updating the count corresponding to a run for each reference address matching the run.

10. The method of claim 3, wherein in the updating step comprises the step of:

updating the count corresponding to a run for each unique reference address matching the run.

11. A system for determining information that is to be prefetched in a multi-stream environment, comprising:

means for receiving a reference address referencing stored information;

means for finding a matching run;

means for updating a count corresponding to the run;

means for determining an amount of information to prefetch, if the count exceeds a predetermined threshold; and

means for retrieving the determined amount of information, if a predetermined fraction of the determined amount of information to prefetch must still be retrieved.

12. The system of claim 11, wherein the means for finding a matching run comprises:

means for searching a stack comprising a plurality of entries to find an entry corresponding to the reference address.

13. The system of claim 12, wherein each of the plurality of entries is associated with a maximum accessed address, a forward range, and a backward range, and the searching means comprises:

means for searching the plurality of stack entries in one direction starting at an end of the stack; and

means for determining whether the reference address is between (maximum accessed address−

backward range) and (maximum accessed address+forward range) for each stack entry until a matching stack entry is found.

14. The system of claim 13, further comprising:

means for rearranging the plurality of stack entries according to a replacement policy.

15. The system of claim 14, wherein the replacement policy is a least-recently used replacement policy.

16. The system of claim 15, further comprising:

means for storing the retrieved information in a prefetch buffer, the prefetch buffer organized using a first-in, first-out replacement policy.

17. The system of claim 16, wherein the rearranging policy makes the referenced information eligible for immediate replacement.

18. The system of claim 13, wherein the means for determining an amount of information to prefetch comprises:

means for determining an amount of information to prefetch based on the count of references corresponding to the run and on a size of the prefetch buffer.

19. The system of claim 13, wherein in the updating means comprises:

means for updating the count corresponding to a run for each reference address matching the run.

20. The system of claim 13, wherein in the updating means comprises:

means for updating the count corresponding to a run for each unique reference address matching the run.

21. A computer program product for determining information that is to be prefetched in a multi-stream environment, comprising:

a computer readable medium;

computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of;

receiving a reference address referencing stored information;

finding a matching run;

updating a count corresponding to the run;

determining an amount of information to prefetch, if the count exceeds a predetermined threshold; and

retrieving the determined amount of information, if a predetermined fraction of the determined amount of information to prefetch must still be retrieved.

22. The computer program product of claim 21, wherein the step of finding a matching run comprises the step of:

searching a stack comprising a plurality of entries to find an entry corresponding to the reference address.

23. The computer program product of claim 22, wherein each of the plurality of entries is associated with a maximum accessed address, a forward range, and a backward range, and the searching step comprises the steps of:

searching the plurality of stack entries in one direction starting at an end of the stack; and

determining whether the reference address is between (maximum accessed address−

backward range) and (maximum accessed address+forward range) for each stack entry until a matching stack entry is found.

24. The computer program product of claim 23, further comprising the step of:

rearranging the plurality of stack entries according to a replacement policy.

25. The computer program product of claim 24, wherein the replacement policy is a least-recently used replacement policy.

26. The computer program product of claim 25, further comprising the step of:

storing the retrieved information in a prefetch buffer, the prefetch buffer organized using a first-in, first-out replacement policy.

27. The computer program product of claim 26, wherein the rearranging policy makes the referenced information eligible for immediate replacement.

28. The computer program product of claim 23, wherein the step of determining an amount of information to prefetch comprises the step of:

determining an amount of information to prefetch based on the count of references corresponding to the run and on a size of the prefetch buffer.

29. The computer program product of claim 23, wherein in the updating step comprises the step of:

updating the count corresponding to a run for each reference address matching the run.

30. The computer program product of claim 23, wherein in the updating step comprises the step of:

updating the count corresponding to a run for each unique reference address matching the run.