Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Reducing an impact of a stall or pipeline bubble
Reexamination Certificate
1999-09-07
2003-09-09
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Reducing an impact of a stall or pipeline bubble
C712S215000
Reexamination Certificate
active
06618802
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to computer processing techniques and, in particular, to a superscalar processing system and method that executes instructions in an in-order fashion and that independently stalls processing of the instructions, when necessary.
2. Related Art
In most early computer processors, a pending instruction of a computer program was fully executed, and the results of the execution were written to a register or a location in memory before commencing execution of the next instruction of the program. The execution of the instructions occurred one at a time, and, therefore, errors from data dependency hazards could be easily prevented.
As used herein, a “data dependency” refers to a situation where a first instruction during execution generates or retrieves data that is needed for the execution of a second instruction. In such a situation, a data dependency is said to exist between the two instructions, and the timing of the execution of the instructions must be controlled such that the needed data produced by execution of the first instruction is available during execution of the second instruction. If steps are not taken to ensure that the first instruction will always execute before the second instruction, then a data dependency hazard exists. A “data dependency hazard” refers to a situation in which an error is possible because an instruction dependent on data from another instruction may execute before the other instruction and, therefore, may utilize incorrect data during execution.
When a processor executes instructions of a computer program one at a time, as described above, preventing errors from data dependency hazards is relatively simple. In this regard, as long as each instruction dependent on data from another instruction is input into the processor after the other instruction, errors caused by data dependency hazards should not occur.
However, to increase the performance of many processors, pipeline processing was developed. In pipeline processing, a single pipeline simulataneously processes multiple instructions. Therefore, execution of one instruction in the pipeline may be commenced before the results of execution of a preceding instruction in the pipeline are available. Consequently, with pipeline processing, errors from data dependency hazards are possible.
Most pipeline processors utilize a control mechanism to prevent errors from data dependency hazards. The control mechanism detects data dependencies that exist between instructions input into the processor. During the execution of each instruction, the control mechanism determines whether the instruction being executed (referred to hereafter as the “pending instruction”) requires data produced by the execution of another instruction. If so, the control mechanism then determines whether the other instruction has been executed, at least to the point where the needed data is available. If this data is not yet available, the control mechanism stalls (i.e., temporarily stops) execution of the pending instruction until the necessary data becomes available.
Stalling of the pending instruction is usually accomplished by asserting a stall signal transmitted to the pipeline executing the pending instruction. In response to the stall signal, the pipeline is designed to stop execution of the pending instruction until the stall signal is deasserted by the control mechanism. Once the necessary data becomes available, the control mechanism deasserts the stall signal, and in response, the pipeline resumes execution of the pending instruction.
To further reduce the amount of time required to process instructions, parallel processing, sometimes known as superscalar processing, was developed. In parallel processing, a plurality of pipelines are defined that simultaneously execute instructions. One type of parallel processing is out-of-order processing. In out-of-order processing, each pipeline of a processor simultaneously executes different instructions independently of the other pipeline(s).
It typically takes different amounts of time for different instructions to execute, and it is, therefore, possible for an instruction of one pipeline to be fully executed before another instruction of another pipeline, even though the other instruction was input into its respective pipeline first. Accordingly, instructions are not necessarily executed in the same order that they were input into the pipelines, and as a result, the control mechanism required to avoid errors from data dependency hazards is relatively complex in out-of-order processors. Furthermore, as the number of pipelines is increased, the complexity of the control mechanism increases dramatically. Consequently, many conventional parallel processors, particularly processors having a large number of pipelines, employ an in-order type of processing in lieu of the out-of-order type of processing described above.
During in-order processing, the instructions being processed by the different pipelines are stepped through the stages of the pipelines on certain edges of a system clock signal. In this regard, the processing of instructions in a pipeline is usually divided into stages, and each stage of the pipeline simultaneously processes a different instruction.
As an example, the processing performed by each pipeline may be divided into a register stage, an execution stage, a detect exceptions stage, and a write stage. During the register stage, any operands necessary for the execution of an instruction are obtained. Once the operands have been obtained, the processing of the instruction enters into the execution stage in which the instruction is executed. After the instruction has been executed, the processing of the instruction enters into a detect exceptions stage in which conditions, such as overruns during execution, for example, that may indicate data unreliability are checked. After the detect exceptions stage is completed, a write stage is entered in which the results of the execution stage are written to a register or a location in memory.
A key feature of in-order processing is that each instruction of an issue group steps through each stage at the same time. An “issue group,” as defined herein, is a set of instructions simultaneously (i.e., during the same clock cycle) processed by the same stage of different pipelines within a single processor. As an example, assume that each stage of each pipeline processes one instruction at a time, as is typically done in the art. The instructions in the detect exceptions stage of the pipelines form a first issue group, and the instructions in the execution stage of the pipelines form a second issue group. Furthermore, the instructions in the register stage of the pipelines form a third issue group. Each of the issue groups advances into the next respective stage in response to an active edge of the system clock signal. In other words, the first issue group steps into the write stage, the second issue group steps into the detect exceptions stage, and the third issue group steps into the execution stage in response to an active edge of the system clock signal.
As used herein, an “active edge” is any edge of the system clock signal, the occurrence of which induces each unstalled instruction in a pipeline to advance to the next stage of processing in the pipeline. For example, assume that a processor is designed to step each unstalled instruction into the next stage of processing every three clock cycles. In this example, the active edges could be defined as every third rising edge of the clock signal. It should be noted that which edges of the clock signal are designated as “active edges” is based on design parameters and may vary from processor to processor.
During in-order processing, each instruction in one issue group is prevented from passing another instruction in another issue group. In other words, instructions of one issue group input into the pipelines after the instructions of another issue group are prevented from entering into the sa
Arnold Ronny Lee
Soltis Jr. Donald Charles
Ellis Richard L.
Hewlett-Packard Company, L.P.
LandOfFree
Superscalar processing system and method for selectively... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Superscalar processing system and method for selectively..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Superscalar processing system and method for selectively... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3026671