NonLinear
Dependence Analysis

Loop parallelization requires
analysis of data dependencies

Many methods exist for linear
data dependence testing

Array index expressions in loops
are often linear

Example: a[i+1]
and [4*i+3] where i
is the loop counter variable

What about more complicated
array index expressions?

Nonlinear expressions, e.g.
a[i*ii]

Symbolic expressions, e.g. a[r*i]

Nonlinear and symbolic expressions
appear in

Scientific applications

Graphics and visualization software
