Patent
1995-04-28
1997-11-11
Eng, David Y.
G06F 940
Patent
active
056873603
ABSTRACT:
In a computer program, a branch instruction selects a prediction heuristic from a plurality of prediction heuristics for predicting whether the branch will be taken during execution of the program by a computer. A current pattern comprises a number of consecutive identical branch decisions for the instruction. A prior pattern comprises a number of consecutive identical prior branch decisions for the instruction, the prior branch decisions occurring prior to the branch decisions comprised by the current pattern. The selected prediction heuristic generates a branch prediction using the current pattern and the prior pattern. The selected prediction heuristic is identified by adding profiling instructions to the program to compute history information for the branch instruction. The profiling instructions input the branch history information to a plurality of prediction heuristics, and each prediction heuristic outputs a prediction of whether the branch instruction will be taken. The program is executed with a sample data set, and the output of each prediction heuristic is compared to the branch decision for the instruction to identify which heuristic most accurately predicts the branch decision for the branch instruction.
REFERENCES:
patent: 5093778 (1992-03-01), Favor et al.
patent: 5394529 (1995-02-01), Brown et al.
patent: 5553253 (1996-09-01), Pan et al.
patent: 5564118 (1996-10-01), Steely et al.
"Correlation-Based Branch Prediction", Pan, S.T., So, K.; Rahmeh, J.T., Conference Title: Conference Record of The Twenty-Sixth Asilomar Conference on Signals, Systems and Computers (Cat. No. 92CH3245-B) pp. 51-55, vol. 1. Publisher: IEEE Computer Soc. Press, Los Alamitos, CA USA. Publ. Date: 1992, USA. Conference Date: Oct. 26-28, 1992., Pacific Grove, CA.
Tse-Yu Yeh and Yale N. Patt, "A Comparison of Dynamic Branch Predictors that Use Two Levels of Branch History"; The 20th Annual Interntional Symposium on Computer Architecture; San Diego, California; 1993; pp. 257-266.
Johnny K.F. Lee and Alan Jay Smith, "Branch Prediction Strategies and Branch Target Buffer Design", Computer; vol. 17, No. 1; Jan. 1984; pp. 6-22.
James E. Smith; "A Study of Branch Prediction Strategies"; The 8th Annual Symposium on Computer Architecture; Minneapolis, MN; 1981; pp. 135-148.
Tse-Yu Yeh and Yale N. Patt; "Alternative Implementations of Two-Level Adaptive Branch Prediction"; 19th Annual International Symposium on Computer Architecture; Australia; 1992; pp. 124-134.
Chang, et al.; "Branch Classification: a New Mechanism for Improving Branch predictor Performance"; Department of Electrical Engineering and Computer Science; Univ. of Michigan; 1991; (10 pages total).
Shien-Tai Pan, et al.; "Improving the Accuracy of Dynamic Branch Prediction Using Branch Correlation"; 1992; pp. 76-84.
Eng David Y.
Intel Corporation
LandOfFree
Branch predictor using multiple prediction heuristics and a heur does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Branch predictor using multiple prediction heuristics and a heur, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Branch predictor using multiple prediction heuristics and a heur will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1236787