Index-Association Based Dependence Analysis and
Its Application in Automatic Parallelization
Yonghong Song and Xiangyun Kong
To appear at
16th Workshop on Languages and Compilers for Parallel Computing (LCPC03), College Station, TX, 2-4 October 2003
Full Text, Printable Abstract.
Abstract
In this paper, we present a technique to
perform dependence analysis on more complex
array subscripts than the linear form of
the enclosing loop indices.
For such complex array subscripts, we
decouple the original iteration space
and the dependence test iteration space
and link them through {\em index-association} functions.
The dependence analysis is performed in the
dependence test iteration space
to determine whether the dependence exists
in the original iteration space.
The dependence distance in the original iteration space
is determined by the distance in the dependence test
iteration space and the property of index-association
functions.
For certain non-linear expressions, we show how to equivalently
transform them to a set of linear expressions.
The latter can be used in traditional dependence
analysis techniques targeting
subscripts which are linear form of enclosing loop indices.
We also show how our advanced dependence analysis
technique can help parallelize
some otherwise hard-to-parallelize loops.