Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
2000-01-24
2002-08-20
Donaghue, Larry D. (Department: 2154)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C712S217000, C712S218000, C712S219000
Reexamination Certificate
active
06438681
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 processing instructions of a computer program and for comparing register identifiers associated with the instructions to detect data hazards between the instructions.
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 minimizing the circuitry and complexity required to detect 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 system and method for processing instructions of a computer program and for detecting data hazards between the instructions.
In architecture, the system of the present invention utilizes at least one pipeline, a first decoder, a second decoder, and comparison logic. The pipeline receives and simultaneously processes instructions of a computer program. The first and second decoders are coupled to the pipeline and decode register identifiers associated with instructions being processed by the pipeline. The comparison logic is interfaced with the first and second decoders and respectively compares the decoded register identifiers produced by the first and second decoders to other decoded register identifiers.
In accordance with another feature of the present invention, each decoded register identifier includes a plurality of bits that respectively correspond to a plurality of registers. To identify a particular register, the bit corresponding with the particular register is asserted, and a remainder of the bits is deasserted. Therefore, the comparison logic may determine whether a data dependency hazard exists between two instructions by determining whether decoded register identifiers associated with the two instructions match.
The present invention can also be viewed as providing a method for processing instructions of a computer program. The method can be broadly conceptualized by the following steps: transmitting an instruction to a pipeline of a processing system; decoding an encoded register identifier associated with the instruction while the instruction is being processed by a first portion of the pipeline; decoding the encoded register identifier while the instruction is being processed by a second portion of the pipeline; producing a first decoded register identifier based on the step of decoding the encoded register identifier while the instruction is being processed by the first portion of the pipeline; producing a second decoded register identifier based on the step of decoding the encoded register identifier while the instruction is being processed by the second portion of the pipeline; comparing the first and second decoded register identifiers to other decoded register identifiers; and detecting a data dependency 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: 4626669 (1986-12-01), Davis et al.
patent: 5150068 (1992-09-01), Kawashima et al.
patent: 5471598 (1995-11-01), Quattromani et al.
patent: 5737629 (1998-04-01), Zuraski, Jr. et al.
patent: 5765035 (1998-06-01), Tran
patent: 5848287 (1998-12-01), Tran et al.
patent: 5859999 (1999-01-01), Morris et al.
patent: 5860017 (1999-01-01), Sharangpani et al.
patent: 6115808 (2000-09-01), Arora
patent: 6202119 (2001-03-01), Manning
patent: 6219781 (2001-04-01), Arora
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 Architecture: A Quantitative Approach,” Morgan Kaufmann Publishers, Inc., 2ed, pp. 150-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
Donaghue Larry D.
El-Hady Nabil
Hewlett--Packard Company
LandOfFree
Detection of data hazards between instructions by decoding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Detection of data hazards between instructions by decoding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detection of data hazards between instructions by decoding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2889602