Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-08-30
2003-02-04
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S237000
Reexamination Certificate
active
06516409
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is related to an improved processor provided with a data value prediction circuit and a branch prediction circuit. In particular, the present invention is related to an improved processor provided with a data value prediction circuit and a branch prediction circuit which makes it possible to improve the efficiency of supplying instructions.
2. Prior Art
Along with the increasing level of superscalar parallelism and the increasing number of superpipelined stages, the disturbance of control flow due to branch instructions tends to increasingly affect the overall performance of a processor system. While the performance penalty due to branch instructions has been recognized and examined for years) after introducing the pipelined control into processors, the parallelism of execution of instructions has been attracted interest of engineers resulting in the importance of the handling of branch instructions. The branch prediction technique has been employed in order to alleviate the influence of branch instructions. Namely, the history of the branch instruction as taken or not taken is written into a table with reference to which is predicted the result of the branch instruction.
FIG. 1
is a schematic diagram showing an example of a processor provided with a branch prediction circuit. Instructions is read from the instruction cache
2
and stored in an instruction window
1
by means of the processor. Instructions latched by the instruction window
1
is ready to be dispatched to the functional units
5
when necessary operands becomes available and received by one of the functional units
5
, which then execute the instruction as dispatched. The result of the execution is broadcasted in the instruction window
1
and, at the same time, stored in the register file
4
after completion of execution. Some instructions may be executed with operands as read from the data cache
3
. The branch prediction circuit
6
conducts branch prediction in order to inform the instruction cache
2
of the address of the instruction to be fetched.
The two-level adaptive branch prediction circuit is a subject of great interest among a number of the branch prediction circuits because of the high accuracy of branch prediction that is expected. The two-level adaptive branch prediction circuit is composed of two tables.
FIG. 2
is a schematic diagram showing an example of the two-level adaptive branch prediction circuits, i.e., PAs. One table is referred to as BHT (Branch History Table)
021
composed of a plurality of shift registers. The shift registers are referred to as Branch History Registers (BHR). Each BHR is provided with one of the branch instructions and stores the history of the branch instruction corresponding thereto. Namely, each BHT is indexed with the address of the corresponding branch instruction. When the direction of a branch, i.e., taken(
1
) vs. not-taken(
0
), is decided, the result is inputted to the BHR. At this time, the oldest result is shifted out. The second table is indexed with the addresses of the branch instructions and the patterns of the history of the respective branch instructions.
The second table is referred to as Pattern History Table (PHT)
022
comprising a number of 2-bit counters with reference to which the branch prediction is conducted. If the branch is taken the corresponding counter is incremented by one, while if the branch is not taken the corresponding counter is decremented by one. The counter is saturated at its maximum and minimum values. The branch is predicted with reference to the most significant bit of the corresponding counter. Namely, if the most significant bit is 1 the branch is predicted as taken while if the most significant bit is 0 the branch is predicted as not taken.
FIG. 3
shows the state transition of the counter. For example, the BHT is indexed with the lower part of the address of a branch instruction to read the history of “0110”. The PHT is indexed with the history of “0110” and the lower part of the address of a branch instruction. The 2-bit counter as shown in broken lines is then pointed to. The direction of a branch (taken vs. not-taken) is predicted with reference to the value of the counter. Other types of the two-level adaptive branch prediction circuits have been described in several references, e.g., T-Y.Yeh, Y. N.Patt, “Alternative Implementation of Two Level Adaptive Branch Prediction”, 19th, International Symposium on Computer architecture (ISCA), 1992.
On the other hand, in the recent years, the data value prediction technique attracts interest of many researchers. Dependence disturbing processor performance includes the name dependence and the data dependence in addition to the control dependence due to the branch instruction. The name dependence is caused by resource shortage, i.e., the shortage of available registers, and can be eliminated using register renaming. However, the data dependence can not be removed by such techniques, as it is called true dependence. Hence, the data dependence is a serious obstacle limiting instruction level parallelism.
The data value prediction technique is proposed in order to remove the data dependence by speculative execution and improve the performance of the processor. Namely, the instruction having the data dependency upon a preceding instruction is executed speculatively by predicting a source operand as required. Instructions having a data dependency can therefore be executed in parallel which execution is inherently impossible.
FIG. 4
shows instructions showing an example of such a data dependency. Namely, the instruction I
1
and the instruction I
2
have a data dependency and therefore can not be executed in parallel which execution is inherently impossible. However, the instruction I
1
and the instruction I
2
can be executed by predicting the source operand &ggr;
2
of the instruction I
2
.
FIG. 5
is a schematic diagram showing an example of a processor provided with a data value prediction circuit. Instructions with source operands which have not been calculated yet are executed by the use of values of the source operands as predicted by the data value prediction circuit
7
.
FIG. 6
is a schematic diagram showing an example of the data value prediction circuit
7
as illustrated in FIG.
5
. The data value prediction circuit
7
has been designed in a hardware structure similar to that of the instruction cache
2
. The history of the execution results as calculated is stored in the data value prediction circuit
7
. Each entry of the data value prediction circuit
7
is indexed with the address PC of the program counter. Namely, each entry of the data value consists of the latest result of the operation (pred_value), the stride of the result of the operation (stride) and the state of the entry indicative of whether or not the prediction is possible. The stride value is obtained as the difference between the latest two results of the execution of the same instruction while the state value is stored by encoding the history of the execution results and indicates whether or not the prediction is possible.
The state transition as required is realized by means of the 2-bit saturation type counter as illustrated in FIG.
3
. If a value prediction succeeds, the counter is incremented while the counter is decremented if it fails. When the tag is matched, the pred_value and the stride value are obtained from the entry as pointed by the address PC. The operand value as predicted is therefore calculated as the sum of the pred_value and the stride value. The state value is obtained at the same time. If the state value is PREDICT or WEAKLY_PREDICT, the operand value as predicted is used for executing an instruction requiring the operand. The data value prediction is otherwise not conducted. Other types of the data value prediction circuit
7
have been described in several references, e.g., M. H. Lipasti, J. P. Shen, “Exceeding the Dataflow Limit via Value Prediction”, 29th International Symposium on
Ellis Richard L.
Foley & Lardner
Kabushiki Kaisha Toshiba
Meonske Tonia
LandOfFree
Processor provided with a data value prediction circuit and... 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 provided with a data value prediction circuit and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processor provided with a data value prediction circuit and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3135641