Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
1999-10-14
2004-03-23
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C712S215000, C712S023000, C712S024000, C717S149000
Reexamination Certificate
active
06711670
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 detects data hazards within instruction groups of a computer program.
2. Related Art
Parallel processing, sometimes known as superscalar processing, has been developed to reduce the amount of time required to process instructions of a computer program. In parallel processing, at least two pipelines are defined that simultaneously execute instructions. One type of parallel processing is out-of-order processing, in which each pipeline of a processor simultaneously executes different instructions independently of the other pipeline(s).
In out-of-order processing, the instructions are not necessarily input into the pipelines in the same order that they were received by the processor. In addition, it typically takes different amounts of time for different instructions to execute, and it is, therefore, possible for an instruction to be fully executed before another instruction, even though the other instruction was input into its respective pipeline first. Accordingly, instructions are not necessarily executed in the same order that they are received by the pipelines within the processor, and as a result, the complexity of preventing errors from read-after-write data hazards and write-after-write data hazards, which will be described in more detail below, is relatively large for out-of-order processing.
A “read-after-write data dependency” exists when one instruction to be executed by a processor utilizes, during execution, data retrieved or produced from the execution of another instruction. If the one instruction executes before the other instruction executes, then an error may occur, since the one instruction may utilize incorrect data during execution. As a result, to prevent errors, steps should be taken to ensure that the instruction utilizing data retrieved or produced from the execution of another instruction does not execute until the necessary data from execution of the other instruction is available. If a read-after-write data dependency exists and if such steps are not taken, then a “read-after-write data hazard” exists, since the read-after-write data dependency may result in the utilization of incorrect data.
A “write-after-write data hazard” exists when an older instruction, during execution, may write data to the same register or other memory location written to by a younger instruction and incorrectly overwrite valid data written by the younger instruction. An instruction is “younger” than another instruction when it is received by a processor after the other instruction. Conversely, an instruction is “older” than another instruction when it is received by a processor before the other instruction.
As an example of a write-after-write data hazard, assume that a first instruction is a load instruction that retrieves data and writes the retrieved data to a particular register. It may take a relatively long time for the data to be retrieved, particularly if the data to be retrieved is not locally available. Therefore, it is possible for a second instruction (i.e., an instruction younger than the first instruction) to write data to the same register after the first instruction has executed but before the data retrieved by the first instruction is written to the register. In such a case, the data written to the register by the second instruction may be overwritten by the data retrieved by the first instruction. As a result, the register may contain incorrect data, and an error may result when a later instruction uses the data in the register.
To prevent errors from read-after-write data hazards and from write-after-write data hazards, most out-of-order parallel processors employ a control mechanism. In this regard, during the execution of each instruction, the control mechanism determines whether an instruction being processed (referred to hereafter as the “pending instruction”) requires data produced by the execution of an older instruction. If so, the control mechanism then determines whether the older instruction has been processed, 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) processing of the pending instruction until the necessary data becomes available, thereby preventing errors from read-after-write data hazards.
In addition, the control mechanism also determines whether data from (i.e., generated or retrieved by) an older instruction is to be written to the same register or memory location as the data from a pending instruction. If so, the control mechanism stalls the pending instruction until the data from the older instruction has been written to the register or memory address, thereby preventing errors from write-after-write data hazards. Consequently, the control mechanism may stall the pending instruction in order to prevent errors from either read-after-write data hazards or from write-after-write data hazards.
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 asserted 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 read-after-write data hazard or the write-after-write data hazard no longer exists, the control mechanism deasserts the stall signal, and in response, the pipeline resumes processing of the pending instruction. The control mechanism required to detect and prevent potential errors from read-after-write data hazards and from write-after-write data hazards is relatively complex in out-of-order processors, and as the number of pipelines is increased, the complexity of the control mechanism increases dramatically.
As a result, 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. In 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.
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. In the absence of a stall, each of the issue groups advances into the next respective stage in respons
Arnold Ronny Lee
Soltis Jr. Donald Charles
Ellis Richard L.
Hewlett--Packard Development Company, L.P.
Meonske Tonia L.
LandOfFree
System and method for detecting data hazards within an... 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 detecting data hazards within an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for detecting data hazards within an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3221736