Voting data prefetch engine

• US 5,822,790 A
• Filed: 02/07/1997
• Issued: 10/13/1998
• Est. Priority Date: 02/07/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Mehrotra, Sharad
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Namazi, Mehdi
• Application Number:
  US08/797,105
• Time in Patent Office: 613 Days
• Field of Search: 711/100, 711/117, 711/118, 711/137, 711/1, 711/3, 711/119, 711/122, 711/213, 711/204, 395/381, 395/383, 395/856-865, 326/11, 371/36
• US Class Current: 711/213
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6022 Using a prefetch buffer or dedicated prefetch cache
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 9/3802 Instruction prefetching

Abstract

A voter provided in combination with a plurality of prefetch predictors provides improved prefetch performance. In one embodiment, the voter determines which of the prefetch predictors is making more accurate predictions, and uses predictions of the more effective prefetch predictor to prefetch data into a buffer for use in satisfying cache misses. A voting prefetch engine advantageously improves cache performance, and therefore processor performance, by reducing cache misses more than cache misses would be reduced by operation an individual prefetch predictor. Stride predictor-type and stream predictor-type prefetch predictors may be provided in combination with a prefetch buffer and voter to provide improved data cache performance in a high-performance processor.

Claims

1. An apparatus comprising:

a prefetch buffer for a cache;

first and second prefetch predictors; and

a voter coupled to select a prefetch address from one of the prefetch predictors based on prediction efficacies thereof and to prefetch data corresponding to the selected prefetch address into the prefetch buffer.

2. An apparatus, as recited in claim 1, wherein the prediction efficacy is indicated based on uses of prefetched data from the prefetch buffer to service misses in the cache.

3. An apparatus, as recited in claim 1,

wherein the prefetch buffer includes prediction source storage and use storage associated with prefetched data storage;

and

wherein the voter is coupled to the prefetch buffer to receive a prediction efficacy feedback signal therefrom, the prediction efficacy feedback signal being a function of respective proportions of prefetched data used to service misses in the cache.

4. An apparatus, as recited in claim 1, wherein the voter is selective between address predictions from the first and the second prefetch predictors based on comparative prediction efficacies thereof.

5. An apparatus, as recited in claim 1, wherein the voter is non-selective for prefetch address predictions from the first and the second prefetch predictors based on a prediction efficacy threshold.

6. An apparatus, as recited in claim 1, wherein the voter is non-selective for prefetch address predictions from the first prefetch predictor based on a first prediction efficacy threshold and is non-selective for prefetch address predictions from the second prefetch predictor based on a second prediction efficacy threshold.

7. An apparatus, as recited in claim 1, wherein the voter is coupled to a memory hierarchy to supply a prefetch address selected from a more effective one of the prefetch predictors if the more effective one exceeds a prediction efficacy threshold, and wherein the voter is selective for a prefetch address from neither of the first and the second prefetch predictors if respective prediction efficacies do not exceed the prediction efficacy threshold.

8. An apparatus, as recited in claim 1, wherein the first prefetch predictor is a stride-type predictor.

9. An apparatus, as recited in claim 1, wherein the second prefetch predictor is a stream-type predictor.

10. An apparatus, as recited in claim 1, wherein the first prefetch predictor is coupled to receive read addresses directed to the cache.

11. An apparatus, as recited in claim 1, wherein the second prefetch predictor is coupled to receive cache miss addresses directed from the cache to lower levels in a memory hierarchy.

12. An apparatus, as recited in claim 1,

wherein the first prefetch predictor is a load stride predictor coupled to receive read addresses directed to the cache;

and

wherein the second prefetch predictor is a stream predictor coupled to receive cache miss addresses directed from the cache to lower levels in a memory hierarchy.

13. An apparatus, as recited in claim 1, wherein the cache is a first-level data cache.

14. An apparatus, as recited in claim 1, wherein storage for the prefetch buffer is integrated with the cache.

15. An apparatus, as recited in claim 1, wherein the prefetch buffer is coupled between the cache and lower levels in a memory hierarchy.

16. An apparatus, as recited in claim 1, further comprising a third prefetch predictor and wherein the voter is selective among respective prefetch addresses from the first, the second, and the third prefetch predictors based on respective prediction efficacies thereof.

17. An apparatus, as recited in claim 1, wherein the prefetch buffer includes first and second portions for respectively storing prefetched data associated with the first and the second prefetch predictors.

18. An apparatus, as recited in claim 1, wherein the first prefetch predictor comprises a stride predictor predictive based at least partially on data states provided by software instructions included with executable code.

19. An apparatus, as recited in claim 1, wherein the first and the second prefetch predictors comprise stride predictors respectively implementing dissimilar stride prediction strategies.

20. An apparatus comprising:

