Instruction-Level Parallelism and Its Exploitation - Computer Architecture: A Quantitative Approach - page 146

DADDUI R1,R1,#-8 ;decrement pointer 8 bytes
BNE R1,R2,LOOP ;branch R1!=R2
The data dependences in this code sequence involve both floating-point data:
and integer data:
In both of the above dependent sequences, as shown by the arrows, each instruction depends
on the previous one. The arrows here and in following examples show the order that must be
preserved for correct execution. The arrow points from an instruction that must precede the
instruction that the arrowhead points to.
If two instructions are data dependent, they must execute in order and cannot execute sim-
ultaneously or be completely overlapped. The dependence implies that there would be a chain
of one or more data hazards between the two instructions. (See Appendix C for a brief descrip-
tion of data hazards, which we will define precisely in a few pages.) Executing the instructions
simultaneously will cause a processor with pipeline interlocks (and a pipeline depth longer
than the distance between the instructions in cycles) to detect a hazard and stall, thereby re-
ducing or eliminating the overlap. In a processor without interlocks that relies on compiler
scheduling, the compiler cannot schedule dependent instructions in such a way that they com-
pletely overlap, since the program will not execute correctly. The presence of a data depend-
ence in an instruction sequence reflects a data dependence in the source code from which the
instruction sequence was generated. The effect of the original data dependence must be pre-
served.
Dependences are a property of programs . Whether a given dependence results in an actual
hazard being detected and whether that hazard actually causes a stall are properties of the
pipeline organization . This difference is critical to understanding how instruction-level parallel-
ism can be exploited.
A data dependence conveys three things: (1) the possibility of a hazard, (2) the order in
which results must be calculated, and (3) an upper bound on how much parallelism can pos-
sibly be exploited. Such limits are explored in Section 3.10 and in Appendix H in more detail.
Since a data dependence can limit the amount of instruction-level parallelism we can ex-
ploit, a major focus of this chapter is overcoming these limitations. A dependence can be over-
come in two different ways: (1) maintaining the dependence but avoiding a hazard, and (2)
eliminating a dependence by transforming the code. Scheduling the code is the primary meth-
od used to avoid a hazard without altering a dependence, and such scheduling can be done
both by the compiler and by the hardware.