Redundant Synchronization Elimination for DOACROSS Loops.
AbstractCross-iterations data dependences in DOACROSS loops require explicit data synchronizations to enforce them. However, the composite effect of some data synchronizations may cover the other dependences and make the enforcement of those covered dependences redundant. In this paper, we propose an efficient and general algorithm to identify redundant synchronizations in multiply nested DOACROSS loops which may have multiple statements and loop-exit control branches. Eliminating redundant sychronizations in DOACROSS loops allows more efficient execution of such loops. We also address the issues of enforcing data synchronizations in iterations near the boundary of the iteration space. Because some dependences may not exist in those boundary iterations, it adds complexity in determining the redundant synchronizations for those boundary iterations. The necessary and sufficient condition under which the synchronization is uniformly redundant is also studied. These results allow a parallelizing compiler to generate efficient data synchronization instructions for DOACROSS loops.
Introduction
Concurrent execution of loops with cross-iteration data dependences, termed DOACROSS loops, allows us to exploit
more loop-level parallelism beyond the vector loops and the DOALL loops in application programs. As the machine size is
becoming larger, exploitingmore parallelism in a programbecomes more important. However, efficient data synchronization
is required to support such an execution model. Some commercially available multiprocessors such as the Alliant FX series
already provide architectural and hardware support for executing DOACROSS loops efficiently.
There can be many cross-iteration data dependences in a DOACROSS loops. Each of such data dependences needs to
be enforced by explicit synchronization in order to satisfy the original memory access order in the program. However,
many of such synchronizations are redundant because of the transitive nature of the data dependences between statements.
Eliminating such redundant data synchronization has several advantages.
First, having fewer data synchronizations allows us to use the system resources, such as the synchronization registers in
the Alliant machines, more effectively. Second, data synchronization usually requires long communication delays between
processors. Fewer synchronizations will cause fewer processor stalls. Third, fewer data synchronizations mean fewer
synchronization instructions need to be generated, which can make the code size smaller.
In this paper, we propose an efficient algorithm to identify redundant synchronizations in multiply-nested DOACROSS
loops which very often have multiple statements in their loop body. We also address the nonuniformity in the redundancy
on the boundary iterations in the multidimensional iteration space, which is caused by the possible backward dependence
directions in some inner loop levels. The nonuniformity in redundancy can make the enforcement of such data dependences
very complicated. A necessary and sufficient condition to identify redundant synchronization that does not have a nonuniformity
problem is also presented in the paper. Our presentation is organized as follows. In Sections 2 and 3, we describe
our algorithms, starting with the single loop and following with multiple loop cases. Discussions and a summary of previous
research in this area are given in Section 4. Section 5 concludes our presentation.
tree edge
forward edge
(d) SEODFS search tree
(b) Control Path Graph (CPG)
(c) Iteration Space Dependence Graph (ISDG)
DO I=1,100
END DO
(a) Single loop

Figure

