|
|
|
|
|
|
|
S1 indicates an address of a source operand (usually a register), S2 is another source operand, and D is the address of the destination of the result. Of course, it is possible for S1 to be the same as D, as in the R/M architecture, or for any of S1, S2, or D to be memory addresses, but for our examples we assume that these are registers; the general principles are the same. |
|
|
|
|
|
|
|
|
With out-of-order execution, three types of dependencies are possible between two instructions Ii and Ij (i precedes j in execution sequence). The first, an essential dependency, arises when the destination of Ii is the same as the source of Ij: |
|
|
|
 |
|
|
|
|
Di = S1j or |
|
|
|
|
|
|
|
|
Di = S2j |
|
|
|
|
|
|
|
|
This is the dependency seen in chapter 4 examples as a data or address dependency. |
|
|
|
|
|
|
|
|
Another condition that causes a dependency occurs when the destination of instruction Ij is the same as the source of a preceding instruction Ii. This can be represented as: |
|
|
|
|
|
|
|
|
Dj = S1i or |
|
|
|
|
|
|
|
|
Dj = S2i. |
|
|
|
|
|
|
|
|
The second dependency arises when an instruction in sequence is delayed and a following instruction is allowed to precede in execution order and change the contents of one of the original instruction's source registers. Consider the following example (R3 is the destination): |
|
|
|
|
|
|
|
|
I1 DIV R3, R1, R2 |
|
|
|
|
|
|
|
|
I2 ADD R5, R3, R4 |
|
|
|
|
|
|
|
|
I3 ADD R3, R6, R7. |
|
|
|
|
|
|
|
|
In this example, instruction 2 is delayed by a divide operation in instruction 1. Instruction 3, whose sources are independent of instructions 1 and 2, if allowed to execute as soon as its operands are available, would cause a change to a register (R3) used in the computation of instruction 2. A dependency of this type is called an ordering dependency, since it is created only when out-of-order execution is allowed. |
|
|
|
|
|
|
|
|
The final type of dependency arises when the destination of instruction Ii is the same as the destination of instruction Ij, or |
|
|
|
|
|
|
|
|
Di = Dj. |
|
|
|
|
|
|
|
|
In this case, it is possible that the instruction Ii would complete after instruction Ij, and the final destination contained in the register would be that of instruction Ii when it ought to have been that of Ij. This dependency, called an output dependency, is somewhat debatable as a true source of instruction conflict. If instruction Ii produces a result that is not used by an instruction that follows it until instruction Ij produces a new result for the same destination, then instruction Ii was unnecessary in the first place and should have been eliminated. Output dependencies thus occur |
|
|
|
|
|