An approach to communication-efficient data redistribution.
We address the development of efficient methods for performing data redistribution of arrays on distributed-memory machines. Data redistribution is important for the distributed-memory implementation of data parallel languages such as High Performance Fortran. An algebraic representation of regular data distributions is used to develop an analytical model for evaluating the communication cost of data redistribution. Using this algebraic representation and the analytical model, an approach to communication-efficient data redistribution is developed. Implementation results on the Intel iPSC/860 are reported.
Introduction
Distributed-memory machines have demonstrated a potential
for high performance. However, their use has been restricted
due to the difficulty of programming these comput-
ers. A programming model based on a single address space
with provisions for explicit specification of data distributions
for shared arrays has recently gained popularity [1, 3,
13]. High Performance Fortran (HPF) [6], a Fortran-90 ex-
tension, provides programmers with directives, that specify
alignment of arrays with one another and distribute these
aligned arrays on a user-defined virtual processor mesh. Directives
to dynamically change the distribution of arrays
during program execution are provided. Redistribution of
data arrays is used under the following circumstances.
This work was supported in part by ARPA, order number
7898, monitored by NIST under grant number 60NANB1D1151, and
DARPA, order number 7899, monitored by NIST under grant number
To appear in the 8th ACM International Conference on
July 1994, Manchester, England.
ffl Different phases of a program vary in their access patterns
to a shared array and a different data distribution
of the array is often best suited for each phase. For
instance, the alternate direction implicit method [12]
consists of two phases - the first phase accesses a two-dimensional
array along the rows and the second phase
along the columns. A distribution in which the array
rows are local to a processor and the columns are dis-
tributed, eliminates communication for the first phase.
Similarly, a distribution in which the array columns are
local and the rows are distributed, eliminates communication
for the second phase. The need to explicitly
redistribute the array between the two phases arises.
ffl Scientific libraries are tuned to provide peak performance
for a fixed set of distributions for the input
arrays. These distributions may not conform with the
distributions of the actual parameters, leading to performance
degradation. Developing library routines for
all possible input distributions is not practical. Hence
the actual array parameters must be explicitly redistributed

