BRANCH PREDICTOR WITH SERIALLY CONNECTED PREDICTOR STAGES FOR IMPROVING BRANCH PREDICTION ACCURACY

• US 20010056531A1
• Filed: 03/19/1998
• Published: 12/27/2001
• Est. Priority Date: 03/19/1998
• Status: Active Grant

• Current Assignee: MCFARLING, SCOTT
• Original Assignee: MCFARLING, SCOTT
• Inventors: MCFARLING, SCOTT
• Granted Patent: US 6,374,349 B2
• Time in Patent Office: Days
• 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 anticipating the 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 predict a branch,

at least one subsequent branch predictor stage, each

given the prediction of the preceding branch predictor stage,

operating according to a different algorithm to predict said branch, and

having means for overruling the prediction from the preceding branch predictor stage if and only if prediction accuracy is likely to improve over the prediction from the preceding stage,

whereby total branch predictor accuracy is increased.

2. A branch predictor stage for anticipating the direction of branches in the execution of instructions in a computer program, comprising:

a cache memory of entries to store branch counter information,

means for storing branch history information, and

means for using the stored branch history information to index the counter information stored in the cache memory.

3. A local branch predictor stage as in

claim 2

further comprising:

a static prediction mechanism,

a local history cache including associated cache tags,

a local counter cache including associated cache tags,

means for affirming a prediction from any prior stage when there is a miss to the local history cache,

means for creating a prediction based on the static prediction mechanism when there is a hit to the local history cache and a miss in the local counter cache, and

means for predicting based on the local counter cache when there is a hit to both caches.

4. A composite branch predictor for ensuring dominance through approximation of a conditional probability function, comprising a serial connection of two dissimilar predictor stages, with the prediction from the first predictor stage fed with additional information into the second predictor stage.

5. A composite branch predictor as in

claim 4

further comprising a prediction counter and wherein a prediction from the first predictor stage and other information available to the predictor selects said prediction counter.

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

using a first algorithm to predict the direction of a branch;

using a second algorithm to predict the direction of said branch;

using said predictions and overruling the prediction of the first algorithm if and only if prediction accuracy of the second algorithm is likely to improve over the accuracy of the first algorithm,

whereby total branch prediction accuracy is increased.

7. A method of reducing the size of hardware structures needed to predict the direction of branches in the execution of instructions in a computer program, comprising the steps of:

storing branch history information for branch instructions in a cache memory, and

encoding the information stored in said cache memory.

8. A method as in

claim 7

comprising, after the step of storing, the steps of:

observing the execution of a branch instruction and, if the stored prediction for that instruction is incorrect, then

allocating new entries in said cache memory to provide space for history entries for branch instructions suffering prediction errors.

9. A method as in

claim 7

comprising, after the step of storing, the step of prioritizing cache entries to retain useful entries over frequently accessed entries.

10. A method as in

claim 7

comprising, after the step of storing, the further step of triggering entry replacement only when a particular branch prediction is incorrect and there is no history entry for the particular branch instruction in the local branch predictor stage, thereby reducing the number of replacements and the number of history entries needed to produce accurate predictions.

11. A method as in

claim 7

comprising, after the step of storing, the further steps of

triggering entry replacement, and

setting new history entries after a replacement and when a bimodal branch predictor stage precedes the local stage, to initial values consistent with the counter state of said bimodal branch predictor stage and the current branch direction, thereby ensuring partial dominance.

12. A method as in

claim 7

comprising, after the step of storing, the step of using history entries having a valid field including a history bit count value which is reset upon replacement and incremented on cache memory hits up to a maximum count value;

prediction being enabled and counter array updating being enabled only upon said maximum count value being attained, ensuring partial dominance.

13. A method as in

claim 7

comprising, after the step of storing, the step of:

shift-or-count encoding information regarding a sequence of branches in two modes including;

a first mode which shifts a sequence of previous branch directions into a shift register, and

a second mode which

counts how many times a branch has gone the same direction beyond what can be represented by said shift register, and

sets a branch bias bit showing the direction the branch usually goes.

14. A method as in

claim 7

comprising, after the step of storing, the step of using two counters to

track the distance between the last two prediction errors and the distance since the last prediction error, and

set a synch bit when said counters have equal values, to detect a loop and a loop branch instruction exit prediction error.

15. A method as in

claim 7

comprising, after the step of storing, the steps of:

using a global history register containing a global stew code formed by the steps of;

exclusive-ORing the current branch address with the value stored in said history register to form a result;

shifting the result one bit to discard the oldest history bit;

concatenating the branch outcome to the result to form a new stew code, and

storing said new stew code back into said global history register to incorporate the global history of recent branch results.

16. A method as in

claim 7

comprising, after the step of storing, the step of hashing cache tags into the set index of a set-associative cache memory to increase the spread of values in said cache memory, thereby reducing collisions.

17. A method as in

claim 7

comprising, after the step of storing, the step of using a cache memory of history entries when a cache hit occurs to access an array of local counters from which to select a prediction, thereby ensuring partial dominance and improving branch predictor accuracy.

18. A method for anticipating the direction of branches in the execution of instructions in a computer program, comprising the steps of:

using a compiler to produce static profile information;

altering branch instruction addresses based on the percentage of executions in which a branch was taken, to set a profile bit; and

using a bimodal branch predictor stage to predict the direction of said branch given the profile bit,

whereby total branch predictor accuracy is increased.