Compile-Time Techniques for Data Distribution in Distributed Memory Machines.
A solution to the problem of partitioning data for distributed memory machines is discussed. The solution uses a matrix notation to describe array accesses in fully parallel loops, which allows the derivation of sufficient conditions for communication-free partitioning (decomposition) of arrays. A series of examples that illustrate the effectiveness of the technique for linear references, the use of loop transformations in deriving the necessary data decompositions, and a formulation that aids in deriving heuristics for minimizing a communication when communication-free partitions are not feasible are presented.
Introduction
In distributed memory machines such as the Intel iPSC/2 and NCUBE, each process has its own
address space and processes must communicate explicitly by sending and receiving messages. Local
memory accesses on these machines are much faster than those involving inter-processor commu-
nication. As a result, the programmer faces the enormously difficult task of orchestrating the
parallel execution. The programmer is forced to manually distribute code and data in addition
to managing communication among tasks explicitly. This task, in addition to being error-prone
and time-consuming, generally leads to non-portable code. Hence, parallelizing compilers for these
machines have been an active area of research recently [3, 4, 5, 9, 14, 19, 20, 22, 24, 25].
The enormity of the task is to some extent relieved by the hypercube programmer's paradigm
[6] where attention is paid to the partitioning of tasks alone, while assuming a fixed data partition
or a programmer-specified (in the form of annotations) data partition [9, 7, 14, 20]. A number of
efforts are under way to develop parallelizing compilers for multicomputers where the programmer
specifies the data decomposition and the compiler generates the tasks with appropriate message
passing constructs [4, 7, 14, 15, 20, 22, 25]. Though these rely on the intuition (based on domain
knowledge) of the programmer, it is not always possible to verify that the annotations indeed result
in efficient execution.
In a recent paper on programming of multiprocessors, Alan Karp [12] observes:
we see that data organization is the key to parallel algorithms even on shared
memory systems The importance of data management is also a problem for people
writing automatic parallelization compilers. Todate, our compiler technology has been
directed toward optimizing control flow today when hierarchical (distributed)
memories make program performance a function of data organization, no compiler in
existence changes the data addresses specified by the programmer to improve perfor-
mance. If such compilers are to be successful, particularly on message-passing systems,
a new kind of analysis will have to be developed. This analysis will have to match the
data structures to the executable code in order to minimize memory traffic."
This paper is an attempt at providing this "new" kind of analysis - we present a matrix
notation to describe array accesses in fully parallel loops which lets us present sufficient conditions
for communication-free partitioning (decomposition) of arrays. In the case of a commonly occurring
class of accesses, we present a formulation as a fractional integer programming problem to minimize
communication costs, when communication-free partitioning of arrays is not possible.
The rest of the paper is organized as follows. In section 2, we present the background and
the assumptions we make, and discuss related work. Section 3 illustrates through examples, the
importance and the difficulty of finding good array decompositions. In section 4, we present a
matrix-based formulation of the problem of determining the existence of communication-free partitions
of arrays; we then present conditions for the case of constant offset array access. In section 5, a
series of examples are presented to illustrate the effectiveness of the technique for linear references;
in addition, we show the use of loop transformations in deriving the necessary data decomposi-
tions. Section 6 generalizes the formulation presented in section 4 for arbitrary linear references. In
section 7, we present a formulation that aids in deriving heuristics for minimizing communication
when communication-free partitions are not feasible. Section 8 concludes with a summary and
discussion.
Assumptions and related work
Communication in message passing machines could arise from the need to synchronize and from
the non-locality of data. The impact of the absence of a globally shared memory on the compiler
writer is severe. In addition to managing parallelism, it is now essential for the compiler writer to
appreciate the significance of data distribution and decide when data should be copied or generated
in local memory. We focus on distribution of arrays which are commonly used in scientific
computation. Our primary interest is in arrays accessed during the execution of nested loops. We
consider the following model where a processor owns a data element and has to make all updates
to it and there is exactly one copy. Even in the case of fully parallel loops, care must be taken to
ensure appropriate distribution of data.
In the next sections, we explore techniques that a compiler can use to determine if the data
can be distributed such that no communication is incurred. Operations involving two or more
operands require that the operands be aligned, that is the corresponding operands are stored in the
memory of the processor executing the operation. In the model we consider here, this means that
the operands used in an operation must be communicated to the processor that holds the operand
which appears on the left hand side of an assignment statement. Alignment of operands generally
requires interprocessor communication.
In current day machines, interprocessor communication is more time-consuming than instruction
execution. If insufficient attention is paid to the data allocation problem, then the amount of time
spent in interprocessor communication might be so high as to seriously undermine the benefits of
parallelism. It is therefore worthwhile for a compiler to analyze patterns of data usage to determine
allocation, in order to minimize interprocessor communication. We present a machine-independent
analysis of communication-free partitions.
We make the following assumptions:
1. There is exactly one copy of every array element and the processor in whose local memory
the element is stored is said to "own" the element.
2. The owner of an array element makes all updates to the element, i.e. all instructions that
modify the value of the element are executed by the "owner" processor.
3. There is a fixed distribution of array elements. (Data re-organization costs are architecture-specific

2.1 Related work
The research on problems related to memory optimizations goes back to studies of the organization
of data for paged memory systems [1]. Balasundaram and others [3] are working on interactive
parallelization tools for multicomputers that provide the user with feedback on the interplay between
data decomposition and task partitioning on the performance of programs. Gallivan et al.
discuss problems associated with automatically restructuring data so that it can be moved to
and from local memories in the case of shared memory machines with complex memory hierarchies.
They present a series of theorems that enable one to describe the structure of disjoint sub-lattices
accessed by different processors, use this information to make "correct" copies of data in local mem-
ories, and write the data back to the shared address space when the modifications are complete.
Gannon et al. [8] discuss program transformations for effective complex-memory management for a
CEDAR-like architecture with a three-level memory. Gupta and Banerjee [10] present a constraint-based
system to automatically select data decompositions for loop nests in a program. Hudak and
Abraham [11] discuss the generation of rectangular and hexagonal partitions of arrays accessed in
sequentially iterated parallel loops. Knobe et al. [13] discuss techniques for automatic layout of
arrays in a compiler targeted to SIMD architectures such as the Connection Machine computer
system. Li and Chen [17] (and [5]) have addressed the problem of index domain alignment which
is that of finding a set of suitable alignment functions that map the index domains of the arrays
into a common index domain in order to minimize the communication cost incurred due to data
movement. The class of alignment functions that they consider primarily are permutations and
embeddings. The kind of alignment functions that we deal with are more general than these. Mace
[18] proves that the problem of finding optimal data storage patterns for parallel processing (the
"shapes" problem) is NP-complete, even when limited to one- and two-dimensional arrays; in ad-
dition, efficient algorithms are derived for the shapes problem for programs modeled by a directed
acyclic graph (DAG) that is derived by series-parallel combinations of tree-like subgraphs. Wang
and Gannon [23] present a heuristic state-space search method for optimizing programs for memory
hierarchies.
In addition several researchers are developing compilers that take a sequential program augmented
with annotations that specify data distribution, and generate the necessary communication.
Koelbel et al. [14, 15] address the problem of automatic process partitioning of programs written in
a functional language called BLAZE given a user-specified data partition. A group led by Kennedy
at Rice University [4] is studying similar techniques for compiling a version of FORTRAN for local
memory machines, that includes annotations for specifying data decomposition. They show how
some existing transformations could be used to improve performance. Rogers and Pingali [20]
present a method which, given a sequential program and its data partition, performs task partitions
to enhance locality of references. Zima et al. [25] have developed SUPERB, an interactive
system for semi-automatic transformation of FORTRAN programs into parallel programs for the
SUPRENUM machine, a loosely-coupled hierarchical multiprocessor.
3 Deriving good partitions: some examples
Consider the following loop:
Example 1:
If we allocate row i of array A and row i of array B to the local memory of the same processor, then
no communication is incurred. If we allocate by columns or blocks, interprocessor communication
is incurred. There are no data dependences in the above example; such loops are referred to as
doall loops. It is easy to see that allocation by rows would result in zero communication since,
there is no offset in the access of B along the first dimension. Figure 1 shows the partitions of
arrays A and B.
In the next example, even though there is a non-zero offset along each dimension, communication-
free partitioning is possible:
Example 2:
In this case, row, column or block allocation of arrays A and B would result in interprocessor
communication. In this case, if A and B are partitioned into a family of parallel lines whose
equation is no communication will result. Figure 2 shows the
partitions of A and B. The kth line in array A i.e. the line in A and the line
in array B must be assigned to the same processor
Figure

1: Partitions of arrays A and B for Example 1

Figure

2: Partitions of arrays A and B for Example 2
In the above loop structure, array A is modified as a function of array B; a communication-
partitioning in this case is referred to as a compatible partition. Consider the following loop
skeleton:
Example 3:
Array A is modified in loop L 1 as a function of elements of array B while loop L 2 modifies array
using elements of array A. Loops L 1 and L 2 are adjacent loops at the same level of nesting.
The effect of a poor partition is exacerbated here since every iteration of the outer loop suffers
inter-processor communication; in such cases, the communication-free partitioning where possible,
is extremely important. Communication-free partitions of arrays involved in adjacent loops is
referred to as mutually compatible partitions.
In all the preceding examples, we had the following array access pattern: for computing some
element A[i; j], element B[i 0
is required where
where c i and c j are constants. Consider the following example:
Example 4:
In this example, allocation of row i of array A and column i of array B to the same processor
would result in no communication. See Figure 3 for the partitions of A and B in this example.
Note that i 0
is a function of j and j 0
is a function of i here.
In the presence of arbitrary array access patterns, the existence of communication-free partitions
is determined by the connectivity of the data access graph, described below. To each array element
that is accessed (either written or read), we associate a node in this graph. If there are k different
arrays that are accessed, this graph has k groups of nodes; all nodes belonging to a given group
are elements of the same array. Let the node associated with the left hand side of an assignment
statement S be referred to as write(S) and the set of all nodes associated with the array elements on
Figure

3: Array partitions for Example 4
the right hand side of the assignment statement S be called read-set(S). There is an edge between
and every member of read-set(S) in the data access graph. If this graph is connected, then
there is no communication-free partition [19].
Reference-based data decomposition
Consider a nested loop of the following form which accesses arrays A and B:
Example 5:
are linear functions of i and j, i.e.
With disjoint partitions of array A, can we find corresponding or required disjoint partitions of array B
in order to eliminate communication? A partition of B is required for a given partition of A if the
elements in that partition (of B) appear in the right hand side of the assignment statements in
the body of the loop which modify elements in the partition of A. For a given partition of A, the
required referred to as its image(s) or map(s). We discuss array partitioning
in the context of fully parallel loops. Though the techniques are presented for 2-dimensional arrays,
these generalize easily to higher dimensions.
In particular, we are interested in partitions of arrays defined by a family of parallel hyper-
planes; such partitions are beneficial from the point of view of restructuring compilers in that the
portion of loop iterations that are executed by a processor can be generated by a relatively simple
transformation of the loop. Thus the question of partitioning can be stated as follows: Can we
find partitions induced by parallel hyperplanes in A and B such that there is no communication?
We focus our attention on 2-dimensional arrays. A hyperplane in 2 dimensions is a line; hence, we
discuss techniques to find partitions of A and B into parallel lines that incur zero communication.
In most loops that occur in scientific computation, the functions f and g are linear in i and j.
The equation
defines a family of parallel lines for different values of c, given that ff and fi are constants and at
most one of them is zero. For example,
defines columns, while
defines diagonals.
Given a family of parallel lines in array A defined by
can we find a corresponding family of lines in array B given by
such that there is no communication among processors?
The conditions on the solutions are: at most one of ff and fi can be zero; similarly, at most one
of ff 0
and fi 0
can be zero. Otherwise, the equations do not define parallel lines. A solution that
satisfies these conditions is referred to as a non-trivial solution and the corresponding partition is
called a non-trivial partition. Since i 0
are given by equations 1 and 2, we have
(a
(a
which implies i
a
a 21
a 22
a 20
Since a family of lines in A is defined by ffi
a
a 21 (5)
a 22 (6)
a 20 (7)
A solution to the above system of equations would imply zero communication. In matrix notation,
we have 0
a 11 a 21 0
a 12 a 22 0
c 0C A =B @
ff
cC A
The above set of equations decouples into:
a 11 a 21
a 12 a 22
ff
and
We illustrate the use of the above sufficient condition with the following example.
Example
for each element A[i; j], we need two elements of B. Consider the element B[i \Gamma 1; j]. For
communication-free partitioning, the systemB @
c 0C A =B @
ff
cC A
must have a solution. Similarly, considering the element solution must exist for the
following system as well: 0
c 0C A =B @
ff
cC A
Given that there is a single allocation for A and B, the two systems of equations must admit a
solution. This reduces to the following system:

Figure

4: Partitions of arrays A and B for Example 6
The set of equations reduce to
which has a solution say This implies that
both A and B are partitioned by anti-diagonals. Figure 4 shows the partitions of the arrays for
zero communication. The relations between c and c 0
give the corresponding lines in A and B.
With a minor modification of example 6 (as shown below),
Example 7:
the reduced system of equations would be:
which has a solution
2.

Figure

5 shows the lines in arrays A and B which
incur zero communication.
The next example shows a nested loop in which arrays can not be partitioned such that there
is no communication.
Example 8:

Figure

5: Lines in arrays A and B for Example 7
The system of equations in this case is:
which reduces to
which has only one solution ff 0
which is not a non-trivial solution. Thus there is no
communication-free partitioning of arrays A and B.
The examples considered so far involve constant offsets for access of array elements and we
had to find compatible partitions. The next case considered is one where we need to find mutually
compatible partitions. Consider the nested loop:
Example 9:
In this case, the accesses due to loop L 1 result in the system:
and the accesses due to loop L 2 result in the system:
Therefore, for communication-free partitioning, the two systems of equations written above must
admit a solution - thus, we get the reduced system:
which has a solution
Figure 6 shows partitions of A and B into
diagonals.
4.1 Constant offsets in reference
We discuss the important special case of array accesses with constant offsets which occur in codes
for the solution of partial differential equations. Consider the following loop:
k and q j
m) are integer constants. The vectors ~
are referred to as
offset vectors. There are m such offset vectors, one for each access pair A[i; j] and B[i
Figure

Mutually compatible partition of A and B for Example 9
In such cases, the system of equations is (for each access indexed by k, where 1  k  m):B @
c 0C A =B @
ff
cC A
which reduces to the following constraints:
Therefore, for a given collection of offset vectors, communication-free partitioning is possible, if
If we consider the offset vectors (q i
k ) as points in 2-dimensional space, then communication
free partitioning is possible, if the points (q i
are collinear. In addition, if all
no communication is required between rowwise partitions; similarly, if all q j
then partitioning the arrays into columns results in zero communication. For zero communication
in nested loops involving K-dimensional arrays, this means that offset vectors treated as points in
K-dimensional space must lie on a dimensional hyperplane.
In all the above examples, there was one solution to the set of values for ff; ff 0
. In the next
section, we show an example where there are an infinite number of solutions, and loop transformations
play a role in the choice of a specific solution.
5 Partitioning for linear references and program transformations
In this section, we discuss communication-free partitioning of arrays when references are not constant
offsets but linear functions. Consider the loop in example 10:
Example 10:
Communication free partitioning is possible if the system of equationsB @
c 0C A =B @
ff
cC A
has a solution where no more than one of ff and fi is zero and no more than one of ff 0
and fi 0
is
zero. The set reduces to:
This set has an infinite number of solutions. We present four of them and discuss their relative
merits.
The first two equations involve four variables, fixing two of which leads to values of the other
two. For example, if we set array A is partitioned into rows. From the set
of equations, we get ff 0
array B is being partitioned into
columns; since
, if we assign row k of array A and column k of array to the same processor,
then there is no communication. See Figure 1 for the partitions.
A second partition can be chosen by setting 1. In this case, array A is partitioned
into columns. Therefore, ff 0
means B is partitioned into rows.

Figure

7(a) for this partition. If we set array A is partitioned into
anti-diagonals. From the set of equations, we get ff 0
means
array B is also being partitioned into anti-diagonals. Figure 7(b) shows the third partition. A
fourth partition can be chosen by setting \Gamma1. In this case, array A is partitioned
into diagonals. Therefore, ff 0
means B is also partitioned into
anti-diagonals. In this case, the kth sub-diagonal (below the diagonal) in A corresponds to the kth
super-diagonal (above the diagonal) in array B. Figure 7(c) illustrates this partition.
Figure

7: Decompositions of arrays A and B for Example 10
From the point of loop transformations [2, 24], we can rewrite the loop to indicate which
processor executes which portion of the loop iterations, partitions 1 and 2 are easy. Let us assume
that the number of processors is p and the number of rows and columns in N and N is a multiple
of p. In such a case, partition 1 partitioned into rows) can be rewritten as:
Processor k executes (1  k  p) :
to N by p
and all rows r of A such that r mod are assigned to processor k; all columns r
of B such that r mod are also assigned to processor k.
In the case of partition 2 partitioned into columns), the loop can be rewritten as:
Processor k executes (1  k  p) :
to N by p
and all columns r of A such that r mod rows r of B such that r mod
are also assigned to processor k. Since there are no data dependences anyway, the
loops can be interchanged and written as:
Processor k executes (1  k  p) :
to N by p
Partitions 3 and 4 can result in complicated loop structures. In partition 3, 1. The
steps we perform to transform the loop use loop skewing and loop interchange transformations [24].
We perform the following steps:
1. If distribute the iterations of the outer loop in a round-robin manner;
in this case, processor k (in a system of p processors) executes all iterations (i;
. This is referred to as wrap distribution.
If apply loop interchange and wrap-distribute the iterations of the
interchanged outer loop. If not, apply the following transformation to the index set:
ff fi
2. Apply loop interchanging so that the outer loop now can be stripmined. Since these loops
do not involve flow or anti-dependences, loop interchanging is always legal. After the first
transformation, the loop need not be rectangular. Therefore, the rules for interchange of
trapezoidal loops in [24] are used for performing the loop interchange.
The resulting loop after transformation and loop interchange is the following:
Example 11:
The load-balanced version of the loop is:
Processor k executes (1  k  p) :
to 2N by p
The reason we distribute the outer loop iterations in a wrap-around manner is that such a distribution
will result in load balanced execution when N ?? p.
In partition 4, \Gamma1. The resulting loop after transformation and loop interchange is
the following:
Processor k executes (1  k  p) :
Next, we consider a more complicated example to illustrate partitioning of linear recurrences:
Example 12:
The access B[i results in the following system:B @
c 0C A =B @
ff
cC A
and the second access results in the system:B @
c 0C A =B @
ff
cC A
which together give rise to the following set of equations:
which has only one solution which is
0: Thus communication-free partitioning
has been shown to be impossible.
But for the following loop, communication-free partitioning into columns is possible.
Example 13:
The accesses give the following set of equations:
In this case, we have a solution:
1. Thus both A and B
are partitioned into columns.
6 Generalized linear references
In this section, we discuss the generalization of the problem formulation discussed in section 4.
Example 14:
are linear functions of i and j, i.e.
Thus the statement in the loop is:
In this case, the family of lines in array B are given by
and lines in array A are given by:
Thus the families of lines are:
Array
(a
(a
which is rewritten as:
Array
a 11 ff 0
a
a 12 ff 0
a 22 fi 0
a 20 (15)
Therefore, for communication-free partitioning, we should find a solution for following system of
equations (with the constraint that at most one of ff; fi is zero and at most one of ff 0
is zero):B @
a 11 a 21 0
a 12 a 22 0
c 0C A =B @
ff
cC A
Consider the following example:
Example 15:
Figure

8: Partitions of arrays A and B for Example 15
The accesses result in the following system of equations:B @
c 0C A =B @
ff
cC A
which leads to the following set of equations:
which has a solution
1. See

Figure

8 for the partitions.
Now for a more complicated example:
Example
The accesses result in the following system of equations:B @
c 0C A =B @
ff
cC A
which leads to the following set of equations:
which has solutions where:/
ff
The system has the following solution:
1. The loop after transformation
is:
Processor k executes (1  k  p) :
to 2N by p
The following section deals with a formulation of the problem for communication minimization,
when communication-free partitions are not feasible.
7 Minimizing communication for constant offsets
In this section, we present a formulation of the communication minimization problem, that can
be used when communication-free partitioning is impossible. We focus on two-dimensional arrays
with constant offsets in accesses. The results can be generalized to higher dimensional arrays.
We consider the following loop model:
The array accesses in the above loop give rise to the set of offset vectors, ~
. The 2 \Theta m
matrix Q whose columns are the offset vectors q i is referred to as the offset matrix. Since A[i; j]
is computed in iteration (i; j), a partition of the array A defines a partition of the iteration space
and vice-versa. For constant offsets, the shape of the partitions for the two arrays A and B will be
the same; the array boundaries depend on the offset vectors.
Given the offset vectors, the problem is to derive partitions such that the processors have equal
amount of work and communication is minimized. We assume that there are N 2 iterations (N 2
elements of array A are being computed) and the number of processors is p. We also assume that
N 2 is a multiple of p. Thus, the workload for each processors is N 2
.
The shapes of partitions considered are parallelograms, of which rectangles are a special case.
A parallelogram is defined by two vectors each of which is normal to one side of the parallelogram.
Let the normal vectors be ~
The matrix S refers to:
S
If i and j are the array indices, ~
defines a family of lines given by S different
values of c 1 and the vector ~
defines a family of lines given by S different values
of c 2 . S must be non-singular in order to define parallelogram blocks that span the entire array.
The matrix S defines a linear transformation applied to each point (i; j); the image of the point
(i; j). We consider parallelograms defined by solutions to the following
set of linear inequalities:
where r 1 l and r 2 l are the lengths of the sides of the parallelograms.
The number of points in the discrete Cartesian space enclosed by this region (which must be the
same as the workload for each processor, N 2
when det(S) 6= 0. The non-zero entries in
the matrix Q 0
(i) be the sum of the absolute
values of the entries in the ith row of Q
, i.e.
The communication volume incurred is:
2l
Thus the problem of finding blocks which minimize inter-processor communication is that of
finding the matrix S, the value l and the aspect ratios r 1 and r 2 such that the communication
volume is minimized subject to the constraint that the processors have about the same amount of
workload i.e.
The elements of matrix S determine the shape of the partitions and the values of r
the size of the partitions.

Summary

In current day distributed memory machines, interprocessor communication is more time-consuming
than instruction execution. If insufficient attention is paid to the data allocation problem, then so
much time may be spent in interprocessor communication that much of the benefit of parallelism
is lost. It is therefore worthwhile for a compiler to analyze patterns of data usage to determine
allocation, in order to minimize interprocessor communication. In this paper, we formulated the
problem of determining if communication-free array partitions (decompositions) exist and presented
machine-independent sufficient conditions for the same for a class of parallel loops without flow or
anti dependences, where array references are affine functions of loop index variables. In addition,
where communication-free decomposition is not possible, we presented a mathematical formulation
that aids in minimizing communication.
Acknowlegdment
We gratefully acknowledge the helpful comments of the referees in improving the earlier draft of
this paper.



--R

"On the Performance Enhancement of Paging Systems through Program Analysis and Transformations,"
"Automatic Translation of FORTRAN Programs to Vector Form,"
"An interactive environment for data partitioning and distribution,"
"Compiling Programs for Distributed-Memory Multiprocessors,"
"Compiling Parallel Programs by Optimizing Performance,"
Solving Problems on Concurrent Processors - Volume <Volume>1</Volume>: General Techniques and Regular Problems
"On the Problem of Optimizing Data Transfers for Complex Memory Systems,"
"Strategies for Cache and Local Memory Management by Global Program Transformations,"
"Array Distribution in SUPERB,"
"Automatic Data Partitioning on Distributed Memory Multipro- cessors,"
"Compiler Techniques for Data Partitioning of Sequentially Iterated Parallel Loops,"
"Programming for Parallelism,"
"Data Optimization: Allocation of Arrays to Reduce Communication on SIMD Machines,"
"Semi-automatic Process Partitioning for Parallel Computation,"
"Supporting Shared Data Structures on Distributed Memory Machines,"
Compiling programs for non-shared memory machines
"Index Domain Alignment: Minimizing Cost of Cross-Referencing between Distributed Arrays,"
Memory Storage Patterns in Parallel Processing

"Process Decomposition Through Locality of Reference,"
Compiling for locality of reference
"Mapping Data to Processors in Distributed Memory Computa- tions,"
"Applying AI Techniques to Program Optimization for Parallel Computers,"
Optimizing Supercompilers for Supercomputers
"SUPERB: A Tool for Semi-automatic MIMD-SIMD Parallelization,"
--TR
Programming for parallelism
Automatic translation of FORTRAN programs to vector form
Memory storage patterns in parallel processing
Solving problems on concurrent processors. Vol. 1: General techniques and regular problems
Strategies for cache and local memory management by global program transformation
On the problem of optimizing data transfers for complex memory systems
process partitioning for parallel computation
Process decomposition through locality of reference
Data optimization: allocation of arrays to reduce communication on SIMD machines
Supporting shared data structures on distributed memory architectures
Compile-time techniques for parallel execution of loops on distributed memory multiprocessors
Compiling programs for nonshared memory machines
Compiler techniques for data partitioning of sequentially iterated parallel loops
Array distribution in SUPERB
Optimizing Supercompilers for Supercomputers
Compiling for locality of reference

--CTR
G. N. Srinivasa Prasanna , A. Agrawal , B. R. Musicus, Hierarchical Compilation of Macro Dataflow Graphs for Multiprocessors with Local Memory, IEEE Transactions on Parallel and Distributed Systems, v.5 n.7, p.720-736, July 1994
Jih-Woei Huang , Chih-Ping Chu, An Efficient Communication Scheduling Method for the Processor Mapping Technique Applied Data Redistribution, The Journal of Supercomputing, v.37 n.3, p.297-318, September 2006
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
array partitioning based on the Smith normal form, International Journal of Parallel Programming, v.33 n.1, p.35-56, February 2005
Ravi Ponnusamy , Yuan-Shin Hwang , Raja Das , Joel H. Saltz , Alok Choudhary , Geoffrey Fox, Supporting Irregular Distributions Using Data-Parallel Languages, IEEE Parallel & Distributed Technology: Systems & Technology, v.3 n.1, p.12-24, March 1995
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
Wenrui Gong , Gang Wang , R. Kastner, Storage assignment during high-level synthesis for configurable architectures, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.3-6, November 06-10, 2005, San Jose, CA
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
M. Kandemir , A. Choudhary , N. Shenoy , P. Banerjee , J. Ramanujam, A hyperplane based approach for optimizing spatial locality in loop nests, Proceedings of the 12th international conference on Supercomputing, p.69-76, July 1998, Melbourne, Australia
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
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
Minyi Guo, Linear data distribution based on index analysis, High performance scientific and engineering computing: hardware/software support, Kluwer Academic Publishers, Norwell, MA, 2004
Catherine Mongenet, Mappings for communication minimization using distribution and alignment, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.185-193, June 27-29, 1995, Limassol, Cyprus
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
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
Esin Onbasioglu , Linet zdamar, Optimization of Data Distribution and Processor Allocation Problem Using Simulated Annealing, The Journal of Supercomputing, v.25 n.3, p.237-253, July
Jordi Garcia , Eduard Ayguad , Jesus Lebarta, A novel approach towards automatic data distribution, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.78-es, December 04-08, 1995, San Diego, California, United States
Thomas Rauber , Gudula Rnger, Deriving Array Distributions by Optimization Techniques, The Journal of Supercomputing, v.15 n.3, p.271-293, Mar.1.2000
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
Vincent Loechner , Catherine Mongenet, Communication Optimization for Affine Recurrence Equations Using Broadcast and Locality, International Journal of Parallel Programming, v.28 n.1, p.47-102, February 2000
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
Wei Li , Keshav Pingali, Access normalization: loop restructuring for NUMA computers, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.353-375, Nov. 1993
Wei Li , Keshav Pingali, Access normalization: loop restructuring for NUMA compilers, ACM SIGPLAN Notices, v.27 n.9, p.285-295, Sept. 1992
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
James R. Larus, Compiling for shared-memory and message-passing computers, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.165-180, MarchDec. 1993
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
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
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
Ender zcan , Esin Onbaioglu, Memetic algorithms for parallel code optimization, International Journal of Parallel Programming, v.35 n.1, p.33-61, February 2007
Mahmut Taylan Kandemir, A compiler technique for improving whole-program locality, ACM SIGPLAN Notices, v.36 n.3, p.179-192, March 2001
Mahmut Kandemir , Alok Choudhary , J. Ramanujam , Prith Banerjee, Reducing False Sharing and Improving Spatial Locality in a Unified Compilation Framework, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.337-354, April
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
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
matrix algebra;matrixnotation;data decompositions;parallel loops;communication-freepartitioning;data distribution;linear references;index termscompile time;program compilers;parallel programming;heuristics;sufficient conditions;array accesses;data partitioning;distributed memory machines;loop transformations