|
|
|
|
|
|
|
Figure 7.29
Instruction window. |
|
|
|
|
|
|
|
|
only in poorly represented code. Since this type of dependency is generally eliminated by any optimizing compiler, it can be largely ignored in our discussions and is not regarded by some as a true instruction dependency. Consider two examples: |
|
|
|
 |
|
|
|
|
DIV R3, R1, R2 |
|
|
|
|
|
|
|
|
ADD R3, R4, R5. |
|
|
|
|
|
|
|
|
DIV R3, R1, R2 |
|
|
|
|
|
|
|
|
ADD R5, R3, R4 |
|
|
|
|
|
|
|
|
ADD R3, R6, R7. |
|
|
|
|
|
|
|
|
The first example is clearly a case of a redundant instruction (the DIV), whereas the second is a case that has an output dependency, but also has an essential dependency; since this essential dependency must be covered, the output dependency is also covered. It is important to realize that the fewer the dependencies that arise in the code, the more concurrency available in the code and the faster the overall program execution. Thus, if output dependencies cannot occur because of the compiler, we achieve a higher degree of concurrency than otherwise. |
|
|
|
|
|
|
|
|
7.6.2 Representing Data Dependencies |
|
|
|
|
|
|
|
|
Suppose we have a block of instructions as shown in Figure 7.29. Instruction i is by definition independent of all others, since it is the first one in sequence. From the previous discussion, subsequent instruction j is dependent and cannot be executed at this time if any of the following three conditions are satisfied (i precedes j): |
|
|
|
|
|
|
|
|
1. EssentialDi = S1j or Di = S2j |
|
|
|
|
|
|
|
|
(also called read after write dependency [171]). |
|
|
|
|
|
|
|
|
2. OrderingDj = S1i or Dj = S2i |
|
|
|
|
|
|
|
|
(also called write after read dependency [171]). |
|
|
|
|
|
|
|
|
(also called write after write dependency [171]). |
|
|
|
|
|
