Statement-Level Communication-Free Partitioning Techniques for Parallelizing Compilers.
This paper addresses the problem of communication-free partition of iteration spaces and data spaces along hyperplanes. To finding more possible communication-free hyperplane partitions, we treat statements within a loop body as separate schedulable units. Instead of using the information about data dependence distance or direction vectors, our technique explicitly formulates array references as transformations from statement-iteration spaces to data spaces. Based on these transformations, the necessary and sufficient conditions for communication-free partition along hyperplanes to be feasible have been proposed. This approach can be applied to all programs with an imperfectly nested loop or sequences of imperfectly nested loops, whose array references are affine functions of outer loop indices or loop invariant variables. The proposed approach is more practical than existing methods in finding the data and computation distribution patterns that can cause the processor to execute fully-parallel on multicomputers without any interprocessor communication.
Introduction
It has been widely accepted that local memory access is much faster than memory access involving
interprocessor communication on distributed-memory multicomputers. If data and computation
are not properly distributed across processors, it may cause heavy interprocessor communication.
Although the problem of data distribution is of critical importance to the efficiency of the parallel
program in distributed memory multicomputers; it is known to be a very difficult problem. Mace
[14] has proved that finding optimal data storage patterns for parallel processing is NP-complete,
even when limited to one- and two-dimensional arrays . In addition, Li and Chen [11, 12] have
shown that the problem of finding the optimal data alignment is also NP-complete.
Thus, in the previous work, a number of researchers have developed parallelizing compilers
that need programmers to specify the data storage patterns. Based on the programmer-specified
data partitioning, parallelizing compilers can automatically generate the parallel program with
appropriate message passing constructs for multicomputers. Projects using this approach include
the Fortran D compiler project [4, 5, 18], the SUPERB project [21], the Kali project [9, 10],
and the DINO project [17]. For the same purpose, the Crystal project [11, 12] and the
compiler [16] deal with functional languages and generate the parallel program with message passing
construct. The parallel program generated by most of these systems is in SPMD (Single-Program
Multiple Data) [8] model.
Recently, automatic data partitioning is an attractive research topic in the field of parallelizing
compilers. There are many researchers that develop systems to help programmers deal with the
problem of data distribution by automatically determining the data distribution at compile time.
The PARADIGM project [3] and the SUIF project [1, 19] are all based on the same purpose. These
systems can automatically determine the appropriate data distribution patterns to minimize the
communication overhead and generate the SPMD code with appropriate message passing constructs
for distributed memory multicomputers.
Since excessive interprocessor communication will offset the benefit of parallelization even if
the program has a large amount of parallelism, consequently, parallelizing compilers must pay
more attention on the distribution of computation and data across processors to reduce the communication
overhead or to completely eliminate the interprocessor communication, if possible.
Communication-free partitioning, therefore, becomes an interesting and worth studying issue for
distributed-memory multicomputers. In recent years, much research has been focused on the area
of partitioning iteration spaces and/or data space to reduce interprocessor communication and
achieve high-performance computing.
Ramanujam and Sadayappan [15] consider the problem of communication-free partitioning of
data spaces along hyperplanes for distributed memory multicomputers. They present a matrix-based
formulation of the problem for determining the existence of communication-free partitions of
data arrays. Their approach proposes only the array decompositions and does not take the iteration
space partitionings into consideration. In addition, they concentrate on fully parallel nested loops
and focus on two-dimensional data arrays.
Huang and Sadayappan [7] generalize the approach proposed in [15]. They consider the issue
of communication-free hyperplane partitioning by explicitly modeling the iteration and data
spaces and provide the conditions for the feasibility of communication-free hyperplane partitioning.
However, they do not deal with imperfectly nested loops. Moreover, the approach is restricted to
loop-level partitioning, i.e., all statements within a loop body must be scheduled together as an
indivisible unit.
Chen and Sheu [2] partition iteration space first according to the data dependence vectors
obtained by analyzing all the reference patterns in a nested loop, and then group all data elements
accessed by the same iteration partition. Two communication-free partitioning strategies, non-duplicate
data and duplicate data strategies, are proposed in this paper. Nevertheless, they require
the loop contain only uniformly generated references and the problem domain be restricted to a
single perfectly nested loop. They also treat all statements within a loop body as an indivisible
unit.
Lim and Lam [13] use affine processor mappings for statements to assign the statement-iterations
to processors and maximize the degree of parallelism available in the program. Their approach
does not treat the loop body as an indivisible unit and can assign different statement-iterations to
different processors. However, they consider only the statement-iteration space partitioning and
do not address the issue of data space partitioning. Furthermore, their uniform affine processor
mappings can cause a large number of idle processors if the affine mappings are non-unimodular
transformations.
In this paper, communication-free partitioning of statement-iteration spaces and data spaces
along hyperplanes are considered. We explicitly formulate array references as transformations from
statement-iteration spaces to data spaces. Based on these transformations, we then present the
necessary and sufficient conditions for the feasibility of communication-free hyperplane partitions.
Currently, most of the existing partitioning schemes take an iteration instance as a basic schedulable
unit that can be allocated to a processor. But, when the loop body contains multiple statements, it
is very difficult to make the loop be communication-freely executed by allocating iteration instances
among processors. That is, the chance of communication-free execution found by using these
methods is limited. For having more flexible and possible in finding communication-free hyperplane
partitions, we treat statements within a loop body as separate schedulable units. Our method does
not consider only one of the iteration space and data space but both of them. As in [13], our
method can be extended to handle more general loop models and can be applied to programs with
imperfectly nested loops and affine array references.
The rest of the paper is organized as follows. In Section 2, we introduce notation and terminology
used throughout the paper. Section 3 describes the characteristics of statement-level
communication-free hyperplane partitioning. The technique of statement-level communication-free
hyperplane partitioning for a perfectly nested loop is presented in Section 4. The necessary and
sufficient conditions for the feasibility of communication-free hyperplane partitioning are also given.
The extension to general case for sequences of imperfectly nested loops is described in Section 5.
Finally, the conclusions are given in Section 6.
Preliminaries
This section explains the statement-iteration space and the data space. It also defines the statement-
iteration hyperplane and the data hyperplane.
2.1 Statement-Iteration Space and Data Space
Let Q, Z and Z + denote the set of rational numbers, the set of integers and the set of positive
integer numbers, respectively. The symbol Z d represents the set of d-tuple of integers. Traditionally,
the iteration space is composed of discrete points where each point represents the execution of all
statements in one iteration of a loop [20]. Instead of viewing each iteration indivisible, an iteration
can be divided into the statements that are enclosed in the iteration, i.e., each statement is a
schedulable unit and has its own iteration space. We use another term, statement-iteration space,
to denote the iteration space of a statement in a nested loop.
The following example illustrates the notion of iteration spaces and statement-iteration spaces.
Example 1: Consider the following nested loop L 1 .
do
do
Fig. 1 illustrates the iteration space and statement-iteration spaces of loop L 1 for 5.
In Fig. 1(a), a circle means an iteration and includes two rectangles with black and gray colors.
The black rectangle indicates statement s 1 and the gray one indicates statement s 2 . In Fig. 1(b)
and Fig. 1(c), each statement is an individual unit and the collection of statements forms two
statement-iteration spaces. 2
The representation of statement-iteration spaces, data spaces and the relations among them is
described as follows. Let S denote the set of statements in the targeted problem domain and D be
the set of array variables that are referenced by S. Consider statement s 2 S, which is enclosed in
a d-nested loop. The statement-iteration space of s, denoted by SIS(s), is a subspace of Z d and
is defined as I i is the loop index
variable, LB i and UB i are the lower and upper bounds of the loop index variable I i , respectively.
The superscript t is a transpose operator. The column vector I is called a
statement-iteration in statement-iteration space SIS(s), LB i - I i - UB i , for On
the other hand, from the geometric point of view, an array variable also forms a space and each
array element is a point in the space. For exactly describing an array variable, we use data space
to represent an n-dimensional array v, which is denoted by DS(v), where v 2 D. An array element
has a corresponding data index in the data space DS(v). We denote this data
index by a column vector D
The relations between statement-iteration spaces and data spaces can be built via array reference
functions. An array reference function is a transformation from statement-iteration space into data

