19-12-2012, 06:10 PM
Data Dependence Analysis
1Data Dependence.pdf (Size: 543.66 KB / Downloads: 16)
Three types of constraints:
Flow or True dependence: When a variable is assigned or defined in
one statement and used in subsequent statement
Anti dependence: When a variable is used in one statement and
reassigned in subsequently executed statement
Output dependence: When a variable is assigned in one statement
and reassigned in subsequent statement
Anti dependence and Output dependence arise from reuse of variable and
are also called False dependence.
Flow dependence is inherent in computation and cannot be eliminated by
renaming. Therefore it is also called True dependence.
Iteration Space
concept associated with the loops
contains one point for each iteration of the loop
if a statement in one iteration dependes on a statement in another
iteration then dependence is represented by an edge from source to
target (called iteration space dependence graph)
for i = 2 to 9 do
x[i] = . . .
= . . . x[i-1] . . .
endfor
2 3 4 5 6 7 8 9
space requirement too large
compiler can not always determine number of iterations
Data dependence with conditionals
there must be a path from definition to use
in case of conditionals, path cannot be determined at compile time
any path may be taken at runtime
data dependence cannot occur between statements in alternate paths
Building dependence systems
- Form dependence equations
- Unknowns are loop induction variables
- Coefficients are compile time constants
- One coefficient for each loop induction variable plus a constant
coefficient
- Generally use induction variable corresponding to normalized or
semi-normalized loops.
i d indicates a definition
i u indicates a use
- Express dependence equation as a matrix notation
AI = C
where A: Coefficient matrix; I: Vector of unknowns C: Constant vector
If there is no solution, there can be no dependence.