Electrical computers and digital processing systems: processing – Processing architecture
Reexamination Certificate
2000-01-24
2003-11-04
Wiley, David (Department: 2143)
Electrical computers and digital processing systems: processing
Processing architecture
C712S217000
Reexamination Certificate
active
06643762
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to data processing techniques and, in particular, to a processing system and method for efficiently indicating when data produced by execution of one instruction is available for use in executing other instructions so that data hazards associated with the one instruction can be detected. The present invention is especially advantageous when the latency for producing the data of the one instruction is relatively long.
2. Related Art
To increase the performance of many processors, pipeline processing has been developed. In pipeline processing, a processor is equipped with at least one pipeline that can simultaneously process 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, thereby creating certain data hazards.
For example, a first instruction, when executed, may produce data and write the data to a particular register, and a second instruction, when executed, may utilize the data produced by the first instruction. If the second instruction executes before the data produced by the first instruction is available, then a data error occurs. Consequently, a data hazard exists between the two instructions until the data produced by the first instruction is available. This type of data hazard is commonly referred to as a “read-after-write” (RAW) data hazard.
In another situation, the second instruction, when executed, may write data to the same register as the first instruction, which commenced execution before the second instruction. If the second instruction produces and writes its data to the register before the first instruction, then a data error is possible, since the register will contain the data of the first instruction instead of the second instruction after both instructions are fully executed and processed. As a result, a data hazard exists between the two instructions until the data produced by the first instruction is written to the register. This type of data hazard is commonly referred to as a “write-after-write” (WAW) data hazard.
To help prevent errors from the aforementioned data hazards and other types of data hazards, most superscalar processors include hazard detection circuitry that detects data hazards associated with the instructions being processed by the pipelines of the processor. The hazard detection circuitry usually detects the aforementioned data hazards by detecting when a later instruction utilizes (e.g., writes to or reads from) the same register as an earlier instruction that has yet to produce available data.
However, the data produced by a first instruction may not be available for use by other instructions or for writing to a particular register of a processor until well after the first instruction has been retired by the pipeline processing the first instruction (e.g., until well after the first instruction has exited the pipeline). For example, a load instruction, when executed, may generate a request to retrieve data from memory external to the processor. Depending on where the data is located in the memory hierarchy, it may take anywhere between a few clock cycles to several thousand clock cycles for the data to be returned to the processor in response to the aforementioned request. Therefore, the processor may not receive the data produced by the first instruction until after the first instruction exits the processor's pipelines or is otherwise retired. In other words, the data produced by the first instruction does not become available for use in executing other instructions until after the first instruction exits the processor's pipeline or is otherwise retired. An instruction, such as the aforementioned load instruction, that produces available data after the instruction has been retired by a pipeline shall be referred to herein as a “long latency instruction.” To facilitate the process of detecting data hazards for long latency instructions, the processor is usually equipped with a register file, commonly referred to as a “scoreboard,” that indicates when the processor has yet to receive data produced in response to a previous execution of a producer (i.e., an instruction that produces data). In other words, the scoreboard indicates when there is a pending write to a general register. As used herein, the term “pending write” shall be used to refer to a situation in which data produced by an earlier executed instruction is destined for a general register but has yet to be written to the general register. As known in the art, a “general register” is one of a set of registers that are either written to via the execution of write instructions and/or are read from via the execution of read instructions.
The scoreboard includes a plurality of registers in which each register contains a bit value. Each scoreboard register and the bit value contained therein correspond to one of the general registers of the processor that receives data produced by the execution of write instructions. When a write instruction is retired before the data produced by the write instruction has been written to the general register that is to receive the data, the bit value in the scoreboard register that corresponds to the general register is asserted. Furthermore, when the data produced by the write instruction is finally written to the general register, the aforementioned bit value is deasserted. Therefore, to determine whether there is a pending write to one of the general registers, the bit value in the scoreboard register corresponding to the one general register can be analyzed.
Each asserted bit value in the scoreboard indicates that there is a pending write to the general register corresponding to the asserted bit value. Therefore, any instruction being processed by the processor should be prevented from writing to or reading from the foregoing general register to prevent errors from RAW or WAW data hazards, until at least the pending write expires (i.e., until the data destined for the general register is actually written to the general register). Furthermore, each deasserted bit value in the scoreboard indicates there is presently no pending write to the general register corresponding to the deasserted bit value. Therefore, an instruction being processed by the processor may read from or write to the foregoing general register without creating any errors from RAW or WAW data hazards.
When a RAW or WAW data hazard is detected by analyzing the scoreboard or otherwise, errors from the RAW or WAW data hazard are often prevented by stalling one or more instructions being processed by the processor. U.S. Patent Application entitled “Superscalar Processing System and Method for Efficiently Performing In Order Processing of Instructions,” assigned Ser. No. 09/390,199, and filed on Sep. 7, 1999, which is incorporated herein by reference, describes in more detail a process of stalling instructions to prevent data hazards. When an instruction is stalled, the processor temporarily refrains from further processing the instruction until the data hazard causing the stall expires.
Unfortunately, the wiring and other circuitry typically used to write to and read from the scoreboard is relatively complex and often utilizes a relatively large amount of surface area within a processor. To minimize the cost of the processor, it is desirable for the circuitry required to detect data hazards to be minimized. In particular, it is desirable to minimize and simplify the circuitry required to write to and read from the scoreboard.
Thus, a heretofore unaddressed need exists in the industry for providing a efficient system and method of utilizing a scoreboard to detect data hazards.
SUMMARY OF THE INVENTION
The present invention overcomes the inadequacies and deficiencies of the prior art as discussed hereinbefore. Generally, the present invention provides a system and method for executing instructions of a computer program and for efficiently indic
Arnold Ronny Lee
Soltis Jr. Donald Charles
Collins Scott M.
Hewlett--Packard Development Company, L.P.
Wiley David
LandOfFree
Processing system and method utilizing a scoreboard to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Processing system and method utilizing a scoreboard to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing system and method utilizing a scoreboard to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3130447