Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-04-07
2003-10-28
Tsai, Henry W. H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S233000, C712S240000
Reexamination Certificate
active
06640298
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method of and an apparatus for predicting, at execution of a sequence of instructions by a processor, before execution of the branch instruction whether or not a branch instruction in the instruction sequence takes a branch.
General processors today use a pipeline system to execute a sequence of instructions to increase the total throughput. However, the pipeline system alone is not sufficient. Namely, when a branch instruction exists in the instruction sequence, an instruction at a branch destination thereof is only known after the branch instruction is completely executed. This causes an idle period of time in the pipeline and its performance is deteriorated. Particularly, in recent processors of a superscalar type to simultaneously execute a large number of instructions, the performance deterioration is conspicuous. To cope with this disadvantage, at a stage to fetch a branch instruction, whether the branch is “taken” or is “not taken” by the branch instruction is predicted to immediately fetch an instruction subsequent to the branch instruction. Namely, when the prediction is true, the performance is not deteriorated. This technique is called branch prediction and is described in detail, for example, in “Computer Architecture: A Quantitative Approach Second Edition” written by David A. Patterson and John L. Hennessy and published from Morgan Kaufmann Publishers. Inc. in 1996.
According to the literature above, a branch prediction mechanism is implemented by a branch prediction buffer which is accessed by low-order bits of an address of a branch instruction. Each entry of the buffer includes a counter or the like to hold 2-bit information and is updated as shown in a state transition diagrams of
FIGS. 2A and 2B
according to a result of the branch instruction, i.e., “taken” or “not taken”. In
FIGS. 2A and 2B
, a one-to-one correspondence exists between states
300
to
303
and values of the counter, and letter t or n assigned to an arrow between the states represents a transition condition. In branch prediction, “a branch is taken” is predicted for state
300
or
301
and “a branch is not taken” for state
302
or
303
. The prediction method using the 2-bit counter predicts “taken” or “not taken” with a high true prediction ratio for branch instructions for which either “taken” or “not taken” occurs in most cases.
To increase the true prediction ratio, there has been also employed a branch prediction method in which the 2-bit counter corresponds to each historical pattern of branch instructions, not each branch instruction. This method requires, in addition to the branch prediction list, a branch history table to keep, for each branch instruction, several branch results thereof in the past. In the branch prediction of a branch instruction, the system refers to a history pattern of the branch history table by low-order bits of an address of the branch instruction and then refers to the 2-bit counter of the branch prediction table.
In addition to the branch prediction method, there has been used a prediction method using a 2-bit counter corresponding to a pattern of a comprehensive or global history of all branch instructions.
Microprocessors described in the “Microprocessor Report Oct. 26, 1998” and in “The 21264: A Superscalar Alpha Microprocessor with Out-of-Order Execution” of Microprocessor Forum 97th Annual adopt these branch prediction methods.
FIG. 3
shows constitution of such microprocessors. A choice prediction
404
according to a global
402
is used to select a result of prediction from a local prediction
401
using a local history
400
for each branch instruction or a result of prediction from a global prediction
403
using a global history
402
.
The branch prediction method of the prior art using a 2-bit counter for each branch instruction cannot appropriately predict a pattern of a branch instruction in which the conditions “taken” and “not taken” alternately and consecutively appear. Namely, at least 50% of predictions are false. The prediction method using a counter for the history of each branch instruction can cope with such a branch pattern. However, to hold the history of each branch instruction and to provide an increased number of counters for the history, the constituent components of hardware are considerably increased.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a branch prediction apparatus in which, while keeping the prediction performance of an imbalanced branch pattern in which either “taken” or “not taken” occurs in most cases and which is suitably handled by the branch prediction method of the prior art, a pattern of a branch instruction in which the conditions “taken” and “not taken” alternately and consecutively appear is appropriately predicted only with a few additional hardware components.
In the method of prior art to select, according to the global history, either one of two predictions including the local and global branch predictions, even when each branch instruction has a tendency towards suitability of either one of the prediction methods, the selection cannot be achieved by directly using the tendency.
Another object of the present invention is to provide a branch prediction apparatus including a branch prediction apparatus above and a global branch prediction apparatus to select a prediction method according to a tendency of each branch instruction.
To achieve the objects in accordance with the present invention, there is provided a branch prediction apparatus comprising a branch prediction table for storing one history bit and a 2-bit counter for each branch instruction, the bit and the counter being updated according to a result of “branch taken” or “branch not taken” for the branch instruction; a prediction generator for outputting, when the counter has a value of 0 or 2 for a branch instruction, a value of the history bit as a result of prediction and for outputting, when the counter has a value of 1 or 3 for a branch instruction, a value obtained by reversing the history bit as a result of prediction; and a counter controller for comparing for a branch instruction a result thereof with a value of the history bit before update, for setting 0 to the counter value when the result matches the value; and for adding, when the result does not match the value and the counter value is other than 3, one to the counter value.
In order to achieve the objects in accordance with the present invention, there is provided a branch prediction apparatus comprising a branch prediction table for storing three prediction bits for each branch instruction, a prediction generator for outputting, when the prediction bits are in one of four states thereof, “branch taken” as a result of prediction and for outputting, when the prediction bits are in other one of the four states thereof, “branch not taken” as a result of prediction; and a prediction bit controller for controlling the prediction bits. The prediction generator generates, when a result of a branch instruction is equal to a previous result thereof, a result of prediction equal to the current result of the branch instruction at next appearance of the branch instruction. The prediction generator generates, when a result of a branch instruction is opposite to a previous result thereof and this condition occurs once or consecutively three times, a result of prediction opposite to the current result of the branch instruction at next appearance of the branch instruction. The prediction generator generates, when a result of a branch instruction is opposite to a previous result thereof and this condition occurs successively two times, a result of prediction equal to the current result of the branch instruction at next appearance of the branch instruction.
To achieve the objects in accordance with the present invention, there is provided a branch prediction apparatus comprising a first branch predictor in accordance with claim 1 or 2, a second branch predictor for predicting a branch
Miki Yoshio
Totsuka Yonetaro
Hitachi , Ltd.
Tsai Henry W. H.
LandOfFree
Branch prediction apparatus 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 apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Branch prediction apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3146589