Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-05-03
2002-07-30
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S240000, C712S245000, C712S236000
Reexamination Certificate
active
06427206
ABSTRACT:
BACKGROUND OF THE INVENTION
I. Field of the Invention
The present invention relates to the field of microprocessors. More specifically, the present invention relates to branch prediction in microprocessors.
II. Background Information
Computer programs typically include a large number of branch instructions which, upon execution, may cause instructions to be executed in a sequence other than the sequence set forth in the program memory. When a branch instruction is executed, execution continues either with the next sequential instruction from memory or execution jumps to an instruction specified by a branch target address. A branch specified by the branch instruction is said to be “Taken” if execution jumps to the instruction specified by the branch target address and “Not Taken” if execution continues with the next sequential instruction from memory.
Branch instructions are either unconditional or conditional. An unconditional branch is Taken every time the instruction is executed. A conditional branch instruction is Taken or Not Taken depending upon resolution of a condition which usually is a result of a logic statement. The instructions that are to be executed following a conditional branch are not known with certainty until the condition upon which the branch depends has been resolved. However, rather than waiting until the condition is resolved, state-of-the-art microprocessors perform branch prediction whereby the microprocessor tries to guess whether the branch will be Taken or Not Taken, so the instructions following the branch may be fetched and executed speculatively. If a branch is predicted to be Not Taken, the microprocessor fetches and speculatively executes the next sequential instruction after the branch from the memory. If the branch is predicted to be Taken, the microprocessor fetches and speculatively executes the instruction at the predicted branch target address. The instructions executed following the branch prediction are “speculative” because the microprocessor does not yet know whether the prediction will be correct or not. Accordingly, any operations caused to be performed by the speculative instructions may not be fully completed. For example, if a memory write operation is performed speculatively, the write operation may not be forwarded to a memory system until all previous branch conditions are executed successfully. Otherwise an instruction in a mispredicted path may improperly alter the contents of the memory.
If the branch prediction is ultimately determined to be correct, the speculatively executed instructions are retired or otherwise committed. In the example of a memory write, retirement is performed by forwarding the write operation to the memory system. If the branch prediction is ultimately found to be incorrect, then any speculatively executed instructions following the mispredicted branch are typically flushed from the system. In the memory write example, the write is not forwarded to the memory system but rather is discarded.
To expedite branch prediction, some state-of-the-art microprocessors include a branch prediction table (BPT) that provides a cache of the most recently predicted branches along with corresponding prediction information such as history of previous executions, also known as dynamic history, and/or predictions for that branch and the success thereof.
In addition to dynamic branch history, prediction mechanisms may also utilize compiler hints to aide the branch prediction. Usually, the compiler hints are determined using program profiling which is acquired by running a program with several sample data sets. From profiling a compiler, one may know whether or not a branch is likely to be taken and how certain the branch is taken or not taken. This information may be encoded into an instruction. However, to find out this information from the instruction, the instruction needs to be read from the instruction cache and decoded. The problem is that an instruction is decoded later in the pipeline. Therefore, the information encoded in the instruction is not available until several stages down the pipeline.
SUMMARY OF THE INVENTION
One embodiment of the present invention includes a microprocessor. The microprocessor includes a branch prediction table (BPT) that has at least one branch entry. The at least one branch entry includes a prediction field to indicate whether a branch is predicted taken. The at least one branch entry also includes a history register to store history information. Moreover, the BPT includes a prediction update logic to update the prediction field and the history register except when a branch is strongly predicted statically.
REFERENCES:
patent: 5553253 (1996-09-01), Pan et al.
patent: 5761490 (1998-06-01), Hunt
patent: 5848269 (1998-12-01), Hara
patent: 5867698 (1999-02-01), Cumming et al.
patent: 5896529 (1999-04-01), Kulkarni et al.
patent: 0 544 026 (1993-02-01), None
“Polymoric Branc Predictor,” IBM Technical Disclosure Bulletin, U.S., IBM Corp., New York, vol. 37, No. 7, Jul. 1, 1994, pp. 109-113.
Hu, L., et al., “A Systematic Branch Strategy and Its Evaluation,” IEEE International Conference on Systems, Man and Cybernetics, Cybernetics, U.S., New York, Oct. 14, 1996, pp. 1008-1013.
Poplingher Mitchell Alexander
Rahman Monis
Yeh Tse-Yu
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Pan Daniel H.
LandOfFree
Optimized branch predictions for strongly predicted compiler... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimized branch predictions for strongly predicted compiler..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimized branch predictions for strongly predicted compiler... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2914451