a first prefetch predictor coupled to receive a memory address presented to a cache memory, and to predict based thereupon, a first prefetch address;

a second prefetch predictor coupled to receive a memory address supplied by the cache memory to a memory subsystem, and to predict based thereupon, a second prefetch address;

a prefetch buffer coupled between the cache memory and the memory subsystem to receive prefetched data from the memory subsystem and to provide the prefetched data to the cache if a correspondence exists between a cache miss memory addresses and the prefetched data; and

a voter coupled to receive the first and the second prefetch addresses, the voter being responsive to prediction efficacy feedback, and in response thereto, being selective for one of the first and the second prefetch addresses for supply to the memory subsystem.

21. An apparatus, as recited in claim 20, wherein the prefetch buffer is coupled to supply the prediction efficacy feedback to the voter.

22. An apparatus, as recited in claim 20,

wherein the prefetch buffer includes prediction source storage and use storage associated with prefetched data storage;

and

wherein the voter is coupled to the prefetch buffer to receive the prediction efficacy feedback therefrom, the prediction efficacy feedback being a dynamic function of prediction source and prefetched data use statistics.

23. An apparatus, as recited in claim 22, wherein the prediction efficacy feedback is continuous function of prediction source and prefetched data use statistics.

24. An apparatus, as recited in claim 22, wherein the prediction efficacy feedback is a periodically updated function of prediction source and prefetched data use statistics.

25. An apparatus, as recited in claim 20,

wherein the prefetch buffer includes a use indication associated with prefetched data storage;

and

wherein the voter is coupled to the prefetch buffer to receive the prediction efficacy feedback therefrom, the prediction efficacy feedback being indicative of a proportion of the prefetched data storage used during a current prefetch interval to service misses in the cache memory.

26. An apparatus, as recited in claim 20,

wherein the prefetch buffer maintains use indications for prefetched data stored therein;

and

wherein the prediction efficacy feedback is indicative of a one of the first prefetch predictor and the second prefetch predictor having a proportionally greater number of use indications during comparable prediction efficacy evaluation intervals.

27. An apparatus, as recited in claim 20,

wherein the first prefetch predictor is coupled to receive memory addressing information corresponding to read accesses to the cache memory;

and

wherein the second prefetch predictor is coupled to receive memory addressing information corresponding to read misses in the cache memory.

28. An apparatus, as recited in claim 20,

wherein the first cache prefetch predictor is coupled to receive memory addressing information corresponding to write accesses to the cache memory;

and

wherein the second cache prefetch predictor is coupled to receive memory addressing information corresponding to write misses in the cache memory.

29. An apparatus, as recited in claim 20,

wherein the second cache prefetch predictor is coupled to receive memory addressing information corresponding to read and write misses in the cache memory.

30. An apparatus, as recited in claim 20,

wherein the first prefetch predictor comprises a stride predictor;

wherein the second prefetch predictor comprises a stream predictor; and

wherein, when the stride predictor and the stream predictor predict non-overlapping first and second prefetch addresses, the voter selects the first prefetch addresses if the prediction efficacy feedback indicates that the stride predictor is more effective than the stream predictor and selects the second prefetch addresses if the prediction efficacy feedback indicates that the stream predictor is more effective than the stride predictor.

31. A method comprising:

predicting a first prefetch address using a first prediction strategy;

predicting a second prefetch address using a second prediction strategy; and

selecting from among the first and the second prefetch addresses based on respective prediction efficacies for the first and the second prediction strategies.

32. A method, as recited in claim 31, further comprising:

selecting neither the first nor the second prefetch addresses if the respective prediction efficacies for the first and the second prediction strategies are both below a prediction efficacy threshold.

33. A method, as recited in claim 31, further comprising:

prefetching, based on the selected one of the first and the second prefetch addresses, data into a prefetch buffer for use in satisfying cache misses.

34. A method, as recited in claim 31, further comprising:

prefetching, based on the selected one of the first and the second prefetch addresses, data into a prefetch buffer; and

satisfying cache misses using data from the prefetch buffer.

35. A method, as recited in claim 31, wherein the selecting from among the first and the second prefetch addresses is in accordance with:

periodic measuring of respective prediction efficacies for the first and the second prediction strategies; and

periodic selecting, coincident with the periodic measuring, of a more effective of the first and the second prediction strategies.

36. A method, as recited in claim 31, wherein the selecting from among the first and the second prefetch addresses is dynamic with changing prediction efficacy measurements.

37. A method, as recited in claim 31, further comprising:

maintaining prediction source and prefetched data use information.

38. A method, as recited in claim 31, further comprising:

measuring predication efficacy for both the first and the second prediction strategies.

39. A method, as recited in claim 38, wherein the measuring is during periodic evaluation intervals.

40. A method, as recited in claim 38, wherein the measuring is continuous.