Electrical computers and digital processing systems: processing – Processing control – Branching
Patent
1998-02-23
2000-11-21
Follansbee, John A.
Electrical computers and digital processing systems: processing
Processing control
Branching
712233, G06F 900
Patent
active
061516724
ABSTRACT:
Interference in a branch history table of a microprocessor is reduced by methods and apparatus which predict the outcome of branch instructions (taken or not taken) through a combination of static and dynamic prediction techniques. Static prediction information (e.g., a compiler hint) may be stored in instruction memory, and dynamic prediction information is stored in a branch history table. A branch prediction results from an exclusive OR of static and dynamic prediction information. After execution of a branch instruction, an indication as to whether a branch was taken or not taken is exclusively ORed with the static prediction information for the branch instruction, and the result of this exclusive OR is used to update an appropriate entry in the branch history table. Using the methods and apparatus disclosed herein, two well-behaved branches may share an entry in a branch history table, yet not interfere with one another (even when the two well-behaved branches include one which is mostly taken, and one which is mostly not taken).
REFERENCES:
patent: 5442756 (1995-08-01), Grochowski
patent: 5454117 (1995-09-01), Puziol et al.
patent: 5740416 (1998-04-01), McMahan
patent: 5815699 (1998-09-01), Puziol
Atukorola, S., "Branch prediction methods used in modern superscalar processors", IEEE, Information, Communications and Signal Processing, Sep. 1197.
McFarling, Scott, Combining Branch Predictors, Western Research Laboratory, pp. 1-17, Jun. 1993.
Burch, Carl,; "PA-8000: A Case Study of Static and Dynamic Branch Prediction"; Oct. 12, 1997; p. 98, paragraph 4; p. 99, paragraph 6; IEEE, 1997.
IBM Corp,; "Polymorphic Branch Predictor"; Jul. 1994; p. 111, line 3; p. 112, line 14; IBM Technical Disclosure Bulletin; Jul., 1994.
Young, Cliff, et al.; "Improving the Accuracy of Static Branch Prediction Using Branch Correlation"; Nov. 1994; vol. 29, No. 11; ACM Sigplan Notices; Nov. 29, 1994.
Mahlke, Scott, et al.; "Compiler Synthesized Dynamic Branch Prediction"; Dec. 2, 1996; vol. SYMP 29; IEEE, 1996.
"PA-8000 Combines Complexity and Speed: HP Aims to Retake Performance Lead--But Not Until 1Q96", L. Gwennap, Nov. 14, 1994, 22 pages.
"Compiler Optimizations for the PA-8000", A. Holler, Feb. 1997, 16 pages.
"PA-8500: The Continuing Evolution of the PA-8000 Family", G. Lesartre & D. Hunt, Feb. 23, 1997, 6 pages.
"The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference," E. Sprangle, R. Chappell, M. Alsup & Y. Patt, Jun. 1997, pp. 284-291.
"Advanced Performance Features of the 64-BIT PA-8000", D. Hunt, Mar. 5, 1995, 7 pages.
"New Algorithm Improves Branch Prediction--Better Accuracy Required for Highly Superscalar Designs" by L. Gwennap, Mar. 27, 1995, pp. 17-21.
"A Study of Branch Prediction Strategies", J. Smith, 1981, pp. 135-148.
"Two-Level Adaptive Training Branch Prediction", Nov. 18, 1991, pp. 51-60,T. Yeh & Y. Patt.
"Correlation and Aliasing in Dynamic Branch Predictors", S. Sechrest, C. Lee, & T. Mudge, May 1996, pp. 22-32.
"The Impact of Branch Prediction Table Interference on Branch Prediction Scheme Performance", A. Talcott, W. Yamamoto, N. Sankar, R. Wood, & M. Nemirovsky, 1995, 17 pages.
"Branch Prediction Strategies and Branch Target Buffer Design", J. Lee & A. Smith, Jan. 1984, pp. 6-22.
"HP Pumps Up PA-8.times.00 Family: PA-8200 in 2Q97, PA-8500 in 2Q98 Aim to Grab Performance Lead", Linley Gwennap, Oct. 28, 1996, 7 pages.
Follansbee John A.
Hewlett--Packard Company
Whitmore Stacy
LandOfFree
Methods and apparatus for reducing interference in a branch hist does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for reducing interference in a branch hist, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for reducing interference in a branch hist will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1267167