An Empirical Study of Fortran Programs for Parallelizing Compilers.
Some results are reported from an empirical study of program characteristics, that are important in parallelizing compiler writers, especially in the area of data dependence analysis and program transformations. The state of the art in data dependence analysis and some parallel execution techniques are examined. The major findings are included. Many subscripts contain symbolic terms with unknown values. A few methods of determining their values at compile time are evaluated. Array references with coupled subscripts appear quite frequently; these subscripts must be handled simultaneously in a dependence test, rather than being handled separately as in current test algorithms. Nonzero coefficients of loop indexes in most subscripts are found to be simple: they are either 1 or -1. This allows an exact real-valued test to be as accurate as an exact integer-valued test for one-dimensional or two-dimensional arrays. Dependencies with uncertain distance are found to be rather common, and one of the main reasons is the frequent appearance of symbolic terms with unknown values.
Introduction
The key to the success of a parallelizing compiler is to have accurate data depen
ence information on all of the statements in a program. We would like to identify all
of the independent variable references and statements in a program, so they can be
xecuted independently (i.e. in parallel). Several algorithms have been proposed and
used quite successfully in many parallelizing compilers [1], [2], [3], [4], [28], [11]
onetheless, their ability is still limited to relatively simple subscripts. This paper
identifies three factors that could potentially weaken the results of current algorithms
terms with unknown values; (2) coupled subscripts; (3) nonzero and non-
sunity coefficients of loop indices. We discuss the effects of these factors and presen
ome measured results on real programs. We also report some characteristics of data
s
a
dependences found in real programs. The state of the art in data dependence analysi
nd various parallel execution techniques can be examined in light of such informa-
tion. The information can also help to indicate the direction of further improvement in
hose areas. We begin with a brief review of some basic concepts in data dependence
analysis and their effects on parallel execution of programs.
2. Data Dependences
There are three types of data dependences [16]. If a statement, S1, uses the resul
f another statement, S2, then S1 is flow dependent on S2. If S1 can store its result
only after S2 fetches the old data stored in that location, then S1 is antidependent on
2. If S1 overwrites the result of S2, then S1 is output dependent on S2. Data dependences
dictate execution precedence among statements. The following DO loop is an
xample.Example 2.
A
A
In this loop, S1 is flow dependent on S2 because it reads the result of S2 (from the
l
previous iteration). Due to the dependence, the execution of S1 in iteration I must fol
ow the execution of S2 in iteration I-1. S3 is antidependent on S1 and the execution
d
of S3 in iteration I must follow the execution of S1 in iteration I-1. S3 is outpu
ependent on S2 and the execution of S3 in iteration I must follow the execution of S2
F
in iteration I-2. Execution precedence may also be affected by control dependence
or example, an IF statement decides which branch to take. Hence, the statements in
s
the branches cannot be executed before the decision is made. Control dependence i
ot studied in this paper.
In order to speed up program execution on a parallel machine, a parallelizing
compiler can be used to discover independent statements which can be executed i
arallel. DO loops are usually the most important source of such parallelism because
d
they usually contain most of the computation in a program. If there are no depen
ences among the statements in a DO loop, or the dependences are restricted within
the iteration boundaries, different iterations of the loop can be executed concurrently.
xample 2.2
In the above example, although S2 is flow dependent on S1, the dependence is restricted
awithin each iteration (i.e. there is no cross-iteration dependences). Therefore
ll of the iterations in the loop can be executed in parallel. This example shows that a
a
parallelizing compiler not only needs to determine whether data dependence exists, bu
lso needs to analyze whether such dependence prohibits loop parallelization. Many
s
l
transformation techniques (e.g. loop interchange [28] and the detection of Doacros
oops [9]) require even more information about dependences, such as dependence distances
and dependence direction vectors.
If a data dependence occurs across several iterations of a loop, the distance is
s
called its dependence distance (with respect to that loop). All of the data dependence
Example 2.1 have constant distances. For instance, the output dependence between
e
d
and S3 has a distance of 2. If a dependence occurs within the same iteration, th
ependence distance is 0. Note that statements may be nested in a number of loops.
Their dependences may have different distances with respect to different loops.
Example 2.3
END
In the example above, the flow dependence between S1 and S2 has a distance of 1
a
d
with respect to the I loop and a distance of -1 with respect to the J loop. A dat
ependence distance may not always be constant. Consider the following example.
Example 2.4
O
END
The dependence between S1 and S2 has a variable distance. If we use S1  to
e
denote the instance of S1 in iteration i of the I loop and use S2<i,k> to denote th
nstance of S2 in iteration i of the I loop and iteration k of the K loop, then S1<1>
d
should be executed before S2<1,1>, S2<2,1>, ., S2<N,1>; S1<2> should be execute
efore S2<2,2>, S2<3,2>, ., S2<N,2>, and so on. We shall give more examples on
variable dependence distances in Section 4.2.
A dependence direction vector [28] contains several elements, each corresponding
d
a
to one of the enclosing loops. Each element of a dependence direction vector is calle
dependence direction. To simplify the discussion, we take as an example a nest of
a
two loops, where the outer loop has index variable I and the inner loop has index vari
ble J. Suppose as the result of a data dependence between statements S1 and S2, the
r
execution of S1< , > must precede that of S2< , >. The dependence direction fo
r
the J loop is "<", "=", or ">" depending on if we have <
espectively. The dependence direction for the I loop is determined similarly. Note,
however, that since the I loop is the outmost loop, its dependence direction cannot be
>". In Example 2.3, the flow dependence between S1 and S2 has a dependence direction
vector (<, >). In Example 2.4, the flow dependence between S1 and S2 has a
ependence direction vector (<) and a dependence direction vector (=). The two vectors
can sometimes be combined, written as (<=).
Obviously, dependence direction vectors can be used to describe general data
dependences, although they are not as precise as the latter. For many important loop
arallelization and transformation techniques, dependence direction vectors usually provide
nsufficient information. Nonetheless, dependence distances are important to tech
iques such as data synchronization [25], [29], loop partitioning [21], [22], [24], processor
fallocation [9], [23], and processor self-scheduling [12], [26]. As a matter
act, most data synchronization and loop partitioning schemes assume subscripts to
a
d
have a simple form of i+c where i is a loop index and c is a constant. Further, dat
ependences are assumed to have constant distances. If dependences do not have constant
distances, existing schemes either fail or suffer from loss of run-time efficiency.
.2 The Experiment
This empirical study evaluates the complexity of array subscripts and data dependences
pin real programs. Our measurements are done on a dozen Fortran numerica
ackages (Table 1) which have a total of more than a thousand routines and over a
hundred thousand lines of code. This sampling is a mix of library packages (Linpack
ispack, Itpack, MSL, Fishpak) and working programs (SPICE, SMPL, etc. Library
packages are important because their routines are called very frequently in user's pro
rams for scientific and engineering computing. On the other hand, the working programs
may better reflect the array reference behavior in user-written programs
urther study may be needed to distinguish array referencing behavior in library routines
and in working programs. Our code for measurement is embedded in Parafrase
13], which is a restructuring compiler developed at the Center for Supercomputing
Research and Development, University of Illinois at Urbana-Champaign.
Our study differs from previous related works in that we directly measure the
variable references and data dependences, whereas previous works (e.g. [22], [25]
15]) focused on counting the number of statements that can be executed in parallel.
Our work is a preliminary attempt to examine closely the effects of array subscript pat-
erns on some important techniques used at compile time and run time for efficient
parallel execution. We have yet to relate our results to previous results which were
ostly at higher levels, e.g. the statement level. The relationship between those
different levels is certainly an important subject for further study.
Our analysis is presented as follows. In Section 3, we examine the form of array
c
subscripts. We cover three factors that can affect data dependence analysis: linearity
oupled subscripts, and coefficients of loop indices. In Section 4, we show the
e
effectiveness of several well-known data dependence test algorithms. To get som
dea of how often a pair of array references are detected to be independent by these
e
algorithms, we recorded the number of independent array reference pairs detected by
ach algorithm. We also report statistics on data dependence distances. Finally, we
make some concluding remarks in Section 5.
3. Subscripts in Array References
3.1 Linearity of array subscripts
Consider an m-dimensional array reference in a loop nesting with n loops 1
ndexed by I , I , ., I . Normally the reference has the following form:
here: Exp is a subscript expression, 1 - i - m.
A subscript expression has the following form
r
where: I is an index variable, 1 - j - n, a is the coefficient of I , 1 - j - n. b is th
emaining part of the subscript expression that does not contain any index variables.
Note that, following the convention in mathematics, b may be called the constant term
owever, in a nest of loops, it is possible that b may contain some unknown variables
that are updated within the loop. For convenience, we call b the zeroth term.
The above subscript expression is linear if all of its coefficients and its zeroth
s
term are integer constants. Otherwise, it is nonlinear because the subscript expression
ay behave like a nonlinear function with respect to the loop indices. If all of the
f
s
subscript expressions in a reference are linear, we say that the reference is linear. I
ome of the subscript expressions are nonlinear, the reference is partially linear.
Finally, if none of the expressions is linear, the reference is nonlinear.
Virtually all current algorithms for data dependence tests operate on linear subscript
pexpressions. Recently, some symbolic manipulation schemes are proposed fo
artially linear and nonlinear cases [18]. Several restructuring techniques can also be
e
e
used to transform nonlinear subscripts into linear ones. The most notable ones ar
xpression forward substitution, induction variable substitution, and constant folding
(e.g., see [2], [14]).

