Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-03-01
2001-07-31
Maung, Zarni (Department: 2154)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S234000, C712S239000
Reexamination Certificate
active
06269438
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of branch prediction in microprocessors.
BACKGROUND OF THE INVENTION
Pipelining is a well-known technique whereby several instructions are overlapped in execution. Today, most microprocessors rely upon pipelining for improved, high-speed performance. A major effect of pipelining, however, is that it introduces data and control hazards, which can cause significant performance losses. For example, the ideal speedup from pipelining can be reduced by half due to pipeline stalls and other delays caused by branch penalties.
Branch instructions can be either unconditional, meaning that the branch is taken every time that the instruction is encountered in the program, or conditional, meaning that the branch is either taken or not taken, depending upon a condition. Most often, the instructions to be executed following a conditional branch are not known with certainty until the condition upon which the branch depends has been resolved. These types of branches can significantly reduce the performance of a pipeline processor since they may interrupt the steady supply of instructions to the execution hardware. Branch predictors attempt to predict the outcome of conditional branch instructions in a program before the branch instruction is executed. If a branch is mispredicted, all of the speculative work, beyond the point in the program where the branch is encountered, must be discarded. Therefore, a highly-accurate branch prediction mechanism is vital to a high-performance, pipelined processor.
The prior art is replete with different branch prediction schemes. A general overview of the problems associated with branch prediction, and the presentation of a number of solutions is provided in an article by J. Lee and A. J. Smith, “Branch Prediction Strategies and Branch Target Buffer Design”,
IEEE Computer
(Jan. 1984). An article authored by James E. Smith, entitled “A Study of Branch Prediction Strategies”,
IEEE
(1981) discusses a variety of branch prediction techniques in terms of accuracy, costs and flexibility of use. A typical method of branch prediction utilizes a memory to store branch history information associated with the branch instruction. An example of this approach to branch prediction is found in U.S. Pat. No. 5,142,634.
Many early implementations of branch predictors used simple history bits and counter-based schemes that provide branch prediction accuracy of about 85-90%. Attempts to improve upon the accuracy simple 2-bit counter schemes have included predictors that relate the sub-history information of a branch to the most recently executed branches via a shift register. An example of this approach is disclosed in the article entitled “Improving the Accuracy of Dynamic Branch Prediction Using Branch Correlation”, by Shien-Tai Pan, et al.
As the complexity of the branch prediction problem increases, so has the sophistication of branch predictors. By way of example, the article “Branch Classification: A New Mechanism for Branch Predictor Performance”, by Po-Young Chang, et al.,
Proceedings from Micro-
27 (Dec. 1994) describes a hybrid predictor in which each component branch predictor predicts only those branches for which it is best suited. Other sophisticated approaches employ complicated branch prediction algorithms that try to predict whether or not a branch will be taken based upon a lot of history information. This category of branch predictions is exemplified by mechanisms disclosed in several papers by Tse-Yu Yeh and Yale N. Patt entitled, “A Comparison of Dynamic Branch Predictors that Use Two Levels of Branch History”
IEEE
(1993); “Two-Level Adaptive Training Branch Prediction”; and “Alternative Implementations of Two-Level Adaptive Branch Prediction”
ACM
(1992).
One of the problems with sophisticated branch predictors is the large amount of the silicon space required for implementing the branch prediction hardware. This has presented microprocessor designers with a dilemma: either utilize a simple branch predictor (with limited accuracy) that occupies a small amount of area, or employ a sophisticated branch predictor (with higher accuracy) that takes up a relatively large amount of silicon space.
Thus, there exists an unsatisfied need for a way to optimize branch prediction.
SUMMARY OF THE INVENTION
The present invention improves the performance of computer systems which execute programs that include branch instructions. Because branch miss penalty is typically very large—especially for deeply pipelined, out-of-order execution processors—the invention advantageously identifies hard-to-predict branches and provides hardware optimization.
In one embodiment, the present invention comprises a method for handling branch instructions contained within a source program. The source program is processed by a compiler to produce a machine-executable code suitable for running on a hardware system. A compile-time semantic analysis of the source program identifies hard-to-predict branches. The analysis is performed by applying a set of heuristics to classify each of the branch instructions in the source program as either a hard-to-predict type or a simple type of branch. The heuristics cleanly differentiate between easy-to-predict (i.e., simple) and hard-to-predict branches so that the hardware can be optimized to achieve the goals of implementing branch prediction algorithms with minimum silicon space, while simultaneously achieving a high prediction accuracy.
REFERENCES:
patent: 4287559 (1981-09-01), Easley et al.
patent: 4399505 (1983-08-01), Druke et al.
patent: 4742453 (1988-05-01), Shibuya
patent: 4777587 (1988-10-01), Case et al.
patent: 5093778 (1992-03-01), Favor et al.
patent: 5142634 (1992-08-01), Fite et al.
patent: 5353421 (1994-10-01), Emma et al.
patent: 5381533 (1995-01-01), Peleg et al.
patent: 5394529 (1995-02-01), Brown, III et al.
patent: 5414822 (1995-05-01), Saito et al.
patent: 5553253 (1996-09-01), Pan et al.
patent: 5564118 (1996-10-01), Steely, Jr. et al.
patent: 5596732 (1997-01-01), Hosoi
patent: 5649203 (1997-07-01), Sites
patent: 5655122 (1997-08-01), Wu
patent: 5933628 (1999-08-01), Chang
Compiler-driven hybrid branch predictor, IBM technical disclosure bulletin, vol. 36, No. 2, Feb. 1993.*
Polymorphic branch predictor, IBM technical disclosure bulletin, vol. 37, No. 7, Jul. 1994.
Blakely , Sokoloff, Taylor & Zafman LLP
Institute for the Development of Emerging Architectures L.L.C.
Maung Zarni
LandOfFree
Method for identifying hard-to-predict branches to enhance... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for identifying hard-to-predict branches to enhance..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for identifying hard-to-predict branches to enhance... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2563173