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

A data value may flow between instructions either through registers or through memory
locations. When the data flow occurs in a register, detecting the dependence is straightforward
since the register names are fixed in the instructions, although it gets more complicated when
branches intervene and correctness concerns force a compiler or hardware to be conservative.
Dependences that flow through memory locations are more difficult to detect, since two ad-
dresses may refer to the same location but look different: For example, 100(R4) and 20(R6) may
be identical memory addresses. In addition, the effective address of a load or store may change
from one execution of the instruction to another (so that 20(R4) and 20(R4) may be different:
further complicating the detection of a dependence.
In this chapter, we examine hardware for detecting data dependences that involve memory
locations, but we will see that these techniques also have limitations. The compiler techniques
for detecting such dependences are critical in uncovering loop-level parallelism.
Name Dependences
The second type of dependence is a name dependence . A name dependence occurs when two in-
structions use the same register or memory location, called a name , but there is no flow of data
between the instructions associated with that name. There are two types of name dependences
between an instruction if that precedes instruction j in program order:
1. An antidependence between instruction if and instruction j occurs when instruction j writes
a register or memory location that instruction if reads. The original ordering must be pre-
served to ensure that if reads the correct value. In the example on page 151, there is an anti-
dependence between S.D and DADDIU on register R1 .
2. An output dependence occurs when instruction if and instruction j write the same register or
memory location. The ordering between the instructions must be preserved to ensure that
the value inally writen corresponds to instruction j .
Both antidependences and output dependences are name dependences, as opposed to true
data dependences, since there is no value being transmited between the instructions. Because
a name dependence is not a true dependence, instructions involved in a name dependence
can execute simultaneously or be reordered, if the name (register number or memory location)
used in the instructions is changed so the instructions do not conlict.
This renaming can be more easily done for register operands, where it is called register re-
naming . Register renaming can be done either statically by a compiler or dynamically by the
hardware. Before describing dependences arising from branches, let's examine the relation-
ship between dependences and pipeline data hazards.
Data Hazards
A hazard exists whenever there is a name or data dependence between instructions, and they
are close enough that the overlap during execution would change the order of access to the
operand involved in the dependence. Because of the dependence, we must preserve what is
called program order —that is, the order that the instructions would execute in if executed se-
quentially one at a time as determined by the original source program. The goal of both our
software and hardware techniques is to exploit parallelism by preserving program order only
where it affects the outcome of the program . Detecting and avoiding hazards ensures that neces-
sary program order is preserved.
Data hazards, which are informally described in Appendix C , may be classified as one of
three types, depending on the order of read and write accesses in the instructions. By conven-
tion, the hazards are named by the ordering in the program that must be preserved by the