Table

2 gives an overview of the linearity of array subscripts (i
he 12 numerical packages) after transformation by those techniques. We count only
the references in loops.
From

Table

2, we can see that only 8% of the array references have more than
c
two dimensions (in column 2) and also that 53% of the references are linear (i
olumn 3), 13% are partially linear (in column 4), and 34% are nonlinear (column 5).
The major reason for a subscript expression to be nonlinear is that it contains a
nknown variable (i.e., a non-index variable with an unknown value) or an array ele-
ment. Between the two, Table 3 shows that unknown variables are the major cause.
We found that quite a number of unknown variables are dummy parameters of
subroutines or are related to dummy parameters. Some of them can assume a fixed
alue at run time. The value is normally set by a user before the program is run and
y
s
is transferred from the main program to the subroutines. These variables usuall
pecify the size of a matrix, the number of diagonals, and the number of vectors to be
e
transformed. It has been a common practice to include user assertions to make th
alue of such parameters known to the compiler [8], [15]. As a matter of fact, the
e
value of such parameters usually does not affect the outcome of a data dependenc
est. Often, providing the value mainly helps the data dependence test algorithms to
s
eliminate the same symbolic terms in the subscripts and the loop bounds. Unknow
ymbolic terms may also be eliminated through interprocedural constant propagation
[8]. Further, if data dependence tests could be extended to allow symbolic terms
fixing the value would be unnecessary. For example, [1] presented suggestions about
how to handle symbolic terms. We did not use interprocedural constant propagation
ecause we analyzed procedures separately and did not write driver programs to call
l
subroutines in the packages. We only examined the effect of user assertions on the
inearity of subscripts. Nonetheless, since user assertions often provide the same
f
results as interprocedural constant propagation, our result partly reflects the effect
nterprocedural constant propagation. It is too time consuming to provide user assertions
to more than one thousand routines. Instead, six packages were chosen and
nalyzed with user assertions. These packages are: Linpack, Eispack, Nasa, Baro,
a
Itpack, and Old. Linpack and Eispack were chosen because user assertions were avail-
ble from a previous experiment [15]. The rest of the packages were chosen randomly
Table

