Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-03-30
2004-07-20
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S233000
Reexamination Certificate
active
06766442
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 predict a condition register-dependent conditional branch instruction utilizing a stale condition register value.
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, a condition register, and a branch prediction circuit that predicts a condition register-dependent branch instruction by reference to a potentially stale condition register value to produce a speculative instruction fetch address. In a preferred embodiment, the processor includes branch execution circuitry that subsequently determines if the speculative instruction fetch address is correct by reference to a non-stale value of the condition register.
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.
Hennessy, John L. and Patterson, David A. Computer Architecture: A Quantitative Approach. Second Edition. San Francisco, CA: Morgan Kaufmann Publishers, Inc. ©1996. pp. 232 and 251-261.*
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
Chan Eddie
Dillon & Yudell LLP
Emile Volel
Li Aimee J.
Roberts Diana L.
LandOfFree
Processor and method that predict condition... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Processor and method that predict condition..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processor and method that predict condition... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3216994