Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
2000-01-28
2002-12-03
Coleman, Eric (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C712S218000
Reexamination Certificate
active
06490674
ABSTRACT:
BACKGROUND OF THE INVENTION
Field of the Invention
The present invention generally relates to data processing techniques and, in particular, to a system and method for producing data indicative of data hazards between instructions of a computer program and for coalescing the data to minimize the circuitry and complexity required to detect the data hazards.
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, and as a result, errors from data dependency hazards are possible.
A data dependency exists when one instruction to be executed by a pipeline utilizes data produced via execution of another instruction, and the data dependency creates a data dependency hazard when the data produced by the other instruction is not yet available for use by the one instruction. For example, a later instruction, when executed, may utilize data that is produced by execution of an earlier instruction (e.g., a later add instruction may utilize data that is retrieved by an earlier load instruction). If the later instruction executes before the data from execution of the earlier instruction is available, then the later instruction utilizes incorrect data, resulting in a data dependency error. Accordingly, a data dependency hazard exists between the two instructions, until the data utilized by the later instruction is available or until the data dependency error occurs.
Needless to say, it is important to detect data dependency hazards so that data dependency errors can be prevented. However, circuitry for detecting data dependency hazards is often complex and often utilizes a relatively large amount of area within a processor. This is especially true in superscalar processors, which include a plurality of pipelines that simultaneously execute instructions. In this regard, an instruction in one pipeline may not only have a dependency with another instruction in the same pipeline but may also have a dependency with another instruction in another pipeline. Therefore, to adequately check for data dependency hazards, a first instruction in one pipeline should be compared with each instruction in each pipeline that could share a data dependency hazard with the first instruction. Consequently, as the number of pipelines within a processor increases, the circuitry and complexity required to detect data dependencies that define data dependency hazards increase dramatically.
Thus, a heretofore unaddressed need exists in the industry for an efficient processing system with minimal complexity and circuitry for detecting data hazards between instructions of a computer program.
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 processing system and method for coalescing instruction data to efficiently detect data hazards between instructions of a computer program.
In architecture, the system of the present invention utilizes a plurality of pipelines, coalescing circuitry, and hazard detection circuitry. Each of the pipelines receives and processes instructions of a computer program, and the coalescing circuitry receives a plurality of register identifiers from the pipelines. Each of the register identifiers identifies one of a plurality of registers, and the coalescing circuitry combines the plurality of register identifiers into a single register identifier such that the single register identifier identifies each of the registers identified by the register identifiers received by the coalescing circuitry. The hazard detection circuitry then compares the single register identifier with other information received by the hazard detection circuitry to detect whether a particular type of data hazard exists. Due to the combining steps of the coalescing circuitry, the number of compares by the hazard detection circuitry required to detect data hazards can be reduced, and the circuitry and complexity of implementing the hazard detection circuitry can be reduced, as well.
In accordance with another feature of the present invention, decoders are coupled to the pipelines, and the coalescing circuitry is coupled to the pipelines via the decoders. Each of the decoders receives and decodes one of the register identifiers transmitted by one of the pipelines.
In accordance with another feature of the present invention, an attribute interface is coupled to one of the pipelines and receives attribute data. The attribute interface then controls, based on the attribute data, the value of at least one of the bits in one of the register identifiers transmitted by one of the pipelines. The present invention can also be viewed as providing a method for detecting data hazards in a computer system. The method can be broadly conceptualized by the following steps: processing instructions of a computer program; receiving a first register identifier associated with one of the instructions, the first register identifier having a plurality of bits corresponding respectively with a plurality of registers such that each of the registers respectively corresponds with at least one of the bits of the first register identifier; receiving a second register identifier associated with another of the instructions, the second register identifier having a plurality of bits corresponding respectively with the plurality of registers such that each of the registers respectively corresponds with at least one of the bits of the first register identifier; asserting, in the first register identifier, one of the bits corresponding with one of the registers to be identified by the first register identifier; deasserting each of the bits of the first register identifier corresponding with any of the registers other than the one register to be identified by the first register identifier; asserting, in the second register identifier, one of the bits corresponding with one of the registers to be identified by the second register identifier; deasserting each of the bits of the second register identifier corresponding with any of the registers other than the one register to be identified by the second register identifier; combining the first register identifier with the second register identifier; producing a third register identifier in response to the combining step, the third register identifier identifying the registers identified by the first and second register identifiers; comparing the third register identifier to another register identifier; and detecting a data hazard based on the comparing step.
Other features and advantages of the present invention will become apparent to one skilled in the art upon examination of the following detailed description, when read in conjunction with the accompanying drawings. It is intended that all such features and advantages be included herein within the scope of the present invention and protected by the claims.
REFERENCES:
patent: 5276683 (1994-01-01), Ohkubo
patent: 5859999 (1999-01-01), Morris et al.
patent: 5860017 (1999-01-01), Sharangpani et al.
patent: 6219781 (2001-04-01), Arora
patent: 6304955 (2001-10-01), Arora
patent: 6374323 (2002-04-01), Stracovsky et al.
patent: 6401195 (2002-06-01), Arora et al.
patent: 6430642 (2002-08-01), Stracovsky et al.
patent: 6438681 (2002-08-01), Arnold et al.
Alexander Wolfe, “Patents Shed Light on Merced: Techniques of Predication and Speculation Detailed,” Electronic Engineering Times, Feb. 15, 1999, pp. 43-44.
Patterson, et al., “Computer Architechture: A Quantitative Approach,” Morgan Kaufmann Publishers, Inc., 2ed, pp. 150-154 and 191-193.
Gary Lauterbach, “Sun's Next-Generation High-End SPARC Microprocessor,” Microprocessor Forum, Oct. 14-15, 1997, pp. 3-6.
Arnold Ronny Lee
Soltis Jr. Donald Charles
Coleman Eric
Hewlett--Packard Company
LandOfFree
System and method for coalescing data utilized to detect... 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 coalescing data utilized to detect..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for coalescing data utilized to detect... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2994905