4 shows some details of the study. Without the help of user assertions
7% of the one-dimensional array references and 45% of the two-dimensional array
l
a
references were nonlinear. Using user assertions, only 28% of the one-dimensiona
rray references and 15% of the two-dimensional array references remained nonlinear.
l
user assertions, 27% of the two-dimensional array references were partially
inear. Using user assertions, 25% of the two-dimensional array references were partially
linear. Table 4 also shows the number of unknown variables found, including
hose in partially linear references.
For the remaining unknown symbolic terms, we examined the causes. One is that
many nonlinear subscripts showed up in loops with subroutine calls or external func-
ion statements. These nonlinear subscripts cannot be transformed into linear subscripts
using simple forward substitution techniques, unless the call effects of these
tatements are determined by interprocedural analysis. We studied 35 real-valued sub-routines
in the Linpack (there are another 35 complex-valued subroutines in Linpack
hich are almost identical [10]) using summary USE and MOD information to expose
l
call effects [6]. The results on Linpack which are given in Table 5 suggest that non
inear subscripts can be reduced considerably by using interprocedural analysis. Note
that the number of unknown variables include those in partially linear references.
Besides unknown symbolic terms, the next most common reason for nonlinear
subscripts is the presence of an array index which is indirectly an element of an array
he following example is from Linpack, where IPVT(*) is an integer vector of pivot
indices.
Z
There are other various minor reasons for nonlinear subscripts which are omitted here
due to limited space.
3.2 Coupled subscripts
In this section, we study a phenomenon called coupled subscripts which demonstrates
a weakness of current data dependence tests.
To test data dependence between a pair of array references, ideally all array
s
dimensions should be considered simultaneously. However, most current algorithm
est each dimension separately, because a single-dimension test is by far easier. For-
tunately, this often suffices for discovering data independence. However, in cases
here data independence could not be proven by testing each dimension separately, a
s
data dependence has to be assumed. The main reason for those cases is coupled sub
cripts in which a loop index appears in more than one dimension. The following
simple example is from Eispack:
R
In this example, there is no data dependence between the two references to RM1. But
this could be detected only when both dimensions are considered simultaneously.
Of course, to measure how often coupled subscripts actually hurt a single dimension
data dependence test requires testing all dimensions simultaneously to find
enuine data dependences. A few methods are known to be very time consuming.
Recently [19] proposed a new algorithm which is quite efficient. Using the new test
Eispack routines, data independence detection has improved by 10% over using single
dimension tests. [7] discussed a different approach called, linearization, to dealing
ith coupled subscripts.
Here we only measure how often coupled subscripts occur in programs. As we
shall discuss later, coupled subscripts are also a common cause for a dependence to
ave a non-constant distance. We examined all pairs of multidimensional array references
(in the 12 packages) that need to be tested for data dependence. Aliasing effects
ere ignored, so each reference pair is to one array. We did not find four- or five-dimensional
array reference pairs to have coupled subscripts. Table 6 shows the
umber of two- and three- dimensional array reference pairs which have linear or partially
linear subscripts. Table 7 shows that in 9257 pairs of two-dimensional array
eferences that are linear or partially linear, 4105 (44%) of them have coupled subscripts

