Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
1998-10-30
2003-04-15
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Reexamination Certificate
active
06550001
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to the detection of matching character pairs in arbitrarily long strings, and more specifically, to detecting ordering dependencies for instructions in the same and in different issue groups within computer systems.
2. Description of the Related Art
Processors and computers execute sequenced instructions. Frequently, the instructions of the sequence exhibit ordering dependencies commonly referred to as write-after-write and read-after-write dependencies. Write-after-write (WAW) and read-after-write (RAW) dependency occurs when a first instruction writes to an address and a later instruction performs a respective write or read at the same address. If the execution order of a WAW or a RAW instruction pair changes, the results produced by the execution of the instruction pair may change.
As used herein, “destination addresses” are data storage addresses to which an instruction writes data, and “source addresses” are data storage addresses from which instructions read data. Together the destination and source addresses form the operand addresses or arguments of the instructions that write and/or read these addresses.
The presence of instruction ordering dependencies in certain subsequences of instructions can lead to undesirable consequences such as undefined behaviors and/or hardware damage. For example, the presence of a WAW instruction pair in a group of instructions for parallel execution can lead to undefined behaviors because either instruction of the pair may perform the last write to a data storage address. Since the last write determines the data stored at the data storage address, the absence of certainty as to which instruction will write last can lead to a loss of certainty as to what data is stored therein. The presence of a WAW instruction pair in a group of instructions for parallel execution can also lead to hardware damage, because the two instructions of the pair may write simultaneously. If the two instructions attempt to simultaneously write different logic signals to the same data storage address, a short circuit may occur causing hardware damage. Similar undesirable consequences may follow from the presence of a RAW instruction pair in a group of instructions for parallel execution. A processor may have hardware for detecting and alerting the presence of undesirable ordering dependencies.
The subsequences of instructions in which hardware design makes ordering dependencies undesirable are referred to as instruction groups. Compilers and other software may schedule instructions with ordering dependencies in hardware defined instruction groups. Thus, the detection of software generated WAW and RAW ordering dependencies may be important if such dependencies are to be avoided in instruction groups. The detection of such ordering dependencies may be useful in redesigning software.
In processors executing many instructions in parallel, the number of instructions for undesirable ordering dependencies requiring checking ordinarily increases. Furthermore, the number of registers to check for undesirable instruction dependencies frequently grows faster than the number of instructions in an instruction group. Thus, in processors that execute several instructions in parallel, the detection of ordering dependencies in an instruction group may involve a significant amount of hardware, i.e., a large area of a chips surface. In such processors, verifying the absence of undesirable dependencies may be both costly and time limiting.
The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.
SUMMARY OF THE INVENTION
In a first aspect of the present invention, an apparatus is provided for detecting instruction ordering dependencies. The apparatus includes a plurality of address comparators including a first input adapted to receive a first operand address from one of a plurality of instructions; a second input adapted to receive a second operand address from a second one of a plurality of instructions; an output to transmit a logic signal responsive to a match between the first and second operand addresses; wherein the address comparators receive the first operand address from a respective, different ones of the plurality of instructions; and a hardware structure to receive the match indications from the address comparators and to indicate a dependency responsive to the match indications from a first one and a second one of the address comparators.
In a second aspect, a method is provided for detecting instruction dependencies. The method includes receiving first and second pluralities of operand addresses that correspond to first and second pluralities of operands of instructions, and selecting ones of the first and second pluralities of operands. The ones of the first and second pluralities of operands have associated respective first and second operand addresses. The one of the first plurality of operands is a destination operand of a first instruction. The method also includes generating a logic signal for a dependency in response to the first and second operand addresses matching and the ones of the first and second pluralities of operands being operands from different instructions.
REFERENCES:
patent: 5497499 (1996-03-01), Garg et al.
patent: 5768555 (1998-06-01), Tran et al.
patent: 5850533 (1998-12-01), Panwar et al.
Corwin Michael P.
Morris Dale Calvin
LandOfFree
Method and implementation of statistical detection of read... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and implementation of statistical detection of read..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and implementation of statistical detection of read... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3055942