Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-08-06
2001-10-16
Kim, Kenneth S. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S239000
Reexamination Certificate
active
06304960
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates to microprocessors, and in particular to systems for processing branch instructions.
2. Background Art
Advanced processors employ pipelining techniques to execute instructions at very high speeds. In a pipelined processor, the overall machine is organized as a pipeline consisting of several cascaded stages of hardware. Instruction processing is divided into a sequence of operations, and each operation is executed by hardware resident in a corresponding pipeline stage (“pipe stage”) in a single cycle of the processor clock. Independent operations from several instructions may be processed simultaneously by different pipe stages, increasing the instruction throughput of the pipeline. Where a processor pipeline includes multiple execution resources in each pipe stage, the throughput of the processor can exceed one instruction per clock cycle. Contemporary superscalar, deeply pipelined processors may have anywhere from 5 to 15 pipe stages and may execute operations from as 4 to 8 instructions simultaneously in each pipe stage.
In order to make full use of a processor's instruction execution capability, the processor must be provided with sufficient instructions from the correct execution path. As long as the correct execution path can be identified, instructions from this execution path can be loaded into the processor pipeline to keep the execution resources busy. Where program instructions are processed sequentially, it is a relatively simple matter to determine the correct execution path. Branch instructions can disrupt sequential execution by transferring control of the processor to a non-sequential target address when an associated branch condition is met. Many programs have branches every five or six instructions. As a result, a deeply pipelined processor may have two or three branch instructions in its pipeline at a given time, making determination of the correct execution path difficult. Moreover, branch conditions are typically not resolved until the back end of the processor pipeline, so the pipeline may begin processing instructions from incorrect execution paths before the error is discovered.
Processors typically include branch prediction systems at the front end of their pipelines to anticipate changes in the control flow due to taken branch instructions. Branch prediction systems use a variety of methods to predict whether a branch instruction entering the front end of the pipeline is likely to be taken when it is executed at the back end of the pipeline, e.g. whether the branch condition is likely to be met. For branch instructions that are predicted taken, instructions beginning at the associated target address may be loaded into the pipeline behind the branch instruction. As long as the branch is resolved taken when it is executed at the back end of the pipeline, the predicted instruction sequence that follows the branch instruction is from the correct execution path, and there is no disruption of the pipeline's operation. If the prediction is incorrect, the predicted instructions are not from the correct execution path. They must be flushed from the pipeline and instructions from the correct instruction path loaded.
Instructions from a predicted branch path must thus be checked at the back end of the pipeline and either validated or corrected. Typically, this is done by comparing the target address and branch condition from the executed branch instruction with the predicted target address and branch condition. When the comparisons match, no action need be taken since the instructions in the pipeline following the branch instruction represent the correct control flow. When the comparisons do not match, the pipeline must be flushed and reloaded with instructions from the correct execution path.
Validating branch predictions can consume additional clock cycles. For example, the branch information from the executed branch instruction is resolved in one stage of the pipeline, and typically compared with the predicted branch information no earlier than the next stage of the pipeline. In processors that support predication, branch conditions are frequently represented by predicates, and predicate evaluation is a critical path in the processor. Delays in validating predicted predicates can lengthen a critical timing path in the processor pipeline.
This problem is exacerbated in processors that execute code compiled by trace scheduling, superblock scheduling, and hyper block scheduling. These methods cause fall-through, i.e. not taken, branches to cluster at the end of a scheduled code block. The clustered branch instructions are generally executed and validated in sequence. Fall through branches do not effect the control flow of the processor and each one that is executed delays the pipeline by an additional clock cycle. Further, delays due to validating each fall through branch are compounded as well. The present invention addresses these and other problems associated with executing and validating branch instructions.
SUMMARY OF THE INVENTION
The present invention is a system and method for validating branch predictions in parallel with execution of the corresponding branch instructions. It is especially suitable for use with branch processing systems capable of executing clustered branch instructions concurrently.
In accordance with the present invention, a branch validation system includes a target validation module and a condition validation module. The target validation module determines a target address for validation, using predicted branch condition information and compares the target address to a predicted target address. The condition validation module compares predicted and resolved branch condition information, and generates a flush signal when either comparison indicates a mismatch.
REFERENCES:
patent: 4833599 (1989-05-01), Colwell et al.
patent: 5333280 (1994-07-01), Ishikawa et al.
patent: 5414822 (1995-05-01), Saito et al.
patent: 5655098 (1997-08-01), Witt et al.
patent: 5699536 (1997-12-01), Hopkins et al.
patent: 5699537 (1997-12-01), Sharangpani et al.
patent: 5796998 (1998-08-01), Levitan et al.
patent: 5826070 (1998-10-01), Olson et al.
patent: 5903750 (1999-05-01), Yeh et al.
patent: 5964869 (1999-10-01), Talcott et al.
Sharangpani, Harsh, Intel Itanium Processor Microarchitecture Overview, Intel p 1-23.
Shanley, Tom, “Pentium Pro Processor System Architecture”, Mindstream, Inc., pp. 63, 66, 67, 80,89, and 109.
Sharangpani, Harsh et al., U.S. Pat. application No. 08/949,277 entitled Efficient Processing of Clustered Branch Instructions, filed Oct. 13, 1997.
Arora Judge K.
Corwin Michael Paul
Jamil Sujat
Kottapalli Sailesh
Yeh Tse-Yu
Intel Corporation
Kim Kenneth S.
Novakoski Leo V.
LandOfFree
Validating prediction for branches in a cluster via... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Validating prediction for branches in a cluster via..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Validating prediction for branches in a cluster via... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2557903