Demonstration of Automatic Data Partitioning Techniques for Parallelizing Compilers on Multicomputers.
An approach to the problem of automatic data partitioning is introduced. The notion of constraints on data distribution is presented, and it is shown how, based on performance considerations, a compiler identifies constraints to be imposed on the distribution of various data structures. These constraints are then combined by the compiler to obtain a complete and consistent picture of the data distribution scheme, one that offers good performance in terms of the overall execution time. Results of a study performed on Fortran programs taken from the Linpack and Eispack libraries and the Perfect Benchmarks to determine the applicability of the approach to real programs are presented. The results are very encouraging, and demonstrate the feasibility of automatic data partitioning for programs with regular computations that may be statically analyzed, which covers an extremely significant class of scientific application programs.
Introduction
Distributed memory multiprocessors (multicomputers) are increasingly being used for providing high levels
of performance for scientific applications. The distributed memory machines offer significant advantages
over their shared memory counterparts in terms of cost and scalability, but it is a widely accepted fact that
they are much more difficult to program than shared memory machines. One major reason for this difficulty
is the absence of a single global address space. As a result, the programmer has to distribute code and
data on processors himself, and manage communication among tasks explicitly. Clearly there is a need for
parallelizing compilers to relieve the programmer of this burden.
The area of parallelizing compilers for multicomputers has seen considerable research activity during the
last few years. A number of researchers are developing compilers that take a program written in a sequential
or shared-memory parallel language, and based on the user-specified partitioning of data, generate the target
parallel program for a multicomputer. These research efforts include the Fortran D compiler project at Rice
University [9], the SUPERB project at Bonn University [22], the Kali project at Purdue University [13],
and the DINO project at Colorado University [20], all of them dealing with imperative languages that are
extensions of Fortran or C. The Crystal project at Yale University [5] and the compiler [19] are
also based on the same idea, but are targeted for functional languages. The parallel program generated by
most of these systems corresponds to the SPMD (single program, multiple-data) [12] model, in which each
processor executes the same program but operates on distinct data items.
The current work on parallelizing compilers for multicomputers has, by and large, concentrated on automating
the generation of messages for communication among processors. Our use of the term "paralleliz-
ing compiler" is somewhat misleading in this context, since all parallelization decisions are really left to the
programmer who specifies data partitioning. It is the method of data partitioning that determines when
interprocessor communication takes place, and which of the independent computations actually get executed
on different processors.
The distribution of data across processors is of critical importance to the efficiency of the parallel program
in a distributed memory system. Since interprocessor communication is much more expensive than
computation on processors, it is essential that a processor be able to do as much of computation as possible
using just local data. Excessive communication among processors can easily offset any gains made by the
use of parallelism. Another important consideration for a good data distribution pattern is that it should
allow the workload to be evenly distributed among processors so that full use is made of the parallelism
inherent in the computation. There is often a tradeoff involved in minimizing interprocessor communication
and balancing load on processors, and a good scheme for data partitioning must take into account both
communication and computation costs governed by the underlying architecture of the machine.
The goal of automatic parallelization of sequential code remains incomplete as long as the programmer is
forced to think about these issues and come up with the right data partitioning scheme for each program. The
task of determining a good partitioning scheme manually can be extremely difficult and tedious. However,
most of the existing projects on parallelization systems for multicomputers have so far chosen not to tackle
this problem at the compiler level because it is known to be a difficult problem. Mace [16] has shown that
the problem of finding optimal data storage patterns for parallel processing, even for 1-D and 2-D arrays,
is NP-complete. Another related problem, the component alignment problem has been discussed by Li and
Chen [15], and shown to be NP-complete.
Recently several researchers have addressed this problem of automatically determining a data partitioning
scheme, or of providing help to the user in this task. Ramanujan and Sadayappan [18] have worked on
deriving data partitions for a restricted class of programs. They, however, concentrate on individual loops
and strongly connected components rather than considering the program as a whole. Hudak and Abraham
[11], and Socha [21] present techniques for data partitioning for programs that may be modeled as sequentially
iterated parallel loops. Balasundaram et al. [1] discuss an interactive tool that provides assistance to the
user for data distribution. The key element in their tool is a performance estimation module, which is used
to evaluate various alternatives regarding the distribution scheme. Li and Chen [15] address the issue of
data movement between processors due to cross-references between multiple distributed arrays. They also
describe how explicit communication can be synthesized and communication costs estimated by analyzing
reference patterns in the source program [14]. These estimates are used to evaluate different partitioning
schemes.
Most of these approaches have serious drawbacks associated with them. Some of them have a problem
of restricted applicability, they apply only to programs that may be modeled as single, multiply nested
loops. Some others require a fairly exhaustive enumeration of possible data partitioning schemes, which
may render the method ineffective for reasonably large problems. Clearly, any strategy for automatic data
partitioning can be expected to work well only for applications with a regular computational structure and
static dependence patterns that can be determined at compile time. However, even though there exists a
significant class of scientific applications with these properties, there is no data to show the effectiveness of
any of these methods on real programs.
In this paper, we present a novel approach, which we call the constraint-based approach [7], to the problem
of automatic data partitioning on multicomputers. In this approach, the compiler analyzes each loop in the
program, and based on performance considerations, identifies some constraints on the distribution of various
data structures being referenced in that loop. There is a quality measure associated with each constraint
that captures its importance with respect to the performance of the program. Finally, the compiler tries to
combine constraints for each data structure in a consistent manner so that the overall execution time of the
parallel program is minimized. We restrict ourselves to the partitioning of arrays. The ideas underlying our
approach can be applied to most distributed memory machines, such as the Intel iPSC/2, the NCUBE, and
the WARP systolic machine. Our examples are all written in a Fortran-like language, and we present results
on Fortran programs. However, the ideas developed on the partitioning of arrays are equally applicable to
any similar programming language.
The rest of this paper is organized as follows. Section 2 describes our abstract machine and the kind of
distributions that arrays may have in our scheme. Section 3 introduces the notion of constraints and describes
the different kinds of constraints that may be imposed on array distributions. Section 4 describes how a
compiler analyzes program references to record constraints and determine the quality measures associated
with them. Section 5 presents our strategy for determining the data partitioning scheme. Section 6 presents
the results of our study on Fortran programs performed to determine the applicability of our approach to
real programs. Finally, conclusions are presented in Section 7.
2 Data Distribution
The abstract target machine we assume is a D-dimensional (D is the maximum dimensionality of any array
used in the program) grid of N 1   N 2  processors. Such a topology can easily be embedded
on almost any distributed memory machine. A processor in such a topology is represented by the tuple
D. The correspondence between a tuple (p
processor number in the range 0 to established by the scheme which embeds the virtual processor
grid topology on the real target machine. To make the notation describing replication of data simpler, we
extend the representation of the processor tuple in the following manner. A processor tuple with an X
appearing in the ith position denotes all processors along the ith grid dimension. Thus for a 2   2 grid of
processors, the tuple (0; X) represents the processors (0; 0) and (0; 1), while the tuple (X; X) represents all
the four processors.
The scalar variables and small arrays used in the program are assumed to be replicated on all processors.
For other arrays, we use a separate distribution function with each dimension to indicate how that array is
distributed across processors. This turns out to be more convenient than having a single distribution function
associated with a multidimensional array. We refer to the kth dimension of an array A as A k . Each array
dimension A k gets mapped to a unique dimension D, of the processor grid. If
the number of processors along that grid dimension is one, we say that the array dimension A k has
been sequentialized. The sequentialization of an array dimension implies that all elements whose subscripts
differ only in that dimension are allocated to the same processor. The distribution function for A k takes as
its argument an index i and returns the component of the tuple representing the processor which
owns the element A[\Gamma; denotes an arbitrary value, and i is the index appearing in
the k th dimension. The array dimension A k may either be partitioned or replicated on the corresponding
grid dimension. The distribution function is of the form
ae
b i\Gammaoffset
block c[modN
replicated
where the square parentheses surrounding modN
indicate that the appearance of this part in the
expression is optional. At a higher level, the given formulation of the distribution function can be thought of
as specifying the following parameters: (1) whether the array dimension is partitioned across processors or
replicated, (2) method of partitioning - contiguous or cyclic, (3) the grid dimension to which the kth array
dimension gets mapped, (4) the block size for distribution, i.e., the number of elements residing together as
a block on a processor, and (5) the displacement applied to the subscript value for mapping.
Examples of some data distribution schemes possible for a array on a 4-processor machine are
shown in Figure 1. The numbers shown in the figure indicate the processor(s) to which that part of the array
is allocated. The machine is considered to be an N 1   N 2 mesh, and the processor number corresponding to
the tuple (p . The distribution functions corresponding to the different figures
are given below. The array subscripts are assumed to start with the value 1, as in Fortran.
a)
c)
d)
f)
The last example illustrates how our notation allows us to specify partial replication of data, i.e., replication
of an array dimension along a specific dimension of the processor grid. An array is replicated completely
on all the processors if the distribution function for each of its dimensions takes the value X.
If the dimensionality (D) of the processor topology is greater than the dimensionality (d) of an array,
we need D \Gamma d more distribution functions in order to completely specify the processor(s) owning a given
element of the array. These functions provide the remaining D \Gamma d numbers of the processor tuple. We
restrict these "functions" to take constant values, or the value X if the array is to be replicated along the
corresponding grid dimension.
Most of the arrays used in real scientific programs, such as routines from LINPACK and EISPACK
libraries and most of the Perfect Benchmark programs [6], have fewer than three dimensions. We believe
that even for programs with higher dimensional arrays, restricting the number of dimensions that can be
distributed across processors to two usually does not lead to any loss of effective parallelism. Consider the
completely parallel loop nest shown below:
do
do
do
Even though the loop has parallelism at all three levels, a two-dimensional grid topology in which Z 1 and Z 2
are distributed and Z 3 is sequentialized would give the same performance as a three-dimensional topology
with the same number of processors, in which all of Z are distributed. In order to simplify our
strategy, and with the above observation providing some justification, we shall assume for now that our
underlying target topology is a two-dimensional mesh. For the sake of notation describing the distribution
of an array dimension on a grid dimension, we shall continue to regard the target topology conceptually as
a D-dimensional grid, with the restriction that the values of N are later set to one.
3 Constraints on Data Distribution
The data references associated with each loop in the program indicate some desirable properties that the
final distribution for various arrays should have. We formulate these desirable characteristics as constraints
on the data distribution functions. Our use of this term differs slightly from its common usage in the sense
that constraints on data distribution represent requirements that should be met, and not requirements that
necessarily have to be met.
Corresponding to each statement assigning values to an array in a parallelizable loop, there are two kinds
of constraints, parallelization constraints and communication constraints. The former kind gives constraints
on the distribution of the array appearing on the left hand side of the assignment statement. The distribution
should be such that the array elements being assigned values in a parallelizable loop are distributed evenly
on as many processors as possible, so that we get good performance due to exploitation of parallelism. The
communication constraints try to ensure that the data elements being read in a statement reside on the same
processor as the one that owns the data element being written into. The motivation for that is the owner
computes rule [9] followed by almost all parallelization systems for multicomputers. According to that rule,
the processor responsible for a computation is the one that owns the data item being assigned a value in that
computation. Whenever that computation involves the use of a value not available locally on the processor,
there is a need for interprocessor communication. The communication constraints try to eliminate this need
for interprocessor communication, whenever possible.
In general, depending on the kind of loop (a single loop may correspond to more than one category), we
have rules for imposing the following kinds of constraints:
1. Parallelizable loop in which array A gets assigned values - parallelization constraints on the distribution
of A.
2. Loop in which assignments to array A use values of array B - communication constraints specifying
the relationship between distributions of A and B.
3. Loop in which assignments to certain elements of A use values of different elements of A - communication
constraints on the distribution of A.
4. Loop in which a single assignment statement uses values of multiple elements of array B - communication
constraints on the distribution of B.
The constraints on the distribution of an array may specify any of the relevant parameters, such as the
number of processors on which an array dimension is distributed, whether the distribution is contiguous or
cyclic, and the block size of distribution. There are two kinds of constraints on the relationship between
distribution of arrays. One kind specifies the alignment between dimensions of different arrays. Two array
dimensions are said to be aligned if they get distributed on the same processor grid dimension. The other
kind of constraint on relationships formulates one distribution function in terms of the other for aligned
dimensions. For example, consider the loop shown below:
do
The data references in this loop suggest that A 1 should be aligned with B 1 , and A 2 should be sequentialized.
Secondly, they suggest the following distribution function for B 1 , in terms of that for A 1 .
A (i)
A (bi=c 2 c) (1)
Thus, given parameters regarding the distribution of A, like the block size, the offset, and the number of
processors, we can determine the corresponding parameters regarding the distribution of B by looking at
the relationship between the two distributions.
Intuitively, the notion of constraints provides an abstraction of the significance of each loop with respect to
data distribution. The distribution of each array involves taking decisions regarding a number of parameters
described earlier, and each constraint specifies only the basic minimal requirements on distribution. Hence
the parameters related to the distribution of an array left unspecified by a constraint may be selected by
combining that constraint with others specifying those parameters. Each such combination leads to an
improvement in the distribution scheme for the program as a whole.
However, different parts of the program may also impose conflicting requirements on the distribution of
various arrays, in the form of constraints inconsistent with each other. In order to resolve those conflicts,
we associate a measure of quality with each constraint. Depending on the kind of constraint, we use one
of the following two quality measures - the penalty in execution time, or the actual execution time. For
constraints which are finally either satisfied or not satisfied by the data distribution scheme (we refer to
them as boolean constraints, an example of such a constraint is one specifying the alignment of two array
dimensions), we use the first measure which estimates the penalty paid in execution time if that constraint is
not honored. For constraints specifying the distribution of an array dimension over a number of processors,
we use the second measure which expresses the execution time as a simple function of the number of proces-
sors. Depending on whether a constraint affects the amount of parallelism exploited or the interprocessor
communication requirement, or both, the expression for its quality measure has terms for the computation
time, the communication time, or both.
One problem with estimating the quality measures of constraints is that they may depend on certain
parameters of the final distribution that are not known beforehand. We express those quality measures
as functions of parameters not known at that stage. For instance, the quality measure of a constraint on
alignment of two array dimensions depends on the numbers of processors on which the two dimensions are
otherwise distributed, and is expressed as a function of those numbers.
Determining Constraints and their Quality Measures
The success of our strategy for data partitioning depends greatly on the compiler's ability to recognize
data reference patterns in various loops of the program, and to record the constraints indicated by those
references, along with their quality measures. We limit our attention to statements that involve assignment
to arrays, since all scalar variables are replicated on all the processors. The computation time component
of the quality measure of a constraint is determined by estimating the time for sequential execution based
on a count of various operations, and by estimating the speedup. Determining the communication time
component is a relatively tougher problem. We have developed a methodology for compile-time estimation
of communication costs incurred by a program [8]. It is based on identifying the primitives needed to carry
out interprocessor communication and determining the message sizes. The communication costs are obtained
as functions of the numbers of processors over which various arrays are distributed, and of the method of
partitioning, namely, contiguous or cyclic. The quality measures of various communication constraints are
based on the estimates obtained by following this methodology. We shall briefly describe it here, further
details can be found in [8].
Communication Primitives We use array reference patterns to determine which communication routines
out of a given library best realize the required communication for various loops. This idea was first
presented by Li and Chen [14] to show how explicit communication can be synthesized by analyzing data
reference patterns. We have extended their work in several ways, and are able to handle a much more
comprehensive set of patterns than those described in [14]. We assume that the following communication
routines are supported by the operating system or by the run-time library:
sending a message from a single source to a single destination processor.
OneToManyMulticast : multicasting a message to all processors along the specified dimension(s) of the
processor grid.
reducing (in the sense of the APL reduction operator) data using a simple associative
operator, over all processors lying on the specified grid dimension(s).
ManyToManyMulticast : replicating data from all processors on the given grid dimension(s) on to
themselves.

