Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-03-30
2003-12-02
Kim, Kenneth S. (Department: 2181)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S234000, C712S240000
Reexamination Certificate
active
06658558
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to data processing and, in particular, to branch prediction within a data processing system. Still more particularly, the present invention relates to a processor and method of branch prediction that select one of a plurality of branch predictions in accordance with the type of underlying condition upon which a branch depends.
2. Description of the Related Art
A state-of-the-art superscalar processor can comprise, for example, an instruction cache for storing instructions, one or more execution units for executing sequential instructions, a branch unit for executing branch instructions, instruction sequencing logic for routing instructions to the various execution units, and registers for storing operands and result data.
Branch instructions executed by the branch unit of the superscalar processor can be classified as either conditional or unconditional branch instructions. Unconditional branch instructions are branch instructions that change the flow of program execution from a sequential execution path to a specified target execution path and which do not depend upon a condition supplied by the occurrence of an event. Thus, the branch in program flow specified by an unconditional branch instruction is always taken. In contrast, conditional branch instructions are branch instructions for which the indicated branch in program flow may be taken or may not taken depending upon a condition within the processor, for example, the state of a specified condition register bit or the value of a counter.
Conditional branch instructions can be further classified as either resolved or unresolved, based upon whether or not the condition upon which the branch depends is available when the conditional branch instruction is evaluated by the branch unit. Because the condition upon which a resolved conditional branch instruction depends is known prior to execution, resolved conditional branch instructions can typically be executed and instructions within the target execution path fetched with little or no delay in the execution of sequential instructions. Unresolved conditional branches, on the other hand, can create significant performance penalties if fetching of sequential instructions is delayed until the condition upon which the branch depends becomes available and the branch is resolved.
Therefore, in order to minimize execution stalls, some processors speculatively execute unresolved branch instructions by predicting whether or not the indicated branch will be taken. Utilizing the result of the prediction, the instruction sequencing logic is then able to speculatively fetch instructions within a target execution path prior to the resolution of the branch, thereby avoiding a stall in the execution pipeline in cases in which the branch is subsequently resolved as correctly predicted. Conventionally, prediction of unresolved conditional branch instructions has been accomplished utilizing static branch prediction, which predicts resolutions of branch instructions based upon criteria determined by a compiler prior to program execution, or dynamic branch prediction, which predicts resolutions of branch instructions by reference to branch history accumulated on a per-address basis within a branch history table. More recently, even more elaborate two-level branch prediction methodologies have been proposed that utilize a first level of branch history that specifies the resolutions of the last K branch instructions to index into a second level of branch prediction storage that associates a resolution prediction with each (or selected ones) of the
2
K-1
possible branch history patterns.
While conventional static and dynamic branch prediction methodologies have reasonably high prediction accuracies for some performance benchmarks, the severity of the performance penalty incurred upon misprediction in state-of-the-art processors having deep pipelines and high dispatch rates makes it desirable to improve prediction accuracy.
SUMMARY OF THE INVENTION
In accordance with the present invention, a processor having improved branch prediction accuracy includes at least one execution unit that executes sequential instructions and branch processing circuitry that processes branch instructions. The branch processing circuitry includes a number of branch prediction circuits that are each capable of providing a branch prediction for a conditional branch instruction, a selector that selects a branch prediction of a branch prediction circuit based upon the type of condition upon which the conditional branch instruction depends, and branch resolution circuitry that corrects for branch misprediction multiple pipeline stages later. The branch processing circuitry further includes path address logic that determines a path address of the selected branch prediction. Thus, branch prediction accuracy can be improved by considering the type of condition upon which a conditional branch instruction depends, rather than just branch history.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 4435756 (1984-03-01), Potash
patent: 4439828 (1984-03-01), Martin
patent: 5193167 (1993-03-01), Sites et al.
patent: 5454117 (1995-09-01), Puziol et al.
patent: 5515518 (1996-05-01), Stiles et al.
patent: 5530825 (1996-06-01), Black et al.
patent: 5553255 (1996-09-01), Jain et al.
patent: 5687360 (1997-11-01), Chang
patent: 5752014 (1998-05-01), Mallick et al.
patent: 5758142 (1998-05-01), McFarling et al.
patent: 5794028 (1998-08-01), Tran
patent: 5794063 (1998-08-01), Favor
patent: 5933628 (1999-08-01), Chang
patent: 6092187 (2000-07-01), Killian
patent: 6105098 (2000-08-01), Ninose et al.
patent: 6230261 (2001-05-01), Henry et al.
patent: 6247122 (2001-06-01), Henry et al.
patent: 6374349 (2002-04-01), McFarling
patent: 6421774 (2002-07-01), Henry et al.
patent: 6499101 (2002-12-01), Henry et al.
Computer Dictionary Second Edition: The Comprehensive Standard for Business, School, Library and Home; Redmond, Washington: Microsoft Press, 1994; p. 253.
Kahle James Allan
Moore Charles Roberts
Bracewell & Patterson L.L.P.
Emile Volel
Kim Kenneth S.
LandOfFree
Branch prediction circuit selector with instruction context... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Branch prediction circuit selector with instruction context..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Branch prediction circuit selector with instruction context... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3181010