1. Explain the data dependences and hazards in
detail with examples. (16)
Various
types of Dependences in ILP. Data Dependence and Hazards:
To
exploit instruction-level parallelism, determine which instructions can be
executed in parallel. If two instructions are parallel, they can execute
simultaneously in a pipeline without causing any stalls. If two instructions
are dependent they are not parallel and must be executed in order.
There
are three different types of dependences: data dependences (also called true
data dependences), name dependences, and control dependences.
Data
Dependences:
An
instruction j is data dependent on instruction i if either of the following
holds:
•
Instruction i produces a result that may be used by instruction j, or
•
Instruction j is data dependent on instruction k, and instruction k is data
dependent on instruction i.
The
second condition simply states that one instruction is dependent on another if
there exists a chain of dependences of the first type between the two
instructions. This dependence chain can be as long as the entire program.
The
importance of the data dependences is that a dependence
(1)
indicates the possibility of a hazard,
(2)
Determines the order in which results must be calculated, and
(3)
Sets an upper bound on how much parallelism can possibly be exploited.
