Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-11-01
2002-09-24
Pan, Daniel H. (Department: 2783)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S236000, C712S237000, C712S245000, C712S240000, C711S123000, C711S125000, C711S144000, C711S145000
Reexamination Certificate
active
06457120
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to a data processing system and, in particular, to a superscalar processor. Still more particularly, the present invention relates to a superscalar processor and method for improving the accuracy of predictions of branch instruction destinations utilizing a cache including confirmation bits.
2. Description of the Related Art
Most architectures include branch instructions whose targets cannot be calculated from the address of the branch and the instruction itself. A branch (conditional or unconditional) whose target address is stored in a separate register and cannot be: calculated from the address of the instruction and the instruction itself is referred to here as an address-predictable branch instruction. For example, in the PowerPC (TM) architecture, the target address for “Branch Conditional to Link Register” (BCLR) or “Branch Conditional to Link Register and Link” (BCLRL) instructions is found in the Link Register (LR), and the target address for “Branch Conditional to Count Register” (BCCTR) or “Branch Conditional to Count Register and Link” (BCCTRL) instructions is found in the Count Register (CTR). The Link Register and Count Register are special purpose registers in the PowerPC architecture which are used mainly for storing the address of these instructions.
The architecture guarantees that these special-purpose registers will contain the requisite target address for an address-predictable branch when the instruction immediately prior to the address-predictable branch completes. An S instruction completes when a completion signal is received from the completion unit. In a deeply-pipelined microprocessor, an instruction is usually fetched many cycles prior to its execution and subsequent completion. Since the completion of this prior instruction usually lags the fetching of the instructions following the address-predictable branch by many cycles, there is a need to be able to predict the target of such branches with high accuracy.
A cache, which is a small amount of memory, may be maintained within a processor to store the predicted target addresses for such address-predictable branches.
A programmer writes code in a particular sequence. The code may include various branch, or jump, instructions. Branch instructions cause a departure during the execution of instructions from the original sequential order of the instructions. One method for increasing the speed of execution of instructions is to predict the likely outcome of the execution of a branch instruction. A prediction is made as to whether or not a branch will be taken the next time this branch instruction is executed.
A cache may be maintained within a processor which is a small amount of memory which includes a predicted destination for a particular type of branch instruction. This particular type of branch instruction is an address-predictable branch instruction whose target address is stored in a separate register, such as the cache described above, and whose target address cannot be calculated from the instruction itself.
The cache includes a plurality of entries. Each branch instruction will be associated with one of the entries. When a branch instruction is fetched, the entry of the cache associated with this branch instruction is read to determine the predicted destination for this branch.
Typically, after the branch is executed, if the actual branch destination was different from the predicted branch destination, the appropriate entry of the cache will be updated to include the actual destination. However, a problem can arise when the branch instruction continues to branch consecutively between a more common destination and a less common destination. For example, if a branch instruction first branches to a destination “A”, then to destination “B”, and then back to destination “A”, and continuing with this pattern, it is clear that the cache will always contain an incorrect prediction. After the branch to “B”, the entry of the cache will be updated to include “B” as the predicted destination. Thereafter, after the next branch to “A”, the cache will again be updated to predict “A” as the destination. For the example given, the cache will always mispredict the destination of this branch instruction.
Therefore a need exists for a data processing system and method for improving the accuracy of predictions of destinations of a particular type of address-predictable branch instructions utilizing a cache.
SUMMARY OF THE INVENTION
A superscalar processor and method are disclosed for improving the accuracy of predictions of a destination of a branch instruction utilizing a cache. The cache is established including multiple entries. Each of multiple branch instructions are associated with one of the entries of the cache. One of the entries of the cache includes a stored predicted destination for the branch instruction associated with this entry of the cache. The predicted destination is a destination the branch instruction is predicted to branch to upon execution of the branch instruction. The stored predicted destination is updated in the one of the entries of the cache only in response to two consecutive mispredictions of the destination of the branch instruction, wherein the two consecutive mispredictions were made utilizing the one of the entries of the cache.
The above as well as additional objectives, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5226130 (1993-07-01), Favor et al.
patent: 5553253 (1996-09-01), Pan et al.
patent: 5625788 (1997-04-01), Boggs et al.
patent: 5835745 (1998-11-01), Sager et al.
patent: 5881277 (1999-03-01), Bondi et al.
patent: 6101577 (2000-08-01), Tran
Bracewell & Patterson L.L.P.
McBurney Mark E.
Pan Daniel H.
LandOfFree
Processor and method including a cache having confirmation... 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 including a cache having confirmation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processor and method including a cache having confirmation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2883942