1: Simple loop example.
redundant synchronization elimination
2.1 Loops with straight control flow
We first look at a simple case of a singly-nested loop with no branches in its loop body (Figure 1a). To identify redundant
synchronizations among statements of different iterations, we build a Control Path Graph (CPG). The CPG of the loop is
a two-dimensional graph where each column represents an iteration, and the nodes in a column are the statements of the
iteration. Because we assume each iteration of the DOACROSS loop is executed sequentially in one processor, there is a
control flow edge from one statement to its immediate successor in the same iteration (represented by the broken edges in
Figure 1b). The solid edges represent loop-carried (cross-iteration) data dependences. The number of rows is determined
by the number of statements in one iteration while the number of columns is is the longest distance
of all data dependences. The loop in Figure 1a has loop-carry data dependences of distances 1 and 2. Figure 1b shows the
corresponding CPG in the shaded area. There are three columns because 2. [8] shows that to identify redundant
data dependences in a single loop, we only need to examine
In [4], Krothapalli uses a Sequential Execution Order Depth First Search (SEODFS) algorithm on an Iteration Space
Dependence Graph (ISDG), where the entire loop body of an iteration is represented by a single node in the ISDG. An edge
exists between two nodes if there is any loop-carried dependence between the two iterations. The ISDG of the simple loop
can be obtained by collapsing the nodes in each column of the CPG in Figure 1b into one "big" node as in Figure 1c. It is very
important to note that every iteration in Figure 1b and Figure 1c has the same incoming edges and outgoing edges except
the first (last) few iterations where some incoming (outgoing) edges are missing because of nonexisting dependence sources
One important characteristic of ISDG is that it is acyclic. Otherwise, an iteration would have to be executed both
before and after another same iteration. A SEODFS differs from a normal Depth-First Search (DFS) in that the successors
at the same depth level are examined according to their sequential execution order in the loop. An edge is marked as one of
the following (see Figure 1d):
ffl a tree edge, if it is on the searching path during the SEODFS, or
ffl a forward edge, if there is already a path formed by the tree edges from its tail node to its head node, or
ffl a cross edge, if it is neither a tree edge nor a forward edge.
The goal of the SEODFS is to find all of the forward edges from the first iteration in the ISDG. It starts the search from
the node representing the first iteration. A forward edge represents a transitive edge that corresponds to a redundant
synchronization because, by its definition, there is a path (formed with tree edges) from its tail (i.e., the dependence source)
to its head (i.e., the dependence sink).
Now let us see how we can extend the SEODFS to a CPG. A CPG is also acyclic, similar to an ISDG, Here are some
observations:
1. For each node in a CPG, its successor in the same column is always searched before the other successors.
2. It is very important to note that all of the columns (i.e., all of the iterations) have the same dependence pattern. We
only need to identify the forward edges from the nodes in the first column.
3. There is no cross edge from the nodes in the first column.
The algorithm performing the DFS on a CPG is shown in Figure 2. From the first observation above, we know that when a
node is reached, all nodes below it in the same column must be traversed before any node in other columns is traversed. For
/* This procedure performs DFS and marks the redundant dependences. The procedure should be invoked by calling check(0,0).
Due to the depth-first nature of the procedure, the process checking for the forward edges is actually performed
starting from the last statement of an iteration. Mark[iter ] is a marker for each iteration to mark the progress
of the checking in each iteration. It is initialized to be N is the total number of statements in the loop body */
procedure check (iter ,start )
begin
mark [iter ]=start ;
for (i =statement N downto statement start ) begin
for (m =all of the dependences with i as their source in the sequential execution order ) begin
sink iter =iter +dist [m ];
if (sink iter >Dmax ) then do nothing; /* it is out of range */
else if (mark [sink iter ]- sink [m ]) then /* if sink has been visited*/
if (iter ==0) then /* we only check the dependences from iter 0 */
mark the dependence m as redundant;
else check (sink iter ,sink [m ]);
/* sink [m ] is first reached, do recursive examination */
end for
end for
procedure check .

Figure

