Electrical computers and digital processing systems: processing – Processing architecture – Superscalar
Reexamination Certificate
1999-11-12
2001-05-08
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Superscalar
C712S041000, C712S206000, C712S219000, C712S245000
Reexamination Certificate
active
06230254
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the design of a superscalar microprocessor and, more particularly, to a system and method for handling load and store operations in a microprocessor that executes instructions out-of-order.
2. Discussion of Related Art
A major consideration in a superscalar Reduced Instruction Set Computer (RISC) processor is how to execute multiple instructions in parallel and out-of-order, without incurring data errors due to dependencies inherent in such execution. The simplest instruction issue policy for RISC processors, is to issue instructions in exact program order (in-order issue) and to write the results in the same order (in-order completion).
Out-of-order completion is more complex than in-order completion, and improves performance of superscalar processors for the same types of operations. For instance, out-of-order completion is used to improve performance of long-latency operations such as loads or floating point operations. Any number of instructions are allowed to be in execution in the functional units, up to the total number of pipeline stages in all functional units. Instructions may complete out of order, because instruction issuing is not stalled when a functional unit takes more than one cycle to compute a result. Consequently, a functional unit may complete an instruction after subsequent instructions already have completed.
Consider the following code sequence where “op” is an operation, “Rn” represents a numbered register, and “:=” represents assignment:
R
3
:=R
3
op R
5
(1)
R
4
:=R
3
+1 (2)
R
3
:=R
5
+1 (3)
R
7
:=R
3
op R
4
(4)
Here, the assignment of the first instruction cannot be completed after the assignment of the third instruction, even though instructions may in general complete out of order. Completing the first and third instructions out of order would leave an odd, incorrect value in register R
3
, possibly causing, for example, the fourth instruction to receive an incorrect operand value. The result of the third instruction has an “output dependency” on the first instruction and the third instruction must complete after the first instruction to produce the correct output values of this code sequence. Thus, issuing of the third instruction must be stalled if its result might later be overwritten by an older instruction which takes longer to compute.
Out-of-order completion yields higher performance, but requires more hardware, namely data dependency logic. Data dependency logic is more complex with out-of-order completion, because this logic checks data dependencies between decoded instructions and all instructions in all pipeline stages. Hardware must also ensure that the results are written in the correct order. In contrast, with in-order completion the dependency logic checks data dependencies between decoded instructions and the few instructions in execution, and results are naturally written in the correct order. Out-of-order completion also creates a need for functional units to arbitrate for result busses and register-file write ports, because there probably are not enough of these to satisfy all instructions that can complete simultaneously.
Moreover, out-of-order completion makes it more difficult to deal with instruction exceptions. An instruction creates an exception when under a given condition, the instruction cannot be properly executed by hardware alone.
In-order issue processors stop decoding instructions whenever a decoded instruction creates a resource conflict or has a true dependency or an output dependency on an uncompleted instruction. The processor is thus not able to look ahead beyond the instructions with the conflict or dependency, even though one or more subsequent instructions might be executable. A conventional solution is to isolate the decoder from the execution stage, so that it continues to decode instructions regardless of whether they could be executed immediately. This isolation is accomplished by providing a buffer (called an “instruction-window”) between the decode and instruction stages.
For look-ahead, the processor decodes instructions and places them into the instruction window as long as there is room in the window, and, at the same time, examines instructions in the window to find instructions that may be executed (i.e., instructions that do not have resource conflicts or dependencies). The instruction window provides a pool of instructions, thus giving the processor a look-ahead ability that is limited by the size of the window and the capability of the processor's Instruction Fetch Unit (IFU). This permits issuing of instructions out of order because instructions may be issued from the window with little regard for their original program order. The only constraints on the instruction issuer are those required to ensure that the program behaves correctly.
The issue constraints on any particular instruction are mostly the same as with in-order issue: an instruction is issued when it is free of resource conflicts and dependencies. Out-of-order issue gives the processor a larger set of instructions available for issue, improving its chances of finding instructions to execute concurrently. However, the capability to issue instructions out of order introduces an additional issue constraint, much as the capability to complete instructions out of order introduced the constraint of output dependencies.
To understand this, again consider the above example code sequence. The assignment of the third instruction cannot be completed until the second instruction begins execution. Otherwise, the third instruction might incorrectly overwrite the first operand of the second instruction. The result of the third instruction is said to have an “anti-dependency” on the first input operand of the second instruction. The term anti-dependency refers to the fact that the constraint is similar to that of true dependencies, except reversed. Instead of the first instruction producing a value that the second uses, the second instruction produces a value that destroys a value that the first one uses. To prevent this, the processor must not issue the third instruction until after the second one begins. Because the second instruction depends on the first, the third instruction also must wait for the first to complete, even though the third instruction is otherwise independent.
Anti-dependencies are mainly of concern when instructions can issue out of order. An input operand of a stalled instruction can be destroyed by a subsequent instruction during normal operation. However, in scalar processors, instruction exceptions are sometimes handled by correcting the exceptional condition, then retrying the problematic instruction. If this instruction completed out of order, it is possible that, when it is retried, its input operands have been overwritten by subsequent instructions. This problem cannot occur in a processor that supports precise interrupts. The solution may require that the processor maintain copies of instruction operands to allow restart.
Two typical operations performed by program instructions are load and store operations. Generally, load and store operations read and modify memory locations, respectively. As with other program instructions, loads and stores can be executed out of order. Even though loads and stores can be decoded at the same time, only one load or store is conventionally issued per cycle. A load is typically given priority over a store to use the data-cache, because the load is likely to produce a value that the processor needs to proceed with computation. If a store conflicts with a load for the data-cache, the store is typically held in a store buffer until the store can be performed. Furthermore, a store is conventionally performed in program-sequential order with respect to other stores, and is performed only after all previous instructions, including loads, have completed. This preserves the processor's in-order state in the data-cache, because cache
Senter Cheryl D.
Wang Johannes
Pan Daniel H.
Seiko Epson Corporation
Sterne Kessler Goldstein & Fox P.L.L.C.
LandOfFree
System and method for handling load and/or store operators... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for handling load and/or store operators..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for handling load and/or store operators... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2453766