Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
2002-10-28
2004-04-27
Coleman, Eric (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C712S218000
Reexamination Certificate
active
06728868
ABSTRACT:
BACKGROUND OF THE INVENTION
1. 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.
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, 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. The plurality of pipelines are configured to process instructions of a computer program, and the coalescing circuitry is configured to receive, from the pipelines, a plurality of register identifiers identifying a plurality of registers. The coalescing circuitry is configured to coalesce said register identifiers thereby generating a coalesced register identifier identifying each of said plurality of registers. The hazard detection circuitry is configured to receive the coalesced register identifier and to perform a comparison of the coalesced register identifier with other information received from the pipelines. The hazard detection circuitry is further configured to detect a data hazard based on the comparison.
The present invention can also be viewed as providing a method that can be broadly conceptualized by the following steps: simultaneously processing, via a plurality of pipelines, instructions of a computer program; receiving a plurality of register identifiers associated with the instructions, the register identifiers identifying a plurality of registers; coalescing the register identifiers thereby generating a coalesced register identifier identifying each of the plurality of registers; comparing the coalesced register identifier to another register identifier identifying at least one register; 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: 860017 (1907-07-01), Sharangpani et al.
patent: 5006980 (1991-04-01), Sanders et al.
patent: 5155817 (1992-10-01), Kishigami et al.
patent: 5276683 (1994-01-01), Ohkubo
patent: 5778248 (1998-07-01), Leung
patent: 5859999 (1999-01-01), Morris et al.
patent: 5933651 (1999-08-01), Masuda et al.
patent: 6219781 (2001-04-01), Arora
patent: 6304955 (2001-10-01), Arora
patent: 6374323 (2002-04-01), Stracousky et al.
patent: 6401195 (2002-06-01), Arora et al.
patent: 6430642 (2002-08-01), Stracousky 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 Kaugmann 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 Development Company, L.P.
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-3227436