Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Commitment control or register bypass
Reexamination Certificate
1999-08-17
2002-08-27
Coleman, Eric (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Commitment control or register bypass
C712S239000
Reexamination Certificate
active
06442679
ABSTRACT:
The present invention relates generally to a dynamically-scheduled microprocessor, and particularly to a guard outcome predictor for a dynamically-scheduled microprocessor that executes predicated instructions.
BACKGROUND OF THE INVENTION
A predicated instruction is a machine-level instruction whose operation is performed only if a specified condition is true. (For brevity, the term “instruction” will be used hereafter for “machine-level instructions”.) A conditional move, CMOV, is an example of a predicated instruction. A predicated instruction includes a guard and guarded instructions. The guard includes a guard operator and at least one guard source. The guard operator is applied to the guard sources to determine whether the specified condition is true. Possible guard operators include, for example: equal-to-zero, EQ; greater-than-zero, GT; and not-equal-to-zero, NEQ. A guard source may be a constant encoded within the predicated instruction or the contents of a register whose ID is encoded within the predicated instruction. Application of the guard operator to the guard sources yields a guard outcome. When the guard outcome is TRUE then the guarded instructions are executed. On the other hand, if the guard outcome is FALSE, then execution of the guarded instructions must not affect the architectural state of the microprocessor. In other words, if the guard outcome is FALSE execution of the guarded instructions must not affect the state visible to an application program.
Execution of predicated instructions impacts the design and performance of dynamically-scheduled microprocessors, particularly those using register renaming. A brief description of dynamically-scheduled microprocessors and register renaming helps illustrate the difficulties presented by predicated instructions. A dynamically-scheduled microprocessor is one in which instructions may be issued to the functional units for execution in an order that is different from the order in which the instructions are fetched. To increase the number of instructions that may be issued in any given cycle, many dynamically-scheduled microprocessors use register renaming to eliminate write-after-write and write-after-read dependencies. Register renaming involves mapping the architectural registers named in the instructions to actual, physical, registers. Register renaming typically occurs after an instruction has been fetched.
FIG. 1
illustrates, in block diagram form, a prior dynamically-scheduled microprocessor. The microprocessor includes a data and instruction cache and a series of cascaded stages: a fetcher, mapper, dispatcher, execution pipes, and a retire unit. The fetcher fetches instructions from the memory hierarchy and decodes them to determine the operation of the instruction as well as all of the architectural registers and/or constants required for instruction execution. The order in which instructions are fetched is called the fetch order. For each fetched instruction, decoding yields zero or more architectural source registers and zero or more destination architectural registers. These two sets of architectural registers are then renamed to physical registers by the mapper. That is, for each instruction I in fetch order, the mapper maps I's source architectural registers to the physical registers that contain the corresponding latest values. Then, if instruction I names one or more destination registers, the mapper maps each of these registers to a unique and free physical register. For example, if instruction I names a single destination architectural register L
dx
, the mapper will create a mapping between L
dx
and some free physical register P
1
. This mapping will remain active until another instruction I
2
that names L
dx
as one of its destination registers subsequently enters the rename stage. When such an instruction occurs, the mapper creates a mapping between L
dx
and a free physical register P
2
and in the process, unmaps P
1
from L
dx
. As a result of this unmapping, for all instructions subsequent to I and up to and including I
2
that name L
dx
as a source register, the mapper will map this source register to P
1
. That is, P
1
will contain the latest value of L
dx
for these instructions. After register renaming, instructions are placed in the dispatch buffer of the dispatcher. The dispatcher dynamically selects from its buffer the next instruction to be issued to the execution pipes. The dispatcher issues instructions when their input dependencies have been resolved and when a suitable functional unit of the execution pipes is available. After the execution pipes have completed execution of an instruction, the result may be written back into a destination register, if one was allocated during register renaming. When all architectural constraints of an instruction have been satisfied, the retire unit retires, or commits, the instruction results to the architectural state of the microprocessor. If the retire unit commits results in program order, when an instruction is committed that names one or more architectural destination registers, one or more physical registers are freed. That is, assuming the retire unit commits instruction I
2
above, during the process it will free physical register P
1
. Physical register P
1
can be freed at this point because there are no longer any instructions in the system that require the value contained in P
1
. In general, physical registers can be freed only when their being freed will not prevent the processor from recovering and resuming execution after a mispredicted branch or a non-fatal exception. Recovery and execution resumption requires, among other things, the ability to restore the register mapping and the list of free physical registers. A number of approaches to state recovery exist.
The design and performance impact upon a dynamically-scheduled microprocessor of supporting predicated instructions arise from the additional data dependencies of predicated instructions. Predicated instructions include three sources of data dependencies, as compared to the single source of data dependency of a non-predicated instruction. The first input-dependency source, which is unique to predicated instructions, relates to the guard sources. To determine the guard outcome, a microprocessor must read the value of the guard sources and apply to it the guard operator. The second input-dependency source, which is not unique to predicated instructions, relates to the source registers named in the guarded instructions. If the guard outcome is TRUE, then the hardware performs the operations specified by the guarded instructions using the values of the sources for the guarded instructions. The reading of these sources induces an input dependency. The final input dependency relates to the destinations of the guarded instructions and is unique to predicated instructions. The general case is more easily explained using an example. If a guarded instruction I names a destination architectural register L
dst
and if the guard outcome is FALSE, those instructions preceding the predicated instruction I in fetch order and those following it must all obtain the same value if they read from L
dst
, assuming that no other intervening instructions write L
dst
. But, because of the use of register renaming, instructions preceding I will read a physical register P
old
while those following I will read another physical register P
new
, assuming that when the renamer renames the registers for I, it unmapped P
old
when mapping P
new
to L
dst
. To ensure that instructions preceding and following instruction I all obtain the same value, if the guard outcome is FALSE. P
old
must be read and its value written into P
new
, The read of this value induces the third input-dependency source. It is possible to implement a more complicated register renaming mechanism that does not introduce this dependency source.
The additional sources of input data dependencies of predicated instructions affect the design and performance of a dynamically-scheduled microprocessor in two ways. First,
Farkas Keith Istvan
Klauser Arthur
Coleman Eric
Compaq Computer Technologies Group, L.P.
Pennie & Edmonds LLP
LandOfFree
Apparatus and method for guard outcome prediction 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 for guard outcome prediction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for guard outcome prediction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2945728