Sharing information to reduce redundancy in hybrid branch prediction

• US 7,203,825 B2
• Filed: 10/03/2001
• Issued: 04/10/2007
• Est. Priority Date: 10/03/2001
• Status: Expired due to Fees

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Intel Corporation
• Inventors: Jourdan, Stephan J., Hum, Herbert H. J.
• Primary Examiner(s): Chan; Eddie
• Assistant Examiner(s): Huisman; David J.
• Application Number:
  US09/970,485
• Publication Number:
  US 20030065912A1
• Time in Patent Office: 2,015 Days
• Field of Search: 712/233, 712/234, 712/238, 712/239, 712/240
• US Class Current: 712/239
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

A hybrid branch predictor is disclosed. The predictor includes prediction aiding information, a plurality of branch predictors to provide a plurality of branch predictions, a plurality of storage elements to hold less than full extent of the branch predictions, but sharing information among said plurality of storage elements enables extraction of said full extent of the prediction. The predictor also includes a selection mechanism to select a prediction from the plurality of branch predictions.

Claims

1. A branch predictor system, comprising:

a plurality of a first kind of storage elements to store prediction aiding information, the prediction aiding information including outcome information of prior branch predictions;

a plurality of branch predictors to provide a plurality of branch predictions, each of the branch predictors corresponding to each of the first kind of storage elements to store prior prediction outcomes of each of the branch predictors, and each predictor to make a corresponding prediction based on at least a portion of a branch instruction pointer and contents of a corresponding one of said plurality of said first kind of storage elements;

a plurality of a second kind of storage elements each corresponding to the plurality of branch predictors, each of the branch predictors to make a determination on the corresponding prediction for a branch location of an instruction, each one of said second kind of storage elements to hold less than full extent of said corresponding prediction, but sharing information among said plurality of said second kind of storage elements to enable extraction of said full extent of said corresponding prediction, wherein a first one of said second kind of storage elements, corresponding to an indirect branch predictor of said plurality of branch predictors, is to store a portion of a target address, and a second one of said second kind of storage elements, corresponding to another predictor of said plurality of branch predictors, is to supply a remainder of said target address; and

a selection mechanism to select a prediction from said plurality of said second kind of storage elements based on prediction scores of the plurality of branch predictors collected based on prior predictions performed by the branch predictors, wherein for each branch instruction, the plurality of branch predictors are configured to perform branch predictions substantially concurrently, and wherein the selection mechanism is configured to select a branch prediction from one of the plurality of branch predictors having the highest prediction score.

2. The system of claim 1, wherein said corresponding prediction includes at least one target address.

3. The system of claim 2, wherein said corresponding prediction also includes a “

taken”

/“

not taken”

bit.

4. The system of claim 1, wherein said full extent of said corresponding prediction includes a 32-bit address.

5. The system of claim 4, wherein said each one of said second kind of storage elements is configured to be less than or equal to 32 bits.

6. The system of claim 1, wherein said prediction aiding information includes prior outcome information.

7. The system of claim 1, wherein said prediction aiding information includes a type of branch.

8. The system of claim 1, wherein said prediction aiding information includes a correlation factor.

9. The system of claim 1, wherein said prediction aiding information includes a confidence level.

10. The system of claim 1, wherein said selection mechanism includes a counter to determine which predictor is currently more accurate.

11. The system of claim 1, wherein a predetermined number of most significant bits in said corresponding prediction is shared.

12. A computer-implemented method, comprising:

storing in a plurality of a first kind of storage elements prediction aiding information, the prediction aiding information including outcome information of prior branch predictions;

performing a plurality of branch predictions using a plurality of branch predictors, each of the branch predictors corresponding to each of the first kind of storage elements to store prior prediction outcomes of each of the branch predictors, each predictor to make a corresponding prediction based on at least a portion of a branch instruction pointer and contents of a corresponding one of the plurality of the first kind of storage elements;

storing in a plurality of a second kind of storage elements each corresponding to the plurality of branch predictors, each of the branch predictors making a determination on the corresponding prediction for a branch location of an instruction, each to hold less than full extent of the corresponding prediction, but sharing information among the plurality of the second kind of storage elements to enable extraction of the full extent of the corresponding prediction, wherein a first one of the second kind of storage elements, corresponding to an indirect branch predictor of the plurality of branch predictors, is to store a portion of a target address, and a second one of the second kind of storage elements, corresponding to another predictor of the plurality of branch predictors, is to supply a remainder of the target address; and

selecting a prediction from the plurality of the second kind of storage elements based on prediction scores of the plurality of branch predictors collected based on prior predictions performed by the branch predictors, wherein for each branch instruction, the plurality of branch predictors are configured to perform branch predictions substantially concurrently, and wherein the selection mechanism is configured to select a branch prediction from one of the plurality of branch predictors having the highest prediction score.

13. The method of claim 12, wherein said corresponding prediction includes at least one target address.

14. The method of claim 13, wherein said corresponding prediction also includes a “

taken”

/“

not taken”

bit.

15. The method of claim 12, wherein said full extent of said corresponding prediction includes a 32-bit address.

16. The method of claim 15, wherein said each one of said second kind of storage elements is configured to be less than or equal to 32 bits.

17. The method of claim 12, wherein said prediction aiding information includes at least one of prior outcome information, a type of branch, a correlation factor, a confidence level.

18. The method of claim 12, wherein said selection mechanism includes a counter to determine which predictor is currently more accurate.

19. The method of claim 12, wherein a predetermined number of most significant bits in said corresponding prediction is shared.

20. A machine-readable medium having instructions which, when executed by a machine, cause the machine to perform a method, the method comprising:

storing in a plurality of a first kind of storage elements prediction aiding information, the prediction aiding information including outcome information of prior branch predictions;

performing a plurality of branch predictions using a plurality of branch predictors, each of the branch predictors corresponding to each of the first kind of storage elements to store prior prediction outcomes of each of the branch predictors, and each predictor to make a corresponding prediction based on at least a portion of a branch instruction pointer and contents of a corresponding one of the plurality of the first kind of storage elements;

storing in a plurality of a second kind of storage elements each corresponding to the plurality of branch predictors, each of the branch predictors making a determination on the corresponding prediction for a branch location of an instruction, each to hold less than full extent of the corresponding prediction, but sharing information among the plurality of the second kind of storage elements to enable extraction of the full extent of the corresponding prediction, wherein a first one of the second kind of storage elements, corresponding to an indirect branch predictor of the plurality of branch predictors, is to store a portion of a target address, and a second one of the second kind of storage elements, corresponding to another predictor of the plurality of branch predictors, is to supply a remainder of the target address; and

selecting a prediction from the plurality of the second kind of storage elements based on prediction scores of the plurality of branch predictors collected based on prior predictions performed by the branch predictors, wherein for each branch instruction, the plurality of branch predictors are configured to perform branch predictions substantially concurrently, and wherein the selection mechanism is configured to select a branch prediction from one of the plurality of branch predictors having the highest prediction score.