Branch predictor with serially connected predictor stages for improving branch prediction accuracy
OwnerScott Mcfarlinginventor
Life of this patent
Estimating the term…
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.
Claims18
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.
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.
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.
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.
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.
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.
Dependencies are inferred from the claim text.