Table

1 shows the cost complexities of functions corresponding to these primitives on the hypercube
architecture. The parameter m denotes the message size in words, seq is a sequence of numbers representing
the numbers of processors in various dimensions over which the aggregate communication primitive is carried
out. The function num applied to a sequence simply returns the total number of processors represented
by that sequence, namely, the product of all the numbers in that sequence. In general, a parallelization
system written for a given machine must have a knowledge of the actual timing figures associated with these
primitives on that machine. One possible approach to obtaining such timing figures is the "training set
method" that has recently been proposed by Balasundaram et al. [2].
Subscript Types An array reference pattern is characterized by the loops in which the statement appears,
and the kind of subscript expressions used to index various dimensions of the array. Each subscript expression
is assigned to one of the following categories:
if the subscript expression evaluates to a constant at compile time.
if the subscript expression reduces to the form c 1   are constants and i is a
loop index. Note that induction variables corresponding to a single loop index also fall in this category.
ffl variable: this is the default case, and signifies that the compiler has no knowledge of how the subscript
expression varies with different iterations of the loop.
For subscripts of the type index or variable, we define a parameter called change-level, which is the level
of the innermost loop in which the subscript expression changes its value. For a subscript of the type index,
that is simply the level of the loop that corresponds to the index appearing in the expression.
Method For each statement in a loop in which the assignment to an array uses values from the same or
a different array (we shall refer to the arrays appearing on the left hand side and the right hand side of the
assignment statement as lhs and rhs arrays), we express estimates of the communication costs as functions
of the numbers of processors on which various dimensions of those arrays are distributed. If the assignment
statement has references to multiple arrays, the same procedure is repeated for each rhs array. For the sake
of brevity, here we shall give only a brief outline of the steps of the procedure. The details of the algorithm
associated with each step are given in [8].
1. For each loop enclosing the statement (the loops need not be perfectly nested inside one another),
determine whether the communication required (if any) can be taken out of that loop. This step
ensures that whenever different messages being sent in different iterations of a loop can be combined,
we recognize that opportunity and use the cost functions associated with aggregate communication
primitives rather than those associated with repeated Transfer operations. Our algorithm for taking
this decision also identifies program transformations, such as loop distribution and loop permutations,
that expose opportunities for combining of messages.
2. For each rhs reference, identify the pairs of dimensions from the arrays on rhs and lhs that should be
aligned. The communication costs are determined assuming such an alignment of array dimensions.
To determine the quality measures of alignment constraints, we simply have to obtain the difference
in costs between the cases when the given dimensions are aligned and when they are not.
3. For each pair of subscripts in the lhs and rhs references corresponding to aligned dimensions, identify
the communication term(s) representing the "contribution" of that pair to the overall communication
costs. Whenever at least one subscript in that pair is of the type index or variable, the term represents
a contribution from an enclosing loop identified by the value of change-level. The kind of contribution
from a loop depends on whether or not the loop has been identified in step 1 as one from which
communication can be taken outside. If communication can be taken outside, the term contributed by
that loop corresponds to an aggregate communication primitive, otherwise it corresponds to a repeated
Transfer.
4. If there are multiple references in the statement to an rhs array, identify the isomorphic references,
namely, the references in which the subscripts corresponding to each dimension are of the same type.
The communication costs pertaining to all isomorphic references are obtained by looking at the costs
corresponding to one of those references, as in step 3, and determining how they get modified by
"adjustment" terms from the remaining references.
5. Once all the communication terms representing the contributions of various loops and of various loop-
independent subscript pairs have been obtained, compose them together using an appropriate ordering,
and determine the overall communication costs involved in executing the given assignment statement
in the program.
Examples We now present some example program segments to show the kind of constraints inferred from
data references and the associated quality measures obtained by applying our methodology. Along with
each example, we provide an explanation to justify the quality measure derived for each constraint. The
expressions for quality measures are, however, obtained automatically by following our methodology.
Example 1: do
do
Parallelization Constraints: Distribute A 1 and A 2 in a cyclic manner.
Our example shows a multiply nested parallel loop in which the extent of variation of the index in an inner
loop varies with the value of the index in an outer loop. A simplified analysis indicates that if A 1 and A 2
are distributed in a cyclic manner, we would obtain a speedup of nearly N , otherwise the imbalance caused
by contiguous distribution would lead to the effective speedup decreasing by a factor of two. If C p is the
estimated time for sequential execution of the given program segment, the quality measure is:
Example 2: do
do
Communication Constraints: Align A 1 with ensure that their distributions are
related in the following manner:
A (j) (2)
A (i)
A (b i
c) (3)
If the dimension pairs we mentioned are not aligned or if the above relationships do not hold, the elements
of B residing on a processor may be needed by any other processor. Hence all the n 1   n 2 =(N I   N J ) elements
held by each processor are replicated on all the processors.
do
do
Communication Constraints :
ffl Align A 1 with
As seen in the previous example, the values of B held by each of the N I   N J processors have to be
replicated if the indicated dimensions are not aligned.
is distributed on N I ? 1 processors, each processor needs to get elements on the "boundary"
rows of the two "neighboring" processors.
The given term indicates that a Transfer operation takes place only if the condition (N I ? 1) is
The analysis is similar to that for the previous case.
in a contiguous manner.
distributed cyclically, each processor needs to communicate all of its B elements to its two
neighboring processors.
in a contiguous manner.
The analysis is similar to that for the previous case.
Note : The above loop also has parallelization constraints associated with it. If C p indicates the estimated
sequential execution time of the loop, by combining the computation time estimate given by the parallelization
constraint with the communication time estimates given above, we get the following expression for
execution time:
I   N J
It is interesting to see that the above expression captures the relative advantages of distribution of arrays A
and B by rows, columns, or blocks for different cases corresponding to the different values of n 1 and n 2 .
5 Strategy for Data Partitioning
The basic idea in our strategy is to consider all constraints on distribution of various arrays indicated by the
important segments of the program, and combine them in a consistent manner to obtain the overall data
distribution. We resolve conflicts between mutually inconsistent constraints on the basis of their quality
measures.
The quality measures of constraints are often expressed in terms of n i (the number of elements along an
arry dimension), and N I (the number of processors on which that dimension is distributed). To compare
them numerically, we need to estimate the values of n i and N I . The value of n i may be supplied by the
user through an assertion, or specified in an interactive environment, or it may be estimated by the compiler
on the basis of the array declarations seen in the program. The need for values of variables of the form
I poses a circular problem - these values become known only after the final distribution scheme has been
determined, and are needed at a stage when decisions about data distribution are being taken. We break this
circularity by assuming initially that all array dimensions are distributed on an equal number of processors.
Once enough decisions on data distribution have been taken so that for each boolean constraint we know
whether it is satisfied or not, we start using expressions for execution time as functions of various N I , and
determine their actual values so that the execution time is minimized.
Our strategy for determining the data distribution scheme, given information about all the constraints,
consists of the steps given below. Each step involves taking decisions about some aspect of the data distribu-
tion. In this manner, we keep building upon the partial information describing the data partitioning scheme
until the complete picture emerges. Such an approach fits in naturally with our idea of using constraints on
distributions, since each constraint can itself be looked upon as a partial specification of the data distribu-
tion. All the steps presented here are simple enough to be automated. Hence the "we" in our discussion
really refers to the parallelizing compiler.
1. Determine the alignment of dimensions of various arrays: This problem has been referred to as the
component alignment problem by Li and Chen in [15]. They prove the problem NP-complete and
give an efficient heuristic algorithm for it. We adapt their approach to our problem and use their
algorithm to determine the alignment of array dimensions. An undirected, weighted graph called a
component affinity graph (CAG) is constructed from the source program. The nodes of the graph
represent dimensions of arrays. For every constraint on the alignment of two dimensions, an edge
having a weight equal to the quality measure of the constraint is generated between the corresponding
two nodes. The component alignment problem is defined as partitioning the node set of the CAG
into D (D being the maximum dimension of arrays) disjoint subsets so that the total weight of edges
across nodes in different subsets is minimized, with the restriction that no two nodes corresponding to
the same array are in the same subset. Thus the (approximate) solution to the component alignment
problem indicates which dimensions of various arrays should be aligned. We can now establish a
one-to-one correspondence between each class of aligned array dimensions and a virtual dimension of
the processor grid topology. Thus, the mapping of each array dimension to a virtual grid dimension
becomes known at the end of this step.
2. Sequentialize array dimensions that need not be partitioned : If in a given class of aligned array dimen-
sions, there is no dimension which necessarily has to be distributed across more than one processor to
get any speedup (this is determined by looking at all the parallelization constraints), we sequentialize
all dimensions in that class. This can lead to significant savings in communication costs without any
loss of effective parallelism.
3. Determine the following parameters for distribution along each dimension - contiguous/cyclic and
relative block sizes: For each class of dimensions that is not sequentialized, all array dimensions with
the same number of elements are given the same kind of distribution, contiguous or cyclic. For all
such array dimensions, we compare the sum total of quality measures of the constraints advocating
contiguous distribution and those favoring cyclic distribution, and choose the one with the higher total
quality measure. Thus a collective decision is taken on all dimensions in that class to maximize overall
gains.
If an array dimension is distributed over a certain number of processors in a contiguous manner, the
block size is determined by the number of elements along that dimension. However, if the distribution
is cyclic, we have some flexibility in choosing the size of blocks that get cyclically distributed. Hence,
if cyclic distribution is chosen for a class of aligned dimensions, we look at constraints on the relative
block sizes pertaining to the distribution of various dimensions in that class. All such constraints
may not be mutually consistent. Hence, the strategy we adopt is to partition the given class of aligned
dimensions into equivalence sub-classes, where each member in a sub-class has the same block size. The
assignment of dimensions to these sub-classes is done by following a greedy approach. The constraints
implying such relationships between two distributions are considered in the non-increasing order of
their quality measures. If any of the two concerned array dimensions has not yet been assigned to a
sub-class, the assignment is done on the basis of their relative block sizes implied by that constraint.
If both dimensions have already been assigned to their respective sub-classes, the present constraint
is ignored, since the assignment must have been done using some constraint with a higher quality
measure. Once all the relative block sizes have been determined using this heuristic, the smallest block
size is fixed at one, and the related block sizes determined accordingly.
4. Determine the number of processors along each dimension: At this point, for each boolean constraint
we know whether it has been satisfied or not. By adding together the terms for computation time and
communication time with the quality measures of constraints that have not been satisfied, we obtain an
expression for the estimated execution time. Let D 0 denote the number of virtual grid dimensions not
yet sequentialized at this point. The expression obtained for execution time is a function of variables
representing the numbers of processors along the corresponding grid dimensions. For
most real programs, we expect the value of D 0 to be two or one. If D 0 ? 2, we first sequentialize all
except for two of the given dimensions based on the following heuristic. We evaluate the execution
time expression of the program for C D 0cases, each case corresponding to 2 different N i variables set
to
N , and the other D set to 1 (N is the total number of processors in the system).
The case which gives the smallest value for execution time is chosen, and the corresponding D
dimensions are sequentialized.
Once we get down to two dimensions, the execution time expression is a function of just one variable,
1 , since N 2 is given by N=N 1 . We now evaluate the execution time expression for different values of
various factors of N ranging from 1 to N , and select the one which leads to the smallest execution
time.
5. Take decisions on replication of arrays or array dimensions: We take two kinds of decisions in this step.
The first kind consists of determining the additional distribution function for each one-dimensional
array when the finally chosen grid topology has two real dimensions. The other kind involves deciding
whether to override the given distribution function for an array dimension to ensure that it is replicated
rather than partitioned over processors in the corresponding grid dimension. We assume that there
is enough memory on each processor to support replication of any array deemed necessary. (If this
assumption does not hold, the strategy simply has to be modified to become more selective about
choosing arrays or array dimensions for replication).
The second distribution function of a one-dimensional array may be an integer constant, in which case
each array element gets mapped to a unique processor, or may take the value X, signifying that the
elements get replicated along that dimension. For each array, we look at the constraints corresponding
to the loops where that array is being used. The array is a candidate for replication along the second
grid dimension if the quality measure of some constraint not being satisfied shows that the array has
to be multicast over that dimension. An example of such an array is the array B in the example loop
shown in Section 3, if A 2 is not sequentialized. A decision favoring replication is taken only if each
time the array is written into, the cost of all processors in the second grid dimension carrying out that
computation is less than the sum of costs of performing that computation on a single processor and
multicasting the result. Note that the cost for performing a computation on all processors can turn
out to be less only if all the values needed for that computation are themselves replicated. For every
one-dimensional array that is not replicated, the second distribution function is given the constant
value of zero.
A decision to override the distribution function of an array dimension from partitioning to replication
on a grid dimension is taken very sparingly. Replication is done only if no array element is written
more than once in the program, and there are loops that involve sending values of elements from that
array to processors along that grid dimension.
A simple example illustrating how our strategy combines constraints across loops is shown below:
do
do
do
The first loop imposes constraints on the alignment of A 1
with
, since the same variable is being used as a
subscript in those dimensions. It also suggests sequentialization of A 2
, so that regardless of the values
of c 1
and c 2
, the elements
may reside on the same processor. The second loop imposes
a requirement that the distribution of A be cyclic. The compiler recognizes that the range of the inner loop
is fixed directly by the value of the outer loop index, hence there would be a serious imbalance of load on
processors carrying out the partial summation unless the array is distributed cyclically. These constraints
are all consistent with each other and get accepted in steps 1, 4 and 3 respectively, of our strategy. Hence
finally, the combination of these constraints leads to the following distributions - row-wise cyclic for A, and
column-wise cyclic for B.
In general, there can be conflicts at each step of our strategy because of different constraints implied
by various loops not being consistent with each other. Such conflicts get resolved on the basis of quality
measures.
6 Study of Numeric Programs
Our approach to automatic data partitioning presupposes the compiler's ability to identify various dependences
in a program. We are currently in the process of implementing our approach using Parafrase-2 [17], a
source-to-source restructurer being developed at the University of Illinois, as the underlying tool for analyzing
programs. Prior to that, we performed an extensive study using some well known scientific application
programs to determine the applicability of our proposed ideas to real programs. One of our objectives was
to determine to what extent a state-of-the-art parallelizing compiler can provide information about data
references in a program so that our system may infer appropriate constraints on the distribution of arrays.
However, even when complete information about a program's computation structure is available, the problem
of determining an optimal data decomposition scheme is NP-hard. Hence, our second objective was to
find out if our strategy leads to good decisions on data partitioning, given enough information about data
references in a program.
Application Programs Five different Fortran programs of varying complexity are used in this study.
The simplest program chosen uses the routine dgefa from the Linpack library. This routine factors a real
matrix using gaussian elimination with partial pivoting. The next program uses the Eispack library routine,
tred2 , which reduces a real symmetric matrix to a symmetric tridiagonal matrix, using and accumulating
orthogonal similarity transformations. The remaining three programs are from the Perfect Club Benchmark
Suite [6]. The program trfd simulates the computational aspects of a two-electron integral transformation.
The code for mdg provides a molecular dynamics model for water molecules in the liquid state at room
temperature and pressure. Flo52 is a two-dimensional code providing an analysis of the transonic inviscid
flow past an airfoil by solving the unsteady Euler equations.
Methodology The testbed for implementation and evaluation of our scheme is the Intel iPSC/2 hyper-cube
system. Our objective is to obtain good data partitionings for programs running on a 16-processor
configuration. Obtaining the actual values of quality measures for various constraints requires us to have a
knowledge of the costs of various communication primitives and of arithmetic operations on the machine.
We use the following approximate function [10] to estimate the time taken, in microseconds, to complete a
ransfer operation on l bytes :
ae
In our parallel code, we implement the ManyToManyMulticast primitive as repeated calls to the OneToMany-
Multicast primitive, hence in our estimates of the quality measures, the former functions is expressed in terms
of the latter one. Each OneToManyMulticast operation sending a message to p processors is assumed to be
pe times as expensive as a Transfer operation for a message of the same size. The time taken to execute
a double precision floating point add or multiply operation is taken to be approximately 5 microseconds.
The floating point division is assumed to be twice as expensive, a simple assignment (load and store) about
one-tenth as expensive, and the overhead of making an arithmetic function call about five times as much.
The timing overhead associated with various control instructions is ignored.
In this study, apart from the use of Parafrase-2 to indicate which loops were parallelizable, all the steps
of our approach were simulated by hand. We used this study more as an opportunity to gain further insight
into the data decomposition problem and examine the feasibility of our approach.
Results For a large majority of loops, Parafrase-2 is able to generate enough information to enable
appropriate formulation of constraints and determination of their quality measures by our approach. There
are some loops for which the information about parallelization is not adequate. Based on an examination of
all the programs, we have identified the following techniques with which the underlying parallelizing compiler
used in implementing our approach needs to be augmented.
ffl More sophisticated interprocedural analysis - there is a need for constant propagation across procedures
[3], and in some cases, we need additional reference information about variables in the procedure or
in-line expansion of the procedure.
ffl An extension of the idea of scalar expansion, namely, the expansion of small arrays. This is essential
to get the benefits of our approach in which, like scalar variables, we also treat small arrays as being
replicated on all processors. This helps in the removal of anti-dependence and output-dependence from
loops in a number of cases, and often saves the compiler from getting "fooled" into parallelizing the
smaller loops involving those arrays, at the expense of leaving the bigger parallelizable loops sequential.
ffl Recognition of reduction operators, so that a loop with such an operator may get parallelized appro-
priately. Examples of these are the addition, the min and the max operators.
Since none of these features are beyond the capabilities of Parafrase-2 when it gets fully developed (or
for that matter, any state-of-the-art parallelizing compiler), we assume in the remaining part of our study
that these capabilities are present in the parallelizing compiler supporting our implementation.
We now present the distribution schemes for various arrays we arrive at by applying our strategy to
the programs after various constraints and the associated quality measures have been recorded. Table 2
summarizes the final distribution of significant arrays for all the programs. We use the following informal
notation in this description. For each array, we indicate the number of elements along each dimension and
specify how each dimension is distributed (cyclic/contiguous/replicated). We also indicate the number of
processors on which that dimension is distributed. For the special case in which that number is one, we
indicate that the dimension has been sequentialized. For example, the first entry in the table shows that
the 2-D arrays A and Z consisting of 512 x 512 elements each are to be distributed cyclically by rows on
processors. We choose the tred2 routine to illustrate the steps of our strategy in greater detail, since it
is a small yet reasonably complex program which defies easy determination of "the right" data partitioning
scheme by simple inspection. For the remaining programs, we explain on what basis certain important
decisions related to the formulation of constraints on array distributions in them are taken, sometimes with
the help of sample program segments. For the tred2 program, we show the effectiveness of our strategy
through actual results on the performance of different versions of the parallel program implemented on the
iPSC/2 using different data partitioning strategies.
TRED2 The source code of tred2 is listed in Figure 2. Along with the code listing, we have shown the
probabilities of taking the branch on various conditional go to statements. These probabilities are assumed to
be supplied to the compiler. Also, corresponding to each statement in a loop that imposes some constraints,
we have indicated which of the four categories (described in Section 3) the constraint belongs to.
Based on the alignment constraints, a component affinity graph (CAG), shown in Figure 3, is constructed
for the program . Each node of a CAG [15] represents an array dimension, the weight on an edge denotes
the communication cost incurred if the array dimensions represented by the two nodes corresponding to that
edge are not aligned. The edge weights for our CAG are as follows:
I   OneToManyMulticast(n=N I ; hN J i) (line 83)
Along with each term, we have indicated the line number in the program to which the constraint corresponding
to the quality measure may be traced. The total number of processors is denoted by N , while
N I and N J refer to the number of processors along which various array dimensions are initially assumed to
be distributed. Applying the algorithm for component alignment [15] on this graph, we get the following
classes of dimensions - class 1 consisting of A 1 consisting of A 2 ; Z 2 . These classes
get mapped to the dimensions 1 and 2 respectively of the processor grid.
In Step 2 of our strategy, none of the array dimensions is sequentialized because there are parallelization
constraints favoring the distribution of both dimensions Z 1 and Z 2 . In Step 3, the distribution functions for
all array dimensions in each of the two classes are determined to be cyclic, because of numerous constraints
on each dimension of arrays Z; D and E favoring cyclic distribution. The block size for the distribution for
each of the aligned array dimensions is set to one. Hence, at the end of this step, the distributions for various
array dimensions are:
Moving on to Step 4, we now determine the value of N 1 , the value of N 2 simply gets fixed as N=N 1 . By
adding together the actual time measures given for various constraints, and the penalty measures of various
constraints not getting satisfied, we get the following expression for execution time of the program (only the
part dependent on N 1 ).
c
For (in fact, for all values of N ranging from 4 to 16), we see that the above
expression for execution time gets minimized when the value of N 1 is set to N . This is easy to see since the
first term (appearing in boldface), which dominates the expression, vanishes when N Incidentally,
that term comes from the quality measures of various constraints to sequentialize Z 2 . The real processor
grid, therefore, has only one dimension, all array dimensions in the second class get sequentialized. Hence
the distribution functions for the array dimensions at the end of this step are:
Since we are using the processor grid as one with a single dimension, we do not need the second distribution
function for the arrays D and E to uniquely specify which processors own various elements of these arrays.
None of the array dimensions is chosen for replication in Step 5. As specified above by the formal definitions
of distribution functions, the data distribution scheme that finally emerges is - distribute arrays A and Z
by rows in a cyclic fashion, distribute arrays D and E also cyclically, on all the N processors.
DGEFA The dgefa routine operates on a single n x n array A, which is factorized using gaussian elimination
with partial pivoting. Let N 1 and N 2 denote, respectively, the number of processors over which the
rows and the columns of the array are distributed. The loop computing the maximum of all elements in a
column (pivot element) and the one scaling all elements in a column both yield execution time terms that
show the communication time part increasing and the computation time part decreasing due to increased
parallelism, with increase in N 1 . The loop involving exchange of rows (due to pivoting) suggests a constraint
to sequentialize A 1 , i.e., setting N 1 to 1, to internalize the communication corresponding to the exchange of
rows. The doubly-nested loop involving update of array elements corresponding to the triangularization of
a column shows parallelism and potential communication (if parallelization is done) at each level of nesting.
All these parallelizable loops are nested inside a single inherently sequential loop in the program, and the
number of iterations they execute varies directly with the value of the outer loop index. Hence these loops
impose constraints on the distribution of A along both dimensions to be cyclic, to have a better load balance.
The compiler needs to know the value of n to evaluate the expression for execution time with N 1 (or
being the only unknown. We present results for two cases, 256. The analysis shows that
for the first case, the compiler would come up with N 1
16, where as for the second case, it would
8. Thus given information about the value of n, the compiler would favor column-cyclic
distribution of A for smaller values of n, and grid-cyclic distribution for larger values of n.
TRFD The trfd benchmark program goes through a series of passes, each pass essentially involves setting
up some data arrays and making repeated calls in a loop to a particular subroutine. We apply our approach
to get the distribution for arrays used in that subroutine. There are nine arrays that get used, as shown in

Table

3 (some of them are actually aliases of each other). To give a flavor for how these distributions get
arrived at, we show some program segments below:
do
do 70
do
70 continue
The first loop leads to the following constraints - alignment of xrsiq 1 with v 2 , and sequentialization of xrsiq 2
and v 1 . The second loop advocates alignment of xij 1 with v 2 , sequentialization of v 1 , and cyclic distribution
of xij 1 (since the number of iterations of the inner loop modifying xij varies with the value of the outer
loop index). The constraint on cyclic distribution gets passed on from xij 1 to v 2 , and from v 2 to xrsiq 1 . All
these constraints together imply a column-cyclic distribution for v, a row-cyclic distribution for xrsiq, and
a cyclic distribution for xij. Similarly, appropriate distribution schemes are determined for the arrays xijks
and xkl. The references involving arrays xrspq; xijrs; xrsij; xijkl are somewhat complex, the variation of
subscripts in many of these references cannot be analyzed by the compiler. The distribution of these arrays
is specified as being contiguous to reduce certain communication costs involving broadcast of values of these
arrays.
MDG This program uses two important arrays, var and vm, and a number of small arrays which are all
replicated according to our strategy. The array vm is divided into three parts, which get used as different
arrays named xm; ym; zm in various subroutines. Similarly, the array var gets partitioned into twelve parts
which appear in different subroutines with different names. In Table 3 we show the distributions of these
individual, smaller arrays. The arrays fx; fy; fz all correspond to two different parts of var each, in different
invocations of the subroutine interf.
In the program there are numerous parallelizable loops in each of which three distinct contiguous elements
of an array corresponding to var get accessed together in each iteration. They lead to constraints that the
distributions of those arrays use a block size that is a multiple of three. There are doubly nested loops in
subroutines interf and poteng operating over some of these arrays with the number of iterations of the inner
loop varying directly with the value of the outer loop index. As seen for the earlier programs, this leads
to constraints on those arrays to be cyclically distributed. Combined with the previous constraints, we get
a distribution scheme in which those arrays are partitioned into blocks of three elements distributed
cyclically. We show parts of a program segment, using a slightly changed syntax (to make the code more
concise), that illustrates how the relationship between distributions of parts of var (x; and parts of vm
do 1000
1000 continue
In this loop, the variables iwo; iw1; iw2 get recognized as induction variables and are expressed in terms
of the loop index i. The references in the loop establish the correspondence of each element of xm with
a three-element block of x, and yield similar relationships involving arrays ym and zm. Hence the arrays
xm; ym; zm are given a cyclic distribution (completely cyclic distribution with a block size of one).
FLO52 This program has computations involving a number of significant arrays shown in Table 3. Many
arrays declared in the main program really represent a collection of smaller arrays of different sizes, referenced
in different steps of the program by the same name. For instance, the array w is declared as a big 1-D array
in the main program, different parts of which get supplied to subroutines such as euler as a parameter (the
formal parameter is a 3-D array w) in different steps of the program. In such cases, we always refer to these
smaller arrays passed to various subroutines, when describing the distribution of arrays. Also, when the size
of an array such as w varies in different steps of the program, the entry for size of the array in the table
indicates that of the largest array.
A number of parallelizable loops referencing the 3-D arrays w and x access all elements varying along the
third dimension of the array together in a single assignment statement. Hence the third dimension of each
of these arrays is sequentialized. There are numerous parallelizable loops that establish constraints on all
of the 2-D arrays listed in the table to have identical distributions. Moreover, the two dimensions of these
array are aligned with the first two dimensions of all listed 3-D arrays, as dictated by the reference patterns
in several other loops. Some other interesting issues are illustrated by the following program segments.
do
do
do
do
38 continue
These loops impose constraints on the (first) two dimensions of all of these arrays to have contiguous rather
than cyclic distributions, so that the communications involving p values occur only "across boundaries"
of regions of the arrays allocated to various processors. Let N 1 and N 2 denote the number of processors
on which the first and second dimensions are distributed. The first part of the program segment specifies
a constraint to sequentialize p 1 , while the second one gives a constraint to sequentialize p 2 . The quality
measures for these constraints give terms for communication costs that vanish when N 1 and N 2 respectively
are set to one. In order to choose the actual values of N 1 and N 2 (given that N 1   the compiler
has to evaluate the expression for execution time for different values of N 1 and N 2 . This requires it to
know the values of array bounds, specified in the above program segment by variables il and jl. Since these
values actually depend on user input, the compiler would assume the real array bounds to be the same as
those given in the array declarations. Based on our simplified analysis, we expect the compiler to finally
come up with Given more accurate information or under different assumptions about the
array bounds, the values chosen for N 1
and N 2
may be different. The distributions for other 1-D arrays
indicated in the table get determined appropriately - in some cases, based on considerations of alignment
of array dimensions, and in others, due to contiguous distribution on processors being the default mode of
distribution.
Experimental Results on TRED2 Program Implementation We now show results on the performance
of different versions of the parallel tred2 program implemented on the iPSC/2 using different data
partitioning strategies. The data distribution scheme selected by our strategy, as shown in Table 2 is -
distribute arrays A and Z by rows in a cyclic fashion, distribute array D and E also in a cyclic manner, on
all the N processors.
Starting from the sequential program, we wrote the target host and node programs for the iPSC/2 by
hand, using the scheme suggested for a parallelizing compiler in [4] and [22], and hand-optimized the code.
We first implemented the version that uses the data distribution scheme suggested by our strategy, i.e,
row cyclic. An alternate scheme that also looks reasonable by looking at various constraints is one which
distributes the arrays A and Z by columns instead of rows. To get an idea of the gains made in performance
by sequentializing a class of dimensions, i.e., by not distributing A and Z in a blocked (grid-like) manner,
and also gains made by choosing a cyclic rather than contiguous distribution for all arrays, we implemented
two other versions of the program. These versions correspond to the "bad" choices on data distribution
that a user might make if he is not careful enough. The programs were run for two different data sizes
corresponding to the values 256 and 512 for n.
The plots of performance of various versions of the program are shown in Figure 4. The sequential time
for the program is not shown for the case since the program could not be run on a single node
due to memory limitations. The data partitioning scheme suggested by our strategy performs much better
than other schemes for that data size as shown in Figure 7 (b). For the smaller data size (Figure 7 (a)),
the scheme using column distribution of arrays works slightly better when fewer processors are being used.
Our approach does identify a number of constraints that favor the column distribution scheme, they just
get outweighed by the constraints that favor row-wise distribution of arrays. Regarding other issues, our
strategy clearly advocates the use of cyclic distribution rather than contiguous, and also the sequentialization
of a class of dimensions, as suggested by numerous constraints to sequentialize various array dimensions.
The fact that both these observations are indeed crucial can be seen from the poor performance of the
program corresponding to contiguous (row-wise, for A and Z) distribution of all arrays, and also of the one
corresponding to blocked (grid-like) distribution of arrays A and Z. These results show for this program
that our approach is able to take the right decisions regarding certain key parameters of data distribution,
and does suggest a data partitioning scheme that leads to good performance.
Conclusions
We have presented a new approach, the constraint-based approach, to the problem of determining suitable
data partitions for a program. Our approach is quite general, and can be applied to a large class of programs
having references that can be analyzed at compile time. We have demonstrated the effectiveness of our
approach for real-life scientific application programs. We feel that our major contributions to the problem
of automatic data partitioning are:
ffl Analysis of the entire program: We look at data distribution from the perspective of performance of
the entire program, not just that of some individual program segments. The notion of constraints
makes it easier to capture the requirements imposed by different parts of the program on the overall
data distribution. Since constraints associated with a loop specify only the basic minimal requirements
on data distribution, we are often able to combine constraints affecting different parameters relating
to the distribution of the same array. Our studies on numeric programs confirm that situations where
such a combining is possible arise frequently in real programs.
ffl Balance between parallelization and communication considerations: We take into account both communication
costs and parallelization considerations so that the overall execution time is reduced.
ffl Variety of distribution functions and relationships between distributions : Our formulation of the distribution
functions allows for a rich variety of possible distribution schemes for each array. The idea
of relationship between array distributions allows the constraints formulated on one array to influence
the distribution of other arrays in a desirable manner.
Our approach to data partitioning has its limitations too. There is no guarantee about the optimality
of results obtained by following our strategy (the given problem is NP-hard). The procedure for compile-time
determination of quality measures of constraints is based on a number of simplifying assumptions.
For instance, we assume that all the loop bounds and the probabilities of executing various branches of a
conditional statement are known to the compiler. For now, we expect the user to supply this information
interactively or in the form of assertions. In the future, we plan to use profiling to supply the compiler with
information regarding how frequently various basic blocks of the code are executed.
As mentioned earlier, we are in the process of implementing our approach for the Intel iPSC/2 hypercube
using the Parafrase-2 restructurer as the underlying system. We are also exploring a number of possible
extensions to our approach. An important issue being looked at is data reorganization: for some programs
it might be desirable to partition the data one way for a particular program segment, and then repartition
it before moving on to the next program segment. We also plan to look at the problem of interprocedural
analysis, so that the formulation of constraints may be done across procedure calls. Finally, we are examining
how better estimates could be obtained for quality measures of various constraints in the presence of compiler
optimizations like overlap of communication and computation, and elimination of redundant messages via
liveness analysis of array variables [9].
The importance of the problem of data partitioning is bound to continue growing as more and more
machines with larger number of processors keep getting built. There are a number of issues that need to
be resolved through further research before a truly automated, high quality system can be built for data
partitioning on multicomputers. However, we believe that the ideas presented in this paper do lay down an
effective framework for solving this problem.

Acknowledgements

We wish to express our sincere thanks to Prof. Constantine Polychronopoulos for giving us access to the
source code of the Parafrase-2 system, and for allowing us to build our system on top of it. We also wish to
thank the referees for their valuable suggestions.



--R

An interactive environment for data partitioning and distribution.
A static performance estimator to guide data partitioning decisions.
Interprocedural constant propagation.
Compiling programs for distributed-memory multiprocessors
Compiling parallel programs by optimizing performance.
The Perfect Club.
Automatic data partitioning on distributed memory multiprocessors.

Compiler support for machine-independent parallel programming in Fortran D
A message passing coprocessor for distributed memory multicomputers.
Compiler techniques for data partitioning of sequentially iterated parallel loops.
Programming for parallelism.
Compiler transformations for non-shared memory machines
Generating explicit communication from shared-memory program references
Index domain alignment: Minimizing cost of cross-referencing between distributed arrays
Memory Storage Patterns in Parallel Processing.

A methodology for parallelizing programs for multicomputers and complex memory multiprocessors.
Process decomposition through locality of reference.
The DINO parallel programming language.
An approach to compiling single-point iterative programs for distributed memory com- puters
SUPERB: A tool for semi-automatic MIMD/SIMD parallelization
--TR
Programming for parallelism
Memory storage patterns in parallel processing
Process decomposition through locality of reference
A methodology for parallelizing programs for multicomputers and complex memory multiprocessors
A static performance estimator to guide data partitioning decisions
A message passing coprocessor for distributed memory multicomputers
Generating explicit communication from shared-memory program references
Compiler techniques for data partitioning of sequentially iterated parallel loops

--CTR
Kuei-Ping Shih , Jang-Ping Sheu , Chua-Huang Huang, Statement-Level Communication-Free Partitioning Techniques for Parallelizing Compilers, The Journal of Supercomputing, v.15 n.3, p.243-269, Mar.1.2000
Rohit Chandra , Ding-Kai Chen , Robert Cox , Dror E. Maydan , Nenad Nedeljkovic , Jennifer M. Anderson, Data distribution support on distributed shared memory multiprocessors, ACM SIGPLAN Notices, v.32 n.5, p.334-345, May 1997
Tom Bennet, Distributed message routing and run-time support for message-passing parallel programs derived from ordinary programs, Proceedings of the 1994 ACM symposium on Applied computing, p.510-514, March 06-08, 1994, Phoenix, Arizona, United States
Manish Gupta , Edith Schonberg, Static analysis to reduce synchronization costs in data-parallel programs, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.322-332, January 21-24, 1996, St. Petersburg Beach, Florida, United States
A. Zaafrani , M. R. Ito, Partitioning the global space for distributed memory systems, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.327-336, December 1993, Portland, Oregon, United States
A. Zaafrani , Mabo Robert Ito, Efficient Execution of Doacross Loops on Distributed Memory Systems, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.27-38, January 20-22, 1993
T. S. Chen , J. P. Sheu, Communication-Free Data Allocation Techniques for Parallelizing Compilers on Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.924-938, September 1994
Ernesto Su , Daniel J. Palermo , Prithviraj Banerjee, Processor Tagged Descriptors: A Data Structure for Compiling for Distributed-Memory Multicomputers, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.123-132, August 24-26, 1994
Ram Subramanian , Santosh Pande, A framework for performance-based program partitioning, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
Ram Subramanian , Santosh Pande, A framework for performance-based program partitioning, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
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
Manish Gupta , Prithviraj Banerjee, A methodology for high-level synthesis of communication on multicomputers, Proceedings of the 6th international conference on Supercomputing, p.357-367, July 19-24, 1992, Washington, D. C., United States
Tatsuya Shindo , Hidetoshi Iwashita , Shaun Kaneshiro , Tsunehisa Doi , Junichi Hagiwara, Twisted data layout, Proceedings of the 8th international conference on Supercomputing, p.374-381, July 11-15, 1994, Manchester, England
Chih-Zong Lin , Chien-Chao Tseng , Yi-Lin Chen , Tso-Wei Kuo, A systematic approach to synthesize data alignment directives for distributed memory machines, Nordic Journal of Computing, v.3 n.2, p.89-110, Summer 1996
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
data parallel programming on NUMA multiprocessors, USENIX Systems on USENIX Experiences with Distributed and Multiprocessor Systems, p.13-13, September 22-23, 1993, San Diego, California
A. Zaafrani , M. R. Ito, Expressing cross-loop dependencies through hyperplane data dependence analysis, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
M. Kandemir, 2D data locality: definition, abstraction, and application, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.275-278, November 06-10, 2005, San Jose, CA
A. Zaafrani , M. R. Ito, Expressing cross-loop dependencies through hyperplane data dependence analysis, Proceedings of the 1994 conference on Supercomputing, p.508-517, December 1994, Washington, D.C., United States
Paul Feautrier, Toward automatic partitioning of arrays on distributed memory computers, Proceedings of the 7th international conference on Supercomputing, p.175-184, July 19-23, 1993, Tokyo, Japan
M. Kandemir , J. Ramanujam , A. Choudhary , P. Banerjee, A Layout-Conscious Iteration Space Transformation Technique, IEEE Transactions on Computers, v.50 n.12, p.1321-1336, December 2001
Niclas Andersson , Peter Fritzson, Generating parallel code from object oriented mathematical models, ACM SIGPLAN Notices, v.30 n.8, p.48-57, Aug. 1995
Gwan-Hwan Hwang , Cheng-Wei Chen , Jenq Kuen Lee , Roy Dz-Ching Ju, Segmented Alignment: An Enhanced Model to Align Data Parallel Programs of HPF, The Journal of Supercomputing, v.25 n.1, p.17-41, May
Anant Agarwal , David A. Kranz , Venkat Natarajan, Automatic Partitioning of Parallel Loops and Data Arrays for Distributed Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.6 n.9, p.943-962, September 1995
Dean Engelhardt , Andrew Wendelborn, A partitioning-independent paradigm for nested data parallelism, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.224-233, June 27-29, 1995, Limassol, Cyprus
Byoungro So , Mary W. Hall , Heidi E. Ziegler, Custom Data Layout for Memory Parallelism, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.291, March 20-24, 2004, Palo Alto, California
Chau-Wen Tseng , Jennifer M. Anderson , Saman P. Amarasinghe , Monica S. Lam, Unified compilation techniques for shared and distributed address space machines, Proceedings of the 9th international conference on Supercomputing, p.67-76, July 03-07, 1995, Barcelona, Spain
Edouard Bugnion , Jennifer M. Anderson , Todd C. Mowry , Mendel Rosenblum , Monica S. Lam, Compiler-directed page coloring for multiprocessors, ACM SIGPLAN Notices, v.31 n.9, p.244-255, Sept. 1996
Wai-Mee Ching , Alex Katz, An experimental APL compiler for a distributed memory parallel machine, Proceedings of the 1994 conference on Supercomputing, p.59-68, December 1994, Washington, D.C., United States
Wai Mee Ching , Alex Katz, An experimental APL compiler for a distributed memory parallel machine, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
PeiZong Lee, Efficient Algorithms for Data Distribution on Distributed Memory Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.8 n.8, p.825-839, August 1997
Jennifer M. Anderson , Monica S. Lam, Global optimizations for parallelism and locality on scalable parallel machines, ACM SIGPLAN Notices, v.28 n.6, p.112-125, June 1993
Vikram Adve , Alan Carle , Elana Granston , Seema Hiranandani , Ken Kennedy , Charles Koelbel , Ulrich Kremer , John Mellor-Crummey , Scott Warren , Chau-Wen Tseng, Requirements for Data-Parallel Programming Environments, IEEE Parallel & Distributed Technology: Systems & Technology, v.2 n.3, p.48-58, September 1994
David A. Garza-Salazar , Wim Bhm, Reducing communication by honoring multiple alignments, Proceedings of the 9th international conference on Supercomputing, p.87-96, July 03-07, 1995, Barcelona, Spain
Mahmut Kandemir , Alok Choudhary , Nagaraj Shenoy , Prithviraj Banerjee , J. Ramanujam, A Linear Algebra Framework for Automatic Determination of Optimal Data Layouts, IEEE Transactions on Parallel and Distributed Systems, v.10 n.2, p.115-135, February 1999
Chau-Wen Tseng, Compiler optimizations for eliminating barrier synchronization, ACM SIGPLAN Notices, v.30 n.8, p.144-155, Aug. 1995
Mario Nakazawa , David K. Lowenthal , Wendou Zhou, The Execution Model for Heterogeneous Clusters, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.7, November 12-18, 2005
John Plevyak , Vijay Karamcheti , Xingbin Zhang , Andrew A. Chien, A hybrid execution model for fine-grained languages on distributed memory multicomputers, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.41-es, December 04-08, 1995, San Diego, California, United States
Mahmut Kandemir , Alok Choudhary , J. Ramanujam , Meenakshi A. Kandaswamy, A Unified Framework for Optimizing Locality, Parallelism, and Communication in Out-of-Core Computations, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.648-668, July 2000
Mahmut Taylan Kandemir, A compiler technique for improving whole-program locality, ACM SIGPLAN Notices, v.36 n.3, p.179-192, March 2001
Jennifer M. Anderson , Saman P. Amarasinghe , Monica S. Lam, Data and computation transformations for multiprocessors, ACM SIGPLAN Notices, v.30 n.8, p.166-178, Aug. 1995
Micha Cierniak , Wei Li, Unifying data and control transformations for distributed shared-memory machines, ACM SIGPLAN Notices, v.30 n.6, p.205-217, June 1995
Ismail Kadayif , Mahmut Kandemir, Quasidynamic Layout Optimizations for Improving Data Locality, IEEE Transactions on Parallel and Distributed Systems, v.15 n.11, p.996-1011, November 2004
Mahmut Taylan Kandemir, Improving whole-program locality using intra-procedural and inter-procedural transformations, Journal of Parallel and Distributed Computing, v.65 n.5, p.564-582, May 2005
Pedro C. Diniz , Martin C. Rinard, Dynamic feedback: an effective technique for adaptive computing, ACM SIGPLAN Notices, v.32 n.5, p.71-84, May 1997
Peizong Lee , Zvi Meir Kedem, Automatic data and computation decomposition on distributed memory parallel computers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.1, p.1-50, January 2002
Mahmut Kandemir , Alok Choudhary , Prithviraj Banerjee , J. Ramanujam , Nagaraj Shenoy, Minimizing Data and Synchronization Costs in One-Way Communication, IEEE Transactions on Parallel and Distributed Systems, v.11 n.12, p.1232-1251, December 2000
Mahmut Kandemir , Prithviraj Banerjee , Alok Choudhary , J. Ramanujam , Eduard Ayguad, Static and Dynamic Locality Optimizations Using Integer Linear Programming, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.922-941, September 2001
Pascal Fradet , Julien Mallet, Compilation of a specialized functional language for massively parallel computers, Journal of Functional Programming, v.10 n.6, p.561-605, November 2000
M. Kandemir , P. Banerjee , A. Choudhary , J. Ramanujam , N. Shenoy, A global communication optimization technique based on data-flow analysis and linear algebra, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.6, p.1251-1297, Nov. 1999
Mahmut Kandemir, Compiler-Directed Collective-I/O, IEEE Transactions on Parallel and Distributed Systems, v.12 n.12, p.1318-1331, December 2001
Mahmut Kendemir , J. Ramanujam, Data Relation Vectors: A New Abstraction for Data Optimizations, IEEE Transactions on Computers, v.50 n.8, p.798-810, August 2001
Pedro C. Diniz , Martin C. Rinard, Eliminating synchronization overhead in automatically parallelized programs using dynamic feedback, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.89-132, May 1999
Akimasa Yoshida , Kenichi Koshizuka , Hironori Kasahara, Data-localization for Fortran macro-dataflow computation using partial static task assignment, Proceedings of the 10th international conference on Supercomputing, p.61-68, May 25-28, 1996, Philadelphia, Pennsylvania, United States
P. Banerjee , M. Peercy, Design and Evaluation of Hardware Strategies for Reconfiguring Hypercubes and Meshes Under Faults, IEEE Transactions on Computers, v.43 n.7, p.841-848, July 1994
Henri E. Bal , M. Frans Kaashoek, Object distribution in Orca using Compile-Time and Run-Time techniques, ACM SIGPLAN Notices, v.28 n.10, p.162-177, Oct. 1, 1993
Ken Kennedy , Ulrich Kremer, Automatic data layout for distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.4, p.869-916, July 1998
constraints;datadistribution;perfectbenchmarks;linpack;parallelizing compilers;fortran programs;data structures;index termsautomatic data partitioning;scientific application programs;multicomputers;eispack libraries;parallel programming;program compilers