All Syllabus

Home About Unit 1 Unit 2 Unit 3 Unit 4 Unit 5 Unit 6 Unit 7 Unit 8  

Instruction Level Parallelism


Data Dependency and Hazard


Dynamic Branch Prediction

Correlating Branch Predictor

Dynamic Branch Prediction Summary


Data Dependency and Hazard

If two instructions are parallel, they can execute simultaneously in a pipeline of arbitrary length without causing any stalls, assuming the pipeline has sufficient resources. If two instructions are dependent, they are not parallel and must be executed in sequential order.

There are three different types dependences.
• Data Dependences (True Data Dependency)
• Name Dependences
• Control Dependences

Data Dependences

An instruction j is data dependant on instruction i if either of the following holds:
i) Instruction i produces a result that may be used by instruction j
Eg1: i: L.D F0, 0(R1)
j: ADD.D F4, F0, F2
ith instruction is loading the data into the F0 and jth instruction use F0 as one the operand. Hence, jth instruction is data dependant on ith instruction.
Eg2: DADD R1, R2, R3
DSUB R4, R1, R5
ii) Instruction j is data dependant on instruction k and instruction k data dependant on instruction i
Eg: L.D F4, 0(R1)
MUL.D F0, F4, F6
ADD.D F5, F0, F7

Dependences are the property of the programs. A Data value may flow between instructions either through registers or through memory locations. Detecting the data flow and dependence that occurs through registers is quite straight forward. Dependences that flow through the memory locations are more difficult to detect. A data dependence convey three things.

a) The possibility of the Hazard.
b) The order in which results must be calculated and
c) An upper bound on how much parallelism can possibly exploited.

Name Dependences

A Name Dependence occurs when two instructions use the same Register or Memory location, but there is no flow of data between the instructions associated with that name.

Two types of Name dependences:

i) Antidependence: between instruction i and instruction j occurs when instruction j writes a register or memory location that instruction i reads. he original ordering must be preserved to ensure that i reads the correct value.
Eg: L.D F0, 0(R1)

ii) Output dependence: Output Dependence occurs when instructions i and j write to the same register or memory location.
Ex: ADD.D F4, F0, F2
SUB.D F4, F3, F5

The ordering between the instructions must be preserved to ensure that the value finally written corresponds to instruction j.The above instruction can be reordered or can be executed simultaneously if the name of the register is changed. The renaming can be easily done either statically by a compiler or dynamically by the hardware.

Data hazard: Hazards are named by the ordering in the program that must be preserved by the pipeline

RAW (Read After Write): j tries to read a source before i writes it, so j in correctly gets old value, this hazard is due to true data dependence.

WAW (Write After Write): j tries to write an operand before it is written by i. WAW hazard arises from output dependence.

WAR (Write After Read): j tries to write a destination before it is read by i, so that I incorrectly gets the new value. WAR hazard arises from an antidependence and normally cannot occur in static issue pipeline.

A control dependence determines the ordering of an instruction i with respect to a branch instruction,

Ex: if P1 {
if P2 {
S1 is Control dependent on P1 and

S2 is control dependent on P2 but not on P1.
a)An instruction that is control dependent on a branch cannot be moved before the branch ,so that its execution is no longer controlled by the branch.
b)An instruction that is not control dependent on a branch cannot be moved after the branch so that its execution is controlled by the branch.