Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-08-09
2002-11-19
Lee, Thomas (Department: 2185)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S239000
Reexamination Certificate
active
06484256
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to data processing systems and, in particular, to a superscalar processor for improving the accuracy of predictions of execution of a plurality of conditional branch instructions. Still more particularly, the present invention relates to a superscalar processor for improving the accuracy of predictions of execution of a plurality of conditional branch instructions by detecting aliasing in a branch history table.
2. Description of the Related Art
A superscalar data processing system is a data processing system which includes a microprocessor architecture which is capable of executing multiple instructions per clock cycle. In order to execute multiple instructions per clock cycle, multiple independent functional units that can execute concurrently are required. These multiple instructions may be executed in their original sequence, or out of order in a sequence which is different in some way from the original sequence.
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 of instructions is to predict the likely outcome of the execution of a conditional branch instruction. A prediction is made as to whether or not a branch will be taken the next time this conditional branch instruction is executed.
A branch history table, also called a branch prediction buffer, may be maintained within a processor which is a small amount of memory which tracks whether or not a branch was taken the last time it was executed. Therefore, for a particular conditional branch instruction, if the last time this conditional branch instruction was taken, a prediction will be made that the next time the conditional branch instruction is executed it will again be taken.
A conditional branch instruction is associated with one entry of the branch history table. Typically, programs will have a large number of conditional branch instructions. Because the branch history table is a small block of memory, there are not enough entries in the table to map to only one conditional branch instruction for each entry. Therefore, some entries in the branch history table may have two or more associated conditional branch instructions. This can result in mispredictions because it is not known for which conditional branch instruction the current prediction is made.
Therefore a need exists for a data processing system and method for improving the accuracy of predictions of conditional branch instructions where the system includes a branch history table having a plurality of entries, some of which are associated with at least two of the conditional branch instructions.
SUMMARY OF THE INVENTION
A data processing system and method are disclosed for improving the accuracy of predictions of a plurality of conditional branch instructions by detecting branch aliasing. A branch history table is established within the processor which includes a plurality of entries. Some of the plurality of entries are associated with at least two of the conditional branch instructions. An aliasing table is established within the processor which includes a plurality of entries. Each of the plurality of aliasing table entries is associated with only one of the plurality of conditional branch instructions. Prior to executing one of the plurality of conditional branch instructions, an outcome of the execution of the one of the plurality of conditional branch instructions is predicted utilizing one of the plurality of branch history table entries associated with the one of the plurality of conditional branch instructions. An outcome of the execution of the one of the plurality of conditional branch instructions is also predicted utilizing one of the plurality of aliasing table entries which is associated with the one of the plurality of conditional branch instructions. Branch aliasing is detected by comparing the prediction made utilizing the branch history table with the prediction made utilizing the aliasing table. In response to the predictions being different, a determination is made that branch aliasing occurred. The prediction made utilizing the aliasing table is then utilized for predicting the outcome of the execution of the one of the plurality of conditional branch instructions.
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: 4477872 (1984-10-01), Losq et al.
patent: 4763245 (1988-08-01), Emma et al.
patent: 5142634 (1992-08-01), Fite et al.
patent: 5163140 (1992-11-01), Stiles et al.
patent: 5367703 (1994-11-01), Levitan
patent: 5577217 (1996-11-01), Hoyt et al.
patent: 5584001 (1996-12-01), Hoyt et al.
patent: 5644759 (1997-07-01), Lucas et al.
patent: 5687360 (1997-11-01), Chang
patent: 5758143 (1998-05-01), Levitan
patent: 6247122 (2001-06-01), Henry et al.
patent: 6374349 (2002-04-01), McFarling
patent: 2001/0032309 (2001-10-01), Henry et al.
“Branch History Table Indexing to Prevent Pipeline Bubbles in Wide-Issue Superscalar Processors”, by Tse-Yu and Yale N. Patt, pp. 164-175, published 1993 by IEEE.*
“Alternative Implementations of Two-Level Adaptive Branch Prediction”, by Tse-Yu and Yale N. Patt (pp. 124-134) published 1992 by ACM.*
“Computer Architecture A Quantitative Approach”, Second Edition, Hennessy and Patterson, 1996 Morgan and Kaufmann Publishers, Inc., pp. 263-264.*
“The Agree Predictor: A Mechanism for reducing Negative Branch History Interference”, by Eric Sprangle, Robert S. Chappell, Mitch alsup and Yale Patt, pp. 284-291, 1997 ACM Press.
Levitan David Stephen
Sinharoy Balaram
Bracewell & Patterson L.L.P.
England Anthony V. S.
Lee Thomas
Trujillo James K.
LandOfFree
Apparatus and method of branch prediction utilizing a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method of branch prediction utilizing a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method of branch prediction utilizing a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2973684