.3 Coefficients of loop indices
A data dependence exists only when there are integer solutions which satisfy loop
r
s
bounds and other constraints. However, it is very time consuming to obtain intege
olutions in general. Existing algorithms either check integer solutions without considering
sloop bounds or only check real-valued solutions one dimension at a time (e. g.
ee [1], [3], [28]). By doing so, the test can be more efficient, although less effective.
Here we give a brief account of two tests that represent the two approaches.
The GCD test
The GCD test is an integer test that ignores loop bounds. It is based on a well-known
fact that if a Diophantine equation has solutions, then the greatest common
ivisor (GCD) of its coefficients must divide its constant term.
Example 3.1
F
END
or data dependences to exist between S1 and S2 due to the two references to A, the
e
e
subscript of A referenced in S1 (for some values of the index variables) should b
qual to that in S2 (for some other values of the index variables). Hence we can
derive the following Diophantine equation from the subscripts.
he GCD of the coefficients of the variable terms is 2, which does not divide the constant
101. Therefore the equation does not have solutions and there is no data
ependence between S1 and S2 due to the A references.
Banerjee-Wolfe test
Same as the GCD test, the Banerjee-Wolfe test first establishes a Diophantine
s
equation to equate subscripts in two tested array references. However, the test treat
he Diophantine equation as a real valued equation whose domain is a convex set
defined by constant loop bounds and dependence directions. According to the well-
nown intermediate value theorem in real analysis, the real valued equation has solutions
over the given domain if and only if the minimum of the left-hand side is no
reater than zero and the maximum no smaller than zero.
Example 3.2
END
he Diophantine equation for the above example is as follows.
e
Treated as a real function on the domain of 1 - 30, the left-hand side of th
quation has a maximum of -110. Therefore the equation has no solutions and there is
no data dependence between S1 and S2 due to the A references.
Banerjee-Wolfe test was first presented in [3]. [28] produced a new version
s
which includes dependence directions in the function's domain. [1] used another ver
ion which determines dependence levels instead of dependence directions.
s
A test based only on real values is not an exact test in general. Nonetheless, [3
howed that, in a pair of single-dimensional arrays, if all of the nonzero coefficients of
r
loop indices are either 1 or -1, then a data dependence exists if and only if there are
eal solutions to the system derived from their subscript expressions. Obviously, for
multidimensional array reference pairs which do not have coupled subscripts (cf. Sec
ion 3.2), each dimension is independent of each other, so the conclusion will apply.
[19] showed that the conclusion could also apply to two-dimensional array references
ith coupled subscripts. For array references with more than two dimensions,
although the conclusion no longer applies in general, small coefficients do make the
est for integer solutions much easier. For these reasons, we are interested in the magnitude
of coefficients in array references.
The data in Table 8 are from array references (in the 12 packages) which are
linear or partially linear. Notice that the percentage shown there is on a dimension
y-dimension basis. The first column shows the percentage of references which have
e
constant subscripts. The second column shows the percentage of references that hav
onzero coefficients, but they are either 1 or -1. The third column shows the percentage
of references in which some coefficients are greater than 1. The percentage of the
hird case is very small. This result suggests that for single-dimensional references
which are linear or partially linear, real-valued solutions suffice in most cases.
We also checked the coefficients for array reference pairs with coupled subscripts.
As expected, we found that among 4,105 pairs of two-dimensional array references
ith coupled subscripts, most (3,997 pairs, i.e. 97%) have all of their coefficients
being 1 or -1. For three-dimensional array reference pairs with coupled subscripts,
airs (100%) have coefficients of 1 or -1. (Note that, in the single dimension cases, we
r
did make the same examination on subscript pairs. Hence, we could not obtain direc
esults on how often real-valued solutions suffice in single dimension tests)
4. Data Dependences and Data Dependence
Test Algorithms
e
We also did some measurements on the frequency of different data dependenc
ests being used in Parafrase, the number of array reference pairs found to be independent
by each method, and statistics of dependence distances.
.1 The usage frequency of dependence test methods
d
c
As mentioned earlier, different test algorithms have different complexity an
apability. In general, more powerful algorithms can handle more general cases with
r
more accuracy, but they usually require more execution time. Hence, these test algo
ithms are applied hierarchically in Parafrase. Parafrase includes most of the existing
single-dimension test algorithms. Simpler and faster tests are applied first. If they ca
rove neither data independence nor data dependence, other tests are then applied. It
is conceivable that the chance for a test to be used can be affected by the arrangemen
f the test sequence, because the testing task may be accomplished before the test is
r
e
used. It was unclear to us what test sequence would achieve the best compile
fficiency. We did not alter the one chosen in Parafrase. That sequence is described
in the following to facilitate understanding of our statistics.
First we explain the input and output of the tests. Parafrase usually retests data
e
dependences for a pass that needs the dependence information. As a result, the sam
air of references may be tested in different passes, undergoing the same test sequence
e
d
described below. However, different passes may require to check different dependenc
irection vectors. The input to the tests is a pair of array references, a loop nesting
e
c
that encloses either of the references, and a dependence direction vector relevant to th
urrent pass. The output is an answer to whether data dependence exists under the
d
constraint of the dependence direction vector. If the answer is uncertain, data depen
ence is assumed.
The test sequence
both subscripts in a reference pair are constants, then the Constant Test is per-
formed, which simply compares the two constants. If they are not equal, there is
dependence. Otherwise, dependence is assumed for this dimension and the
test proceeds to the next dimension.
If (1) does not apply, then the Root Test is performed. The Root Test is a
Banerjee-Wolfe test disregarding the constraint of the given dependence direction
ector. If it reports data independence, the test terminates. Otherwise, it
proceeds to either test (3), test (4), or test (5), depending on the loop nesting.
test (2) did not prove data independence and both references are in the same
e
singly nested loop, the Exact Test [4], [28] is performed. In this case, th
iophantine equation derived from the subscripts has at most two unknowns;
d
hence it can be determined exactly whether the dependence exists. If dependence
oes not exist, the test terminates. Otherwise, it proceeds to test (5).
s
test (2) did not succeed and test (3) does not apply, but each subscript contain
at most one loop index with a nonzero coefficient, then the GCD test [4] is per-
formed. If independence is proven, the test terminates; otherwise, it proceeds to
est (5). We have three remarks here.
(Remark 1) In test (3), the Exact Test could be extended to determine exactly
what dependence directions are possible. However, Parafrase chooses to disre
ard dependence directions in the Exact Test. Instead, it uses the Theta Test in
(5) to examine the given dependence directions.
Remark 2) The Exact Test could be extended and to be used in test (4) where
s
e
both indices may not be the same. But we did not measure the result of thi
xtension.
(Remark 3) The GCD test could be applied to any subscript. However, if there
d
are more than two unknowns in the equation, it is very likely that the common
ivisor of their coefficients would equal 1, which is not useful for the test
(because 1 can divide any number).
If none of (1), (3) and (4) applies, or (3) did not prove independence, then the
d
Theta Test is performed. It is a Banerjee-Wolfe test that uses the given depen
ence direction vector as a further constraint. Thus it is more accurate than the
e
Root Test in (2). It would either show that the given dependence directions ar
mpossible (in this case, the test terminates), or conclude that some of the directions
bare possible. In the latter case, if "=" direction is the only remaining possi
le direction for every loop, the All Equal Test in (6) is performed. Otherwise,
the test proceeds to the next dimension.
Test enters here from (5). At this point, "=" is the only remaining possible direction
for every loop. This corresponds to a dependence which crosses no loop
teration. The All Equal Test is performed to see if such a direction vector contradicts
ethe program's control flow. If all possible execution paths from the refer
nce r1 to r2 need to cross an iteration of any loop, then dependence could not
exist from r1 to r2 with an "all equal" direction. In other words, independence is
roven. Otherwise, dependence is assumed. Test proceeds to the next dimension.
Following the above test steps, we measured the usage frequency and the
ndependence detection rate of the single dimension tests in Parafrase. Table 9 gives
the measured results. These data are obtained by running each program through
arafrase for detecting Doall loops (i.e. the loops without cross-iteration data depen-
dences). The independence detection rate is the rate a particular test method detects
ndependence between a reference pair, under the constraints of given dependence
s
direction vectors. If a method detects data independence before others have been used
uccess is counted only for this method, even though other methods used next could
potentially detect independence as well. From Table 9, some useful observations ca
e made. Overall, the above test sequence was applied 119,755 times, which is the
sum of the using frequencies of the Constant Test and the Real Root Test. Summing
he independences proven by each method together, we have 50,625 independences in
c
total. This represents an overall independence detection rate of 44%. One can als
ompute the percentage of the independences detected by each test method over the
l
total independences to get an idea of the contribution by each method (in this particu
ar test sequence). It is very important to note that the test sequence was only applied
to linear subscripts or partially linear subscripts.
We mentioned earlier that the same pair of references may be tested repeatedly
l
under different constraints of dependence direction vectors and in different passes. Al
ses of each test method are counted cumulatively, so are its independence detection
s
successes. They are counted cumulatively because all the uses are required and eac
uccess contributes to a certain parallelization technique. Recall, for instance, that
d
even if data dependence exists between two statements, absence of cross-iteration
ependence directions (i.e. "<" and ">") would allow parallel execution of different
loop iterations.
We point out that the All Equal Test benefits from the Theta Test whenever the
latter reduces the original dependence direction vector to one of "all equal" directions
he All Equal Test is a good example of using information of control flow within a
e
loop body to sharpen data dependence analysis. It would be interesting to measur
ow often independences are detected by the Theta Test and the All Equal Test jointly
but not by either one alone.
Our result can certainly be refined by further study. For example, the capability
s
of each test method can be evaluated more precisely by applying it first in the tes
equence.
3.2 Data dependence distance
As mentioned earlier, many data synchronization schemes and loop partitioning
techniques assume constant dependence distance. Constant dependence distance als
akes loop scheduling on Doacross loops more effective. Complicated dependence
e
d
patterns are very difficult to handle efficiently. Moreover, dependence distances ar
ifficult to determine if subscript patterns are complicated. As a matter of fact, many
e
d
parallelization techniques (e.g., [22], [24], [27]) which require constant dependenc
istances assumed the following three conditions for array subscripts and loop nesting:
a
(1) Each reference has subscripts of the form a*i+c where i is a loop index, and c and
are constants. Note that if more than one loop index appears in a subscript expres-
Tsion, the dependence at the outer loop level is likely to have varied distances. (2
here are no coupled subscripts (cf. Section 3.2). (3) Nonzero coefficients are the
same in the same dimension.
(1) can be explained by the following example.
Example 4.1
A
END
For S1 and S2 in the above example, the dependence distance with respect to the
f
c
I loop is variable. The dependence distance with respect to the J loop is I which
ourse remains fixed within an outer loop iteration, but changes when I increments.
Condition (2) can be explained by another example.
xample 4.2
A
END
For S1 and S2 in the above example, the dependence distance with respect to the I
loop is variable. The dependence distance with respect to the J loop is 1. But to find
ut this, both dimensions need to be considered simultaneously.
A
Example 2.4 in Section 2 explained condition (3).
lthouth exceptions can be found for each of the three conditions, our tests
d
looked for such simple forms in real programs. If any condition is not satisfied, we
id not pursue more sophisticated algorithms to determine whether the distances are
e
c
constant but leave the distances as uncertain instead. The only exception is when w
ould determine that "=" is the only possible dependence direction for a loop, in which
case the corresponding dependence distance is zero.
We first determine the common nest loops for an array reference pair. Then we
d
measure the dependence distance for each common nest loop. We divide the depen
ence distances into four classes:
Zero: The dependence does not cross loop iterations. It occurs within an
U
iteration.
nity: The dependence crosses one iteration (either forward or backward).
r
Constant: The dependence crosses a constant number (> 1) of iterations (eithe
forward or backward).
Uncertain: The dependence distance is not constant or cannot be decided in our
O
experiment.
ur measurement shows that 73% of the array references with linear or partially
s
linear subscripts have the i+c form. However, not many dependence distances are con
tant. The results of dependence distance measurement are presented in Table 10.
e
Note that distance is measured for every loop common to a pair of dependent refer-
nces, because of its definition and its usage. The main reasons for uncertain distance
r
s
are (1) loops not common to both references, (2) coupled subscripts, and (3) nonlinea
ubscripts. Note also that a good symbolic dependence test could help to reduce the
d
number of nonlinear subscripts and hence could reduce the cases of uncertain depen
ence distance. A study can be pursued further by counting the cases for different reasons

5. Conclusion
l
We presented some measurements critical to data dependence analysis and DO
oop parallel execution. We found that quite a few array references are not amenable
to current data dependence test methods. Although we do not have the data to show
how many of those failed tests really have data dependences, more efficient and more
accurate tests are certainly very desirable.
We discovered that a lot of subscripts become nonlinear because of unknown
r
terms. User assertions and interprocedural analysis can be used effectively t
educe unknown symbolic terms (see Tables 3, 4, 5). A more sophisticated and yet
efficient symbolic manipulation scheme could be very useful, since a significan
umber of nonlinear subscripts still remain (Table 5).
s
We also discovered that a significant number of reference pairs have coupled sub
cripts (Table 7), which could cause the inaccuracy in the current dependence test
algorithms. Efficient algorithms are needed to handle such subscripts.
A welcome result is that an overwhelming majority of nonzero coefficients are
e
a
either 1 or -1 (Table 8), which allows more efficient real-valued tests to be as accurat
s integer-valued tests [5], [19]. It also makes the test on array references with higher
dimensions much easier.
We reported the measurements on the usage frequencies and independence detection
urates of several well-known data dependence test methods (Table 9). Those meas
rements followed the testing sequence in Parafrase. Data dependence distance is also
f
measured between each dependent reference pair (Table 10). The large percentage
ncertain dependence distances (over 86%) suggests that more sophisticated algorithms
s
are needed for distance calculation. It also calls for more effective schemes for data
ynchronization and DO-loop scheduling. However, in our measurements, we did not
separate numerical libraries from user programs. It is conceivable that, because of the
enerality in library routines, there might be more unknown symbolic terms than in
user programs. In our study, we have more numerical packages than user programs
ence the statistics might be more biased toward library routines than toward user pro-
grams. In the future studies, it would be interesting to see if there are differences
etween these two groups of programs.

Acknowledgement

We thank the referees for their careful reading and insightful comments, whic
ave helped us to improve the paper significantly.
J. R. Allen, "Dependence analysis for subscripted variables and its application to
e
program transformations," Ph.D. dissertation, Department of Mathematical Sci
nce, Rice University, Houston, TX, April 1983.
r
J. R. Allen and K. Kennedy, "Automatic translation of Fortran programs to vecto
form," Dept. of Computer Science, Rice University, Houston, TX, Rice Comp
TR84-9, July, 1984.
[3] U. Banerjee, "Data dependence in ordinary programs," Department of ComputerSciences, University of Illinois at Urbana-Champaign, Rpt. No. 76-837, Nov
976.
[4] U. Banerjee, "Speedup of ordinary programs", Ph.D. dissertation, University of
Illinois at Urbana-Champaign, DCS Rpt. No. UIUCDCS-R-79-989, 1979.
5] U. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publish-
ers, Norwell, Mass., 1988.
J. Banning, "A method for determining the side effects of procedure calls," Ph.D.
dissertation, Standford University, Aug. 1978.
7] M. Burke and R. Cytron, "Interprocedural dependence analysis and paralleliza-
tion," Proc. of the ACM SIGPLAN'86 Symposium on Compiler Construction
CM SIGPLAN Not., Vol. 21, No. 7, pp. 162-175, July 1986.
[8] D. Callahan, K. Cooper, K. Kennedy, and L. Torczan, "Interprocedural constan
propagation," Proc. of the ACM SIGPLAN '86 Symp. on Compiler Construction,
ACM SIGPLAN Not., Vol. 21, No. 6, June 1986.
9] R. G. Cytron, "Compile-time scheduling and optimization for multiprocessors,"
U
Ph.D. dissertation, University of Illinois at Urbana-Champaign, DCS Rep
IUCDCS-R-84-1177, 1984.
[10] J. Dongarra, J. Bunch, C. Moler, and G. W. Stewart, LINPACK Users' Guide,
SIAM, Philadelphia, 1979. Spring-Verlag, Heidelberg, 1976.
J. A. Fisher, J. R. Ellis, J. C. Ruttenberg, and A. Nicolau, "Parallel processing: A
smart compiler and a dumb machine," Proc. of the ACM SIGPLAN '84 Symp.
ompiler Construction, SIGPLAN Notices Vol. 19, No. 6, June 1984.
r
[12] Z. Fang, P. Yew, P. Tang, and C. Zhu, "Dynamic processor self-scheduling fo
general parallel nested loops," Proc. 1987 Int'l. Conf. on Parallel Processing
(August, 1987), pp. 1-10.
13]D. Kuck, R. Kuhn, B. Leasure, and M. Wolfe, "The structure of an advanced vec-
ttorizer for pipelined processors", Proceedings of COMPSAC 80, The 4th Interna
ional Computer Software and Applications Conference, October 1980, pp. 709-
715.
14]D. Kuck, R. Kuhn, D. Padua, B. Leasure and M. Wolfe, "Dependence graphs and
f
compiler organizations", Proceedings of the 8th ACM Symposium on Principles
rogramming Languages, Williamsburgh, VA, January 1981, pp. 207-218.
[15] D. Kuck, A. Sameh, R. Cytron, A. Veidenbaum, et al. "The effects of progra
restructuring, algorithm change, and architecture choice on program performance,"
Proc. 1984 Int'l. Conf. on Parallel Processing, pp. 129-138, August 1984.
16]D. Kuck, The Structure of Computers and Computations, Vol. 1, John Wiley and
Sons, New York, 1978.
17]D. J. Kuck, Y. Muraoka, and S.-C. Chen, "On the number of operations simultaneously
executable in Fortran-like programs and their resulting speedup," IEEE
rans. Compt., vol. c-21, No. 12, pp. 1293-1310, Dec. 1972.
[18] A. Lichnewsky and F. Thomasset, "Introducing symbolic problem solving tech
niques in the dependence testing phases of a vectorizer," Proc. 1988 Int'l. Conf.
on Supercomputing, July, 1988.
19]Z. Li, P.-C. Yew, and C.-Q. Zhu, "An efficient data dependence analysis for parallelizing
pcompilers," IEEE Trans. Parallel and Distributed Systems, vol. 1, No. 1
p. 26-34, Jan. 1990.
[20] A. Nicolau and J. A. Fisher, "Measuring the parallelism available for very long
-instruction word architectures," IEEE Trans. Comput., vol. c-33, No. 11, pp. 968
76, Nov. 1984.
[21] D. A. Padua, "Multiprocessors: Discussions of some theoretical and practical prob-
lems," Ph.D. dissertation, University of Illinois at Urbana-Champaign, DCS Rep
IUCDCS-R-79-990, Nov. 1979.
[22] J.-K. Peir, "Program partitioning and synchronization on multiprocessor systems,"
U
Ph.D. dissertation, University of Illinois at Urbana-Champaign, DCS Rep
IUCDCS-R-86-1259, Mar. 1986.
[23] C. D. Polychronopoulos, D. J. Kuck, and D. A. Padua, "Optimal processor allocation
Pof programs on multiprocessor systems," Proc. 1986 Int'l. Conf. on Paralle
rocessing, Aug. 1986.
[24] W. Shang and J. A. B. Fortes, "Independent partitioning of algorithms with uniform
dependencies," Proc. 1988 Int'l. Conf. Parallel Processing, Aug. 1988, pp
6-33.
[25] B. J. Smith, "A pipelined, shared resource MIMD computer," in Proc. 1978 Int'l.
Conf. Parallel Processing, Aug. 1978, pp. 6-8.
26] P. Tang, P. Yew, and C. Zhu, "Impact of self-scheduling order on performance of
,multiprocessor systems," Proc. of ACM 1988 Int'l. Conf. on Supercomputing (July
[27] P. Tang, P. Yew, and C. Zhu, "Algorithms for generating data-level synchronization
sinstructions," Center for Supercomputing Research and Development, Univer
ity of Illinois at Urbana-Champaign, Rpt. No. 733, Urbana, January, 1988.
[28] M. J. Wolfe, "Optimizing Supercompilers for Supercomputers", Ph.D. dissertation
University of Illinois at Urbana-Champaign, DCS Rpt. No. UIUCDCS-R-82-1105,
October 1982.
29]C. Q. Zhu and P. C. Yew, "A scheme to enforce data dependence on large multiprocessor
systems," IEEE Trans. Software Eng., vol. SE-13, pp. 726-739, June
# Package Description Subroutines Lines
LINPACK Linear system package
ISPACK Eigensystem package 70 11700ITPACK 68 559
Sparse matrix algorithms (iterative
methods)
SL Mathematic science library (CDC) 407 20473FISHPAK 159 2264
Separable elliptic partial differential equations
package
CM Random algorithms from ACM 25 2712B
OLD Checon Chebyshev economization program 74 321
ARO Shallow water atmospheric model 8 1052S
NASA Program from NASA 4 78
MPL Flow analysis program 15 2072S
WEATHER Weather forecasting program 64 391
PICE Circuit simulation program 120 17857 #
Total 1074 102195 #