2: DFS algorithm for CPG.
each column, we use a marker to record the statement we have just traversed in the column. The markers are initialized to
be below the last statement in each column. If an edge whose head statement is lexically later than the marked statement of
that column, the edge is a forward edge because according to the DFS algorithm in Figure 2, the head statement must have
been visited before, and hence there must be an alternative path from the tail statement to the head statement of the edge.
We can mark the edge a forward edge which corresponds to a redundant synchronization.
Because every edge will be traversed at most once, the time complexity of this algorithm is O(n 2 ) where n is the number
of nodes in the CPG. The storage used is proportional to the sum of the number of dependences and to the number of
columns in the CPG. Checking for redundant synchronizations is started with check(0; 0).
2.2 Loops with multiple control flows
In this section, we show a general algorithm handles the control branches in a loop. However, we assume there are no
exit-loop branches in the loop. Such statements abort loop execution and are discussed in Section 4. With branches, there
can be more than one control flow path for each iteration. We have to examine every possible control flow path to make
sure that a synchronization is really redundant in all paths. In [8], the author showed that examining CPGs with all possible
control flow combinations in the windows of Dmax iterations is necessary and sufficient for determining all redundant
synchronization in a single loop. Our algorithm is based on the same approach but it also incorporates the DFS algorithm
in the previous section to make the checking of each case easier. We need to identify all possible paths in one iteration
and record them in path[][], where path[i][j] is the jth statement in path i. Another array ipath[][] acts as
an inverse function of path where ipath[path[i][j]][i]=j. The sequence number of a statement s in path i is
given by ipath[s][i]. Finally, iter path[i] gives the control flow path assumed by iteration i in the current CPG.
If there is a total of Pcount+1 possible control flow paths in one iteration, the value of iter path[] will range from
0 to Pcount. We also assume that there is no backward jump in the loop so that all of the possible control flow paths
can be found with a variation of the depth-first traversal. Figure 3 shows the general algorithm. The algorithm starts with
cond check(0). When the examination is finished, synchronization for the dependence m is redundant if count[m] is
zero.
3 Doubly-nested loop redundant synchronization elimination
In this section, we extend the single loop algorithm to multiply-nested loops. In a single loop, there is only one dimension
in the iteration space and all data dependences must point forward. Therefore, if the source and the sink of a dependence
fall within the iteration space, all of the iterations between the source and sink iterations are within the iteration space.
In a multiply-nested loop, dependences can have a negative direction in some nesting levels other than the outmost level.
Synchronization for a dependence that is redundant in the middle of the iteration space may not be redundant in the boundary
iterations because some necessary intermediate iterations may be outside of the iteration space. It causes the redundant
synchronization checking to be different (or nonuniform) when we are in the boundary iterations of the iteration space.
In [4], it is shown that in a doubly-nested loop, if the inner loop has at least pmax +anmin +1 iterations, where pmax is the
most positive distance and anmin is the absolute value of the most negative distance in the inner loop, then the redundancy
checking is uniform and the redundant synchronization found can be covered in all iterations. However, as pointed out in
[11], this is true only when the loop body has only a single statement or the synchronization is done at the iteration level
instead of at the statement level. It is because in a CPG, the alternative path to cover a redundant synchronization has to
consider the lexical order of the statements while in a ISDG, all statements in an iteration have been grouped together.
procedure check (iter ,start )
begin
u =ipath [N ][iter path [iter ]]; /* get the sequence number of the last statement N */
=ipath [start ][iter path [iter ]]; /* get the sequence number of the statement start */
mark [iter ]=start ;
for (n =u downto v ) begin
=path [iter path [iter ]][n ]; /* i is the current statement under examination */
for (m =all of the dependences with i as the source in the sequential execution order ) begin
sink iter =iter +dist [m ];
if (sink iter >Dmax ) then do nothing; /* it is out of range */
else if (m 's sink is not in this CPG) then do nothing;
else if (mark [sink iter ]- sink [m ]) then /* if sink is covered */
if (iter ==0) then /* we only examine dependences from iteration 0 */
count [m ]++; /* m is redundant in this CPG */
else check (sink iter ,sink [m ]);
/* sink [m ] is first reached, do a recursive examination */
end for
procedure check .
procedure cond check (iter )
begin
/* try all possible flow paths for this iteration */
for (p
iter path [iter ]=p ;
/* if not the last iter, call recursively */
if (iter <Dmax ) then cond check (iter +1);
else begin
/* this is the last iter, perform redundancy check */
all markers to the bottom */
for (i =all dependences from nodes of the first iteration) begin
/* record all the dependences need to be checked */
if (the source and the sink of dependence i are both on the control flow path being examined)
count [i ]\Gamma\Gamma;
check (0,0); /* start checking */
end for
procedure cond check .

Figure

3: DFS algorithm for loops with branches.
Therefore, an alternative path in the ISDG does not imply an alternative path in the corresponding CPG. A restricted
algorithm for the loops with multiple statements is proposed in [11]. It can find a subset of redundant synchronizations that
are guaranteed to be redundant throughout the entire iteration space. Unfortunately, that algorithm could also miss many
synchronizations that are redundant throughout the iteration space.
In this section, we propose a new scheme to identify all uniformly redundant synchronizations in a multiply-nested loop
with multiple statements in each iteration. This scheme is based on a necessary and sufficient condition that determines
when a synchronization is uniformly redundant. We use a doubly-nested loop for illustration. However, it can be easily
extended to multiply-nested loops. Without loss of generality, we also assume the dependence distances of both loop levels
are positive. Because our goal is to determine how large an area in iteration space we have to use to generate the CPG for
our DFS algorithm, we will show the dependence distance vector space and the iteration space where each node (or point) is
an iteration, but the CPG and the DFS algorithm presented in Figure 3 are used when identifying redundant synchronization.
It is because our DFS algorithm works on CPG to handle loops with multiple statements, and the synchronization is done at
the statement level instead of at the iteration level.
3.1 Dependence slope and synchronization chain
First, given a data dependence, we determine what areas need to be checked for the uniform redundancy of the
synchronization.
a dependence has the source (i and the sink (j in the iteration space, then it has a dependence
distance vector ~
Definition 2 The dependence slope of a dependence distance vector ~
D is defined as
possible dependence slopes are in the interval (\Gamma1; +1].
The first component of a valid dependence distance vector has to be positive or zero, that is, we must have to have
a valid loop execution order. When it is zero (j second component has to be a positive integer or zero, that is,
Hence, a slope of \Gamma1 is not possible.
region 1 region 2
region 3
region 4
outer loop index I
inner loop index J
(1)
(2)
E(b/M,b)
y-axis
x-axis
x=a

Figure

4: A 2-D dependence distance vector space.
\Gammam \Theta

Figure

5: Line equations.

Figure

4 shows a dependence represented by a dependence distance vector ~
in a 2-D dependence vector space.
Let S denote the set of all dependence distance vectors in the loop and M (\Gammam) be the maximal (minimal) value of all of
the dependence slopes. The four lines (1), (2), (3), and (4) in Figure 4 are defined by the equations in Figure 5. The four
intersections are points ~
O(0; which form a parallelogram. There are also four regions
in

Figure

4 that are specified in Figure 6.
These regions are well defined when M 6= +1. When regions 1 and 4 are empty sets. It is easy to see that
the union of the four regions and the parallelogram ADCO always include all points between lines
checking for redundant synchronization in a doubly-nested loop, the areas to the left of and to the right of x = a can
region 2
x - a
region 3
region 4
x - a

Figure

Defnitions for regions in Figure 4.
be ignored.
synchronization chain in the dependence distance vector space is a path P which consists of an ordered set
of points f~p i (a ng in the space where each segment ( ~
dependence vector in S.
Lemma 1 In Figure 4, there exists no synchronization chain from the point ~
O to a point ~
G in region 1.
region 1 is empty and the lemma is true. Otherwise, M 6= +1. Suppose there is a synchronization
chain P from ~
O to ~
G is in region 1. Let is the maximum of the
dependence slope and each segment (a in P is in S, b
(b
which contradicts the fact that ~
G is in region 1. Hence there is no synchronization chain from ~
O to a point ~
G in region 1 of

Figure

4. 2
Lemma 2 In Figure 4, there exists no synchronization chain from a point ~
G in region 2 to the point ~
D.
Proof: From observation 1, \Gammam 6= \Gamma1. Suppose there is a synchronization chain P from ~
D and
~
G is in region 2. Let ng. Since \Gammam is the minimum of the dependence slope and each segment
(a in P is in S, b
(b
an
which contradicts the fact that ~
G is in region 2 and b a). Hence there is no synchronization chain that
is from a point ~
G in region 2 to ~
D. 2
Similar lemmas can be proved for regions 3 and 4. Theorem 1 shows that the parallelogram ADCO is all we need to
examine to find redundant synchronizations.
Theorem 1 No synchronization chain P from ~
O to ~
D contains points in region 1, 2, 3, or 4.
Proof: If there exists a synchronization chain P from ~
O to ~
containing ~
G in region 1, then the subpath from ~
O to ~
G
is a synchronization chain and the end point ~
G is in region 1. This contradicts the result from Lemma 1. Therefore, no
synchronization chain P from ~
O to ~
D contains points in region 1. Similar results for regions 2, 3 and 4 can be proved from
Lemmas 1 and 2. 2
3.2 The boundary problem of redundant synchronization elimination
In the previous section, we see that if there exists an alternative path from ~
O to ~
D, it must follow a synchronization chain
that is contained entirely in the parallelogram ADCO. We can use this conclusion to examine every iteration in the iteration
space (e.g., Figure 7a). The origin ~
O will correspond to the iteration we are examining (see Figure 7b). However, it is
not sufficient to examine ADCO in order to determine if all instances of ~
are redundant. For example, if the origin in

Figure

4 corresponds to an iteration at the bottom of the iteration space (as in Figure 7c), then any synchronization chain
containing intermediate points in the region FCO would be invalid to cover ~
D. It is because these intermediate points are
not in the iteration space of our loop (they are below the x-axis) and will not be executed. This is mainly caused by the
negative values in the second component (which corresponds to the inner loop) of some dependence distance vectors.
In this section, we will show a sufficient condition followed by a necessary and sufficient condition to determine if the
iteration space is large enough to contain an alternative path, that is, a synchronization chain, for a particular dependence.
The sufficient condition is easier to understand and to calculate while the necessary and sufficient condition gives more
precise redundancy information. We assume a rectangular 2-D iteration space as shown in Figure 7a.
The results of the following lemma is useful for later theorems.
Lemma 3 The following relations are true in Figure 4,
a - h
a - a \Gamma b
outer loop index
inner loop index
top
middle
bottom
O
(a) iteration space
(b) a redundant
synchronization
(c) a nonredundant
synchronization

Figure

7: A 2-D iteration space.
a - h 0
Proof: The value of h and h 0 ,
+m \Theta a
can be obtained by combining equations of line (1) and (3), (2) and (4), respectively, in Figure 5. Additionally, we have 1
a
a )M \Theta a \Gamma b - 0
Therefore,
M+m - 0Theorem 2 If a dependence distance vector ~
D(a; b), where a ? 0 and b ? 0, has an alternative path in the trapezoid
ADFO, then synchronization for ~
D is unnecessary if the source iteration is in the middle or bottom section of the iteration
space in Figure 7a.
Proof: If the source of an instance of ~
D is in the middle or the bottom section of the iteration space in Figure 7a then we
can align the origin ( ~
O) of

Figure

4 to the source iteration and two possible cases arise. If the sink iteration of ~
D is not
in the iteration space, then no synchronization is needed. Otherwise, we show that the trapezoid ADFO is entirely in the
iteration space. Since there are h rows of iteration in the top section and a - h
A is also in the
rectangular iteration space. Finally, since a - a \Gamma b
F is also in the rectangular iteration space.
Because ADFO is a trapezoid and all four corners are inside the rectangular iteration space, the entire trapezoid ADFO is
in the iteration space. Since there is an alternative path in ADFO, we conclude that the synchronization for dependence ~
is unnecessary. 2
Theorem 3 If a dependence distance vector ~
D(a; b), where a ? 0 and b ? 0, has an alternative path in the trapezoid
OEDC , then synchronization for ~
D is unnecessary if the source iteration is in the top or middle section of the iteration
space in Figure 7a.
Proof: If the source of an instance of ~
D is in the top or the middle section of the iteration space in Figure 7a then we can align
the origin ( ~
O) of

Figure

4 to the source iteration and two possible cases arise. If the sink iteration of ~
D is not in the iteration
space, then no synchronization is needed. Otherwise, we show that the trapezoid OEDC is entirely in the iteration space.
Since there are h 0 rows of iterations in the bottom section and a - h 0
C is also in the rectangular
iteration space. Finally, since a - b
E is also in the rectangular iteration space. Because OEDC
is a trapezoid and all four corners are inside the rectangular iteration space, the entire trapezoid OEDC is in the iteration
space. Since there is an alternative path in OEDC , we conclude that the synchronization for dependence ~
D is unnecessary.Theorem 4 If a rectangular iteration space (e.g., Figure 7a) has at least (h+h 0 ) rows and if a dependence ~
D has alternative
paths in both trapezoids ADFO and OEDC, respectively, then the synchronization for ~
D is redundant for all iterations,
including boundary iterations in the iteration space.
Proof: If the rectangular iteration space has at least (h we have the top and bottom sections, and probably
a non-empty middle section, as in Figure 7a. From Theorem 2, synchronization for ~
D is redundant in the middle and
the bottom sections. From Theorem 3, synchronization for ~
D is redundant in the top and the middle sections. Therefore,
synchronization for ~
D is redundant for all iterations. 2
Theorem 4 gives a sufficient condition for a synchronization to be redundant in a large enough iteration space. Besides,
h and h 0 can be easily determined from equations. (5) and (6). If the dimensions of an iteration space are known at compile
time, the redundancy of synchronizations can be determined by the compiler. On the other hand, if the dimensions of an
iteration space depend on the program input, we may generate multiple versions of this loop. A simple test can be placed
before the loop to dynamically determine which version to execute and to take advantage of eliminating some redundant
synchronizations.
Although the precise information of redundant synchronization can be determined by applying the DFS algorithm in
Section 2 to the entire iteration space, it is certainly quite time consuming and impractical. Based on the results derived
so far, we actually can find a necessary and sufficient condition for a synchronization to be redundant in an iteration space.
The condition is specified by a threshold on the height of the iteration space, called critical height. We now describe how
to calculate the critical height.
Lemma 4 In Figure 4, if ~
D has no alternative path in the rectangle with corners (0; 0), (0; k), (a; k), and (a; 0), where k
is a positive integer, then ~
D has no alternative path in the rectangle with corners (0; 0), (0;
Proof: It is easy to see that the second rectangle is enclosed entirely in the first rectangle. Therefore, if there is an alternative
path in the smaller rectangle, there must be an alternative path in the larger rectangle. 2
The basic idea in finding the critical height is to find, for the trapezoid ADFO, the smallest integer value k which
specifies the rectangle containing an alternative path for ~
D. Similarly, k 0 is determined for the trapezoid OEDC except
that the rectangle will grow downwards and have two corners fixed at (0; b) and (a; b). Based on the result of Lemma 4,
the search for k (k 0 ) can be done efficiently by a binary search in the interval [b; h] ([0; h 0 ]). If no k can be found in the
searched interval specifying a rectangle with an alternative path, then ~
D is not redundant no matter how large the iteration
space is and the critical height for ~
D equals +1. Otherwise, the critical height for ~
D is k
Theorem 5 In a doubly-nested loop, the synchronization for a dependence ~
D is redundant if and only if the iteration space
has a height larger than the critical height for ~
D.
Proof: We first prove the "if" part. If the iteration space has a height larger than k , we can use a partition scheme
similar to that of Figure 7a with h and h 0 being replaced by k and k 0 , respectively. Now the synchronization is redundant
in the top and the middle sections because the bottom section provides necessary room to contain an alternative path for ~
with its source iteration in the lowest row of the middle section. Similarly, the synchronization is redundant in the middle
and the bottom sections because the top section provides necessary room to contain an alternative path for ~
D with its source
iteration in the highest row of the middle section. Therefore, the synchronization for ~
D is redundant for all iterations.
We now prove the "only if" part. Suppose on the contrary, the height of the iteration space is less than the critical height.
If the critical height is +1, then the synchronization for ~
D is not redundant. Otherwise, let the height be k
where r is a positive integer. Let rows beneath the jth row, by the definition
of k 0 , these rows are not large enough to contain an alternative path for ~
D with its source iteration in the jth row. Similarly,
since there are k rows above the jth row, by the definition of k, these rows are not large enough
to contain an alternative path for ~
D with its source iteration in the jth row. Therefore, synchronization for ~
D with its source
iteration in the jth row is not redundant, and this implies that synchronization for ~
D is not redundant for all iterations. 2
Implementation issues
When h and h 0 are small, Theorem 4 can be satisfied by most loops and should be used for better efficiency. For the
two trapezoids ADFO and OEDC in Figure 4 that need examination, the integer loop bounds are not easy to determine.
Instead, we should use the rectangle with corners at (0; 0); (0; dhe); (a; dhe), and (a; 0) for ADFO. For OEDC , we use
rectangle with corners at (0; b); (a; b); (a; b\Gammah 0 c), and (0; b\Gammah 0 c). These two rectangles actually have a very similar size as
it can be shown that b. For each dependence distance vector ~
D(a; b), the number of iterations need to be examined
are approximately
2 \Theta a \Theta a \Theta M \Theta b +M \Theta m \Theta a
a \Theta M \Theta M \Theta a +M \Theta m \Theta a
If there are too many dependences to check, we can trade precision for efficiency by calculating the largest rectangle
from all dependences and check every dependence in that rectangle (instead of in their own rectangles). This results in only
one pair of h and h 0 . The set of the dependences we thus obtained will be redundant for all iterations if the iteration space
has a height larger than h
Also some simple optimizations can be done such as checking if the iteration space is large enough to contain both the
source and the sink of a dependence. If it is not, then no synchronization is needed.
Exit-loop control branches
If there is an exit-loop control branch in the loop, it implies that the execution of the later iterations will depend on this
branch. In the context of redundant synchronization elimination, since we assume that all statements in an iteration be
executed sequentially, we can add a dependence with its source the conditional statement of the branch and its sink the first
statement of the next iteration. Then we can use the same algorithm described in Section 2.
Higher dimension iteration spaces
We have used a doubly-nested loop as our example. To extend the results in the Section 3 to an n\Gammadimensional iteration
space, we simply have to modify Definition 2 to define the dependence slope for each dimension. Then we calculate the
maximum and the minimum of the slopes in each dimension. An n\Gammadimension region corresponding to the parallelogram
ADCO in Figure 4 can thus be found. The higher dimensional version of the sufficient condition is very similar to that
specified in Theorem 4 with the exception that now we have different h+h 0 in each dimension. To obtain the critical height
of the necessary and sufficient condition in Theorem 5 for each dimension is also straightforward. We need to examine the n
different dimensions one by one and search for its critical height. Because the critical heights found in later dimensions also
guarantee the existence of the alternative path if there is one, the order of examination is not critical and no backtracking is
necessary.
Previous works
The redundant synchronization elimination problem was first described by Li and Abu-sufah [7, 6] using dominant locks.
A lock specifies a dependence relation, and a lock dominates another lock if enforcing the first lock ensures that the second
lock is preserved. Three conditions for identifying dominant locks are provided, but they cover only very limited cases.
Midkiff and Padua [10, 9] described schemes to generate synchronization instructions in a compiler using test and testset,
which are very similar to await and advance instructions used in the Alliant minisupercomputers [1]. They also introduced
the Control Path Graph (CPG) to show the ordering imposed by the synchronization and the control dependences on a
MIMD machine. To eliminate redundant synchronizations, they used a transitive closure method to check, for a given
synchronization, whether the transitive closure of the remaining synchronizations cover it. Because the arcs previously
determined redundant have to be checked again, the time complexity of this algorithm is O(Dn 3 is the
number of statements in CPG and D is the number of dependences (which is bounded by n 2 ). So the complexity can also
be shown as O(n 5 ). For single loop, they showed that the columns of CPG needed is at most Dmax is the
largest dependence distance.
Shaffer [12] showed an algorithm which can find all the transitive synchronization arcs between tasks. A synchronization
is transitive if any other successors of the synchronization source have at least one path to the sink. This algorithm has time
complexity of O(n 3 ) where n is the number of nodes in the task graph.
The work done by Callahan et al. [2] used data flow analysis and algebraic formulations to determine whether a
dependence is properly covered by synchronizations. The synchronization primitives used are post&wait, and they can
handle more general program constructs not limited to parallel loops and hence the time complexity is potentially higher.
A very efficient algorithm for finding redundant synchronization in DOACROSS loops with uniform dependences is
proposed by Krothapalli and Sadayappan [4, 5]. It works on either single statement loops or synchronization at the
iteration level instead of the statement level. Because the dependences are uniform in each iteration, only the dependences
from the first iteration need to be verified. They used a variation of depth-first search (DFS) to determine the transitive
synchronization arcs. This scheme can be extended to multiply-nested loops provided the iteration space is large enough
such that the dependences are uniform even with iterations at the boundaries. Given a graph with n nodes with e edges, the
depth-first search algorithm has time complexity of O(e) or equivalently, O(n 2 ).
That approach is very efficient in finding redundant synchronizations between iterations. However, synchronization at the
iteration level is often not very satisfactory because the parallelism provided by overlapping loop iterations in a DOACROSS
loop execution is lost.
Recently, a scheme proposed by Midkiff and Padua in [11] is equivalent to examining the rectangle with corner
(0; 0); (0; b); (a; b), and (a; 0) in Figure 4 for an alternative path of the dependence ~
D. If there is an alternative path for
the dependence ~
D in this rectangle, it must be in the parallelogram OEDF (which is the intersection of the two trapezoid
ADFO and OEDC). Because it satisfies both Theorems 2 and 3, the synchronization is redundant for all iterations and in
this case, k which is exactly the minimal size to have both its source and sink in the iteration space.
The uniform redundant synchronizationsthus found are a subset of all uniformredundant synchronizations foundusing the
scheme described in the previous section. The number of iterations needed to be examined in the rectangle is a \Theta b - M \Theta a 2 :
5 Conclusion
In this paper, we described an algorithm to detect redundant synchronization efficiently for multiply-nested loops with
multiple statements. There could also be branches in the loop with multiple control flows. To solve the boundary problem
for multiply-nested loops, we used a doubly-nested loop as an example and derived the necessary and sufficient condition for
a synchronization to be redundant in the entire iteration space. The scheme is a significant improvement over the previous
schemes in the sense that it can efficiently identify all of the redundant synchronization while the previous schemes will be
either unable or too inefficient to find them. The results presented in this paper are important for a parallelizing compiler to
generate efficient code for DOACROSS loops,



--R

Alliant Computer System Corp.
Analysis of event synchronization in a parallel programming tool.

Removal of redundant dependences in doacross loops with constant dependences.
Removal of redundant dependences in doacross loops with constant dependences.
On reducing data synchronization in multiprocessed loops.
A technique for reducing synchronization overhead in large scale multiprocessors.
Automatic generation of synchronization instructions for parallel processors.
Compiler algorithms for synchronization.
Compiler generated synchronization for do loops.
A comparison of four synchronization optimization techniques.
Minimization of interprocessor synchronization in multiprocessors with shared and private memory.
--TR

--CTR
Antonia Zhai , Christopher B. Colohan , J. Gregory Steffan , Todd C. Mowry, Compiler Optimization of Memory-Resident Value Communication Between Speculative Threads, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.39, March 20-24, 2004, Palo Alto, California
Michiel Ronsse , Koen De Bosschere, Non-Intrusive Detection of Synchronization Errors Using Execution Replay, Automated Software Engineering, v.9 n.1, p.95-121, January 2002
Cheng-Zhong Xu , Vipin Chaudhary, Time Stamp Algorithms for Runtime Parallelization of DOACROSS Loops with Dynamic Dependences, IEEE Transactions on Parallel and Distributed Systems, v.12 n.5, p.433-450, May 2001
Long Li , Bo Huang , Jinquan Dai , Luddy Harrison, Automatic multithreading and multiprocessing of C programs for IXP, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA
DOACROSS;compiler optimization;redundant synchronization elimination;data synchronization;data dependence