Electrical computers and digital processing systems: processing – Processing control – Branching
Utility Patent
1997-12-31
2001-01-02
Follansbee, John A. (Department: 2783)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S023000, C712S226000, C712S240000
Utility Patent
active
06170052
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to processors and computers, and more particularly, to a method and apparatus for implementing predicated sequences in a processor that renames registers.
2. Description of the Related Art
Modern processors and computers have increased their operating speed and efficiencies through a variety of methods. One method involves sequentially fetching instructions from caches and/or memory without waiting for prior instructions to be executed. A processor that uses the no-wait sequential fetching can operate more efficiently, because the instruction stored in the next sequential memory location is frequently the next instruction to be executed by the processor. No-wait sequential fetching enables the processor reduce the number of time periods when execution units remain idle due to no instruction being available for execution.
Occasionally, the instruction sequence will contain a branch instruction that jumps to a non-sequential memory address for the next instruction to be executed. After executing a branch instruction, instructions previously fetched from memory addresses that sequentially follow the address of the branch are flushed from fetch and execution pipelines. Flushes result in wasted processor time. In a processor that uses no-wait sequential fetching, software and/or hardware are employed to predict branch addresses so that instruction fetching can be redirected and flushes of fetch and execution pipelines avoided. Unfortunately, any method for predicting branch addresses makes some mispredictions, and each misprediction leads to a costly flush of the fetch and execution pipelines.
Sometimes branch instructions can be replaced by other instructions that do not make jumps to non-sequential memory addresses. For example, some conditional instructions may be implemented with either branch instructions or predicated sequences. Since predicated sequences do not introduce jumps to non-sequential memory addresses, implementing conditional instructions through predicated sequences can help a processor reduce the number of wasteful flushes of the fetch and execution pipelines.
FIG. 1
illustrates a predicated sequence
10
. Predicated sequences are instruction sequences containing a predicate evaluating instruction and one or more associated conditional instructions. The predicate evaluating instruction determines whether a predicate about data is true or false. For example, a predicate evaluating instruction
12
determines whether the predicate that data words in registers A and B are equal is true or false. The predicate evaluating instruction
12
stores true or false information in paired predicate registers P
x
and P
y
. P
x
and P
y
store conjugated logic information, i.e. when one register stores the value logic 1 the other register stores the value logic 0. The predicate evaluating instruction stores logic 1 in the
predicate register P
x
if the predicate is true and stores logic 1 in the predicate register P
y
if the predicate is false. The second part of a predicated sequence includes one or more instructions whose execution is conditioned on whether the predicate is true or false, i.e. dependent on the logic information stored in the predicate registers P
x
and P
y
. For example, the second instruction
14
is only executed if the predicate register P
x
stores the value logic 1, i.e., the first predicate evaluating instruction
12
determined that the predicate is true. If the predicate is false, the conditional instruction
14
is skipped and data in the register Z is unchanged. Program control by a true/false test enables predicated sequences to implement conditional instructions.
Predicated sequences include a predicate and one or more instructions whose execution depends on the predicate. The form of the predicate itself can vary in different predicated sequences. The form of the predicate evaluating instruction may employ a single predicate register P
x
and store logic 1 in the predicate register P
x
if the predicate is true and store logic 1 in the same predicate register P
x
if the predicate is false. The number of instructions whose execution is conditioned on the predicate also varies in different predicated sequences. Some predicated sequences have one instruction conditioned on the predicate being, for example, true. Some predicated sequences have first and second conditional instructions that are executed when the predicate is true and false, respectively. In the varied forms for predicated sequences, the conditional instructions are ordinarily in sequential memory locations that are executed sequentially.
Artificial dependencies among instructions lower the flexibility of the execution order thereby reducing the efficiency of an out-of-order processor. Register renaming eliminates artificial dependencies associated with write-after-write and write-after-read instruction sequences. Thus, register renaming can improve the efficiency of an out-of-order processor. Register renaming can lead, however, to problems when the instruction sequence contains predicated sequences.
FIG. 2
illustrates the effect of prior art renaming on the predicated sequence
10
in FIG.
1
. In
FIG. 1
, the conditional instruction
14
and an earlier instruction
16
have the same destination register Z and form a write-after-write sequence, i.e. two instructions having the same destination registers. Therefore, a prior art renamer would replace the destination register Z of the conditional instruction
14
with a register Z
1
, to produce renamed instructions
18
,
16
having different destination registers Z
1
, and Z, respectively.
Ordinarily, renaming removes artificial dependencies between instructions such that out-of-order execution does not change the results. In the prior art, renaming replaces logical registers of source addresses of an instruction with the physical register that was assigned to the most recent instruction having the same logical register as a destination address. Prior art renaming changes the nature of the predicated sequence, because later instructions (not shown), having Z as a source address, depend on “both” of the instructions
16
,
14
, in
FIG. 1
, and depend only on the conditional instruction
18
after renaming. Prior art renaming changes the real double dependencies of later instructions (not shown) on both of the instructions
14
,
16
. Renaming breaks the dependency of later instructions, having Z as a source register, on any earlier instruction when the predicate
12
is false.
Both renaming and predicated sequences can improve the performance of out-of-order processors. Renaming can eliminate artificial dependencies that would otherwise make the execution order of the instruction sequence less flexible. Predicated sequences can eliminate the need for some conditional branch instructions that could otherwise lead to mispredicted branches and processor flushes. Unfortunately, implementing predicated sequences with prior art renaming changes the results from a predicated sequence and will produce incorrect results.
The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.
SUMMARY OF THE INVENTION
In one aspect of the present invention, a method is provided for renaming registers. The method includes renaming a destination register of a first conditional micro-op with a physical register, and renaming a destination register of a second conditional micro-op with the physical register. The first conditional micro-op belongs to a special predicated sequence. The second conditional micro-op belongs to the same special predicated sequence.
In another aspect of the present invention, an apparatus is provided. The apparatus includes a renamer to rename the destination registers of two conditional micro-ops with a single physical register in response to the two conditional micro-ops having the same destination register and belonging to a single special predicated sequence. The app
Blakely , Sokoloff, Taylor & Zafman LLP
Follansbee John A.
Intel Corporation
Nguyen Dzung C.
LandOfFree
Method and apparatus for implementing predicated sequences... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for implementing predicated sequences..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing predicated sequences... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2452849