Electrical computers and digital processing systems: processing – Processing control – Branching
Patent
1998-05-06
2000-08-22
Treat, William M.
Electrical computers and digital processing systems: processing
Processing control
Branching
G06F 938
Patent
active
061087777
ABSTRACT:
In a first aspect of the invention, branch prediction hardware, comprising logic and interconnect, is configurable via a control line to alter the manner in which the branch prediction is generated. The configuration can be done programmatically in software. Or, the configuration can be done by hardware in response to processor events. Such processor events include the loading of the CS register and changes in the instruction workload. In a second aspect of the invention, related to speculative execution, the directions of a plurality of branches are predicted based partly on resolved branch history information. Tentative branch history information is then stored for each of the predicted branches. When a predicted branch is resolved, the resolved branch history information is updated based on the stored tentative branch history information for the branch most recently resolved. Additionally, the predictions may be partly based on preceding unresolved branch predictions if any are outstanding. In a third aspect of the invention, Hit/Miss information from a Branch Prediction Cache (BPC) can optionally be used in formulating the next state value of an addressed two-bit counter stored in a correlation-based branch history table. Since a Miss in the BPC may indicate that this branch has not been encountered recently, whatever state currently exists can be optionally forced to a state that is based solely on whether the branch is resolved taken or not. This feature may be enabled and disabled under software control. In a fourth aspect of the invention, information from the instruction decoder is optionally used to override the correlation-based branch history table based prediction for select branch instructions. This feature may be enabled and disabled under software or hardware control.
REFERENCES:
patent: 5093778 (1992-03-01), Favor et al.
patent: 5142634 (1992-08-01), Fite et al.
patent: 5163140 (1992-11-01), Stiles et al.
patent: 5226126 (1993-07-01), McFarland et al.
patent: 5226130 (1993-07-01), Favor et al.
patent: 5228131 (1993-07-01), Ueda et al.
patent: 5230068 (1993-07-01), Van Dyke et al.
patent: 5265213 (1993-11-01), Weiser et al.
patent: 5553253 (1996-09-01), Pan et al.
patent: 5584001 (1996-12-01), Hoyt et al.
patent: 5623614 (1997-04-01), Van Dyke et al.
"Predict Instruction Flow Based on Sequential Segments," IBM Technical Disclosure Bulletin, vol. 33, No. 11, Apr. 1991, pp. 66-69.
D. W. Anderson et al., "The IBM System/360 Model 91: Machine Philosophy and Instruction-Handling", Jan. 1967, IBM Journal, pp. 9-24.
S. F. Anderson et al., "The IBM System/360 Model 91: Floating-Point Execution Unit", Jan. 1967, IBM Journal, pp. 34-53.
L. J. Boland et al., "The IBM System/360 Model 91: Storage System", Jan. 1967, IBM Journal, pp. 54-68.
Harvey G. Cragon, "Prediction Strategies", 1992, Branch Strategy Taxonomy and Performance Models, Chapter 4, pp. 13-57.
D. R. Ditzel and H. R. McLellan, "Branch Folding in the CRISP Microprocessor: Reducing Branch Delay to Zero", 1987, ACM Sigarch Computer Architecture News, pp. 2-9.
M. J. Flynn and P. R. Low, "The IBM System/360 Model 91: Some Remarks System Development", Jan. 1967, IBM Journal, pp. 2-7.
Pan et al, "Improving the Accuracy of Dynamic Branch Prediction Using Branch Correlation", 1992, AMC Sigarch Computer Architecture New, pp. 76-84.
D. R. Kaeli and P. G. Emma, "Branch History Table Prediction of Moving Target Branches Due to Subroutine Returns", May 1991, ACM Sigarch Computer Architecture News, vol. 19, No. 3, pp. 34-42.
P. M. Kogge, "Pipelining in SISD Machine Designs", 1981, The Architecture of Pipelined Computers, pp. 269-278.
John Levine, "Why Programmers Hate the 8086 and 286", Aug. 1990, Microprocessor Report, pp. 2-4 through 2-9.
John S. Liptay, "Design of the IBM Enterprise system/9000 High-end Processor", Jul. 1992, IBM Journal of Research and Development.
Shien-Tai Pan et al., "Correlation-Based Branch Prediction", Aug. 1991, pp. 0-31.
Shien-Tai Pan et al., "Improving the Accuracy of Dynamic Branch Prediction Using Branch Correlation", 1992, ACM Sigarch Computer Architecture News, pp. 76-84.
David A. Patterson and John L. Hennessy, Advanced Pipelining-Dynamic Scheduling in Pipelines, 1990, Computer Architecture A Quantitative Approach, pp. 290-314.
Chris H. Perleberg and Alan J. Smith, "Branch Target Buffer Design and Optimization", 1993, IEEE Transaction on Computers, vol. 42, No. 4, pp. 396-412.
Marc Rose, "Structured Control Flow: An Architectural Technique for Improving Control Flow Performance", Nov. 1983, pp. 1-71.
Johnny K. F. Lee and Alan J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design", 1984, IEEE, pp. 6-22.
C. O. Stjernfeldt et al., Survey of Branch Prediction Strategies, Jul. 1993, pp. 1-26.
Robert M. Supnik, "Digital's Alpha Chip Project", 1993, Communications of the ACM, vol. 36, No. 2, pp. 29-44.
R. M. Tomasulo, "An Efficient Algorithm for Exploiting Multiple Arithmetic Units", Jan. 1967,IBM Journal, pp. 25-33.
Tse-Yu Yeh and Yale N. Patt, "A Comparison of Dynamic Branch Predictors that use Two Levels of Branch History", 1993, IEEE, pp. 257-266.
Tse-Yu Yeh and Yale N. Patt, "Alternative Implementations of Two-Level Adaptive Branch Prediction", 1992, ACM Sigarch Computer Architecture News, pp. 124-134.
Am29050.TM. Microprocessor User's Manual, 1991. pp. 2-14, 2-15, 4-1, 4-5 thru 4-10.
IBM Technical Disclosure Bulletin, 1988, vol. 30, No. 11, pp. 221-225.
Puziol David L.
Shar Len
Smith, III Walstein Bennett
Van Dyke Korbin S.
Widigen Larry
Advanced Micro Devices , Inc.
Treat William M.
LandOfFree
Configurable branch prediction for a processor performing specul does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Configurable branch prediction for a processor performing specul, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Configurable branch prediction for a processor performing specul will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-595091