Hardware Reference
In-Depth Information
Finding Dependences
Clearly, finding the dependences in a program is important both to determine which loops
might contain parallelism and to eliminate name dependences. The complexity of dependence
analysis arises also because of the presence of arrays and pointers in languages such as C or
C++, or pass-by-reference parameter passing in FORTRAN. Since scalar variable references
explicitly refer to a name, they can usually be analyzed quite easily with aliasing because of
pointers and reference parameters causing some complications and uncertainty in the analys-
is.
How does the compiler detect dependences in general? Nearly all dependence analysis all
gorithms work on the assumption that array indices are
affine
. In simplest terms, a one-dimen-
sional array index is aine if it can be writen in the form
a
×
i
+
b
, where
a
and
b
are constants
and
i
is the loop index variable. The index of a multidimensional array is affine if the index in
each dimension is affine. Sparse array accesses, which typically have the form
x[y[i]]
, are one
of the major examples of non-affine accesses.
Determining whether there is a dependence between two references to the same array in a
loop is thus equivalent to determining whether two affine functions can have the same value
for different indices between the bounds of the loop. For example, suppose we have stored to
an array element with index value
a
×
i
+
b
and loaded from the same array with index value
c
×
i
+
d
, where
i
is the for-loop index variable that runs from
m
to
n
. A dependence exists if two
conditions hold:
1. There are two iteration indices,
j
and
k
, that are both within the limits of the for loop. That
is,
m
≤
j
≤
n
,
m
≤
k
≤
n
.
2. The loop stores into an array element indexed by
a
×
j
+
b
and later fetches from that
same
array element when it is indexed by
c
×
k
+
d
. That is,
a
×
j
+
b
=
c
×
k
+
d
.
In general, we cannot determine whether dependence exists at compile time. For example,
the values of
a
,
b
,
c
, and d may not be known (they could be values in other arrays), making
it impossible to tell if a dependence exists. In other cases, the dependence testing may be very
expensive but decidable at compile time; for example, the accesses may depend on the itera-
tion indices of multiple nested loops. Many programs, however, contain primarily simple in-
dices where
a
,
b
,
c
, and
d
are all constants. For these cases, it is possible to devise reasonable
compile time tests for dependence.
As an example, a simple and sufficient test for the absence of a dependence is the
greatest
common divisor
(GCD) test. It is based on the observation that if a loop-carried dependence ex-
ists, then GCD (
c,a
) must divide (
d
−
b
). (Recall that an integer,
x, divides
another integer,
y
, if
we get an integer quotient when we do the division
y/x
and there is no remainder.)
Example
Use the GCD test to determine whether dependences exist in the following
loop:
for (i=0; i<100; i=i+1) {
X[2*i+3] = X[2*i] * 5.0;
}
Answer
Search WWH ::
Custom Search