Branch predictor with serially connected predictor stages for improving branch prediction accuracy

• US 6,374,349 B2
• Filed: 03/19/1998
• Issued: 04/16/2002
• Est. Priority Date: 03/19/1998
• Status: Expired due to Term

• Current Assignee: McFarling, Scott
• Original Assignee: McFarling, Scott
• Inventors: McFarling, Scott
• Primary Examiner(s): Niebling, John F.
• Assistant Examiner(s): WHITMORE, STACY
• Application Number:
  US09/044,306
• Publication Number:
  US 20010056531A1
• Time in Patent Office: 1,489 Days
• Field of Search: 712/233-240
• US Class Current: 712/239
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

System for accurately predicting the outcome of conditional branch instructions subject to execution in a pipelined processor digital computer. The system comprises a series of predictor stages utilizing different prediction algorithms. The stages are linked to successively refine branch predictions only where prediction accuracy from a previous stage is likely to be improved by a subsequent stage. Improvements to each stage and techniques for stage linkage are described.

Claims

1. A serial branch predictor for predicting a direction of branches in the execution of instructions in a computer program, comprising:

a first branch predictor stage operating according to a first algorithm to generate a first signal representative of the predicted direction of a branch; and

at least one subsequent branch predictor stage, each subsequent branch predictor stage,

being serially coupled to a preceding branch predictor stage,

receiving at least one input including a signal representative of the predicted direction generated by the preceding branch predictor stage, and

operating upon the at least one input according to a different algorithm to generate a signal representative of the predicted direction of a branch.

2. The serial branch predictor as in claim 1 wherein

the at least one subsequent branch predictor stage comprises a cache memory storing entries of history information, the entries being dynamically allocable, updateable, and replaceable.

3. The serial branch predictor as in claim 2 wherein

the predicted direction of the preceding stage is output by the at least one subsequent stage if there is no entry corresponding to the branch.

4. The serial branch predictor as in claim 2 wherein

the cache memory entries are indexed by the signal representative of the predicted direction generated by the preceding branch predictor stage.

5. The serial branch predictor as in claim 4 wherein

the cache memory entries are further indexed by a bit from a global history register.

6. The serial branch predictor as in claim 2 wherein

the cache memory entries are not replaced if the predicted direction of the preceding branch predictor stage is correct.

7. The serial branch predictor as in claim 2 wherein

the cache memory entries are not replaced if the predicted direction of a final branch predictor stage is correct.

8. The serial branch predictor as in claim 2 wherein

the cache memory entries are updated only if an updated cache memory entry provides an improved predicted direction in relation to the predicted direction of the preceding branch predictor stage.

9. The serial branch predictor as in claim 1 wherein each of the at least one subsequent branch predictor stage comprises a counter indexed by the signal representative of the predicted direction generated by the preceding branch predictor stage.

10. The serial branch predictor as in claim 9 wherein

the at least one subsequent branch predictor stage comprises a global predictor.

11. The serial branch predictor as in claim 10 wherein the first branch predictor stage comprises a bimodal predictor.

12. The serial branch predictor as in claim 11 wherein

the at least one subsequent branch predictor stage comprises a local predictor coupled between the bimodal predictor and the global predictor.

13. The serial branch predictor as in claim 1 wherein

the at least one subsequent branch predictor stage comprises a local predictor including a cache memory for storing entries of branch history, the entries being dynamically allocable, updateable, and replaceable.

14. The serial branch predictor as in claim 13 wherein

the predicted direction of the preceding stage is output by the branch predictor stage if there is no entry corresponding to the branch.

15. The serial branch predictor as in claim 13 wherein

the cache memory entries are indexed by the signal representative of the predicted direction generated by the preceding branch predictor stage.

16. The serial branch predictor as in claim 13 wherein

the cache memory entries are not replaced if the predicted direction of the preceding branch predictor stage is correct.

17. The serial branch predictor as in claim 13 wherein

the cache memory entries are not replaced if the predicted direction of a final branch predictor stage is correct.

18. The serial branch predictor as in claim 13 wherein

the cache memory entries are updated only if an updated cache memory entry provides an improved predicted direction in relation to the predicted direction of the preceding branch predictor stage.

19. The serial branch predictor as in claim 13 wherein

a cache memory of entries storing branch counter information, the branch counter entries being dynamically allocable, updateable, and replaceable.

20. The serial branch predictor as in claim 13 wherein

replaced branch history entries comprise information consistent with the predicted direction of the preceding branch predictor stage and a current direction of the branch.

21. The serial branch predictor as in claim 13 wherein

allocated branch history entries comprise information consistent with the predicted direction of the preceding branch predictor stage and a current direction of the branch.

22. The serial branch predictor as in claim 3 wherein

each entry is stored in a register, the register including a mode bit for switching between a history storage mode and a counter mode, and a shift field in history storage mode and a branch bias bit and counter field in counter mode, the mode bit being set when all the bits in the shift field represent the same branch direction, the branch bias bit representing the branch direction and the counter field saturating at a predefined value, and the mode bit being reset when the branch changes direction.

23. The serial branch predictor as in claim 1 wherein

the first branch predictor stage comprises a static predictor.

24. The serial branch predictor as in claim 23 wherein

during compilation of the computer program, the first algorithm sets a bit representing the predicted direction.

25. The serial branch predictor as in claim 23 wherein

the first algorithm comprises a program compilation algorithm which

counts a first number representative of the number of times a branch is taken and counts a second number representative of the number of times the branch is not taken,

makes a branch address even if the first number is greater than the second number, and else

makes the branch address odd, and

wherein a plurality of low order bits represent the predicted direction.

26. A branch predictor comprising:

a serial connection of two dissimilar predictor stages, a first prediction output of the first predictor stage being used directly in the computation of a second prediction output of the second predictor stage.

27. The branch predictor as in claim 26, wherein the second predictor stage comprises an array of prediction counters and wherein the first prediction output and other information available to the second predictor stage is used to index a prediction counter used in computing the second prediction output.

28. A method of predicting a direction of branches in the execution of instructions in a computer program, comprising the steps of:

using a first algorithm to make a first prediction of the direction of a branch;

providing the first prediction to a second algorithm;

using the second algorithm to make a second prediction of the direction of the branch, the second algorithm overruling the first prediction if the second prediction is likely to improve over the accuracy of the first prediction.