Table

1. Analyzed Fortran packages
# Dim.



--R

Linear Partially linear nonlinear




Table 2.
Array element
Table 3.



dimensions Undefined Defined



Table 4.
dimension Undefined Defined Def.
Total array references 623 623 623
references w/ nonlinear subscripts 305

dimensions Undefined Defined Def.
Total array references 250 250 250
references w/ nonlinear subscripts
eferences w/ partially linear subscripts 67 27


Table 5.
Total array reference pairs 18698 2867

Table 6.
Pairs w/ linear/partially linear subscripts 9257 2798
Pairs w/ coupled subscripts (linear) 2935
airs w/ coupled subscripts (partially linear) 1170 13
Table 7.




Table 8.
with linear or partially linear subscripts
Test method Usage frequency Indep.
Table 9.
detection rate of various dependence test methods
--TR
Interprocedural constant propagation
Interprocedural dependence analysis and parallelization
Program partitioning and synchronization on multiprocessor systems
A scheme to enforce data dependence on large multiprocessor systems
Introducing symbolic problem solving techniques in the dependence testing phases of a vectorizer
Impact of self-scheduling order on performance on multiprocessor systems
Parallel processing
Dependence Analysis for Supercomputing
Dependence graphs and compiler optimizations
Structure of Computers and Computations
An Efficient Data Dependence Analysis for Parallelizing Compilers
A method for determining the side effects of procedure calls.
Speedup of ordinary programs
Multiprocessors
Dependence analysis for subscripted variables and its application to program transformations
Optimizing supercompilers for supercomputers
Compile-time scheduling and optimization for asynchronous machines (multiprocessor, compiler, parallel processing)

