Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-07-11
2002-03-05
Kim, Kenneth S. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S240000
Reexamination Certificate
active
06353882
ABSTRACT:
FIELD OF THE INVENTION
The invention pertains to the maintenance and use of a branch history table in a microprocessor.
BACKGROUND OF THE INVENTION
Most modern computers, including those that execute instructions out-of-order and/or via a pipelined execution unit, execute instructions “speculatively”. That is, instructions are executed before the instructions on which they depend have been fully executed, and quite possibly, before the outcomes of branches in the instruction stream are known. To achieve a high degree of performance, the microprocessors in these computers employ a variety of techniques to minimize the cost of erroneously predicted branches in the instruction stream. These techniques usually involve some form of “branch prediction”. Branch prediction is a means of optimizing for the outcome of a branch instruction which is mostly likely to occur (either “taken” or “not taken”).
Typically, a branch prediction will be based on one of two types of information: 1) static prediction information, or 2) dynamic prediction information. Static prediction information is generated prior to the execution of a computer program, and may be based on factors such as instruction type, position in the instruction stream, instruction repetition, and so on. Dynamic prediction information is generated during the execution of a computer program, and usually depends on a history of previous outcomes of a given branch and/or other branch instructions.
Dynamic prediction information is stored in a branch history table comprising a number of entries. If a branch history table was large enough, it is conceivable that a distinct history could be maintained for each branch instruction of a computer program. However, given that microprocessor chip area is a costly resource, and that branch history tables are often scaled back to make room for other important microprocessor elements, entries in a branch history table are often shared. Interference between conflicting branch histories is therefore a significant problem.
When conflicting histories share a single entry in a branch history table, the history for any given branch instruction is often corrupted by other branch instructions, thereby resulting in a mispredicted branch outcome. When a branch outcome is mispredicted, serious and costly consequences result. For example, instruction pipelines may stall, instruction execution units may be halted, caches and registers may need to be flushed, and so on. All of these consequences result in unacceptable delays.
It is therefore a primary object of this invention to provide methods and apparatus which reduce interference in a branch history table of a microprocessor, thereby yielding 1) more accurate branch predictions, and consequently 2) fewer delays caused by erroneously predicted branches.
SUMMARY OF THE INVENTION
To understand the invention, it must first be recognized that the vast majority of branches are either “almost always taken” or “almost always not taken”. These branches may be referred to as “well-behaved” branches. One must also recognize that when the outcome of a branch switches, it often switches from “almost always taken” to “almost always not taken”, or vice versa. It is also important to note that branch prediction schemes typically rely on the assumption that most branches are well-behaved. As a result, the goal of both static and many dynamic branch prediction schemes is to predict what the dominant outcome of a branch will be.
Recognizing the above facts, one can appreciate that the prediction accuracy of a well-behaved branch of one type (e.g., an “almost always taken” branch) is degraded when the branch shares a branch history table entry with a well-behaved branch of the other type (e.g., an “almost always not taken” branch).
The branch prediction schemes of the Hewlett-Packard Company PA-8x00 family of microprocessors (e.g., the PA-8000, PA-8200, and PA-8500) presume the above facts on well-behaved branches to be true. Hewlett-Packard Company is based in Palo Alto, Calif., USA, and the PA-8x00 family of microprocessors is described in more detail in Advanced Performance Features of the 64-bit PA-8000 by D. Hunt (Mar. 5, 1995), HP Pumps Up PA-8x00 Family: PA-8200 in 2Q97, PA-8500 in 2Q98 Aim to Grab Performance Lead by L. Gwennap (Oct. 28, 1996), and PA-8500: The Continuing Evolution of the PA-8000 Family by G. Lesartre and D. Hunt (Feb. 23, 1997). These papers are hereby incorporated by reference for all that they disclose.
Compilers which generate code for the PA-8x00 family of microprocessors are capable of encoding a “hint” in most branch instructions. These hints are a form of static prediction information, and are indication as to whether the compiler believes a given branch will be mostly taken or mostly not-taken. The compiler for the PA-8000 microprocessor is described in more detail in Compiler Optimizations for the PA-8000 by A. Holler. This paper is hereby incorporated by reference for all that it discloses.
In the achievement of the foregoing objects, the inventor has devised methods and apparatus which utilize these compiler generated hints (or any other static prediction information) to insure that two or more well-behaved branches sharing a single entry in a branch history table do not corrupt the history information stored therein. After execution of a branch instruction, an indication as to whether a branch instruction resulted in a branch being taken or not taken is exclusively ORed with the compiler generated hint for the branch instruction, and the result of this exclusive OR is used to update an appropriate entry in the branch history table. Furthermore, the outcome of a branch instruction is predicted in response to the exclusive OR of 1) the compiler generated hint, and 2) dynamic prediction information read from an appropriate entry of the branch history table.
Using the methods and apparatus disclosed herein, two well-behaved branches may share an entry in the branch history table, yet not corrupt the history information stored therein (even when the two well-behaved branches comprise one which is mostly taken, and one which is mostly not taken).
These and other important advantages and objectives of the present invention will be further explained in, or will become apparent from, the accompanying description, drawings and claims.
REFERENCES:
patent: 5442756 (1995-08-01), Grochowski et al.
patent: 5454117 (1995-09-01), Puziol et al.
patent: 5687360 (1997-11-01), Chang
patent: 5740416 (1998-04-01), McMahan
patent: 5752014 (1998-05-01), Mallick et al.
patent: 5805878 (1998-09-01), Rahman et al.
patent: 5815699 (1998-09-01), Puziol et al.
patent: 5901307 (1999-05-01), Potter et al.
patent: 5928358 (1999-07-01), Takayama et al.
patent: 5978909 (1999-11-01), Lempel
patent: 6108777 (2000-08-01), Puziol et al.
patent: 0320098 (1989-06-01), None
patent: 0381444 (1990-08-01), None
“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-50, T. Yeh and Y. Patt.
“Correlation and Aliasing in Dynamic Branch Predictors”, S. Sechrest, C. Lee, & T. Mudge, May 1996, pp. 22-32.
Burch, Carl, : “PA-8000: A Case of Static and Dynamic Branch Prediction”; Oct. 12, 1997; p. 98, paragraph 4; p. 99, paragraph 6; IEEE, 1997.
IBM Corp.; “Polymorphic Branch Predictor”; 07-94; p. 111, line 3; p. 112,
Hewlett--Packard Company
Kim Kenneth S.
LandOfFree
Reducing branch prediction interference of opposite well... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reducing branch prediction interference of opposite well..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducing branch prediction interference of opposite well... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2838624