Method and apparatus of prefetching streams of varying prefetch depth

• US 8,103,832 B2
• Filed: 06/26/2007
• Issued: 01/24/2012
• Est. Priority Date: 06/26/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gara, Alan, Ohmacht, Martin, Salapura, Valentina, Sugavanam, Krishnan, Hoenicke, Dirk
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): CARDWELL, ERIC
• Application Number:
  US11/768,697
• Publication Number:
  US 20090006762A1
• Time in Patent Office: 1,673 Days
• Field of Search: None
• 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;

wherein in response to an occurrence of a load miss on requested data contained in cache line n, determining whether the cache line n exists in the prefetch buffer,

and if the cache line n exists in the prefetch buffer, fetching next cache line n+1 into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n+1 to true if the next cache line n+1 does not exist in the prefetch buffer,

and if the cache line n does not exist in the prefetch buffer, checking a history buffer for an address associated with the cache line n and if the history buffer contains the address associated with the cache line n, fetching the cache line n into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n to true, and if the history buffer does not contain the address associated with the cache line n, inserting the address associated with the cache line n and an address associated with the cache line n+1 into the history buffer,

and if the next cache line n+1 exists in the prefetch buffer, determining whether the access pattern is single memory stream access pattern or whether the prefetch on hit flag associated with the cache line n+1 is set to true and

if the access pattern is single memory access pattern or the prefetch on hit flag associated with the cache line n+1 is set to true or both, fetching cache line n+2 into the prefetch buffer if the cache line n+2 is not in the prefetch buffer, and setting a prefetch on hit flag associated with the cache line n+2 to true, and resetting the prefetch on hit flag associated with the cache line n to false; and

if the access pattern is not single memory access pattern and the prefetch on hit flag associated with the cache line n+1 is not set to true, resetting the prefetch on hit flag associated with the cache line n to false.

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, wherein the plurality of states includes at least an idle state in which a control of a prefetcher waits for a load miss to occur, a check state to which the control transitions if a prefetch was issued to the cache line n+1, and in which the control stays if one or more hits occur to the cache line n or no additional load requests, and a single stream state, to which the control transitions if a load request for latest prefetched line occurs.

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,

wherein in response to an occurrence of a load miss on requested data contained in cache line n, determining whether the cache line n exists in the prefetch buffer,

and if the cache line n exists in the prefetch buffer, fetching next cache line n+1 into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n+1 to true if the next cache line n+1 does not exist in the prefetch buffer,

and if the cache line n does not exist in the prefetch buffer, checking a history buffer for an address associated with the cache line n and if the history buffer contains the address associated with the cache line n, fetching the cache line n into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n to true, and if the history buffer does not contain the address associated with the cache line n, inserting the address associated with the cache line n and an address associated with the cache line n+1 into the history buffer,

and if the next cache line n+1 exists in the prefetch buffer, determining whether the access pattern is single memory stream access pattern or whether the prefetch on hit flag associated with the cache line n+1 is set to true and

if the access pattern is single memory access pattern or the prefetch on hit flag associated with the cache line n+1 is set to true or both, fetching cache line n+2 into the prefetch buffer if the cache line n+2 is not in the prefetch buffer, and setting a prefetch on hit flag associated with the cache line n+2 to true, and resetting the prefetch on hit flag associated with the cache line n to false.

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,

wherein in response to an occurrence of a load miss on requested data contained in cache line n, determining whether the cache line n exists in the prefetch buffer,

and if the cache line n exists in the prefetch buffer, fetching next cache line n+1 into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n+1 to true if the next cache line n+1 does not exist in the prefetch buffer,

and if the cache line n does not exist in the prefetch buffer, checking a history buffer for an address associated with the cache line n and if the history buffer contains the address associated with the cache line n, fetching the cache line n into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n to true, and if the history buffer does not contain the address associated with the cache line n, inserting the address associated with the cache line n and an address associated with the cache line n+1 into the history buffer,

and if the next cache line n+1 exists in the prefetch buffer, determining whether the access pattern is single memory stream access pattern or whether the prefetch on hit flag associated with the cache line n+1 is set to true and

if the access pattern is single memory access pattern or the prefetch on hit flag associated with the cache line n+1 is set to true or both, fetching cache line n+2 into the prefetch buffer if the cache line n+2 is not in the prefetch buffer, and setting a prefetch on hit flag associated with the cache line n+2 to true, and resetting the prefetch on hit flag associated with the cache line n to false; and

if the access pattern is not single memory access pattern and the prefetch on hit flag associated with the cache line n+1 is not set to true, resetting the prefetch on hit flag associated with the cache line n to false.

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,

wherein in response to an occurrence of a load miss on requested data contained in cache line n, determining whether the cache line n exists in the prefetch buffer,

and if the cache line n exists in the prefetch buffer, fetching next cache line n+1 into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n+1 to true if the next cache line n+1 does not exist in the prefetch buffer,

and if the cache line n does not exist in the prefetch buffer, checking a history buffer for an address associated with the cache line n and if the history buffer contains the address associated with the cache line n, fetching the cache line n into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n to true, and if the history buffer does not contain the address associated with the cache line n, inserting the address associated with the cache line n and an address associated with the cache line n+1 into the history buffer,

and if the next cache line n+1 exists in the prefetch buffer, determining whether the access pattern is single memory stream access pattern or whether the prefetch on hit flag associated with the cache line n+1 is set to true and

if the access pattern is single memory access pattern or the prefetch on hit flag associated with the cache line n+1 is set to true or both, fetching cache line n+2 into the prefetch buffer if the cache line n+2 is not in the prefetch buffer, and setting a prefetch on hit flag associated with the cache line n+2 to true, and resetting the prefetch on hit flag associated with the cache line n to false; and

if the access pattern is not single memory access pattern and the prefetch on hit flag associated with the cache line n+1 is not set to true, resetting the prefetch on hit flag associated with the cache line n to false.