ffl Data redistribution is implicitly required in the execution
of array statements, where the array sections in
the statement are the entire arrays and have different
distributions.
Thus efficient methods for performing data redistribution
are of great importance in the distributed-memory implementations
of HPF.
Some data redistribution strategies have been presented
in the literature. The issue of reshaping perfect power-of-two
sized data arrays on hypercubes is addressed in [15]. Closed
form expressions for the processor sets which a processor
needs to communicate with, and data sets that need to be
communicated during data redistribution are constructed
in [10]. Algorithms for runtime array redistribution are provided
in [22]. In [17], closed-form expressions to characterize
the data communication required in DoAll loops involving
arrays with identical (block and cyclic) distributions and
simple index expressions are developed. In [13], the inter-processor
data communication for loops involving arrays
with invertible index expressions is expressed as the composition
of index and distribution functions. Schemes for efficiently
executing HPF array statements for block-cyclically
distributed arrays are presented in [4, 11, 21]. Schemes for
communication generation and compile-time estimation of
communication costs are presented in [18]. These schemes
are based on identifying communication primitives [7] by
comparing index expressions of array references. Detailed
techniques along the lines of [18] for estimation of communication
cost are developed in [8]. However, these schemes
do not accurately identify the communication cost when
the corresponding arrays are not identically dis-tributed.
Schemes for generating alignments for arrays using cost metrics
for various interconnection networks are developed in [5].
The issue of efficient redistribution for arbitrary block-cyclic
data distributions is addressed in [10]. The scheme
presented therein performs data redistribution by communicating
in one step, all the data as required by the source and
target data distributions. We refer to this as a single-phase
data redistribution strategy. Under certain circumstances,
a characterization of the interprocessor communication is
possible which facilitates the development of efficient redistribution
schemes. Redistribution can be performed as a sequence
of single-phase data redistributions. We refer to this
as a multi-phase data redistribution strategy. The intermediate
data distributions can be chosen such that the total
cost for this sequence is lower that the cost of the single-phase
redistribution. For example, consider an array A of
192 elements, distributed block-wise on eight processors. Let
the target distribution be block-cyclic with block size three.
During the single-phase data redistribution, each processor
communicates with seven other processors. Suppose the re-distribution
is performed in two phases - a redistribution
from block to block-cyclic with block size 12, followed by a
second redistribution to the target distribution. The first
data redistribution requires each processor to send at most
two messages and the second requires at most four messages.
If the message setup time were the dominant component of
the communication cost, then the use of the two-phase strategy
will reduce the total communication cost.
A communication cost model for data redistribution should
take into account the total startup cost, message transmission
cost and the overhead arising due to network con-
tention. In this paper, we first present an analytical model
based on the number of messages and the volume of data
communicated for estimating the communication cost of the
single-phase data redistribution. We model the network contention
by expressing the communication as a sequence of
permutations, each of which can be executed in a fixed number
of contention-free steps. Using this analytical model and
the tensor product representation of data distributions [9],
we develop cost estimates of single-phase data redistribution
for a given source to target distribution. We then show that
use of a multi-phase strategy can reduce the communication
cost. We present methods for determining the intermediate
distributions such that the total communication cost for the
multi-phase strategy is minimized.
The paper is organized as follows. Section 2 briefly describes
the tensor product representation of regular data distributions
supported by HPF. In Section 3, a communication
cost model is described and is used to develop cost estimates
for single-phase data redistribution. Section 4 presents efficient
algorithms for data redistribution. Preliminary performance
results on the Intel iPSC/860 are reported in Section
5. Conclusions are presented in Section 6.
Regular Data Distributions
In this section, we briefly describe the tensor product representation
of regular data distributions. Details of the tensor
product theory, are presented in [14].
HPF supports a two-level mapping of data objects to an
abstract processor array. The language introduces a Cartesian
grid referred to as a template. Array are aligned with
a template and the templates are distributed onto a virtual
processor array using regular data distributions. Consider
an array A(0 aligned with a template D such
that A(i) is aligned with D(ai b). The template is distributed
onto P processors using a cyclic(k) distribution,
such that template element D(i) is mapped to processor
(i div . The array A is divided into P arrays, each
referred to as A loc, residing in the local memory of each
processor. In this paper, we focus on identity alignments,
i.e., A(i) is aligned with D(i).
2.1 The Tensor Product Notation
Let A be an m \Theta n matrix and B a p \Theta q matrix. The
tensor product of A and B is the block matrix obtained by
replacing each element a i;j by a i;j B.
A\Omega B is the mp \Theta nq
matrix defined as
We focus on the tensor product of vector bases. A vector
basis element e is a column vector of length
m with one at position i and zeros elsewhere. The tensor
product e m
of two vector bases, e m i and e n j is called a
tensor basis and e m
. The size of the tensor
j is mn. Expressing a vector basis e M
i as the
tensor product of vector bases e m
is called the
factorization of the vector basis, where
and
For example, the vector basis e 12
8 can be factorized into the
tensor bases e 2
0 or e 4
. Expressing a tensor basis
as a vector basis e M
is called linearization of the tensor basis. For example, the
tensor basis e 4
2 can be linearized to give the vector basis
5 . We now define the compatibility of two tensor bases.
Definition 2.1 (Compatible Tensor Bases) Two
tensor bases b1 and b2 are compatible if they can be factorized
and
The factorized tensor bases are such that the sizes of the
vector bases at corresponding positions are equal. For ex-
ample,
are compatible tensor
bases as by factorization we get
and
. Note that
are not compatible. We now define the semantics of regular
data distributions using the tensor basis.
2.2 Algebraic Semantics of Regular Data Distributions
Consider an array A(0 processors
using a regular data distribution. We assume that N is a
multiple of P 1 . The location of the element A(i) is specified
by the tuple (p; l) where p is the processor, and l is the local
index of A(i). For a cyclic(b) distribution, element A(i)
has processor index (i div b) mod P and has a local index
b. The block and cyclic distributions are
equivalent to cyclic( N
respectively.
The indices of A(0 can be represented by the
vector basis e N i . Suppose A(0 : 15) is distributed onto
four processors using a block distribution. Element A(9)
is mapped to processor and has a local
processor 2. In general, element
will be located on processor
and will have a local index i 4. Consider the
factorization of the vector basis e
i into the tensor basis
In the tensor basis e 4
, the index in vector basis e 4
corresponds to the processor on which element A(i) is located
and the index in e 4
corresponds to the local address
of A(i) on processor i 1 . We say that the vector basis e 4
cor-
responds to the processor on which element A(i) is located
and e 4
corresponds to the local address of A(i) on the pro-
cessor. If we denote the vector basis corresponding to the
processor by ae, then the tensor basis ae 4
represents
the array A(0 : 15) distributed in a block fashion on four
processors. Such a tensor basis, in which the vector basis
corresponding to the processor index is identified, is called
a distribution basis. The vector basis e is referred to as the
data basis and ae as the processor basis. Thus a distribution
basis for a linear array A(0 a factorization of e N
Every vector basis of the resulting tensor basis is identified
as either a processor basis or a data basis.
block distribution on P proces-
cyclic distribution on P processors
and distribution
on P processors with block size B. The regular distribution
bases for a linear array are defined as:
Definition 2.2 (Distribution function) For a one-dimensional
array
i correspond to the index
of A(i) and let . The Distribution function DIST
is:
DIST (basis; dist) distribution basis
We define the following indexing functions for the distribution
basis. These indexing functions select the vector
bases of the distribution which identify the processor index,
the local index and the global index of each element of the
distributed array.
does not divide N , then the array is assumed to be padded
to dN=PeP .
Definition 2.3 (Indexing functions) Let array A(0
1) have the distribution basis e C
then the processor
index function, proc, local index function, local, and
global index function, global, are
Index functions indices
global(e C
local(e C
proc(e C
The distribution basis for a multi-dimensional array is defined
as the tensor product of the distribution bases for each
dimension. The distribution and indexing functions for a
multi-dimensional array can be defined in terms of the corresponding
functions of a one-dimensional array.
Definition 2.4 (Distribution function) Let A(0 : N
distributed using a distribution (d
t. The distribution basis is
DIST ((e N
i\Omega
\Delta\Omega \Theta DIST (e N 0

The distribution basis for a 20 \Theta 10 array distributed (Block;
Cyclic) on a 2 \Theta 2 virtual processor mesh is [ae 2
l 1
]\Omega
l
The square parenthesis separate the distribution
bases corresponding to each dimension.
Definition 2.5 (Indexing functions) The index
functions, proc, local, and global for a multi-dimensional
array are defined as follows:
In the remainder of the paper, we assume that the source
and the target distribution bases are compatible. We also
assume that the dimensionality of the virtual processor array
and the number of virtual processors is not greater than
that of the underlying physical network. We now define the
semantics of the redistribute command.
Redistribute is a regular data
distribution, corresponds to a remapping of the processor
basis in the distribution basis. If fi s is the initial distribution
basis and fi d is the distribution basis after the redistribution
then
proc(fid) may be different, which implies that redistribution
involves communication. Also, local(fis) and local(fid ) may
be different.
For example,
l represents a block distribution
of processors. Remapping the processor
basis gives the new distribution basis fi
l which
corresponds to a cyclic distribution on 4 processors. Clearly
global(fis
4\Lambdal+p . But
l , which implies that communication will be
required. Also local(fis)
l and local(fid)
which
implies that the local index of an element can change after
redistribution.
Consider the distribution bases of the source and target
distributions of the array A(0 : 191) described in the intro-
duction. The source distribution basis is ae 8
ps\Omega e 24
l s and the
target distribution basis is e 8
l
l d2
. The intermediate
data distribution used in the two-phase redistribution
strategy is given by the distribution basis e 2
l
l t2
The single-phase redistribution corresponds to the remapping
ae 8
ps\Omega e 24
l s
l
l d2
. The two-phase redistribution
corresponds to the sequence of remappings ae 8
ps\Omega e 24
l s
l
l
l
l d2
. To estimate the
benefits of the multi-phase redistribution, it is necessary to
develop cost metrics for the communication cost of data re-distribution

3 Communication Cost Estimation for Data Redistribu-
tion
In this section, we model the communication cost of single-phase
data redistribution on circuit-switched or worm-hole
routed mesh networks using fixed routing rules. A survey of
these routing techniques is presented in [19]. The communication
time can be expressed in terms of the following.
ffl Startup Time (ts is composed of the time for packing
non-consecutive data elements into a buffer, copying
the data from (to) user space to (from) system space
and unpacking the data.
ffl Transfer Time (te is the time for data transmission
and is dependent on the communication bandwidth
and the path length from the source to destination
node. For circuit-switched and worm-hole routed net-
works, for large messages, in the absence of network
contention, the time is nearly independent of the path
length [2, 19]. Since the transfer time for a message of
size n is nte , in the absence of contention, the communication
cost for a message of n elements is ts
ffl Network Contention: When the source node is communicating
with the destination node, several other
pairs of processors can be communicating across the
network. Path conflicts occur causing communication
overheads. It was shown in [2], that the impact of
node conflicts is negligible, while that of link conflicts
is significant. In general, data redistribution requires
all-to-many personalized communication. We decompose
this communication into a set of permutations
each of which can be performed in a fixed number of
contention-free steps (for a fixed underlying network
configuration). The total time for performing the sequence
of permutations provides an estimate of the
communication cost, taking into account the network
contention.
We now evaluate the redistribution cost for a linear data
array distributed on a linear processor array. We first consider
the case where both the data array size and processor
array size are perfect powers of an integer r 2 Z and then
generalize to a non-perfect-power data and processor array
l
ps\Omega e Bs
l s2
and fi
l
l d2
, be
compatible source and the target distribution bases and let
d) be the cost of the data redistribution. We define
terms which are used to determine the maximum number of
messages sent by a processor and the volume of data communicated

Definition 3.6 (Distribution Bases Difference) Let
t\Omega
\Delta\Omega oe n 0
and
\Delta\Omega
, where oe; aeg.
The difference of fi 2 with fi 1 is given by Q(fi1
l
l
l
For example,
l
l 12
and
l
, can
be factorized to
l
l 12
l
l
The difference Q(fi1 ; fi 2) is the size of the vector basis e 2
l 12
Thus, 2. Similarly, Q(fi2 ; 2. If the number
of processors in the source and target distributions is
equal then the distribution bases difference is symmetric,
Definition 3.7 (Distribution Bases Union) Let fi 1 and
fi 2 be compatible distribution bases, s.t.,
\Delta\Omega oe n 0
and
\Delta\Omega
, where oe; aeg. The union of
l
l
l
The union U(fi1 ; fi 2 ), of the distribution bases shown above,
is the size of the tensor basis ae 2
l 12
. Thus, we
have If the number of processors in the
source and target distribution is P , then U(fis ; fi d) = P \Theta
We now estimate the communication cost for
data redistribution using the difference and union of the
source and target distribution bases.
3.1 Perfect Power Data and Processor Array Sizes
loss of generality, let bs ! bd
results hold otherwise). We have
l
l s2
and fi
l
l d2
. The two
bases are compatible and
l
l
l s2
l
l
l d22
Consider a processor
Under the source distribution, all elements with global in-
dices, g, s.t., (g div r bs are located on processor
q. These elements have global indices of the form ir p+bs
bs and are represented
by e r c d
. (Note that
the indices of the processor bases are set to values q1 and
q2 ). Consider a particular element located on processor q,
with a global index
This
element corresponds to the basis element e r c d
l
l 2
\Omega
ae r p\Gammab d +bs
l 3
. Its global index after data redistribution
will be unchanged. But it will be located on processor
q will have to communicate with processor l 2 r p\Gammab d +bs
during the data redistribution. Since q1 is fixed for all the
elements on processor q, the largest number of processors
that q needs to communicate with, is determined by the total
number of different values of l 2 for elements located on
q. Since l 2 is the index of the vector basis e r b d \Gammab s
l s2 , it can
take r b d \Gammab s values
needs to communicate with at most r b d \Gammab s processors during
data redistribution. This estimate can be directly obtained
by comparing the source and target distribution bases. The
number of processors that q will communicate with depends
on the size of the data basis e r b d \Gammab s
l si2
, which corresponds to
the difference of fi d with fi s . Since a similar argument holds
for all source processors, using Def. 3.6 it follows that the
maximum number of messages a processor needs to send
during data redistribution is the difference Q(fis ; fi d ).
The maximum size of data to be sent in a message is determined
as follows. Consider a processor
From the previous discussion, it follows that processor q will
communicate with processors ir p\Gammab d +bs
during data redistribution. Consider the message, processor
q sends to the processor . The
elements located on processor q which are to be sent to processor
and (i div r b d elements with indices of
the
r c d and 0 - bs . These elements are represented by
e r c d
. Thus the total
number of data items to be communicated is r c d \Theta r bs ,
which is the total size of the vector bases e r c d
. The
union U(fis ; fi d) corresponds to the size of the tensor basis
l
r c d +bs . Thus the number of data elements to be communicated
is given by N
Using the presented
cost model, the largest communication cost for a message in
the absence of contention is given by
ts
te
We will now model the required communication as a sequence
of permutations. We first consider an example. Let
the source and target distributions are cyclic and block dis-
tributions, respectively, of a 27 element array on 9 proces-
sors. This redistribution is shown in Fig. 1. The necessary
communication can be represented in terms of a communication
matrix C, where C(i;
sends data to processor P j else C(i;
and Q2 are permutation matrices. If the underlying
topology is a 3 \Theta 3 mesh then each of the permuta-
tions, Q0 ; Q1 and Q2 , can be scheduled in three contention-free
steps, using scheduling techniques presented in [23, 24].
Thus the maximum communication time for the data re-distribution
will correspond to the time for performing the
three permutations. The sequence of permutations Q0
Q2 is said to exactly cover the communication C required
for the data redistribution, as no redundant messages are
sent and all the messages required by the redistribution are
communicated.
In general, the communication for data redistribution
requires that each processor communicate with Q(fis ; fi d)
distinct processors. We show that the communication can
be expressed in terms of exactly Q(fis ; fi d) permutations.
each processor can be expressed in radix r
as - be a permutation of
s; permutation f-;a;s can be expressed
in terms of -, a, and s as f-;a;s
In
the above example we have corresponds
to
Q2 to
Source Distribution: Cyclic
Target Distribution: Block

Figure

1: Data Redistribution of A(0:26) from Cyclic to Block.
Input: Compatible distribution bases fi
l
l s2
and fi
l
l d2
Output: Permutations that exactly cover the redistribution communication.
else

Figure

2: Algorithm 1 - Construct permutations to cover communication for data redistribution.
In Fig. 2, we present an algorithm that constructs the
sequence of permutations that exactly covers the communication
required for data redistribution. In the algorithm,
an x-tuple, each of whose elements has a value 0 is represented
as (0)x and (ir )s corresponds to a base r representation
of i using s digits. Also (x) \Delta (y) corresponds to a
concatenation of x and y. For example,
Note that the difference Q(fis ; fi d) is a
perfect power of r.
Theorem 3.1 The communication for data redistribution
from
l
l s2
to fi
l
l d2
is
exactly covered by Q(fis ; fi d) permutations.
Proof: We prove that the sequence of permutations constructed
in Algorithm 1 exactly covers the required commu-
nication. We consider the case where bs ! bd and bs +p ? bd .
v. Consider a
processor . According to the argument in
Section 3.1, processor q will communicate with all processors
ir p\Gammab d +bs
From algorithm 1, we have
r p\Gammab d +bs , . Thus we have
Also, from Algorithm 1, a
(ir )v . Thus a
Therefore
permutation
covers the communication of q with processor
r b d \Gammab s , each permutation f-;a
a communication with a distinct processor. The theorem
follows by noting that q needs to communicate with r b d \Gammab s
processors, and each permutation covers a required communication
with a distinct processor. 2
Thus performing the data redistribution requires totally
d) permutations. Each permutation can be performed
in a fixed number of contention-free steps determined by the
underlying mesh architecture (say k). As each step requires
time at most equal to the time for sending a message of size
the total cost of the data redistribution is
ts
te
uniformly scales the redistribution cost it is not considered
in the remaining cost estimates.
The use of the distribution bases also facilitates the indexing
code generation for data redistribution. To perform
redistribution, each processor u; 0 - needs to evaluate
the following.
ffl Send processor set of processor u (PSend(u)): set of
processors to which u has to send data.
ffl Send data index set of processor u to processor v
(DSend(u; v)): local indices of the array elements which
are resident on u but are needed by v.
Receive processor set of processor u
of processors from which u has to receive data.
ffl Receive data index set of processor u from processor
local indices of the array elements
which are needed by u but are resident on v.
If the arrays have only block or cyclic distribution, then the
data index sets and the processor sets can be characterized
using regular sections for closed forms [10, 11, 17]. For a
general cyclic(bs) to a cyclic(bd) redistribution, closed form
characterization of these sets using simple regular sections
is not possible. However, when the source and destination
distribution bases are compatible, closed forms can be eval-
uated. From the discussion in Section 3.1, it follows that
processor communicates with all processors
ir p\Gammab d +bs
similar evaluation for the other cases
where
We use a recursive
regular section notation to represent the data send sets. A
two-level recursive regular section of array A given by l+((0 :
directly to the following loop nest
do
do
Thus for the case considered in Section 3.1, DSend(u; v)
where
to local(e r c d
l
2\Omega
l s2
l s11 r b d +v 1 r b s +l s2
r b d ). Performing a similar evaluation for the other cases and
letting
vr b d \Gammap
The receive processor and data sets can be evaluated similarly
and are given by
where
The data receive sets are as follows. DRecv(u;
vr bs \Gammap
3.2 General Data and Processor Array Sizes
l
ps\Omega e Bs
l s2
and fi
l
l d2
. Let
results hold for the other
cases). Since the two distribution bases are compatible Bs jBd
and Bd jPBs .
l
Bs
l
PBs
Bs
l s2
l
Bs
PBs
Bs
l
d21\Omega e Bs
l d22
Using an argument similar to Section 3.1, it can be shown
that processor
Bs needs to communicate
with all processors i PBs
Bs . Thus
the largest number of processors a source processor needs to
communicate with is B d
Bs (= Q(fis ; fi d )). Similarly, the largest
message size to be communicated is N=P
. The required
communication can be expressed as a sequence of permuta-
tions. We have
Theorem 3.2 The communication for data redistribution
from
l
ps\Omega e Bs
l s2
to fi
l
l d2
is exactly
covered by Q(fis ; fi d) permutations.
The proof is similar to Theorem 3.1. The permutations are
constructed as shown in Fig. 3. Since Q(fis ; fi d) permutations
are required and each permutation can be performed
in a fixed number of contention-free steps, the total communication
cost is given by
ts
te
For example, consider the data distributions shown in Fig. 4.
The distribution bases are given by fi
l s , fi
e 6
l
. The basis difference is Q(fis ; fi d) = 6 and the basis
union is U(fis ; fi d) = 36. The largest number of messages
sent by a processor is six and the largest size of any messages
is one 2 . The cost of the single-phase data redistribution is
Closed forms for the processor index and data index sets
can be determined in a manner similar to that used for perfect
power data and array sizes in Section 3.1.
The distribution basis for a multidimensional array is
the tensor product of the distribution basis of each dimen-
sion. Since shape-preserving data redistribution is consid-
ered, only the distribution along each array dimension changes
without changing the shape of the data or processor ar-
ray. The above analysis can be performed independently
for each array dimension and the results combined for the
multidimensional array.
4 Communication-Efficient Data Redistribution
In this section, we describe the multi-phase redistribution
strategy. We first consider a specific example and then de-
2 The message sent by a processor to itself is also accounted.
Input: Compatible distribution bases fi
l
ps\Omega e Bs
l s2
and fi
l
l d2
Output: Permutations that exactly cover the redistribution communication.
do
ii
mod Bs
PBs
else if ((Bd ! Bs) - (PBd ? Bs))
Bs

Figure

3: Algorithm 2 - Construct permutations to cover communication for data redistribution.
Source Distribution: Block
Target Distribution: Cyclic

Figure

4: Data Redistribution of A(0:35) from Block to Cyclic.
scribe the general procedure. Let fi
l
l s2
and
l
l d2
. We have
0:
Redistribution corresponds to remapping the appropriate
data basis to a processor basis. Redistribution from fi s to
fi d corresponds to remapping the data bases e r
and e r
to processor bases and ae r
1 to data bases. Each
such remapping involves communication with a subset of
the other processors. The remapping can be performed directly
by mapping all data bases to processor bases in one
step or as a sequence of steps. Consider performing the re-distribution
using the intermediate distribution where the
data basis e r
is first mapped to a processor basis. During
the first redistribution from fi
l
l s2
to
l
l s3
a processor communicates with at most
r other processors. The cost of the redistribution is given
by C(fis
P te . The redistribution from fi t to fi d
involves the mapping of the data base e r
to a processor ba-
sis. The cost of the redistribution is
The total cost of the two-phase redistribution is C(fis ; fi d) =
P te . The single-phase redistribution would have a
cost of r 2 ts
In general, data bases with a total size of Q(fis ; fi d) need
to be remapped to processor bases. The multi-phase strategy
corresponds to performing the mapping, one factor of
s) at a time. The choice of the intermediate distribution
depends on the factorization of Q(fis ; fi d ). In the above
example, r, is the factorization used. In
general, if the difference Q(fis ; fi d) is factorized into k factors
distributions
are used. Redistribution is performed in k-phases.
Phase i corresponds to redistribution from distribution basis
fi i to distribution basis fi i+1 such that Q(fi
and . Using the cost model developed in
Section 3, the cost of phase i is r ts
P te . The total cost
of the k-phase redistribution is given by
ts
The redistribution method for multi-dimensional arrays
is developed from the method for linear arrays. The number
of intermediate distributions is determined by the number
of factors of the difference of the two distribution bases. Let
l s1
l s2
l
]\Omega
l
l d21
different factor-
izations. We consider two factorizations Q(fis ; fi d)
3. The first factorization corresponds
to the following sequence of distributions - [ae 6
l s1
]\Omega
[ae 4
l s2
l 11
l
l t22
l
l
l d2
]. The second factorization
corresponds to the sequence of distributions [ae 6
s1\Omega
e 6
l s1
l s2
l
l
l t2
l
l
l d2
]. The first method costs
8ts +2   36te and the second costs 7ts +2   36te . The second
method has the lowest communication cost among all possible
factorizations. In general, the redistribution strategy
with the smallest cost will depend on the actual values of the
message setup and transfer times. We formulate the problem
of determining the intermediate distributions such that
the total communication cost is minimized as the following
optimization problem.
Given the machine parameters ts ; te ; P , and the data array
parameters the problem is to find a multiplicative
partition of Q(fis ; fi d) = r0 \Theta \Delta \Delta \Delta \Theta r t\Gamma1 such that the
the total communication cost C(fis ; fi d) is minimized:
ts
For the special case, where Q(fis finding
a multiplicative partition of P is equivalent to finding an
additive partition of p. An O(p) algorithm for finding the
optimal partition is presented in [20]. This case is the most
frequently occurring case as the number of physical processors
are usually perfect powers of two and difference in the
distribution bases will be a perfect power of two. Heuristics
for the general case when Q(fis ; fi d) is not a perfect power
are provided in [16].
Performance Results
In this section, we compare the performance of the multi-phase
and single-phase strategies for specific source and target
data distributions on a 32-node Intel iPSC/860 hyper-
cube. Due to lack of access to a mesh-connected computer,
the strategies could not be compared for a mesh network.
The communication for the two approaches was performed
according to the permutations generated in Algorithm 2.
The total time required for the redistribution using the single-phase
and multi-phase strategies for block-cyclic source and
destination distributions was measured for increasing data
sizes. This time includes the indexing time for packing and
unpacking data and the actual communication time. The
timings were taken using the millisecond wallclock timer
mclock().

Table

1(a) shows the total times in milliseconds for the
redistribution from cyclic(256) to cyclic(16) on 16 proces-
sors. The difference of the corresponding distribution bases
is 16. The two-phase strategy used a cyclic(64) intermediate
distribution. According to the communication cost model,
the two phase strategy corresponding to the factorization
4 has the lowest communication cost among all
possible multi-phase strategies. As seen in Table 1(a) the
two phase strategy performs better than the single-phase
strategy up to a data size of 28K. For larger data sizes,
the increase in the transmission cost overrides the decrease
in the message startup times. Table 1(b) shows the total
times in milliseconds for the redistribution from cyclic(256)
to cyclic(8) on 32 processors. The difference of the corresponding
distribution bases is 32 and two two-phase strategies
corresponding to the factorizations
respectively can be used. The two strategies
use cyclic(32) (referred to as Two-Phase(1)) and cyclic(64)
(referred to as Two-Phase(2)) as intermediate data distri-
butions, respectively. According the cost model, the two
strategies should have identical communication times. The
difference between the times for the two-phase strategies as
shown in Table 1(b) is negligible. Also the two-phase strategy
performs better than the single-phase strategy up to
a data size of 64K. For larger data sizes, the increase in
the transmission cost overrides the decrease in the message
startup times.
6 Conclusion
In this paper, we have presented an approach to communication
efficient data redistribution. Using the tensor product
representation of regular data distributions, we have developed
cost estimates for data redistribution. Using these
estimates we have demonstrated that the use of a multi-phase
redistribution strategy can reduce the total cost. We
have presented methods for determining the appropriate intermediate
distributions. Performance results on the Intel
iPSC/860 show that the multi-phase redistribution strategy
can improve performance over single-phase redistribution.

Acknowledgments

We would like to thank the Advanced Concepts Computational
Laboratory at NASA Lewis Research Center for access
to the Intel iPSC/860 hypercube.



--R


Communication overheads on the Intel iPSC-2 hypercube
Vienna Fortran - a Fortran language extension for distributed memory multiprocessors
Generating local addresses and communication sets for data parallel programs.
Optimal evaluation of array expressions on massively parallel machines.
High Performance Fortran Forum.
Solving Problems on Concurrent Processors.




Compiler optimizations for Fortran-D on MIMD distributed-memory machines
Compiler support for machine-independent parallel programming in Fortran-D
Topics in Matrix Analy- sis
The complexity of re-shaping arrays on boolean cubes


Compiling communication-efficient programs for massively parallel machines
A survey of wormhole routing techniques in direct networks.
Optimal phase barrier synchronization in k-ary n-cube wormhole-routed systems using mul- tirendezvous primitives
Efficient compilation of array statements for private memory multicomputers.
Runtime array redistribution in HPF programs.


--TR
Solving problems on concurrent processors. Vol. 1: General techniques and regular problems
Compiler optimizations for Fortran D on MIMD distributed-memory machines
Compile-time generation of regular communications patterns
Vienna FortranMYAMPERSANDmdash;a Fortran language extension for distributed memory multiprocessors
Computer support for machine-independent parallel programming in Fortran D
Generating local addresses and communication sets for data-parallel programs
Implementing a parallel C++ runtime system for scalable parallel systems
A Survey of Wormhole Routing Techniques in Direct Networks
Compiling Communication-Efficient Programs for Massively Parallel Machines
Compile-Time Estimation of Communication Costs on Multicomputers
On-Line Communication on Circuit-Switched Fixed Routing Meshes
Efficient Compilation of Array Statements for Private Memory Multicomputers

--CTR
Stavros Souravlas , Manos Roumeliotis, A pipeline technique for dynamic data transfer on a multiprocessor grid, International Journal of Parallel Programming, v.32 n.5, p.361-388, October 2004
Thakur , Alok Choudhary , J. Ramanujam, Efficient Algorithms for Array Redistribution, IEEE Transactions on Parallel and Distributed Systems, v.7 n.6, p.587-594, June 1996
Neungsoo Park , Viktor K. Prasanna , Cauligi S. Raghavendra, Efficient Algorithms for Block-Cyclic Array Redistribution Between Processor Sets, IEEE Transactions on Parallel and Distributed Systems, v.10 n.12, p.1217-1240, December 1999
Minyi Guo , Yi Pan, Improving communication scheduling for array redistribution, Journal of Parallel and Distributed Computing, v.65 n.5, p.553-563, May 2005
Narasimhan Ramasubramanian , Ram Subramanian , Santosh Pande, Automatic Compilation of Loops to Exploit Operator Parallelism on Configurable Arithmetic Logic Units, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.45-66, January 2002
Ram Subramanian , Santosh Pande, A framework for performance-based program partitioning, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
Minyi Guo , Ikuo Nakata, A Framework for Efficient Data Redistribution on Distributed Memory Multicomputers, The Journal of Supercomputing, v.20 n.3, p.243-265, November 2001
Ram Subramanian , Santosh Pande, A framework for performance-based program partitioning, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
Ching-Hsien Hsu , Sheng-Wen Bai , Yeh-Ching Chung , Chu-Sing Yang, A Generalized Basic-Cycle Calculation Method for Efficient Array Redistribution, IEEE Transactions on Parallel and Distributed Systems, v.11 n.12, p.1201-1216, December 2000
Yeh-Ching Chung , Ching-Hsien Hsu , Sheng-Wen Bai, A Basic-Cycle Calculation Technique for Efficient Dynamic Data Redistribution, IEEE Transactions on Parallel and Distributed Systems, v.9 n.4, p.359-377, April 1998
Ching-Hsien Hsu , Yeh-Ching Chung, Efficient Methods for kr  r and r  kr Array Redistribution1, The Journal of Supercomputing, v.12 n.3, p.253-276, May 1, 1998
Ching-Hsien Hsu , Yeh-Ching Chung , Don-Lin Yang , Chyi-Ren Dow, A Generalized Processor Mapping Technique for Array Redistribution, IEEE Transactions on Parallel and Distributed Systems, v.12 n.7, p.743-757, July 2001
Ching-Hsien Hsu , Yeh-Ching Chung , Chyi-Ren Dow, Efficient Methods for Multi-Dimensional Array Redistribution, The Journal of Supercomputing, v.17 n.1, p.23-46, Aug. 2000
PeiZong Lee , Wen-Yao Chen, Generating communication sets of array assignment statements for block-cyclic distribution on distributed memory parallel computers, Parallel Computing, v.28 n.9, p.1329-1368, September 2002
Edgar T. Kalns , Lionel M. Ni, Processor Mapping Techniques Toward Efficient Data Redistribution, IEEE Transactions on Parallel and Distributed Systems, v.6 n.12, p.1234-1247, December 1995
Neungsoo Park , Viktor K. Prasanna , Cauligi Raghavendra, Efficient algorithms for block-cyclic array redistribution between processor sets, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-13, November 07-13, 1998, San Jose, CA
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
Manojkumar Krishnan , Jarek Nieplocha, Memory efficient parallel matrix multiplication operation for irregular problems, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy
tensor products;data distribution;high performance Fortran;data communication;distributed-memory machine