Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Commitment control or register bypass
Reexamination Certificate
2000-08-02
2002-06-25
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Commitment control or register bypass
C712S217000
Reexamination Certificate
active
06412064
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of superscalar processors, and more particularly, to a system and method for retiring multiple instructions executed out-of-order in a superscalar processor.
2. Discussion of Related Art
One method of increasing performance of microprocessor-based systems is overlapping the steps of different instructions using a technique called pipelining. In pipelining operations, various steps of instruction execution (e.g. fetch, decode and execute) are performed by independent units called pipeline stages. The steps are performed in parallel in the various pipeline stages so that the processor can handle more than one instruction at a time.
As a result of pipelining, processor-based systems are typically able to execute more than one instruction per clock cycle. This practice allows the rate of instruction execution to exceed the clock rate. Processors that issue, or initiate execution of, multiple independent instructions per clock cycle are known as superscalar processors. A superscalar processor reduces the average number of cycles per instruction beyond what is possible in ordinary pipelining systems.
In a superscalar system, the hardware can execute a small number of independent instructions in a single clock cycle. Multiple instructions can be executed in a single cycle as long as there are no data dependencies, procedural dependencies, or resource conflicts. When such dependencies or conflicts exist, only the first instruction in a sequence can be executed. As a result, a plurality of functional units in a superscalar architecture can not be fully utilized.
To better utilize a superscalar architecture, processor designers have enhanced processor look-ahead capabilities; that is the ability of the processor to examine instructions beyond the current point of execution in an attempt to find independent instructions for immediate execution. For example, if an instruction dependency or resource conflict inhibits instruction execution, a processor with look-ahead capabilities can look beyond the present instruction, locate an independent instruction, and execute it.
As a result, more efficient processors, when executing instructions, put less emphasis on the order in which instructions are fetched and more emphasis on the order in which they are executed. As a further result, instructions are executed out of order.
For a more in-depth discussion of superscalar processors, see Johnson,
Superscalar Microprocessor Design
, Prentice Hall, Inc. (1991).
Scenarios occur whereby the execution of the instructions is interrupted or altered, and the execution must be restarted in the correct order. Two such scenarios will be described.
In a first scenario, during look-ahead operations, many processor designs employ predictive techniques to predict a branch that the program is going to follow in that particular execution. In these systems, the instructions fetched and executed as a result of look-ahead operations are instructions from the branch of code that was predicted. High instruction throughput is achieved by fetching and issuing instructions under the assumption that branches chosen are predicted correctly and that exceptions do not occur. This technique, known as speculative execution, allows instruction execution to proceed without waiting for the completion of previous instructions. In other words, execution of the branch target instruction stream begins before it is determined whether the conditional branch will be taken.
Since the branch predication occasionally fails, the processor must provide recovery mechanisms for canceling the effects of instructions that were speculatively executed. The processor must also provide restart mechanisms to reestablish the correct instruction sequence.
In a second scenario, out-of-order completion makes it difficult to deal with exceptions. Exceptions are created by instructions when the instruction cannot be properly executed by hardware alone. These exceptions are commonly handled by interrupts, permitting a software routine to correct the situation. Once the routine is completed, the execution of the interrupted program must be restarted so it can continue as before the exception.
Processors contains information that must be saved for a program to be suspended and then restored for execution to continue. This information is known as the ‘state’ of the processor. The state information typically includes a program counter (PC), an interrupt address register (LAR), and a program status register (PSR); the PSR contains status flags such as interrupt enable, condition codes, and so forth.
As program instructions are executed, the state machine is updated based on the instructions. When execution is halted and must later be restarted (i.e., one of the two above scenarios occurs) the processor looks to the state machine for information on how to restart execution. In superscalar processors, recovery and restart occur frequently and must be accomplished rapidly.
In some conventional systems, when instructions are executed out of order, the state of the machine is updated out of order (i.e., in the same order as the instructions were executed). Consequently, when the processor goes back to restart the execution, the state of the machine has to be ‘undone’ to put it back in a condition such that execution may begin again.
To understand conventional systems, it is helpful to understand some common terminology. An in-order state is made up of the most recent instruction result assignments resulting from a continuous sequence of executed instructions. Assignments made by instructions completed out-of-order where previous instruction(s) have not been completed, are not included in this state.
If an instruction is completed and all previous instructions have also been completed, the instruction's results can be stored in the in-order state. When instructions are stored in the in-order state, the machine never has to access results from previous instructions and the instruction is considered ‘retired.’
A look-ahead state is made up of all future assignments, completed and uncompleted, beginning with the first uncompleted instruction. Since there are completed and uncompleted instructions, the look-ahead state contains actual as well as pending register values.
Finally, an architectural state is made up of the most recently completed assignment of the continuous string of completed instructions and all pending assignments to each register. Subsequent instructions executed out of order must access the architectural state to determine what state the register would be in had the instruction been executed in order.
One method used in conventional systems to recover from misdirected branches and exceptions is known as checkpoint repair. In checkpoint repair, the processor provides a set of logical spaces, only one of which is used for current execution. The other logical spaces contain backup copies of the in-order state, each corresponding to a previous point in execution. During execution, a checkpoint is made by copying the current architectural state to a backup space. At this time, the oldest backup state is discarded. The checkpoint is updated as instructions are executed until an in-order state is reached. If an exception occurs, all previous instructions are allowed to execute, thus bringing the checkpoint to the in-order state.
To minimize the amount of required overhead, checkpoints are not made at every instruction. When an exception occurs, restarting is accomplished by loading the contents of the checkpointed state preceding the point of exception, and then executing the instructions in order up to the point of exception. For branch misprediction recovery, checkpoints are made at every branch and contain the precise state at which to restart execution immediately.
The disadvantage of checkpoint repair is that it requires a tremendous amount of storage for the logical spaces. This storage overhead requires additional chip real estate which is a
Deosaran Trevor
Garg Sanjiv
Wang Johannes
Ellis Richard L.
Seiko Epson Corporation
Sterne Kessler Goldstein & Fox P.L.L.C.
LandOfFree
System and method for retiring approximately simultaneously... 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 retiring approximately simultaneously..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for retiring approximately simultaneously... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2939383