METHOD AND APPARATUS OF PREFETCHING STREAMS OF VARYING PREFETCH DEPTH

• US 20090006762A1
• Filed: 06/26/2007
• Published: 01/01/2009
• Est. Priority Date: 06/26/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gara, Alan G., Ohmacht, Martin, Salapura, Valentina, Hoenicke, Dirk, Sugavanam, Krishnan
• Granted Patent: US 8,103,832 B2
• Time in Patent Office: Days
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

Method and apparatus of prefetching streams of varying prefetch depth dynamically changes the depth of prefetching so that the number of multiple streams as well as the hit rate of a single stream are optimized. The method and apparatus in one aspect monitor a plurality of load requests from a processing unit for data in a prefetch buffer, determine an access pattern associated with the plurality of load requests and adjust a prefetch depth according to the access pattern.

Claims

1. A method of prefetching streams of varying prefetch depth, comprising:

monitoring a plurality of load requests from a processing unit for data in a prefetch buffer and determining an access pattern associated with the plurality of load requests;

adjusting a prefetch depth according to the access pattern; and

prefetching data of prefetch depth to the prefetch buffer.

2. The method of claim 1, wherein the step of monitoring is performed using a state machine that transitions among a plurality of states based on the plurality of load requests from the processing unit.

3. The method of claim 1, wherein the prefetch depth is adjusted so that the prefetch depth when the plurality of load requests follow a sequential access pattern is greater than the prefetch depth when the plurality of load requests do not follow a sequential access pattern.

4. The method of claim 1, wherein the prefetch depth is at least a data size that can be processed by the processing unit per cycle multiplied by a number of cycles it takes to prefetch data into the prefetch buffer, when the plurality of load requests follow a sequential access pattern.

5. The method of claim 1, wherein the step of adjusting includes:

increasing the prefetch depth when the plurality of load requests follow a sequential access pattern; and

decreasing the prefetch depth when the plurality of load requests do not follow a sequential access pattern.

6. The method of claim 1, wherein the step of adjusting includes:

increasing the prefetch depth to at least one more cache line than previous prefetch depth when the plurality of load requests follow a sequential access pattern.

7. The method of claim 1, wherein the load requests from the processing unit are triggered when there is a miss in a first level of cache memory, and wherein data of prefetch depth is prefetched from a second level of cache memory to the prefetch buffer.

8. The method of claim 1, wherein the steps are performed dynamically as each load request is received from the processing unit.

9. The method of claim 1, wherein the step of monitoring includes receiving a signal from the processing unit to determine an access pattern associated with the plurality of load requests.

10. A method of prefetching streams of varying prefetch depth, comprising:

receiving a load request from a processing unit;

determining whether the load request follows a sequential access pattern of memory locations;

for the load request that follows a sequential access pattern, increasing or maintaining a prefetch depth to have at least two additional cache lines adjacent to a cache line associated with the load request prefetched to a prefetch buffer;

for the load request that does not follow a sequential access pattern, decreasing the prefetch depth if a previous load request was following a sequential access pattern; and

prefetching data of the prefetch depth to the prefetch buffer.

11. The method of claim 10, further including:

returning data associated with the load request to the processing unit.

12. The method of claim 10, wherein the step of determining is performed using a state machine that transitions among different states based on the received load request from the processing unit.

13. The method of claim 10, wherein the step of determining is performed using a hint from the processing unit.

14. The method of claim 10, wherein the steps are performed dynamically as each load request is received from the processing unit.

15. An apparatus for prefetching streams of varying prefetch depth, comprising:

a prefetch buffer operable to store prefetched data;

a mode control logic operable to monitor a plurality of load requests from a processing unit for data in the prefetch buffer and to determine an access mode associated with the plurality of load requests; and

a prefetch engine operable to adjust a prefetch depth according to the access mode to prefetch data of prefetch depth to the prefetch buffer.

16. The apparatus of claim 15, wherein the mode control logic includes a state machine for determining the access mode based on the plurality of load requests.

17. The apparatus of claim 15, further including:

registers for storing signals from the processing unit, wherein the mode control logic determines an access mode based on the signals in the registers.

18. The apparatus of claim 15, wherein the prefetch engine adjusts a prefetch depth so that for the access mode that is determined to have a single sequential memory access pattern, the prefetch depth is increased.

19. The apparatus of claim 15, wherein said apparatus is a prefetch cache operating between two levels of cache memory in a hierarchical cache memory structure.

20. A system for prefetching streams of varying prefetch depth, comprising:

means for storing prefetched data;

means for monitoring a plurality of load requests from a processing unit for data in the prefetch buffer and determining an access mode associated with the plurality of load requests; and

means for adjusting a prefetch depth according to the access mode and prefetching data of prefetch depth to the prefetch buffer.