Stride-based prefetch mechanism using a prediction confidence value

• US 6,976,147 B1
• Filed: 01/21/2003
• Issued: 12/13/2005
• Est. Priority Date: 01/21/2003
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Alsup, Mitchell, Isaac, Roger D.
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): Doan, Duc T
• Application Number:
  US10/347,828
• Time in Patent Office: 1,057 Days
• Field of Search: 711/137, 711/205, 711/239, 712/205, 712/239
• US Class Current: 711/205
• 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

A prefetch mechanism includes a prefetch predictor table coupled to a prefetch control. The prefetch predictor table may include a plurality of locations configured to store a plurality of entries each indicative of a stride between a respective pair of memory requests. Each of the plurality of entries may be stored in a respective one of the plurality of locations dependent upon a value of an earlier stride. The prefetch control may be configured to prefetch an address based upon a given one of the plurality of entries in the prefetch predictor table.

Claims

1. A prefetch mechanism comprising:

a prefetch predictor table including a plurality of locations configured to store a first plurality of entries each indicative of a stride between a respective pair of memory requests, wherein each of said first plurality of entries is stored in a respective location of said plurality of locations dependent upon a value of an earlier stride;

wherein said prefetch predictor table further includes a second plurality of entries each corresponding to a respective one of said first plurality of entries, wherein each of said second plurality of entries includes a count value indicative of a number of times said stride between a respective pair of memory requests is equal to said value of said current stride;

a prefetch control coupled to said prefetch predictor table and configured to access a first location of said plurality of locations dependent upon a value of a current stride and to prefetch an address based upon a given one of said first plurality of entries stored within the first location in response to said count value stored within the first location being greater than a first predetermined threshold.

2. The prefetch mechanism as recited in claim 1 further comprising an address queue configured to store addresses associated with received memory requests.

3. The prefetch mechanism as recited in claim 1, wherein said prefetch control is further configured to access a respective one of said plurality of locations dependent upon said value of an earlier stride and to compare said stride between a respective pair of memory requests with a value of a current stride.

4. The prefetch mechanism as recited in claim 3, wherein said prefetch control is further configured to increment said count value in response to said stride between a respective pair of memory requests being equal to said value of said current stride.

5. The prefetch mechanism as recited in claim 3, wherein said prefetch control is further configured to decrement said count value in response to said stride between a respective pair of memory requests not being equal to said value of said current stride.

6. The prefetch mechanism as recited in claim 3, wherein said prefetch control is further configured to replace said stride between a respective pair of memory requests with said value of said current stride in response to said count value being equal to zero.

7. The prefetch mechanism as recited in claim 1, wherein said prefetch control is further configured to prefetch a second address based upon accessing a second location of said plurality of locations dependent upon a stride value stored in said first location of said plurality of locations and in response to said count values stored within said first location and said second location being greater than or equal to a second predetermined threshold.

8. The prefetch mechanism as recited in claim 7, wherein said prefetch control is further configured to prefetch a third address based upon accessing a third location of said plurality of locations dependent upon a stride value stored in said second location of said plurality of locations and in response to said count values stored within said second location and said third location being greater than or equal to a third predetermined threshold.

9. A method of prefetching addresses comprising:

storing a first plurality of entries each indicative of a stride between a respective pair of memory requests within a plurality of locations of a prefetch predictor table, wherein each of said first plurality of entries is stored in a respective location of said plurality of locations dependent upon a value of an earlier stride;

storing a second plurality of entries each corresponding to a respective one of said first plurality of entries, wherein each of said second plurality of entries includes a count value indicative of a number of times said stride between a respective pair of memory requests is equal to said value of said current stride;

accessing a first location of said plurality of locations dependent upon a value of a current stride; and

prefetching an address based upon a given one of said plurality of entries stored within the first location in response to said count value stored within the first location being greater than a first predetermined threshold.

10. The method as recited in claim 9 further comprising storing addresses associated with received memory requests within an address queue.

11. The method as recited in claim 9 further comprising accessing a respective one of said plurality of locations dependent upon said value of an earlier stride and comparing said stride between a respective pair of memory requests with a value of a current stride.

