Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-03-30
2004-01-13
Wiley, David (Department: 2143)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S241000
Reexamination Certificate
active
06678820
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 separately predict conditional branches dependent on lock acquisition.
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 a plurality of branch prediction circuits including a lock acquisition branch prediction circuit that predicts a speculative execution path for a conditional branch instruction. The processor further includes a selector that selects the speculative execution path predicted by the lock acquisition branch prediction circuit in response to an indication that the conditional branch instruction is dependent upon lock acquisition. In a preferred embodiment, the indication that the conditional branch instruction is dependent upon lock acquisition is encoded within the conditional branch instruction.
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: 5175827 (1992-12-01), Morisada
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: 5909573 (1999-06-01), Sheaffer
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: 6438682 (2002-08-01), Morris 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.
Collins Scott M.
Emile Volel
International Business Machines - Corporation
Wiley David
LandOfFree
Processor and method for separately predicting conditional... 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 for separately predicting conditional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processor and method for separately predicting conditional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3253348