An Efficient Data Dependence Analysis for Parallelizing Compilers.
A novel algorithm, called the lambda test, is presented for an efficient and accurate data dependence analysis of multidimensional array references. It extends the numerical methods to allow all dimensions of array references to be tested simultaneously. Hence, it combines the efficiency and the accuracy of both approaches. This algorithm has been implemented in Parafrase, a Fortran program parallelization restructurer developed at the University of Illinois at Urbana-Champaign. Some experimental results are presented to show its effectiveness.
Introduction
A parallelizing compiler relies on data dependence analysis to detect
independent operations in a user's program. For array operands, the analysis needs to
check the existence of integer solutions to a linear system obtained from array
subscript expressions. In simple cases, this can be done rather easily. But in many
cases, this is not so. An analyzer can only resort to checking certain sufficient
conditions to determine the absence of a data dependence. If the conditions do not
hold, the existence of a data dependence becomes unclear. To err on the safe side, the
analyzer must assume that a data dependence exists. Most existing analysis algorithms
give only such "incomplete" tests. There are several well-known data dependence
analysis algorithms in practice. They are based on the theories of Diophantine
equations and the bounds on real functions [3], [4], [22], [1], [2]. [13] calls this class
of algorithms numerical methods. Current numerical methods handle only one single
dimension. For multi-dimensional array references, each dimension has to be tested
separatedly. These methods are generally efficient and can detect data independence in
many practical cases. Nevertheless, for complicated array subscripts, especially for
multi-dimensional arrays, their test results are often too conservative. More precise
results can be achieved by checking the consistency of a linear system of inequalities
and equalities. In theory, it could be solved by integer programming (IP) or, with
some loss of precision, by linear programming (LP). However, currently known LP
and IP algorithms, such as the simplex method [7] and the Karmarkar's method [8],
are aimed at large systems with at least a few hundred constraints and variables. They
are not suitable for data dependence analysis where a large number of small systems
need to be analyzed. Program verification faces similar problems - methods other
than IP or LP are needed to improve its efficiency. Recently, several authors proposed
to use methods such as the Fourier-Motzkin elimination and the loop residue method
(see e. g. [6], [17]) for data dependence analysis [11], [20], [13] 1 . In [21], a modified
simplex method for IP without considering the cycling problem is considered. It can
yield a conservative solution when no conclusion could be reached after a certain
number of iterations. Most of these methods can determine whether there exists a
real-valued solution to a system of equations and inequalities. Even though these
methods [11], [20], [13] still do not answer whether integer solutions exist, they are a
very good approximation in practical cases. Unfortunately, compared to earlier
numerical methods, these methods are very time consuming. The worst-case
computing time is exponential in the number of loop indices even for single-dimensional
array references. Even though empirical data on the efficiency of these
methods is very limited, some experimental results have shown that average testing
time in the Fourier-Motzkin elimination is about 22 to 28 times longer than existing
numerical methods [19]. Unless far more efficient algorithms are found, difficulties in
testing multi-dimensional array references will remain. In this paper, we extend the
existing numerical methods to overcome these difficulties. A geometrical analysis
reveals that we can take advantage of the regular shape of the convex sets derived
from multi-dimensional arrays in a data dependence test. The general methods
proposed before assume very general convex sets; this assumption causes their
inefficiency. We have implemented a new algorithm called the l-test and performed
some measurements. Results were quite encouraging (see Section 4). As in earlier
numerical methods, the proposed scheme uses Diophantine equations and bounds of
real functions. The major difference lies in the way multiple dimensions are treated.
In earlier numerical methods, data areas accessed by two array references are
examined dimension by dimension. If the examination of any dimension shows that
the two areas representing the subscript expressions are disjoint, there is no data
dependence between the two references. However, if each pair of areas appears to
overlap in each individual dimension, it is unclear whether there is an overlapped area
when all dimensions are considered simultaneously. In this case, a data dependence
has to be assumed. Our algorithm treats all dimensions simultaneously. Based on the
subscripts, it selects a few suitable "viewing angles" so that it gets an exact view of
the data areas. Selection of the viewing angles is rather straightforward and only a
few angles are needed in most cases. We present the rest of our paper as follows. In
Section 2, we give some examples to illustrate the difficulties in data dependence
analysis on multi-dimensional array references. Some measurement results on a large
set of real programs are presented to show the actual frequency of such difficult cases.
In Section 3, we describe our new algorithm and provide its theoretical background.
In Section 4, we present our experimental results and give a brief conclusion.
2. Coupled Subscripts in Multi-Dimensional Array References In this section, we
identify coupled subscripts as the main difficulty in data dependence analysis on
multi-dimensional array references. First, we show a couple of examples.
Example 2.1
END END
In the above, r1 and r2 are two references to array A. If there is no data dependence between r1 and r2,
then both loops in the example can be parallelized. In order to determine whether there is a data
dependence between r1 and r2, a system of equations and inequalities should be examined. Let x
and x 2 - j for reference r1, x 3 - i and x 4 - j for reference r2. We equate the subscript expressions in r1
and r2 and get the followings:
because of the loop bounds. Data dependence exists between r1 and r2 if
and only if equations (2.1) and (2.2) have common integer solutions within the loop bounds. We can show that such
common solutions do not exist in this example. Consider a linear combination of (2.1) and (2.2) by (2.1) - 3 - (2.2)
- 2, which gives a new equation:
Given the loop bounds, the minimum value on the left hand side of (2.3) is 17 which is larger than the right hand side
5. This means (2.1) and (2.2) have no solutions. Thus r1 and r2 are independent. However, in most existing numerical
methods, each dimension of the array A is treated separately. Therefore, instead of examining both (2.1) and (2.2)
simultaneously, most algorithms examine each equation separately. If any equation can be shown to have no solution
within the loop bounds, then there is no data dependence. But if each equation has solutions independently, the algorithm
has to assume the existence of data dependence. In (2.1) and (2.2), some loop indices appear in both dimensions
of array A (either in r1 or in r2). As a result, equations (2.1) and (2.2) share some common un-knowns. We say
the references have coupled subscripts. Due to such coupled subscripts, while the simultaneous equations do not have
common solutions (as shown earlier), each individual equation may have independent solutions. As a matter of fact,
is a solution to (2.1), and is a solution to (2.2). Both solutions
are within the loop bounds. No algorithms based on dimension-by-dimension approach could detect the independence
between r1 and r2. In the next example, we consider the effect of coupled subscripts on the determination of dependence
directions [22].
Example 2.2
Obviously there is data dependence between references r1 and r2 in the loop above. However, if the dependence does
not cross loop iterations, then the loop can still be parallelized. This is exactly the case with the inner loop: when
index i of the outer loop is fixed, r1 and r2 could never access the same data element from different iterations of the
inner loop. So the inner loop can be parallelized. Testing cross-iteration dependences is normally done by examining
dependence directions [22]. The procedure of checking these directions starts with setting up the following equations
and inequalities.
The dependence directions to be examined are specified in (2.7). We have because the iteration of the outer
loop should be fixed. is the condition for a data dependence (from r1 to r2) to cross the iterations of the inner
loop. Note that we also need to examine cross-iteration dependences from r2 to r1, for which we should set
The discussion is similar so we omit it. It is not hard to see that equations (2.4) and (2.5) do not have common solutions
satisfying both (2.6) and (2.7). However, earlier numerical methods cannot detect this, again because they treat
each dimension of an array separately. They check on two subsystems. One contains (2.4), (2.6) and (2.7). The
other contains (2.5), (2.6) and (2.7). Now that each subsystem has solutions (e. g.
and (2.7)), the algorithms must assume that the inner loop has cross-iteration
dependences. Dimension-by-dimension approach fails to detect impossible dependence directions in this case because
some loop indices (say, index i ) appear in both dimensions of the array A, i.e., there are coupled subscripts. According
to an empirical study reported in [16], coupled subscripts appear quite frequently in real programs. In that study,
twelve Fortran program packages which contain 1074 subroutines and more than one hundred thousand lines of statements
were examined. The packages include LINPACK, EISPACK, ITPACK, FISHPAK, SPICE and others. Of all
the array references examined, two-dimensional array references account for 36.23%, and three-dimensional array
references account for 7%. The percentage of array references with more than three dimensions are negligible. In
more than four thousand pairs of two-dimensional array references with linear subscripts in DO loops, about 46%
have coupled subscripts 2 . As for array references with more than two dimensions, only 2% have coupled subscripts.
The data show several interesting things. First, multi-dimensional array references are very common. Second, coupled
subscripts appear quite frequently. Third, two-dimensional arrays are dominant in references with coupled sub-
scripts. Although a single dimension test could sometimes succeed in detecting data independence despite the coupled
subscripts, often it may fail. Therefore, it is important to have an efficient test algorithm to handle coupled subscripts.
As the data indicates, two-dimensional array references are especially important.
3. The l-test: a new algorithm We present our new algorithm, the l-test, in this section. We consider a data dependence
problem where subscript expressions are linear in terms of loop indices. Loop bounds are assumed to be con-
-stant, otherwise they are replaced with their closest constant bounds. Dependence directions may also be given if
required. We consider only constant loop bounds in this paper because an efficient test in the presence of variable
loop bounds is a research topic by itself and is beyond the scope of this paper. [5] gave a very good discussion of
dependence tests for single dimensional array references in the presence of variable loop bounds. Handling coupled
subscripts in loops with variable bounds is discussed in [12]. Given the data dependence problem as specified, the l-
test examines a system of equalities and inequalities and determines whether the system has real-valued solutions.
(Section 4 will discuss integer solutions.) Some notations need be defined before we describe the test.
3.1 Notation (r 1 , r 2 ), is a pair of references to an array A of m dimensions. r 1 is nested in l 1 loops. r 1 - A(f 1 (i 1 ,
are the loop indices (from the outermost to the inner-
most). The loops have constant lower bounds
, ., L i, and constant upper bounds U
. r 2 is nested
in l 2 loops. r 2 - A(g 1 (j 1 ,
are the loop indices
(from the outermost to the innermost). The loops have constant lower bounds
, ., L j, and constant upper
bounds
, ., U j. Equating the subscripts of r 1 and r 2 , we have the following:
only if (3.1) has an integer solution (i 1
, ., etc. (r 1 , r 2 ) is said to intersect at (i 1
Assume that f i and g i are all linear. A dependence direction is q - {<, >, =}. A dependence direction vector is q
each q i is a dependence direction [22]. Suppose r 1 and r 2 have l c common loops of which the
innermost is indexed by i l in r 1 , (or j l c
in r 2 ), l c - min(l 1 , l 2 ). (r 1 , r 2 ) is said to intersect with dependence direction
vector q
they intersect at (i 1
may intersect with more than one dependence direction vector.
We denote the set of loop indices in (r 1 ,
} and denote the index set of (r 1 , r 2 )
that appears in the array dimension j, 1-j -d , by IND appears in either f j or g j }.
(a) If IND j 1
-, then dimension j 1 and dimension j 2 are said to be coupled. (r 1 , r 2 ) is said to have coupled
subscripts;
(b) If dimension j 1 and j 2 are coupled, and j 2 and j 3 are coupled, then j 1 and j 3 are also coupled.
3.2 A geometrical analysis Our algorithm is best explained with the aid of a geometrical illustration. Suppose f i 's
and g i 's in (3.1) are linear equations with n unknowns, we can rewrite (3.1) as:
a m
(n
a 2
(n
a 1
(n
We assume that there are no redundant equations in (3.2). Otherwise, they can simply be eliminated. Further, all
array dimensions are assumed to be coupled. Otherwise, (3.2) can be broken into several disjoint subsystems. Partial
solutions can be obtained for each subsystem and later merged together to form a complete solution. Of course, the
number of coupled dimensions, m, is very small in practice. An especially important case is
effort should be expended to derive a fast test. Geometrically, each linear equation is a hyperplane p in R n space.
The intersection, S, of the m hyperplanes corresponds to the common solutions to all the equations in (3.2). Obvi-
ously, if S is empty then there is no data dependence. Checking whether S is empty is trivial in linear algebra.
Therefore we consider only nonempty S henceforth. The loop bounds and the given dependence directions correspond
to a bounded convex set V in R n . An equation has a real-valued solution satisfying the loop bounds and the dependence
directions if and only if its corresponding hyperplane p intersects V. A dimension-by-dimension test would be
able to determine whether each p intersects V. What we want is to determine whether S itself intersects V. If any of
the hyperplanes does not intersect V, then obviously S cannot intersect V. However, even if every hyperplane in (3.2)
intersects V, it is still possible that S and V are disjoint. In Figure 1, p 1 and p 2 are two such hyperplanes representing
two equations from the system, each of which intersects V. But the intersection of p 1 and p 2 is outside of V. If one
can find a new hyperplane which contains S but is disjoint from V, then it immediately follows that S and V do not
intersect. In Figure 1, p 3 is such a new hyperplane. The following theorem guarantees that if S and V are disjoint,
then there must be a hyperplane in R n which contains S and is disjoint from V. Further, this hyperplane is a linear
combination of the hyperplanes in (3.2). On the other hand, if S and V intersect, then no such linear combination
exists.
Theorem 1
only if there exists a hyperplane, p, which corresponds to a linear combination of equations in
l i a -
denotes the inner product of a -
(1) , a i
a i
[proof] See Appendix. An array (l 1 , l 2 , ., l m ) in Theorem 1 determines a hyperplane that contains S. There are
an infinite number of such hyperplanes. The tricky part in the l-test is to examine as few hyperplanes as necessary to
determine whether S and V intersect. We start from the case of both for the convenience of presentation and
for the practical importance of this case, as described above.
3.3 The case of 2-dimensional array references In the case of 2-dimensional array references, the equations in
(3.2) are f
(n . For convenience, we directly refer
to a linear equation as a hyperplane in R n . An arbitrary linear combination of the two equations can be written as
The domain of (l 1 , l 2 ) is the whole R 2 space. Let f l 1
that is f l 1
l 2 a 2
(n
can be viewed in two ways. With (l 1 , l 2
is a linear function of (v (1) , v (2) , ., v (n ) ) in R n . With
(v (1) , v (2) , ., v (n it is a linear function of (l 1 , l 2 ) in R 2 . Further, the coefficient of each v (i ) in f l 1
is a
linear function of (l 1 , l 2 ) in R 2 , i. e. y (i
(i ) .
Definition The equation y (i called a y-equation. A y-equation corresponds to a line in R 2 which
is called a y-line.
Definition Each y-line is the boundary of two half-spaces: Y i
There are at most n y-lines which together divide R 2 into at most 2n regions. Each region is a cone (Figure 2) called
a l-cone. In each l-cone, none of the functions y (i ) can change the sign of its value (except change to zero in a y-
line). This leads to the following lemma.
is defined by loop bounds but not by dependence directions. (Note: we will consider dependence
directions later.) If f l 1
for every (l 1 , l 2 ) in every y-line, then f l 1
every (l 1 , l 2 ) in R 2 .
[Proof] From the well-known intermediate value theorem, f l 1
only if min(f l 1
on V. Since V is bounded and f l 1
is continuous on V, when (l 1 ,l 2 ) is fixed, there exist v
that min(f l 1
(v - min ), and v - such that max(f l 1
(v - max ). With a fixed (l 1 , l 2 ), it is easy to verify
that v - max and v - min are determined by the sign of the coefficient of each v (i
x , if y (i
y , if y (i
where are the lower bound and the upper bound of v (i ) respectively. x , y are arbitrary values in [L (i ) , U (i ) ].
The coefficient of each v (i ) in f l 1
does not change its sign in each l-cone. It follows that v - max and v - min
remain the same in each l-cone. Therefore, f l 1 ,l 2
(v -
(n
(1)
(n
linear function of (l 1 ,l 2 ) in each l-cone. From the assumption of the lemma,
we have f l 1 ,l 2
(v -
on the boundaries of each cone. It is a well-known fact in the convex
theory that any point (l 1 , l 2 ) in a cone can be expressed as a linear combination of some points on the cone's boun-
daries. It immediately follows that f l 1
(v -
is true in each l-cone. Of course it is also true in the whole R 2
space. By the same argument, we have f l 1
(v -
Therefore, for any (l 1 , l 2 ),
intersects V in R n space.
If V is defined by loop bounds plus dependence directions, we have a similar lemma. First we should discuss the
rules for the selection of v -
min and v
dependence directions are given. Note that each dependence direction q
relates a unique pair of loop indices v (i (j ) which are associated with one of the common loops. L (i
U (j ) . Obviously v min
(i
(j
(i
(j ) should be chosen such that the partial sum a (i (j ) has the
minimum value at (v min
(i
(j ) ) and has the maximum value at (v max
(i
(j constrained by a dependence
direction, v max
(i ) and v min
(i ) should be chosen as in the proof of Lemma 1. The following rules determine the
minimum and maximum points of a function f, f - a (1) v (1) + a (2) v (2) in the convex set V defined by
both loop bounds and dependence directions.
Rules If v (i
(j
(j
consider (iia) and (iib). Unless a (i ) < 0 and a (j ) > 0, we have
(j
U (j ) , if a (j ) < 0,
(j
where rules in (iia) would conflict with the dependence
direction. Instead, since we have
a (i
the rules in this case should be
(j
(j
where
(i
(j are similar. Consider (iic) and (iid). Unless
a (i ) >0 and a (j ) <0, we have
(j
(j ) +1, if a (j ) < 0,
U (j ) , if a (j ) > 0,
where
(j
(j
where Rules for the case v (i ) > v (j ) are symmetrical to those in (ii). Details are
omitted.
be the sum of the coefficients of v (i ) and v (j ) in f l 1
, where v (i ) and v (j ) are related by a dependence
direction, i. e., f (i ,
(j
(j From the rules stated above, it is clear that the minimum
point and the maximum point of f l 1
in V, in the presence of dependence directions, depend not only on the sign of
the coefficient of each v (i ) but also on the sign of f (i , j ) .
called a f-equation. Each f-equation corresponds to a f-line in R 2 space.
There are at most n/2 f-lines. All f-lines and y-lines divide R 2 space into at most 3n regions. Each region is a cone,
still called a l-cone. We have the following lemma similar to Lemma 1.
is defined by loop bounds as well as dependence directions. If f l 1
(l 1 , l 2 ) in every y-line and every f-line, then f l 1 ,l 2
[Proof] Follow the same argument as for Lemma 1. As a matter of fact, in order to determine whether f l 1 ,l 2
sects V for every (l 1 , l 2 ) in a f-line or a y-line, it suffices to test a single point in the line. This is from the following
lemma.
Lemma 3 Given a line in R 2 corresponding to an equation al 1
fixed
(l 1
in the line, then for every (l 1 , l 2 ) in the line, f l 1
[Proof] Note that f l 1
only if min(f l 1
on V. Every point in the line can
be expressed as (el 1
el 2
min for f el 1
should be the same as for f l 1
Therefore we have min(f el 1
0). If e - 0 then v -
min for f el 1
in V is the same as v -
and we have min(f el 1
0). In either case, we should have min(f el 1
because of min(f l 1
For the same reason, we have max(f el 1
Definition Given an equation of the form a l 1 are not zero simultaneously, we define a canonical
solution of the equation as follows:
neither of a, b is zero and b > 0;
neither of a, b is zero and b < 0.
Definition The L set is defined to be the set of all canonical solutions to the y-equations and f-equations. The hyper-plane
in R n corresponding to l 1 canonical solution in L, is called a l-plane. Obvi-
ously, the size of the L set is at most n if V is defined by loop bounds only, and is at most 3n/2 if V is defined by
loop bounds as well as dependence directions.
Theorem 2 S intersects V if and only if every l-plane intersects V. If V is defined by loop bounds only, then there
are no more than n l-planes. If V is defined by loop bounds as well as dependence directions, then there are no more
than 3n/2 l-planes.
[Proof] From Lemmas 1-3 and the definition of l-planes. Theorem 2 provides a foundation for the l-test in the
case of 2. The test examines the subscripts from the two coupled dimensions, then determines the L set from the
f-equations and the y-equations. Each element of L determines a l-plane. Each l-plane is tested to see if it intersects
V, by checking its minimum and maximum values as done in Banerjee-Wolfe test on each single dimension. If
any l-plane does not intersect V, then there is no data dependence. If every l-plane intersects V, then data dependence
should be assumed, unless further tests on integer solutions are to be performed. For the sake of efficiency,
computation of the L set and the test on l-planes are performed alternately, i.e., a new element in L is computed only
after it has been tested that the previous l-plane intersects with V. Obviously, repeated canonical solutions can be
ignored. We illustrate the l-test by applying it to Examples 2.1 and 2.2 in Section 2. In Example 2.1, no dependence
directions are given. We only have y-equations, from which the L set is easily determined:
-1), (1, -1)}. A canonical solution (3, -2) determines a l-plane which is exactly the linear combination we used to
show the absence of data dependence in Example 2.1. In Example 2.2, the y-equations have two canonical solutions
(1, 1), each corresponding to an original hyperplane in one of the dimensions. The f-equations are l 1 - l 2
canonical solutions are both (1, 1). This gives a l-plane: which does
not intersect V. In practice, the original hyperplanes f are usually l-planes to be tested. Due to the
regularity of coefficients in subscripts, it is extremely rare that more than one l-plane besides f needs
be tested. In our experiments, the l-test takes less than twice as much time as needed for a dimension-by-dimension
test in most programs and total increase in compile time is very insignificant. Hence, the l test is quite efficient.
3.4 The case of m > 2 To generalize the l-test, we consider m equations in (3.2) with m > 2. All m equations are
assumed to be connected; otherwise they can be partitioned into smaller systems. This case is more of theoretical
interest than of practical concern, since it is rare in real programs to have more than two coupled dimensions. As
stated before, we can assume that there are no redundant equations. An arbitrary linear combination of the m equations
can be written as
,l 2,
,l 2,
l j a j
l j a j
l j a j
(n
It is to be determined whether f l 1
, . ,l m
space for arbitrary (l 1 ,l 2 , . ,l m ). The coefficient
of each v (i ) in f l 1
,l 2,
is a linear function of (l 1 , l 2 , ., l m ) in R m , which is y (i
(i ) .
Definition The equation y (i called a y-equation. A y-equation corresponds to a hyperplane in R m ,
called a y-plane.
Each y-plane is the boundary of two half-spaces defined as follows. Y i
be the sum of the coefficients of v (i ) and v (j ) in f l 1
,l 2,
, where v (i ) and v (j ) are related by a dependence
direction, i. e., f (i j
(j
(j
(j
Definition The equation f (i called a f-equation. A f-equation corresponds to a hyperplane in R m
which is called a f-plane.
Each f-plane is the boundary of two half-spaces defined as follows. F i
Definition If V is defined by loop bounds only, then a nonempty set
- }, is called a l-
-region.
Definition If V is defined by loop bounds as well as dependence directions, then a nonempty set (
- }, is called a l-region. Note that the intersection of F i , j is taken for
all pairs of index variables which are related by a dependence direction.
Lemma 4 Every l-region is a cone in R m space. The l-regions in R m space have several lines as the frame of their
boundaries. Each line (called a l-line) is the intersection of some y-planes and f-planes.
Lemma 5 If f l 1
,l 2,
for every (l 1 , l 2 , ., l m ) in every l-line, then f l 1
,l 2,
for every (l 1 , l 2 , ., l m ) in R m .
[Proof] Follow the same argument as for Lemmas 1 and 2. Note that every point in a cone can be expressed as a
linear combination of some points in the cone's 1-dimensional boundaries.
Lemma 6 Given a line in R m which crosses the origin of the coordinates, if f l 1
,l 2,
fixed (l 1
in the line, then for every (l 1 , l 2 , ., l m ) in the line, f l 1
,l 2,
V.
[Proof] Follow the same argument as for Lemma 3.
Theorem 3 There is a finite set of hyperplanes in R n such that S intersects V if and only if every hyperplane in the
set intersects V. If V is defined by loop bounds only, then there are no more than
hyperplanes in the set. If
V is defined by loop bounds as well as dependence directions, then there are no more than
hyperplanes in the
set.
[Proof] See Appendix. Lemmas 4 through 6 and Theorem 3 provide a foundation for the l-test in the case of m -
3. Obviously, Theorem 3 is also true for the case of 2. We do not go into the detail of the l-test in the general
case, since the discussion is very similar to the case of 2. Compared with the theoretical time complexity of
methods based on inequality consistency checking, the l-test is clearly much faster, especially for small m.
4. Experimental Results and Conclusion
4.1 Experimental results We have implemented the l-test in a program parallelization
restructurer, Parafrase [10], [9], [15]. Almost all well-known dimension-by-dimension data dependence
test algorithms can be found in Parafrase. We added the l-test and performed experiments
on a numerical package, EISPACK [18]. The package has 56 subroutines, 31 of which were
found to have coupled subscripts. Among these 31 subroutines, 25 had their data dependence
analysis improved by the l-test. In our experiments, parallelization of EISPACK subroutines
required examination of 72,697 pairs of array references. Array dimensions ranged from one to
three. Some involved the same pair of array references with different dependence directions. The
dimension-by-dimension algorithms in Parafrase found 30,973 cases that had no data dependence.
In many other cases, the algorithms made a conservative assumption that dependences existed.
We then checked whether coupled subscripts were present. If so, the l-test was applied. The l-
test found an additional 3,214 cases that had no data dependence. So we had an improvement
rate of 10.4%. The improvement rate can be affected by two factors. First, the frequency of coupled
subscripts. Second, the "success rate" of the l-test, by which we mean how often a l-test
detects a case where there is no data independence. In our experiment, coupled subscripts were
found in 8943 cases where the dimension-by-dimension algorithms assumed data dependences.
3214 of them were found to have no data dependence, so the "success rate" was 36%. Table 1
shows a rough breakdown of an improvement rate for various subroutines. For instance, the first
row shows that there are 7 subroutines with the improvement rate between 20% to 40% in each
subroutine. In our experiments, l-planes always included the hyperplane from each dimension of
an array reference. Note that the dimension-by-dimension algorithms had already tested these
hyperplanes. The l-tests examined a total number of 8971 additional l-planes in our experiment.
That is, almost every l-test had examined only one additional l-plane. In light of this fact, the
additional time needed by a l-test is very small. Timing results are shown in Table 2. Each row
shows how much additional time was needed in the l-tests. For instance, the first row shows that
there were 12 subroutines in which the l-tests consumed no more than 20% additional time. For
most of the subroutines (53 out of 56), the l-tests never need more than 100% additional time.
Additional time was spent mostly on (1) finding coupled dimensions, (2) calculating l-values, and
(3) examining each l-plane.
4.2 Conclusion The l-test is a new algorithm that can improve data dependence analysis
significantly when there are coupled subscripts in multi-dimensional array references. It achieves
the same testing precision as methods based on inequality consistency checking. However, its
testing time is much less, especially for small coupled dimensions which occur most frequently.
Therefore, it seems to be a promising practical scheme to overcome many difficulties in existing
data dependence analysis methods. As in the methods based on inequality consistency checking,
the l-test can only determine whether real-valued solutions exist. However, in most practical
cases, it is a very good approximation. [14] found that in many common cases the existence of
real-valued solutions and the unconstrained integer solutions, i. e., integer solutions without considering
loop bounds as well as dependence directions [5], [14], can guarantee the existence of
integer solutions that satisfy the loop bounds as well as dependence directions. There is still
much work to be done in data dependence analysis. A general and efficient way to obtain integer
solutions is very desirable. We hope the proposed l-test has moved one step closer toward that
goal.



--R

"Dependence Analysis for Subscripted Variables And Its Application to Program Transformations,"
"Automatic Translation of Fortran Programs to Vector Form,"
"Data Dependence in Ordinary Programs,"
"Speedup of Ordinary Programs,"
Dependence Analysis for Supercomputing
"Automatic discovery of linear restraints among variables of a pro- gram,"
Linear Programming and Extensions
"A new polynomial-time algorithm for linear programming,"
"The structure of an advanced vectorizer for pipelined processors,"
"Automatic program restructuring for high-speed computations,"
"Optimization And Interconnection Complexity for: Parallel Processors, Single-Stage Networks, And Decision Trees,"
"Intraprocedural and Interprocedural Data Dependence Analysis for Parallel Computing,"
"Introducing symbolic problem solving techniques in the dependence testing phase of a vectorizer,"
Practical methods for exact data dependence analysis
"High-speed multiprocessors and compilation techniques,"
"An empirical study on array subscripts and data dependences,"
"Deciding linear inequalities by computing loop residues,"
Matrix Eigensystem Routines - Eispack Guide
"Interprocedural Analysis for Program Restructuring with Parafrase,"
"Direct parallelization of CALL statements,"
"Dependence of multi-dimensional array references,"
"Optimizing Supercompilers for Supercomputers,"
--TR
Direct parallelization of call statements
Introducing symbolic problem solving techniques in the dependence testing phases of a vectorizer
Dependence of multi-dimensional array references
Some results on exact data dependence analysis
Linear programming 1
Deciding Linear Inequalities by Computing Loop Residues
Automatic discovery of linear restraints among variables of a program
Dependence Analysis for Supercomputing
Automatic program restructuring for high-speed computation
A new polynomial-time algorithm for linear programming
Speedup of ordinary programs
Optimization and interconnection complexity for
Dependence analysis for subscripted variables and its application to program transformations
Optimizing supercompilers for supercomputers
Intraprocedural and interprocedural data dependence analysis for parallel computing

--CTR
Weng-Long Chang , Chih-Ping Chu, The infinity Lambda test, Proceedings of the 12th international conference on Supercomputing, p.196-203, July 1998, Melbourne, Australia
Jay P. Hoeflinger , Yunheung Paek , Kwang Yi, Unified Interprocedural Parallelism Detection, International Journal of Parallel Programming, v.29 n.2, p.185-215, April 2001
Jingke Li , Michael Wolfe, Defining, Analyzing, and Transforming Program Constructs, IEEE Parallel & Distributed Technology: Systems & Technology, v.2 n.1, p.32-39, March 1994
S. Sharma , C.-H. Huang , P. Sadayappan, On data dependence analysis for compiling programs on distributed-memory machines (extended abstract), ACM SIGPLAN Notices, v.28 n.1, p.13-16, Jan. 1993
Jan-Jan Wu, An Interleaving Transformation for Parallelizing Reductions for Distributed-Memory Parallel Machines, The Journal of Supercomputing, v.15 n.3, p.321-339, Mar.1.2000
Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, ACM SIGPLAN Notices, v.26 n.6, p.1-14, June 1991
T. H. Tzen , L. M. Ni, Dependence Uniformization: A Loop Parallelization Technique, IEEE Transactions on Parallel and Distributed Systems, v.4 n.5, p.547-558, May 1993
Lee-Chung Lu , Marina C. Chen, Subdomain dependence test for massive parallelism, Proceedings of the 1990 conference on Supercomputing, p.962-972, October 1990, New York, New York, United States
Lee-Chung Lu , Marina C. Chen, Subdomain dependence test for massive parallelism, Proceedings of the 1990 ACM/IEEE conference on Supercomputing, p.962-972, November 12-16, 1990, New York, New York
Michael Wolfe, Experiences with data dependence abstractions, Proceedings of the 5th international conference on Supercomputing, p.321-329, June 17-21, 1991, Cologne, West Germany
Z. Shen , Z. Li , P. C. Yew, An Empirical Study of Fortran Programs for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.356-364, July 1990
Yu-Kwong Kwok , Ishfaq Ahmad, FASTEST: A Practical Low-Complexity Algorithm for Compile-Time Assignment of Parallel Programs to Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.10 n.2, p.147-159, February 1999
Weng-Long Chang , Chih-Ping Chu , Jia-Hwa Wu, A Polynomial-Time Dependence Test for Determining Integer-Valued Solutions in Multi-Dimensional Arrays Under Variable Bounds, The Journal of Supercomputing, v.31 n.2, p.111-135, December  2004
Yunheung Paek , Jay Hoeflinger , David Padua, Simplification of array access patterns for compiler optimizations, ACM SIGPLAN Notices, v.33 n.5, p.60-71, May 1998
M. Wolfe , C. W. Tseng, The Power Test for Data Dependence, IEEE Transactions on Parallel and Distributed Systems, v.3 n.5, p.591-601, September 1992
Junjie Gu , Zhiyuan Li , Gyungho Lee, Symbolic array dataflow analysis for array privatization and program parallelization, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.47-es, December 04-08, 1995, San Diego, California, United States
Minjoong Rim , Rajiv Jain, Valid Transformations: A New Class of Loop Transformations for High-Level Synthesis and Pipelined Scheduling Applications, IEEE Transactions on Parallel and Distributed Systems, v.7 n.4, p.399-410, April 1996
David J. Lilja, Cache coherence in large-scale shared-memory multiprocessors: issues and comparisons, ACM Computing Surveys (CSUR), v.25 n.3, p.303-338, Sept. 1993
David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994
Baowen Xu , Ju Qian , Xiaofang Zhang , Zhongqiang Wu , Lin Chen, A brief survey of program slicing, ACM SIGSOFT Software Engineering Notes, v.30 n.2, March 2005
numerical methods;hyperplanes;parafrase;array subscripts;fortran program parallelization restructurer;linear inequalities;parallelizing compilers;lambda test;multidimensional array references;FORTRAN;index termsprogram restructuring;data dependence analysis;loop bounds;parallel programming;program compilers;convex set