12. The method as recited in claim 11 further comprising storing a count value within each of a second plurality of entries of said prefetch predictor table, wherein said count value is indicative of a number of times said stride between a respective pair of memory requests is equal to said value of said current stride wherein each of said second plurality of entries corresponds to a respective one of said plurality of entries.

13. The method as recited in claim 12 further comprising incrementing said count value in response to said stride between a respective pair of memory requests being equal to said value of said current stride.

14. The method as recited in claim 12 further comprising decrementing said count value in response to said stride between a respective pair of memory requests not being equal to said value of said current stride.

15. The method as recited in claim 12 further comprising replacing said stride between a respective pair of memory requests with said value of said current stride in response to said count value being equal to zero.

16. The method as recited in claim 9, further comprising prefetching a second address based upon accessing a second location of said plurality of locations dependent upon a stride value stored in said first location of said plurality of locations and in response to said count values stored within said first location and said second location being greater than or equal to a second predetermined threshold.

17. The method as recited in claim 16 further comprising prefetching a third address based upon accessing a third location of said plurality of locations dependent upon a stride value stored in said second location of said plurality of locations and in response to said count values stored within said second location and said third location being greater than or equal to a third predetermined threshold.

18. A processor comprising:

a memory controller configured to control accesses to a system memory, wherein said memory controller includes a prefetch mechanism comprising;

a prefetch predictor table including a plurality of locations configured to store a first plurality of entries each indicative of a stride between a respective pair of memory requests, wherein each of said plurality of entries is stored in a respective location of said plurality of locations dependent upon a value of an earlier stride;

wherein said prefetch predictor table further includes a second plurality of entries each corresponding to a respective one of said first plurality of entries, wherein each of said second plurality of entries includes a count value indicative of a number of times said stride between a respective pair of memory requests is equal to said value of said current stride; and

a prefetch control coupled to said prefetch predictor table and configured to access a first location of said plurality of locations dependent upon a value of a current stride and to prefetch an address based upon a given one of said first plurality of entries stored within the first location in response to said count value stored within the first location being greater than a first predetermined threshold.

19. A computer system comprising:

a system memory configured to store instructions and data; and

a processor coupled to execute said instructions, wherein said processor includes a memory controller configured to control accesses to said system memory, wherein said memory controller includes a prefetch mechanism comprising;

a prefetch predictor table including a plurality of locations configured to store a first plurality of entries each indicative of a stride between a respective pair of memory requests, wherein each of said plurality of entries is stored in a respective location of said plurality of locations dependent upon a value of an earlier stride;

wherein said prefetch predictor table further includes a second plurality of entries each corresponding to a respective one of said first plurality of entries, wherein each of said second plurality of entries includes a count value indicative of a number of times said stride between a respective pair of memory requests is equal to said value of said current stride; and

a prefetch control coupled to said prefetch predictor table and configured to access a first location of said plurality of locations dependent upon a value of a current stride and to prefetch an address based upon a given one of said first plurality of entries stored within the first location in response to said count value stored within the first location being greater than a first predetermined threshold.

20. A computer system comprising:

a system memory configured to store instructions and data;

a processor coupled to execute said instructions; and

a system controller coupled between said processor and said system memory, wherein said system controller includes a memory controller configured to control accesses to said system memory, wherein said memory controller includes a prefetch mechanism comprising;

a prefetch predictor table including a plurality of locations configured to store a first plurality of entries each indicative of a stride between a respective pair of memory requests, wherein each of said plurality of entries is stored in a respective location of said plurality of locations dependent upon a value of an earlier stride;

wherein said prefetch predictor table further includes a second plurality of entries each corresponding to a respective one of said first plurality of entries wherein each of said second plurality of entries includes a count value indicative of a number of times said stride between a respective pair of memory requests is equal to said value of said current stride; and

a prefetch control coupled to said prefetch predictor table and configured to access a first location of said plurality of locations dependent upon a value of a current stride and to prefetch an address based upon a given one of said first plurality of entries stored within the first location in response to said count value stored within the first location being greater than a first predetermined threshold.