Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Scoreboarding – reservation station – or aliasing
Reexamination Certificate
1999-11-09
2003-04-01
Coleman, Eric (Department: 2783)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Scoreboarding, reservation station, or aliasing
C712S023000
Reexamination Certificate
active
06542986
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to the field of superscalar microprocessors and, more particularly, to handling data dependencies between concurrently dispatched instructions.
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.
In order to increase performance, superscalar microprocessors often employ out of order execution. The instructions within a program are ordered, such that a first instruction is intended to be executed before a second instruction, etc. One hazard of out of order execution is ensuring the intended functionality of the program is not altered. When the instructions are executed in the order specified, the intended functionality of the program is realized. However, instructions may be executed in any order as long as the original functionality is maintained. For example, a second instruction which does not depend upon a first instruction may be executed prior to the first instruction, even if the first instruction is prior to the second instruction in program order. A second instruction depends upon a first instruction if a result produced by the first instruction is employed as an operand of the second instruction. The second instruction is said to have a dependency upon the first instruction.
As used herein, a source operand of an instruction is a value to be operated upon by the instruction in order to produce a result. Conversely, a destination operand is the result of the instruction. Source and destination operands of an instruction are generally referred to as operand information. An instruction specifies the location storing the source operands and the location in which to store the destination operand. An operand may be stored in a register (a “register operand”) or a memory location (a “memory operand”). As used herein, a register is a storage location included within the microprocessor which is used to store instruction results. Registers may be specified as source or destination storage locations for an instruction.
Another hazard that arises in superscalar processors is due to the intra-line dependencies that may exist among concurrently dispatched instructions in the multiple dispatch model of instruction processing. The multiple dispatch model refers to the ability to dispatch multiple instructions for execution simultaneously. This is in contrast to the single dispatch model, wherein a single instruction is dispatched for execution at one time. When multiple instructions are dispatched simultaneously, it is possible for one of the simultaneously dispatched instructions to have a dependency on another one of the simultaneously dispatched instructions. This dependency arises when the source of a later instruction in program order is also the destination of an earlier instruction in program order. Because instructions may be executed out of order, incorrect results may be obtained if intra-line dependencies are not detected and resolved. One possible solution is to detect and resolve intra-line dependencies within the reorder buffer prior to dispatching the instructions to the reservation stations. However, the added circuitry involved in resolving the intra-line dependency within the reorder buffer, which may be in the “critical path” of the microprocessor, may result in a frequency limitation of the microprocessor. As used herein, “critical path” refers to those portions of the microprocessor which must be executed in the ordinary operation of the microprocessor and whose delay places a limitation on the operating frequency of the microprocessor. Consequently, increasing the delay associated with the critical path of the processor may adversely impact its performance.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by a microprocessor and method as described herein. When an intra-line dependency is detected amongst a group of simultaneously dispatched instructions, an indication of the dependency, along with an indication of the position within the group of the instruction upon which the dependency is detected, is conveyed to the corresponding reservation station. When the reservation station receives the indication, the operand tag associated with the dependency may be overwritten with the correct tag. Advantageously, the circuitry used to resolve the dependency may be moved out of the critical path of the processor; thus, improving the performance of the microprocessor by allowing it to be operated at an increased frequency.
Broadly speaking, a microprocessor is contemplated comprising a plurality of decode units, a reorder buffer, and a plurality of reservation stations. The decode units are configured to concurrently decode instructions and are configured to convey operand request information. The reorder buffer is configured to receive operand request information and convey operand information responsive to a dependency check on instructions prior in program order to the concurrently decoded instructions. The reorder buffer is further configured to detect and convey an indication of a dependency of a second instruction of concurrently received instructions on a first instruction of concurrently received instructions, where the second instruction is subsequent to the first instruction in program order. Finally, the reservation stations are coupled to receive and store operand information and the above mentioned indication. In addition, the reservation stations are configured to update the stored operand information with a tag of the above mentioned first instruction, in response to detecting the indication of a dependency.
Further, a method is contemplated. A plurality of instructions are concurrently decoded and operand request information is obtained from the decoded instructions. A dependency of a second instruction of the plurality of instructions on a first instruction of the plurality of instructions is detected, where the second instruction is subsequent to the first instruction in program order. Operand information corresponding to instructions prior to the plurality of instructions is stored for the second instruction in a reservation station. The stored operand information is updated with a tag of the first instruction in response to detecting the above dependency.
Still further contemplated is a microprocessor comprising a reorder buffer and a reservation station. The reorder buffer is coupled to concurrently receive an indication of a first instruction and a second instruction which is subsequent to the first instruction in program order. The reorder buffer is configured to output operand information for the second instruction in response to dependency checking the second instruction against instructions prior in program order to the first instruction. In addition, the reorder buffer is configured to output a dependency indication responsive to detecting a dependency of the second instruction on the first instruction. The re
Coleman Eric
Merkel Lawrence J.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
LandOfFree
Resolving dependencies among concurrently dispatched... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Resolving dependencies among concurrently dispatched..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resolving dependencies among concurrently dispatched... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3042584