Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-05-29
2001-07-17
Eng, David Y. (Department: 2155)
Electrical computers and digital processing systems: processing
Processing control
Branching
Reexamination Certificate
active
06263428
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a branch predictor for predicting the presence of a branch in a branch instruction, and more particularly to a technique which is effective when it is applied to a branch predictor making the prediction of whether or not a branch is to be taken by a conditional branch instruction with which the judgement is made as to whether or not a loop processing is to be iterated.
Recent microprocessors have remarkable improvements in speed. It is general in these microprocessors that the deep-pipeline execution or the out-of-order execution (in which the execution of a successor instruction is started without waiting for the completion of the execution of a predecessor instruction) is made or a cache memory is used. Though those techniques are effective, the performance is degraded in the following cases.
Namely, the pipeline execution and the out-of-order execution are effective in the case where a continuous train of instructions are to be executed. In many instances, however, a large penalty is imposed in the case where the continuity is destroyed owing to a conditional branch instruction. Accordingly, the performance is degraded in the case where a branch is generated by a conditional branch instruction.
As to the improvement in speed by the use of the cache memory, on the other hand, an instruction cache miss is generated in the case where the reference to an instruction included in no cache memory is made in a program. The generation of the instruction cache miss causes the degradation in speed.
For such circumstances, the possession of a mechanism for predicting whether or not a branch is to be taken by a conditional branch instruction is a primary issue of late. Especially, a method disclosed in the article by Tse-Yu Yeh and Yale N. Patt, “Two-Level Adaptive Training Branch Prediction”, Proceedings of the 24th Annual International Symposium on Microarchitecture, 1991, pp. 51-61 is widely used in view of the accuracy of prediction. In the disclosed method, there is prepared a branch information table which includes the record of what branch was taken for each conditional branch instruction (the record showing the presence of previous branch execution will hereinafter be referred to as branch history information). On the basis of the record, the prediction is made as to whether or not a branch is to be taken at the time of next execution of that conditional branch instruction.
In the method disclosed by the above article, the branch history information includes only the branch execution history record of the last branches up to several. times the amount of the last branches at the most. Therefore, this method has a disadvantage in that it is difficult to predict the result of execution of a conditional branch instruction making an operation in which a branch is taken to a certain branch target address some times and the next instruction is thereafter executed with no branch being taken only one time. Such an operation appears in the most conditional branch instructions with which the judgement is made as to whether or not a loop is to be iterated in a loop portion included in a program. For such a conditional branch instruction, it is difficult to predict a branch at the time of termination of a loop after the iterative execution thereof. Therefore, the prediction in the case of loop termination results in a miss always.
SUMMARY OF THE INVENTION
An object of the present invention is to solve the above-mentioned problem, thereby providing a branch predictor which is capable of making the accurate prediction of a branch at the time of loop termination in a conditional branch instruction with which the judgement of loop termination is made.
In a branch predictor of the present invention for predicting an instruction to be executed next to a conditional branch instruction in a program to read the predicted instruction beforehand, there is acquired a hint indicating whether or not a branch is to be taken by the execution of a conditional branch instruction with which the judgement of loop termination. An instruction predicted as executed next to a conditional branch instruction is read in accordance with the hint.
In the present invention, there are prepared, in addition to a branch prediction mechanism based on ordinary branch history information, hint acquisition control means for controlling the acquisition of a hint indicating whether or not a branch is to be taken by the execution of a conditional branch instruction with which the termination of a loop is judged, hint acquisition means for acquiring, the hint indicating whether or not a branch is to be taken, in accordance with the value of a certain register, for example, a loop counter register (hereinafter referred to as CTR), hint store means for storing the hint, and instruction read means for reading an instruction predicted as executed next to a conditional branch instruction in accordance with the hint. With the use of these means, an accurate prediction is made as to whether a branch is to be taken by a conditional branch instruction with which the judgement of loop termination is made.
The hint acquisition control means makes upon compilation the determination and designation of whether the value of the above-mentioned hint or a prediction result by the branch prediction mechanism based on ordinary branch history information should be used as the predictor of whether a branch is to be taken by a conditional branch instruction. With this designation, the accurate prediction is made as to whether a branch at the time of loop termination is to be taken by a conditional branch instruction with which the judgement of loop termination is made.
The CTR is set with a specified value at the time of start of a loop in a program and is updated during the iterative operation of the loop. In the case where the CTR takes a value which satisfies a specified condition, the loop is terminated.
The hint acquisition means makes, in accordance with the value of the CTR, the prediction of whether a branch is to be taken by a conditional branch instruction with which the judgement of loop termination is made. The result of prediction is recorded as a hint bit in a branch hint table which is the hint store means.
In the case where a loop trip count is known at the time of loop start, the value of the loop trip count is set to the CTR, for example, at the time of loop start. In this case, the value of the CTR is decremented each time a conditional branch instruction for looping is executed and the CTR takes 0 at the time of loop termination. At this time, it is possible to determine the value of the hint bit by making predictions while taking notice of, for example, a change in value of the CTR as shown in the following.
(1) In the case where the value of the CTR is larger than 1, the CTR will not take 0 at the time of next execution of the loop termination judging conditional branch instruction and hence the control can be predicted as turned to an instruction address with which the loop is iterated.
(2) In the case where the value of the CTR is 1, the CTR will take 0 at the time of next execution of the loop termination judging conditional branch instruction and hence the control can be predicted as turned to an instruction address with which the loop is terminated.
In the case where the value of the CTR is 1 in the above example, the hint acquisition means predicts the control as turned to an instruction address with which the loop is terminated, so that a hint indicating that the loop is to be terminated is recorded into the hint bit of the branch hint table.
The instruction read means reads, in accordance with the value of the hint bit in the branch hint table, an instruction predicted as executed next to a conditional branch instruction with which the judgement of loop termination is made.
With the prediction of whether or not a branch is to be taken by a conditional branch instruction with which the judgement of loop termination is made, as mentioned above, it is possible to re
Kikuchi Sumio
Nonomura Yo
Antonelli Terry Stout & Kraus LLP
Eng David Y.
Hitachi Ltd
LandOfFree
Branch predictor 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 predictor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Branch predictor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2481551