Electrical computers and digital processing systems: processing – Instruction issuing – Simultaneous issuance of multiple instructions
Reexamination Certificate
1999-02-18
2001-02-27
Donaghue, Larry D. (Department: 2783)
Electrical computers and digital processing systems: processing
Instruction issuing
Simultaneous issuance of multiple instructions
C712S023000, C712S239000
Reexamination Certificate
active
06195744
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to digital processor systems, and in particular to methods and circuits for controlling the order of execution of operations to maximize processor performance.
2. Description of Related Art
A typical computer program is a list of instructions which when compiled or assembled generates a sequence of machine instructions or operations which a processor executes. The operations have a program order defined by the logic of the computer program and are generally intended for sequential execution in the program order. Scalar processors execute the operations in the program order which limits a scalar processor to completing one operation before completing the next operation. Superscalar processors contain a variety of execution units which operate in parallel to execute and complete multiple operation in parallel. Superscalar processors can therefore be faster than scalar processors operating at the same clock speed because superscalar processors can complete multiple operation per clock cycle while scalar processors ideally complete one operation per cycle.
A superscalar processor typically schedule execution of operations so that operations can be executed in parallel and complete out of the normal program order. Difficulties in out-of-order execution arise because one operation may depend on another in that the logic of a computer program requires that the first operation in the program be executed before the second operation. For example, whether an operation should be executed at all often depends on the result of a branch operation. Processors often predict the result of a branch operation before evaluating the branch operation and proceed with executing operations based on the prediction. The execution must be speculative because the branch prediction may have been incorrect so that the wrong operations were executed. Additionally, many computers require that a system's state be known just before or after an operation generates an error, interrupt, or trap; but when operations are executed out of order, an operation which follows an error in a program may have been executed before the error occurred. Thus, the processor must be able to undo operations which should not have been executed and must be able to construct the system's state following an error.
Superscalar architectures attempt to achieve several somewhat conflicting goals for scheduling operations. One goal is efficient scheduling to maximize parallel execution of operations which are actually required for completion of the program. Another goal is that scheduling circuitry not be overly complex because complexity increases the difficulty in providing a robust error free design and increases circuit size and cost. Still another goal is rapid scheduling so that a processor can operate at a high clock rate. Scheduling circuits which accomplish these goals are desired.
SUMMARY OF THE INVENTION
In accordance with the invention, an out-of-order execution engine includes a set of execution units capable of operating in parallel and a scheduler which dispatches operations to the execution units. The scheduler contains entries corresponding to operations to be executed. Each entry includes storage for information required for execution of the associated operation and logic for directing the information to the correct execution unit when required. Operations are dispatched first according to type and availability of an execution unit for the type of operation and second according to the sequential program order. Accordingly, operations of different types are often executed out of the normal program order. Operations of the same type can also be executed out-of-order because more than one execution unit may be available for a type of operation, and one operation may be held up in one execution pipeline while another execution unit completes following operations of the same type. Additionally, operations which would block an execution pipeline can be bumped from early stages of the pipeline so that even operations for a single execution unit can be executed out of the program order.
The entries in the scheduler are not specialized according to operation type, and the execution units do not have specialized stations or queues which can be blocked if an execution unit is stalled. After execution of an abortable operation, the results of the operation is kept in the associated scheduler entry and/or in a store queue. The scheduler keeps a result until an operation commit unit coupled to the scheduler determines that no fault and no mispredicted branch precedes the associated operation. If the operation commit unit determines that the results of the oldest executed operations would be generated in a sequential execution of a program, the results are made permanent by writing to a register file, a status register, or memory, and the operation is retired and removed from the scheduler. If the operation commit unit determines that a result would not be generated in a sequential execution of the program, the operation is retired without making permanent changes.
In addition to scheduling functions, the scheduler also incorporates the functions of a re-order buffer with implied register renaming. Tags indicating the program order of operation results are not required because the physical positions of entries in the scheduler indicate the program order and result values stored in an entry provide the register and status values at the corresponding point in the program order. This removes the complexity required to maintain or transfer tag information between various separate execution stations. Actual register renaming during operation execution is not required because scan chains directed in the proper physical direction in the scheduler locate preceding operations which affect desired register operands for subsequent operations.
In one embodiment of the invention, the scheduler includes rows of entries associated with pending operations. Each entry corresponds to a single operation, and each row of entries corresponds to multiple operations, for example four operations. The organization of the scheduler into rows simplifies the scheduler structure, but scheduling and execution of operations is independent of the grouping of operations in rows. The scheduler in some ways operates as a shift register where information associated with a new group of operations is loaded into a top row of the scheduler and shifts down as a group toward the bottom row of the scheduler as older operations are retired. Accordingly, the position of an operation in the scheduler indicates its age. Newer operations (i.e., operations later in the program order) are at the top of the scheduler, and older operations (i.e., operations earlier in the program order) are at the bottom of the scheduler.
Most operations are immediately eligible for execution when loaded into the top row of the scheduler but may be issued to execution units from any point in the scheduler. A state field in an entry for an operation indicates whether the operation has been issued, is in a specific stage of an execution pipeline, or has been completed. The state of the operation is independent of the operation's position in the scheduler, but the longer an operation is in the scheduler, the greater the chance that the operation will be issued and completed. Operations in a row are retired simultaneously so that multiple operations can be completed each clock cycle. Accordingly, multiple operations can be loaded into the scheduler and multiple operations can be removed from the scheduler each clock cycle.
Some operations such as evaluations of conditional branches and register operations which depend on status flags are executed when the operations reach a particular row of the scheduler. This simplifies, reduces, and speeds up hardware in the scheduler by eliminating general hardware to support execution of these operations in other rows. Scheduling delays are minimized by selecting the row for ex
Ben-Meir Amos
Favor John G.
Stapleton Warren G.
Advanced Micro Devices , Inc.
Donaghue Larry D.
Miller David
Skjerven Morrill & MacPherson LLP
LandOfFree
Unified multi-function operation scheduler for out-of-order... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Unified multi-function operation scheduler for out-of-order..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unified multi-function operation scheduler for out-of-order... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2615577