Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
1999-12-30
2001-09-18
An, Meng-Al T. (Department: 2154)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C712S023000, C712S214000, C712S215000, C712S217000, C712S218000
Reexamination Certificate
active
06292884
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of microprocessors and, more particularly, to reorder buffers within microprocessors.
2. Description of the Related Art
Superscalar microprocessors achieve high performance by executing multiple instructions per clock cycle and by choosing the shortest possible clock cycle consistent with the design. As used herein, the term “clock cycle” refers to an interval of time accorded to various stages of an instruction processing pipeline within the microprocessor. Storage devices (e.g. registers and arrays) capture their values according to the clock cycle. For example, a storage device may capture a value according to a rising or falling edge of a clock signal defining the clock cycle. The storage device then stores the value until the subsequent rising or falling edge of the clock signal, respectively. The term “instruction processing pipeline” is used herein to refer to the logic circuits employed to process instructions in a pipelined fashion. Although the pipeline may be divided into any number of stages at which portions of instruction processing are performed, instruction processing generally comprises fetching the instruction, decoding the instruction, executing the instruction, and storing the execution results in the destination identified by the instruction.
Generally speaking, a given instruction has one or more source operands which are input values to be operated upon by the microprocessor in response to the given instruction. Each source operand is specified by the instruction via a source operand specifier. The source operand specifier identifies a storage location which stores the corresponding source operand. In the x86 microprocessor architecture, for example, a source operand may be stored in a register or a memory location. If a source operand is stored in a register, the source operand specifier identifies one of the registers defined for the instruction set. The identified register stores the source operand. Additionally, the given instruction typically has a destination operand. The destination operand is the result of the instruction. A destination operand is stored into a location specified by a destination operand specifier, similar to the source operand specifier. It is noted that operand specifiers are sometimes referred to as operand addresses.
In order to locate a larger number of instructions which may be concurrently executed, superscalar microprocessors often employ out of order execution. If instructions are executed in order (i.e. “program order”, or the order of instructions as listed in the program sequence being executed), then the number of instructions which may be concurrently executed is limited by dependencies between the instructions. A dependency exists between a first instruction and a second instruction if the second instruction receives a value produced via execution of the first instruction (the “result” of the first instruction) as a source operand. In other words, a dependency exists if the destination operand of the first instruction is the stored in the same storage location as the source operand of the second instruction. Since the second instruction needs the result of the first instruction prior to executing, the first and second instructions cannot be concurrently executed. However, an instruction subsequent to the second instruction which does not depend upon either the first instruction or the second instruction may be concurrently executed with the first instruction.
Microprocessors which implement out of order execution often employ a reorder buffer for storing speculatively generated instruction results until the corresponding instructions become non-speculative. After the corresponding instructions become non-speculative, the instruction results may be moved from the reorder buffer to the storage locations indicated by the destination operand specifiers. Generally, a particular instruction becomes non-speculative when each of the instructions which may cause an exception and which are prior to the particular instruction in program order have executed and reported no exception. Often, reorder buffers are configured to store the instruction results into the destination storage locations (i.e. retire the instructions) in program order.
Because instruction results are held in the reorder buffer and the instruction results may be source operands for subsequent instructions, reorder buffers perform dependency checking between source operands of the subsequent instructions and the instructions represented within the reorder buffer. Dependency checking is performed in order to forward the source operands (or a reorder buffer tag which identifies an instruction result corresponding to that source operand if the instruction result has not yet been generated via the execution of a prior instruction) to the execution units which receive the subsequent instructions (or to the reservation stations associated with the execution units). If a reorder buffer tag is forwarded, the execution unit monitors instruction results provided to the reorder buffer to capture, as a source operand, the instruction result corresponding to that reorder buffer tag. Generally speaking, dependency checking comprises comparing source operand specifiers of instructions to destination operand specifiers stored in the reorder buffer. If the source operand specifier and one of the destination operand specifiers indicate the same storage location, the source operand specifier and the destination operand specifier as said to match. For register operand specifiers, a match is generally detected if the operand specifiers are equal to each other.
Unfortunately, dependency checking generally involves more than a simple comparison of operand specifiers. More than one of the destination operand specifiers stored in the reorder buffer may match a particular source operand. The correct dependency is a dependency upon the instruction which is last, in program order, of the instructions for which the destination operand specifier matches the particular source operand specifier. Typically, a source operand specifier is compared to all the destination operand specifiers stored in the reorder buffer. The resulting match indications are then prioritized according to the program order of the instructions. In other words, a match indicated according to a comparison between a source operand specifier and one of the destination operand specifiers in the reorder buffer is qualified by the result of other comparisons before the corresponding reorder buffer tag or instruction result is selected for forwarding. The prioritization of matches increases the amount of time required to detect a given dependency. It is desirable to decrease the amount of time needed to perform dependency checking and to simplify the dependency checking logic.
A similar problem occurs upon retirement of instructions from the reorder buffer. Upon retirement, the instruction results corresponding to the instructions being retired are stored into the register file. Typically, the reorder buffer attempts to retire multiple instructions during a clock cycle. The destination operands of the instructions being retired are compared to each other to ensure that only one update to a given register is performed (i.e. the update corresponding to the last of the retiring instructions in program order). It is desirable to simplify the retirement logic as well.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by a reorder buffer in accordance with the present invention. The reorder buffer described herein stores a last in buffer (LIB) indication corresponding to each instruction. The last in buffer indication indicates whether or not the corresponding instruction is last, in program order, of the instructions within the buffer to update the storage location defined as the destination of that instruction. The LIB indication is included in the dependency checking comparisons. A dependency is indicated for
Tran Thang M.
Witt David B.
Advanced Micro Devices , Inc.
An Meng-Al T.
Conley Rose & Tayon PC
El-Hady Nabil
Merkel Lawrence J.
LandOfFree
Reorder buffer employing last in line indication does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reorder buffer employing last in line indication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reorder buffer employing last in line indication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2470680