--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
Reiner W. Hartenstein , Karin Schmidt, Combining structural and procedural programming by parallelizing compilation, Proceedings of the 1995 ACM symposium on Applied computing, p.130-134, February 26-28, 1995, Nashville, Tennessee, United States
Zhiyuan Li, Compiler algorithms for event variable synchronization, Proceedings of the 5th international conference on Supercomputing, p.85-95, June 17-21, 1991, Cologne, West Germany
Dan Grove , Linda Torczon, Interprocedural constant propagation: a study of jump function implementation, ACM SIGPLAN Notices, v.28 n.6, p.90-99, June 1993
Niclas Andersson , Peter Fritzson, Generating parallel code from object oriented mathematical models, ACM SIGPLAN Notices, v.30 n.8, p.48-57, Aug. 1995
Venugopal , William Eventoff, Automatic transformation of FORTRAN loops to reduce cache conflicts, Proceedings of the 5th international conference on Supercomputing, p.183-193, June 17-21, 1991, Cologne, West Germany
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 P. Gerlek , Eric Stoltz , Michael Wolfe, Beyond induction variables: detecting and classifying sequences using a demand-driven SSA form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.85-122, Jan. 1995
On Effective Execution of Nonuniform DOACROSS Loops, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.463-476, May 1996
Manish Gupta , Prithviraj Banerjee, PARADIGM: a compiler for automatic data distribution on multicomputers, Proceedings of the 7th international conference on Supercomputing, p.87-96, July 19-23, 1993, Tokyo, Japan
Kuei-Ping Shih , Jang-Ping Sheu , Chih-Yung Chang, Efficient Address Generation for Affine Subscripts in Data-Parallel Programs, The Journal of Supercomputing, v.17 n.2, p.205-227, Sept. 2000
Michael Wolfe, Beyond induction variables, ACM SIGPLAN Notices, v.27 n.7, p.162-174, July 1992
E. Christopher Lewis , Calvin Lin , Lawrence Snyder, The implementation and evaluation of fusion and contraction in array languages, ACM SIGPLAN Notices, v.33 n.5, p.50-59, May 1998
Michael O'Boyle , G. A. Hedayat, A transformational approach to compiling Sisal for distributed memory architectures, Proceedings of the 6th international conference on Supercomputing, p.335-346, July 19-24, 1992, Washington, D. C., United States
Vivek Sarkar , Guang R. Gao, Optimization of array accesses by collective loop transformations, Proceedings of the 5th international conference on Supercomputing, p.194-205, June 17-21, 1991, Cologne, West Germany
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
C. Koelbel , P. Mehrotra, Compiling Global Name-Space Parallel Loops for Distributed Execution, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.440-451, October 1991
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
Guohua Jin , Zhiyuan Li , Fujie Chen, An Efficient Solution to the Cache Thrashing Problem Caused by True Data Sharing, IEEE Transactions on Computers, v.47 n.5, p.527-543, May 1998
Yunheung Paek , Jay Hoeflinger , David Padua, Efficient and precise array access analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.1, p.65-109, January 2002
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
Partitioning and Labeling of Loops by Unimodular Transformations, IEEE Transactions on Parallel and Distributed Systems, v.3 n.4, p.465-476, July 1992
Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, ACM SIGPLAN Notices, v.26 n.6, p.15-29, June 1991
Patricio Buli , Veselko Gutin, An extended ANSI C for processors with a multimedia extension, International Journal of Parallel Programming, v.31 n.2, p.107-136, April
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
integer-valued test;parallelizing compilers;fortran programs;FORTRAN;program transformations;program characteristics;data dependence analysis;program compilers;index termsarray references