Figure

1: Loop (L 1 )'s iteration space and its corresponding statement-iteration spaces, assuming
5. (a) IS(L 1 ), iteration space of loop (L 1 ). (b) SIS(s 1 ), statement-iteration space of statement
statement-iteration space of statement s 2 .
space. As most of the existing methods, we require the array references be affine functions of outer
loop indices or loop invariant variables. Suppose statement s is enclosed in a d-nested loop and
has an array reference pattern v[a 1;1 I 1
a a i;j are integer constants, for 1 - i - n and
d, then the array reference function can be written as:
where
F s;v =6 4
a 1;1 \Delta \Delta \Delta a 1;d
a
a 1;0
a
We term F s;v the array reference coefficient matrix and f s;v the array reference constant vector.
If data index D v 2 DS(v) is referenced in statement-iteration I s 2 SIS(s), then Ref s;v
Take the array reference pattern as an example. The array
reference coefficient matrix and constant vector of A[i are F
and f
\Gamma4#
, respectively.
We define statement-iteration hyperplanes and data hyperplanes in the next subsection.
2.2 Statement-Iteration Hyperplane and Data Hyperplane
A statement-iteration hyperplane on statement-iteration space SIS(s), denoted by \Psi(s), is a hyperspace
[6] of SIS(s) and is defined as \Psi h
are the coefficients of the statement-iteration hyperplane and c h 2 Q is
the constant term of the hyperplane. The formula can be abbreviated as \Psi h
is the statement-iteration hyperplane coefficient vector. Similarly, a data
hyperplane on data space DS(v), denoted by \Phi(v), is a hyperspace of DS(v) and is defined as
are the
coefficients of the data hyperplane and c g 2 Q is the constant term of the hyperplane. In the same
way, the formula also can be abbreviated as \Phi
the data hyperplane coefficient vector. The hyperplanes that include at least one integer point are
considered in this paper.
Statement-iteration hyperplanes and data hyperplanes are used for characterizing communica-
tion-free partitioning. We discuss some of these characteristics in the next section.
3 Characteristics of Communication-Free Hyperplane Partition-
ing
A program execution is communication-free if all operations on each of all processors access only
data elements allocated to that processor. A trivial partition strategy allocates all statement-
iterations and data elements to a single processor. The program execution of this trivial partitioning
is communication-free. However, we are not interested in this single processor program execution
because it does not exploit the potential of parallelization and it conflicts with the goal of parallel
processing. Hence, in this paper, we consider only nontrivial partitioning, in specific, hyperplane
partitioning.
The formal definition of communication-free hyperplane partition is defined as below. Let
partition group, G,
be the set of hyperplanes that should be assigned to one processor. The definition of communica-
tion-free hyperplane partition can be given as the following.
1 The hyperplane partitions of statement-iteration spaces and data spaces are said to
be communication-free if and only if for any partition group
above, the statement-iterations which access the same array element should
be allocated to the same statement-iteration hyperplane. Therefore, it is important to decide
statement-iterations that access the same array element. The following lemma states the necessary
and sufficient condition that two statement-iterations will access the same array element.
Lemma 1 For some statement s 2 S and its referenced array v 2 D, I s and I 0
s are two statement-
iterations on SIS(s) and Ref s;v is the array reference function from SIS(s) into DS(v) as defined
above. Then
where Ker(S) denotes the null space of S [6].
Proof. ()): Suppose that Ref s;v
Thus
Conversely, suppose that (I 0
be a basis of Ker(F s;v ), then vectors belonged to Ker(F s;v ) can be represented
as a linear combination of vectors in fff 1 g. Since (I 0
Thus Ref s;v
We using the following example.
Example 2: Consider the array reference A[i j]. The array reference coefficient ma-
. The null space of F s;A is Ker(F s;A Zg. By Lemma 1, any
two statement-iterations with the difference of r[1; \Gamma1] t will access the same array element, where
Z. As Fig. 2 shows, the statement-iterations f(1; 3); (2; 2); (3; 1)g all access the same array
element A[4; 4]. 2
We explain the significance of Lemma 1 and show how this lemma can help to find com-
munication-free hyperplane partitions. Communication-free hyperplane partitioning requires those
statement-iterations that access the same array element be allocated to the same statement-iteration
hyperplane. According to Lemma 1, two statement-iterations access the same array element if
and only if the difference of these two statement-iterations belongs to the kernel of F s;v . Hence,
should be a subspace of the statement-iteration hyperplane. Since there may exist many
different array references, partitioning a statement-iteration space must consider all array references
appeared in the statement. Thus, the space spanned from Ker(F s;v ) for all array references
appearing in the same statement should be a subspace of the statement-iteration hyperplane. The

Figure

2: Those statement-iterations whose differences are in Ker(F s;v ) will access the same array
element.
dimension of a statement-iteration hyperplane is one less than the dimension of the statement-
iteration space. If there exists a statement s such that the dimension of the spanning space of
equal to the dimension of SIS(s), then the spanning space cannot be a subspace of
a statement-iteration hyperplane. Therefore, there exists no nontrivial communication-free hyper-plane
partitioning. From the above observation, we obtain the following theorem.
Theorem 1 If 9s 2 S such that
dim(span([ v2D Ker(F s;v
then there exists no nontrivial communication-free hyperplane partitioning for S and D. 2
Example 3: Consider matrix multiplication.
do
do
do
s:
In the above program, there are three array variables, A, B, and C, with three distinct array
references involved in statement s. The three array reference coefficient matrices, F s;A , F s;B ,
and F s;C , are
, and
, respectively. Thus, Ker(F s;A
which has the same dimensionality as the statement-
iteration space. By Theorem 1, matrix multiplication has no nontrivial communication-free hyper-plane
partitioning. 2
Theorem 1 can be useful for determining nested loops that have no nontrivial communica-
tion-free hyperplane partitioning. Furthermore, when a nontrivial communication-free hyperplane
partitioning exists, Theorem 1 can also be useful for finding the hyperplane coefficient vectors. We
state this result in the following corollary.
Corollary 1 For any communication-free statement-iteration hyperplane \Psi h
the following two conditions must hold:
denotes the orthogonal complement space of S.
Proof. By Lemma 1, two statement-iterations access the same data element using array reference
F s;v if and only if the difference between these two statement-iterations belongs to the kernel of
F s;v . Therefore, the kernel of F s;v should be contained in the statement-iteration hyperplane,
(s). The fact should be true for all array references appeared in the same statement. Hence,
(s). The first condition is obtained.
is the normal vector of \Psi h (s). That is, \Delta t is orthogonal to
By condition (1), it implies that \Delta t is orthogonal to the subspace span([ v2D Ker(F s;v )).
Thus, belongs to the orthogonal complement of span([ v2D Ker(F s;v
Corollary 1 gives the range of communication-free statement-iteration hyperplane coefficient
vectors. It can be used for the finding of communication-free statement-iteration hyperplane co-efficient
vectors. On the other hand, the range of communication-free data hyperplane coefficient
vectors is also given as follows.
As mentioned before, the relations between statement-iteration spaces and data spaces can be
established via array references. Moreover, the statement-iteration hyperplane coefficient vectors
and data hyperplane coefficient vectors are related. The following lemma expresses the relation
between these two hyperplane coefficient vectors. A similar result is given in [7].
Lemma 2 For any statement s 2 S and its referenced array v 2 D, Ref s;v is the array reference
function from SIS(s) into DS(v). \Psi h are
communication-free hyperplane partitions if and only if
Proof. ()): Suppose that \Psi h are
communication-free hyperplane partitionings. Let I 0
s and I 00
s be two distinct statement-iterations
and belong to the same statement-iteration hyperplane, \Psi h (s). If D 0
v and D 00
are two data indices
such that Ref s;v (I 0
v and Ref s;v (I 00
v , from the above assumptions, D 0
v and D 00
should
belong to the same data hyperplane, \Phi g (v).
Because I 0
s and I 00
s belong to the same statement-iteration hyperplane, \Psi h (s), then, \Delta \Delta I 0
and \Delta \Delta I 00
Therefore,
s
1 Note that \Delta is a row vector. However, it is \Delta t , but not \Delta, that is orthogonal to \Psi h(s).
On the other hand, since D 0
v and D 00
v belong to the same data hyperplane, \Phi g (v), that means
\Theta \Delta D 0
and \Theta \Delta D 00
. Thus,
\Theta \Delta D 0
Since I 0
s and I 00
s are any two statement-iterations on the statement-iteration hyperplane \Psi h (s),
s ) is a vector on the statement-iteration hyperplane. Furthermore, both \Delta \Delta
and (\Theta \Delta F s;v )
hence we can conclude that \Delta and \Theta \Delta F s;v are linearly dependent. It
implies
are hyperplane partitions
for SIS(s) and DS(v) respectively and
\Phi g (v) are communication-free partitioning. According to Definition 1, what we have to do is to
prove (v).
Let I s be any statement-iteration on statement-iteration hyperplane \Psi h (s). Then \Delta
From the assumption that
(ff\Theta
Let c
(v). We have shown that 8I s 2 \Psi h (s); Ref s;v
\Phi g (v). It then follows that \Psi h (s) and \Phi g (v) are communication-free partitioning. 2
By Lemma 2, the statement-iteration hyperplane coefficient vector \Delta can be decided if the data
hyperplane coefficient vector \Theta has been determined. If F s;v is invertible, the statement-iteration
hyperplane coefficient vectors can be decided first, then the data hyperplane coefficient vectors
can be derived by
The range of communication-free data
hyperplane coefficient vectors can be derived from this lemma. Corollary 1 shows the range of
statement-iteration hyperplane coefficient vectors. The next corollary provides the ranges of data
hyperplane coefficient vectors.
Corollary 2 For any communication-free data hyperplane \Phi g, the following
condition must hold:
denotes the complement set of S.
Proof. This paper considers the nontrivial hyperplane partitioning, which requires \Delta be a nonzero
vector. By Lemma 2, Therefore, \Theta \Delta F s;v is not equal to 0. It implies that
\Theta t 62 Ker((F s;v ) t ). The condition should be true for all s; s 2 S. Hence, \Theta t 62 ([ s2S Ker((F s;v ) t )).
It follows that \Theta t belongs to the complement of ([ s2S Ker((F s;v Consider the following loop.
do
do
The nested loop is communication-free if and only if the statement-iteration hyperplane coefficient
vectors for s 1 and s 2 and data hyperplane coefficient vectors for v 1 and v 2 are
respectively, where f0g. We
show that \Delta 1 and \Delta 2 satisfy the Corollary 1 as follows.
The test of Corollary 2 for \Theta 1 and \Theta 2 is as below.
=) \Theta t
section describes the communication-free hyperplane partitioning technique. The necessary
and sufficient conditions of communication-free hyperplane partitioning for a single perfectly
nested loop will be presented.
4 Communication-Free Hyperplane Partitioning for a Perfectly
Nested Loop
Each data array has a corresponding data space. However, a nested loop with multiple statements
may have multiple statement-iteration spaces. In this section, we will consider additional conditions
of multiple statement-iteration spaces for communication-free hyperplane partitioning. These
conditions are also used in determining statement-iteration hyperplanes and data hyperplanes.
. The number of
occurrences of array variable v j in statement s i is r i;j , where r i;j
does not reference v j , r i;j is set to 0. The previous representation of array
reference function can be modified slightly to describe the array reference of statement s i to variable
in the k-th occurrence as Ref s i ;v j
. The related representations will be
changed accordingly, such as Ref s i ;v j
In this section, a partition group that contains a statement-iteration hyperplane for each
statement-iteration space and a data hyperplane for each data space is considered. Suppose that
the data hyperplane in data space DS(v j ) is \Phi g (v j
g, for all
we have
, \Theta j \Delta
Let
As a result, those statement-iterations that access the data lay on the data hyperplane \Phi g (v j
g will be located on the statement-iteration hyperplane \Psi h (I s i
)g.
To simplify the presentation, we assume all variables v j appear in every statement s i . To satisfy
that each statement-iteration space contains a unique statement-iteration hyperplane, the following
two conditions should be met.
(j
for
(j
for
Condition (i) can infer to the following two equivalent equations.
Condition (ii) deduces the following two equations, and vice
versa.
Eq. (6) can be used to evaluate the data hyperplane constant terms while some constant term
is fixed, say c
. Furthermore, we obtain the following results. For some j, c g j
should be the same
for all i, 1 - i - m. Therefore,
can be further inferred to obtain the following
After describing the conditions for satisfying the communication-free hyperplane partitioning
constraints, we can conclude the following theorem.
Theorem 2 Let be the sets of statements and array
variables, respectively. Ref s i ;v j
k is the array reference function for statement s i accessing array
variables v j at the k-th occurrence in s i , where
g is the statement-iteration hyperplane in SIS(s i ), for
(D v j
g is the data hyperplane in DS(v j ), for
(D v j
are communication-free hyperplane partitions if and only if the following conditions hold.
for some j; k, g.
for some
for some j; k, g.
Theorem 2 can be used to determine whether a nested loop is communication-free. It can also
be used as a procedure of finding a communication-free hyperplane partitioning systematically.
Conditions (C1) to (C4) in Theorem 2 are used for finding the data hyperplane coefficient vectors.
Condition (C5) can check whether the data hyperplane coefficient vectors found in preceding
steps are within the legal range. Following the determination of the data hyperplane coefficient
vectors, the statement-iteration hyperplane coefficient vectors can be obtained by using Condition
(C6). Similarly, Condition (C7) can check whether the statement-iteration hyperplane coefficient
vectors are within the legal range. The data hyperplane constant terms and statement-iteration
hyperplane constant terms can be obtained by using Conditions (C8) and (C9), respectively. If
one of the conditions is violated, the whole procedure will stop and verify that the nested loop has
no communication-free hyperplane partitioning.
On the other hand, combining Equations (3) and (5) together, a sufficient condition of commu-
nication-free hyperplane partitioning can be derived as follows.
r i;j
r i;j
To satisfy the constraint that \Theta is a non-zero row vector,
the following condition should be true.
r i;j
r i;j
Note that this condition is similar to the result in [7] for
loop-level hyperplane partitioning. We conclude the following corollary.
Corollary 3 Suppose are the sets of statements
and array variables, respectively. F s i ;v j
k are the array reference coefficient matrix and
constant vector, respectively, where ng and k 2 g. If
communication-free hyperplane partitioning exists then Eq. must hold. 2
Theorem 1 and Corollary 3 can be used to check the absence of communication-free hyperplane
partitioning for a nested loop, because these conditions are sufficient but not necessary. Theorem 1
is the statement-iteration space dimension test and Corollary 3 is the data space dimension test.
To determine the existence of a communication-free hyperplane partitioning, we need to check the
conditions in Theorem 2. We show the following example to explain the finding of communication-
free hyperplanes of statement-iteration spaces and data spaces.
Example 5: Reconsider loop L1. The set of statements S is fs and the set of array variables
D is fv B. The occurrences of array variables are r
2. From Section 2.1, the array reference coefficient matrices and constant
vectors for statements s 1 and s 2 are listed below, respectively.
\Gamma1#
"1
\Gamma1#
\Gamma2
2.
By Theorem 1, it may exist a communication-free hyperplane partitioning for loop L 1 . Again,
by Corollary 3, the loop is tested for the possible existence of a nontrivial communication-free
hyperplane partitioning. For array variable v 1 , the following inequality is satisfied:
2:
Similarly, with respect to the array variable v 2 , the following inequality is obtained:
2:
Although Eq. (9) holds for all array variables, it still can not ensure that the loop has a nontrivial
communication-free hyperplane partitioning.
Using Theorem 2, we further check the existence of a nontrivial communication-free hyperplane
partitioning. In the mean time, the statement-iteration and data hyperplanes will be derived if
they exist. Recall that the dimensions of data spaces DS(v 1 ) and DS(v 2 ) are two, \Theta 1 and \Theta 2 can
be assumed to be [' respectively. The conditions listed in Theorem 2 will be
checked to determine the hyperplane coefficient vectors and constants.
By Condition (C1) in Theorem 2, the following equations are obtained.
By the Condition (C2) in Theorem 2,
By Condition (C3) in Theorem 2,
By Condition (C4) in Theorem 2,
Substituting [' respectively, the above equations form a
homogeneous linear system. Solving this homogeneous linear system, we obtain the general solution
f0g. Therefore, \Theta
Next, we show \Theta 1 and \Theta 2 satisfy Condition (C5):
=) \Theta t
=) \Theta t
Now the statement-iteration hyperplane coefficient vectors can be determined using Condition
(C6) in Theorem 2.
Note that the statement-iteration hyperplane coefficient vectors may be obtained using many different
can be obtained using \Theta 1
1 . Conditions
(C1) and (C2) in Theorem 2 ensure that all the equations lead to the same result.
For the statement-iteration hyperplane coefficient vectors, Condition (C7) is satisfied:
Next, we determine the data hyperplane constant terms. Due to the hyperplanes are related to
each other, once a hyperplane constant term is determined, the other constant terms will be determined
accordingly. Assuming c g 1
is known, c g 2
, and c h 2
can be determined using Conditions
(C8) and (C9) as below:
Similarly, statement-iteration and data hyperplane constant terms can be evaluated using many
different equations. However, Conditions (C3) and (C4) in Theorem 2 ensure that they all lead
to the same values.
It is clear that there exists at least one set of nonzero statement-iteration and data hyperplane
coefficient vectors such that the conditions listed in Theorem 2 are all satisfied. By Theorem 2, this
fact implies that the nested loop has a nontrivial communication-free hyperplane partitioning. The
partition group is defined as the set of statement-iteration and data hyperplanes that are allocated
to a processor. The partition group for this example follows.
(D
(D
(D
(D
Given loop bounds 1, the constant term c g 1
corresponding to
statement-iteration hyperplane coefficient vector \Delta 1 and \Delta 2 are ranged from \Gamma5 to 3 and from 0 to
respectively. The intersection part of these two ranges means that the two statement-iteration
hyperplanes have to be coupled together onto a processor. For the rest, just one statement-iteration
hyperplane, either \Delta 1 or \Delta 2 , is allocated to a processor. The constant terms c g 2
, and c h 2
are
evaluated to the following values:
The corresponding parallelized program is as follows.
doall
do
do
enddoall
Fig. 3 illustrates the communication-free hyperplane partitionings for a particular partition
2. 2
The communication-free hyperplane partitioning technique for a perfectly nested loop has been
discussed in this section. Our method treats statements within a loop body as separate schedulable
units and considers both iteration and data spaces at the same time. Partitioning groups are
determined using affine array reference functions directly, instead of using data dependence vectors.
5 Communication-Free Hyperplane Partitioning for Sequences of
Imperfectly Nested Loops
The conditions presented in Section 4 for communication-free hyperplane partitioning can be applicable
to the general case for sequences of imperfectly nested loops. In a perfectly nested loop, all

Figure

3: Communication-free statement-iteration hyperplanes and data hyperplanes for a partition
group of loop (L 1 ), where
2. (a) Statement-iteration hyperplane of SIS(s 1 ). (b)
Statement-iteration hyperplane of SIS(s 2 ). (c) Data hyperplane of DS(A). (d) Data hyperplane
of DS(B).
statements are enclosed in the same depth of the nested loop, i.e., the statement-iteration space of
each statement has the same dimensionality. The statement-iteration spaces of two statements in
imperfectly nested loops may have different dimension. Since each statement-iteration is a schedulable
unit and the partitioning technique is independent to the dimensionality of statement-iteration
spaces, Theorem 2 can be directly applied to sequences of imperfectly nested loops. The following
example is to demonstrate the technique in applying to sequences of imperfectly nested loops.
Example Consider the following sequences of nested loops L 2 .
do
do
do
do
do
do
The set of statements S is fs g. The set of array variables is
respectively. The values of r 11 , r 12 , r 13 , r
r 43 all are 1. We use Theorem 1 and Corollary 3 to verify whether (L2)
has no communication-free hyperplane partitioning. Since dim(
which is
smaller than dim(SIS(s i )), for Theorem 1 is helpless for ensuring that (L2) exists no
communication-free hyperplane partitioning. Corollary 3 is useless here because all the values of
are 1, for Further examinations are necessary, because Theorem 1 and
Corollary 3 can not prove that (L2) has no communication-free hyperplane partitioning, From Theorem
2, if a communication-free hyperplane partitioning exists, the conditions listed in Theorem 2
should be satisfied; otherwise, (L2) exists no communication-free hyperplane partitioning.
Due to the dimensions of the data spaces DS(v 1
tively, without loss of generality, the data hyperplane coefficient vectors can be respectively assumed
to be \Theta In what follows, the requirements to
satisfy the feasibility of communication-free hyperplane partitioning are examined one-by-one.
There is no need to examine the Conditions (C1) and (C3) because all the values of r ij are 1.
By Condition (C2), we obtain
By Condition (C4), we obtain
Solving the above linear system, the general solutions are (' 11 , ' 12 , ' 21 , ' 22 , ' 31 , '
2t, \Gammat, t, t, f0g. Therefore, \Theta
The verification of Condition (C5) is as follows:
=) \Theta t
=) \Theta t
=) \Theta t
All the data hyperplane coefficient vectors are within the legal range.
The statement-iteration hyperplane coefficient vectors can be determined by Condition (C6)
as follows.
The legality of these statement-iteration hyperplane coefficient vectors is then checked by Condition
(C7) as follows:
From the above observation, all the statement-iteration and data hyperplane coefficient vectors
are legal. This fact reveals that the nested loops has communication-free hyperplane partitionings.
Next, the data and statement-iteration hyperplanes constant terms are decided.
First, let one data hyperplane constant term be fixed, say c
. The rest of data hyperplane
constant terms can be determined by Condition (C8).
Similarly, the statement-iteration hyperplane constant terms can be determined by Condition (C9)
after data hyperplane constant terms have been decided.
The corresponding partition group is as follows.
(D
(D
(D v 3
(D
(D
(D v 3
Fig. 4 illustrates the communication-free hyperplane partitionings for a partition group, where
and c g 1
0. The corresponding parallelized program is as follows.
doall
do
endif
do
do
do
do
enddoall
6 Conclusions
This paper presents the techniques for finding statement-level communication-free hyperplane partitioning
for a perfectly nested loop and sequences of imperfectly nested loops. The necessary
and sufficient conditions for the feasibility of communication-free partitioning along hyperplane are
proposed. The techniques can be applied to loops with affine array references and do not use any
information of data dependence distances or direction vectors.
Although our goal is to determine communication-free partitioning for loops, in reality, most
loops are not communication-free. If a program is not communication-free, the technique can be

Figure

4: Communication-free statement-iteration hyperplanes and data hyperplanes for a partition
group of loop (L 2 ), where
Statement-iteration hyperplane of SIS(s 1 ). (b)
Statement-iteration hyperplane of SIS(s 2 ). (c) Statement-iteration hyperplane of SIS(s 3 ). (d)
Statement-iteration hyperplane of SIS(s 4 ). (e) Data hyperplane of DS(A). (f) Data hyperplane
of DS(B). (g) Data hyperplane of DS(C).
used to identify subsets of statement-iteration and data spaces which are communication-free. For
other statement-iterations, it is necessary to generate communication code. Two important tasks
in our future work are to develop heuristics for searching a subset of statement-iterations which is
communication-free and to generate efficient code when communication is inevitable.



--R

"Global optimizations for parallelism and locality on scalable parallel machines,"
"Communication-free data allocation techniques for parallelizing compilers on multicomputers,"
"Demonstration of automatic data partitioning techniques for parallelizing compilers on multicomputers,"
"Compiling Fortran D for MIMD distributed-memory machines,"
"Evaluating compiler optimizations for Fortran D,"
Englewood Cliffs
"Communication-free hyperplane partitioning of nested loops,"
"Programming for parallelism,"
Compiling Programs for Nonshared Memory Machines.
"Compiling global name-space parallel loops for distributed ex- ecution,"
"Index domain alignment: Minimizing cost of cross-referencing between distributed arrays,"
"The data alignment phase in compiling programs for distributed-memory machines,"
"Communication-free parallelization via affine transformations,"
Memory Storage Patterns in Parallel Processing.
"Compile-time techniques for data distribution in distributed memory machines,"
"Process decomposition through locality of reference,"
"The dino parallel programming language,"
An Optimizing Fortran D Compiler for MIMD distributed-Memory Machines
"A loop transformation theory and an algorithm to maximize parallelism,"
High Performance Compilers for Parallel Computing.
"SUPERB and Vienna Fortran,"
--TR

--CTR
Weng-Long Chang , Chih-Ping Chu , Jia-Hwa Wu, Communication-Free Alignment for Array References with Linear Subscripts in Three Loop Index Variables or Quadratic Subscripts, The Journal of Supercomputing, v.20 n.1, p.67-83, August 2001
Skewed Data Partition and Alignment Techniques for Compiling Programs on Distributed Memory Multicomputers, The Journal of Supercomputing, v.21 n.2, p.191-211, February 2002
Weng-Long Chang , Jih-Woei Huang , Chih-Ping Chu, Using Elementary Linear Algebra to Solve Data Alignment for Arrays with Linear or Quadratic References, IEEE Transactions on Parallel and Distributed Systems, v.15 n.1, p.28-39, January 2004
hyperplane partition;parallelizing compilers;communication-free;distributed-memory multicomputers;data communication