Scheduling Block-Cyclic Array Redistribution.
AbstractThis article is devoted to the run-time redistribution of one-dimensional arrays that are distributed in a block-cyclic fashion over a processor grid. While previous studies have concentrated on efficiently generating the communication messages to be exchanged by the processors involved in the redistribution, we focus on the scheduling of those messages: how to organize the message exchanges into "structured" communication steps that minimize contention. We build upon results of Walker and Otto, who solved a particular instance of the problem, and we derive an optimal scheduling for the most general case, namely, moving from a CYCLIC(r) distribution on a P-processor grid to a CYCLIC(s) distribution on a Q-processor grid, for arbitrary values of the redistribution parameters P, Q, r, and s.
Introduction
Run-time redistribution of arrays that are distributed in a block-cyclic fashion over a multidimensional
processor grid is a difficult problem that has recently received considerable attention. This
interest is motivated largely by the HPF [13] programming style, in which scientific applications
are decomposed into phases. At each phase, there is an optimal distribution of the data arrays
onto the processor grid. Typically, arrays are distributed according to a CYCLIC(r) pattern along
one or several dimensions of the grid. The best value of the distribution parameter r depends on
the characteristics of the algorithmic kernel as well as on the communication-to-computation ratio
of the target machine [5]. Because the optimal value of r changes from phase to phase and from
one machine to another (think of a heterogeneous environment), run-time redistribution turns out
to be a critical operation, as stated in [10, 21, 22] (among others).
Basically, we can decompose the redistribution problem into the following two subproblems:
Message generation The array to be redistributed should be efficiently scanned or processed in
order to build up all the messages that are to be exchanged between processors.
Communication scheduling All the messages must be efficiently scheduled so as to minimize
communication overhead. A given processor typically has several messages to send, to all
other processors or to a subset of these. In terms of MPI collective operations [16], we must
schedule something similar to an MPI ALLTOALL communication, except that each processor
may send messages only to a particular subset of receivers (the subset depending on the
sender).
Previous work has concentrated mainly on the first subproblem, message generation. Message
generation makes it possible to build a different message for each pair of processors that must
communicate, thereby guaranteeing a volume-minimal communication phase (each processor sends
or receives no more data than needed). However, the question of how to efficiently schedule the
messages has received little attention. One exception is an interesting paper by Walker and Otto [21]
on how to schedule messages in order to change the array distribution from CYCLIC(r) on a P -
processor linear grid to CYCLIC(Kr) on the same grid. Our aim here is to extend Walker and Otto's
work in order to solve the general redistribution problem, that is, moving from a CYCLIC(r)
distribution on a P -processor grid to a CYCLIC(s) distribution on a Q-processor grid.
The general instance of the redistribution problem turns out to be much more complicated
than the particular case considered by Walker and Otto. However, we provide efficient algorithms
and heuristics to optimize the scheduling of the communications induced by the redistribution
operation. Our main result is the following: For any values of the redistribution parameters P , Q,
r and s, we construct an optimal schedule, that is, a schedule whose number of communication
steps is minimal. A communication step is defined so that each processor sends/receives at most one
message, thereby optimizing the amount of buffering and minimizing contention on communication
ports. The construction of such an optimal schedule relies on graph-theoretic techniques such as
the edge coloring number of bipartite graphs. We delay the precise (mathematical) formulation of
our results until Section 4 because we need several definitions beforehand.
Without loss of generality, we focus on one-dimensional redistribution problems in this article.
Although we usually deal with multidimensional arrays in high-performance computing, the problem
reduces to the "tensor product" of the individual dimensions. This is because HPF does not
allow more than one loop variable in an ALIGN directive. Therefore, multidimensional assignments
and redistributions are treated as several independent one-dimensional problem instances.
The rest of this article is organized as follows. In Section 2 we provide some examples of
redistribution operations to expose the difficulties in scheduling the communications. In Section 3
we briefly survey the literature on the redistribution problem, with particular emphasis given to
the Walker and Otto paper [21]. In Section 4 we present our main results. In Section 5 we report
on some MPI experiments that demonstrate the usefulness of our results. Finally, in Section 6, we
state some conclusions and future work directions.
Motivating Examples
Consider an array X[0:::M \Gamma 1] of size M that is distributed according to a block cyclic distribution
CYCLIC(r) onto a linear grid of P processors (numbered from Our goal is to
redistribute X using a CYCLIC(s) distribution on Q processors (numbered from
For simplicity, assume that the size M of X is a multiple of Qs), the least common
multiple of P r and Qs: this is because the redistribution pattern repeats after each slice of L
elements. Therefore, assuming an even number of slices in X will enable us (without loss of
generality) to avoid discussing side effects. Let L be the number of slices.
Example 1
Consider a first example with 5. Note that the new grid
of Q processors can be identical to, or disjoint of, the original grid of P processors. The actual
total number of processors in use is an unknown value between 16 and 32. All communications are
summarized in Table 1, which we refer to as a communication grid. Note that we view the source
and target processor grids as disjoint in Table 1 (even if it may not actually be the case). We see
that each source processor messages and that each processor
receives 7 messages, too. Hence there is no need to use a full all-to-all
communication scheme that would require 16 steps, with a total of 16 messages to be sent per
processor (or more precisely, 15 messages and a local copy). Rather, we should try to schedule
the communication more efficiently. Ideally, we could think of organizing the redistribution in 7
steps, or communication phases. At each step, 16 messages would be exchanged, involving
disjoint pairs of processors. This would be perfect for one-port communication machines, where
each processor can send and/or receive at most one message at a time.
Note that we may ask something more: we can try to organize the steps in such a way that at
each step, the 8 involved pairs of processors exchange a message of the same length. This approach
is of interest because the cost of a step is likely to be dictated by the length of the longest message
exchanged during the step. Note that message lengths may or may not vary significantly. The
numbers in Table 1 vary from 1 to 3, but they are for a single slice vector. For a vector X of length
lengths vary from 1000 to 3000 (times the number of
bytes needed to represent one data-type element).
A schedule that meets all these requirements, namely, 7 steps of 16 disjoint processor pairs
exchanging messages of the same length, will be provided in Section 4.3.2. We report the solution
schedule in Table 2. Entry in position (p; q) in this table denotes the step (numbered from a to g
for clarity) at which processor p sends its message to processor q.
In

Table

3, we compute the cost of each communication step as (being proportional to) the
length of the longest message involved in this step. The total cost of the redistribution is then the
sum of the cost of all the steps. We further elaborate on how to model communication costs in
Section 4.3.1.

Table

1: Communication grid for 5. Message lengths are indicated for
a vector X of size
Communication grid for
of msg.
Nbr of msg. 7 7
Example 2
The second example, with shows the usefulness of an efficient
schedule even when each processor communicates with every other processor. As illustrated in

Table

4, message lengths vary with a ratio from 2 to 7, and we need to organize the all-to-all
exchange steps in such a way that messages of the same length are communicated at each step.
Again, we are able to achieve such a goal (see Section 4.3.2). The solution schedule is given in

Table

5 (where steps are numbered from a to p), and its cost is given in Table 6. (We do check
that each of the 16 steps is composed of messages of the same length.)
Example 3
Our third motivating example is with As shown in Table 7, the
communication scheme is severely unbalanced, in that processors may have a different number of
messages to send and/or to receive. Our technique is able to handle such complicated situations.
We provide in Section 4.4 a schedule composed of 10 steps. It is no longer possible to have messages
of the same length at each step (for instance, processor messages only of length 3 to send,
while processor messages only of length 1 or 2), but we do achieve a redistribution in
communication steps, where each processor sends/receives at most one message per step. The
number of communication steps in Table 8 is clearly optimal, as processor
to send. The cost of the schedule is given in Table 9.

Table

2: Communication steps for
Communication steps for
9 - a - b - d f - g e - c

Table

3: Communication costs for
Communication costs for
Step a b c d e f g Total
Cost
Example 4
Our final example is with P 6= Q, just to show that the size of the two processor grids need not be
the same. See Table 10 for the communication grid, which is unbalanced. The solution schedule
(see Section 4.4) is composed of 4 communication steps, and this number is optimal, since processor
messages to receive. Note that the total cost is equal to the sum of the message lengths
that processor must receive; hence, it too is optimal.
3 Literature overview
We briefly survey the literature on the redistribution problem, with particular emphasis given to
the work of Walker and Otto [21].

Table

4: Communication grid for are indicated
for a vector X of size
of msg.
Nbr of msg.
3.1 Message Generation
Several papers have dealt with the problem of efficient code generation for an HPF array assignment
statement like
where both arrays A and B are distributed in a block-cyclic fashion on a linear processor grid. Some
researchers (see Stichnoth et al.[17], van Reeuwijk et al.[19], and Wakatani and Wolfe [20]) have
dealt principally with arrays distributed by using either a purely scattered or cyclic distribution
(CYCLIC(1) in HPF) or a full block distribution (CYCLIC(d n
is the array size and p the
number of processors).
Recently, however, several algorithms have been published that handle general block-cyclic
distributions. Sophisticated techniques involve finite-state machines (see Chatterjee et
al. [3]), set-theoretic methods (see Gupta et al. [8]), Diophantine equations (see Kennedy et al. [11,
12]), Hermite forms and lattices (see Thirumalai and Ramanujam [18]), or linear programming (see
Ancourt et al. [1]). A comparative survey of these algorithms can be found in Wang et al. [22],
where it is reported that the most powerful algorithms can handle block-cyclic distributions as
efficiently as the simpler case of pure cyclic or full-block mapping.
At the end of the message generation phase, each processor has computed several different
messages (usually stored in temporary buffers). These messages must be sent to a set of receiving
processors, as the examples of Section 2 illustrate. Symmetrically, each processor computes the
number and length of the messages it has to receive and therefore can allocate the corresponding
memory space. To summarize, when the message generation phase is completed, each processor

Table

5: Communication steps for
Communication steps for
9 g a

Table

Communication costs for
Communication costs for
Step a b c d e f
Cost
has prepared a message for all those processors to which it must send data, and each processor
possesses all the information regarding the messages it will receive (number, length, and origin).
3.2 Communication Scheduling
Little attention has been paid to the scheduling of the communications induced by the redistribution
operation. Simple strategies have been advocated. For instance, Kalns and Ni [10] view the
communications as a total exchange between all processors and do not further specify the operation.
In their comparative survey, Wang et al. [22] use the following template for executing an array
assignment statement:
1. Generate message tables, and post all receives in advance to minimize operating systems
overhead
2. Pack all communication buffers
3. Carry out barrier synchronization

Table

7: Communication grid for 5. Message lengths are indicated for
a vector X of size
14 Nbr of msg.
Nbr of msg. 6 9 6 6 9 6 6 9 6 6 9 6 6 9 9
4. Send all buffers
5. Wait for all messages to arrive
6. Unpack all buffers
Although the communication phase is described more precisely, note that there is no explicit
scheduling: all messages are sent simultaneously by using an asynchronous communication pro-
tocol. This approach induces a tremendous requirement in terms of buffering space, and deadlock
may well happen when redistributing large arrays.
The ScaLAPACK library [4] provides a set of routines to perform array redistribution. As
described by Prylli and Tourancheau [15], a total exchange is organized between processors, which
are arranged as a (virtual) caterpillar. The total exchange is implemented as a succession of steps.
At each step, processors are arranged into pairs that perform a send/receive operation. Then the
caterpillar is shifted so that new exchange pairs are formed. Again, even though special care is taken
in implementing the total exchange, no attempt is made to exploit the fact that some processor
pairs may not need to communicate.
The first paper devoted to scheduling the communications induced by a redistribution is that
of Walker and Otto [21]. They review two main possibilities for implementing the communications
induced by a redistribution operation:
Wildcarded nonblocking receives Similar to the strategy of Wang et al. described above, this
asynchronous strategy is simple to implement but requires buffering for all the messages to
be received (hence, the total amount of buffering is as high as the total volume of data to be
redistributed).

Table

8: Communication steps for
Communication steps for

Table

9: Communication costs for
Communication costs for
Step a b c d e f g h i j Total
Cost
Synchronous schedules A synchronized algorithm involves communication phases or steps. At
each step, each participating processor posts a receive, sends data, and then waits for the
completion of the receive. But several factors can lead to performance degradation. For
instance, some processors may have to wait for others before they can receive any data. Or
hot spots can arise if several processors attempt to send messages to the same processor at
the same step. To avoid these drawbacks, Walker and Otto propose to schedule messages
so that, at each step, each processor sends no more than one message and receives no more
than one message. This strategy leads to a synchronized algorithm that is as efficient as the
asynchronous version, as demonstrated by experiments (written in MPI [16]) on the IBM
SP-1 and Intel Paragon, while requiring much less buffering space.
Walker and Otto [21] provide synchronous schedules only for some special instances of the
redistribution problem, namely, to change the array distribution from CYCLIC(r) on a P -processor
linear grid to CYCLIC(Kr) on a grid of same size. Their main result is to provide a schedule
composed of K steps. At each step, all processors send and receive exactly one message. If K is
smaller than P , the size of the grid, there is a dramatic improvement over a traditional all-to-all
implementation.

Table

10: Communication grid for Message lengths are indicated
for a vector X of size
msg.
Nbr of msg. 2 4
Our aim in this article is to extend Walker and Otto's work in order to solve the general re-distribution
problem, that is, moving from a CYCLIC(r) distribution on a P -processor grid to a
CYCLIC(s) distribution on a Q-processor grid. We retain their original idea: schedule the communications
into steps. At each step, each participating processor neither sends nor receives more
than one message, to avoid hot spots and resource contentions. As explained in [21], this strategy
is well suited to current parallel architectures. In Section 4.3.1, we give a precise framework to
model the cost of a redistribution.
4 Main Results
4.1 Problem Formulation
Consider an array X[0:::M \Gamma 1] of size M that is distributed according to a block-cyclic distribution
CYCLIC(r) onto a linear grid of P processors (numbered from Our goal is
to redistribute X by using a CYCLIC(s) distribution on Q processors (numbered from
1). Equivalently, we perform the HPF assignment is CYCLIC(r) on a
-processor grid, while Y is CYCLIC(s) on a Q-processor grid 1 .
The block-cyclic data distribution maps the global index i of vector X (i.e., element X[i]) onto a
processor index p, a block index l, and an item index x, local to the block (with all indices starting
at 0). The mapping i \Gamma! (p; l; x) may be written as
bi=rc
We derive the relation
1 The more general assignment Y [a can be dealt with similarly.

Table

11: Communication steps for
Communication steps for

Table

12: Communication costs for
Communication costs for
Step a b c d Total
Cost
Similarly, since Y is distributed CYCLIC(s) on a Q-processor grid, its global index j is mapped as
y. We then get the redistribution equation
Qs) be the least common multiple of P r and Qs. Elements i and L+i of X are
initially distributed onto the same processor (because L is a multiple of P r, hence
r divides L, and P divides L \Xi r). For a similar reason, these two elements will be redistributed
onto the same processor In other words, the redistribution pattern repeats after
each slice of L elements. Therefore, we restrict the discussion to a vector X of length L in the
following. Let rQs). The bounds in equation (3) become
s:
Given the distribution parameters r and s, and the grid parameters P and Q, the
redistribution problem is to determine all the messages to be exchanged, that is, to find all
values of p and q such that the redistribution equation (3) has a solution in the unknowns l, m,
x, and y, subject to the bounds in Equation (4). Computing the number of solutions for a given
processor pair (p; q) will give the length of the message.
We start with a simple lemma that leads to a handy simplification:
Lemma 1 We can assume that r and s are relatively prime, that is,
Proof The redistribution equation (3) can be expressed as
Equation (3) can be
expressed as
If it has a solution for a given processor pair (p; q), then \Delta divides z, z = \Deltaz 0 , and we deduce a
solution for the redistribution problem with r 0 , s 0 , P , and Q.
Let us illustrate this simplification on one of our motivating examples:
Back to Example 3
Note that we need to scale message lengths to move from a redistribution operation where r and s
are relatively prime to one where they are not. Let us return to Example 3 and assume for a while
that we know how to build the communication grid in Table 7. To deduce the communication grid
for say, we keep the same messages, but we scale all lengths by
This process makes sense because the new size of a vector slice is \DeltaL rather than L. See Table 13
for the resulting communication grid. Of course, the scheduling of the communications will remain
the same as with while the cost in Table 9 will be multiplied by \Delta.
4.2 Communication Pattern
Consider a redistribution with parameters r, s, P , and Q, and assume that
Qs). The communication pattern induced by the redistribution operation is a
complete all-to-all operation if and only if
Proof We rewrite Equation (5) as ps \Gamma because P r:l \Gamma Qs:m is an arbitrary multiple
of g. Since z lies in the interval [1 \Gamma whose length is r guaranteed that a
multiple of g can be found within this interval if Conversely, assume that g - r s:
we will exhibit a processor pair (p; q) exchanging no message. Indeed, is the
desired processor pair. To see this, note that pr \Gamma (because g divides P r); hence,
no multiple of g can be added to pr \Gamma qs so that it lies in the interval [1 \Gamma Therefore, no
message will be sent from p to q during the redistribution. 2
In the following, our aim is to characterize the pairs of processors that need to communicate
during the redistribution operation (in the case s). Consider the following function
2 For another proof, see Petitet [14].

Table

13: Communications for are indicated for
a vector X of size
14 Nbr of msg.
Nbr of msg. 6 9 6 6 9 6 6 9 6 6 9 6 6 9 9
Function f maps each processor pair (p; q) onto the congruence class of pr \Gamma qs modulo g.
According to the proof of Lemma 2, p sends a message to q if and only if f(p;
(modg). Let us illustrate this process by using one of our motivating examples.
Back to Example 4
In this example, We have (as in the proof
of Lemma 2). If
receives no message from p. But if
does receive a message (see Table 10 to check this).
To characterize classes, we introduce integers u and v such that
r \Theta
(the extended Euclid algorithm provides such numbers for relatively prime r and s). We have the
following result.
Proposition 1 Assume that
r
' u
mod
g:
Proof First, to see that PQ
indeed is an integer, note that
Since g divides both P r and Qs, it divides PQ.
Two different classes are disjoint (by definition). It turns out that all classes have the same
number of elements. To see this, note that for all k 2 [0;
integer d 0 , and
Since there are g classes, we deduce that the number of elements in each class is PQ
.
Next, we see that (p - ; q -s mod
(because
Finally, (p
both P r and Qs divide
divides )rs. We deduce
that PQ
divides hence all the processors pairs (p
are distinct. We
have thus enumerated class(0).
Definition 3 Consider a redistribution with parameters r, s, P , and Q, and assume that
1. Let length(p; q) be the length of the message sent by processor p to processor q to redistribute a
single slice vector X of size
As we said earlier, the communication pattern repeats for each slice, and the value reported in
the communication grid tables of Section 2 are for a single slice; that is, they are equal to length(p; q).
are interesting because they represent homogeneous communications: all processor pairs in
a given class exchange a message of same length.
Proposition 2 Assume that Qs) be the length of the vector X
to be redistributed. Let vol(k) be the piecewise function given by Figure 1 for k 2 [1 \Gamma
(recall that if (p; q) 2 class(k) where
sends no message to q).
vol(k
s
volr

Figure

1: The piecewise linear function vol.
Proof We simply count the number of solutions to the redistribution equation pr
easily derive the piecewise linear vol function
represented in Figure 1.
We now know how to build the communication tables in Section 2. We still have to derive a
schedule, that is, a way to organize the communications as efficiently as possible.
4.3 Communication Schedule
4.3.1 Communication Model
According to the previous discussion, we concentrate on schedules that are composed of several
successive steps. At each step, each sender should send no more than one message; symmetrically,
each receiver should receive no more than one message. We give a formal definition of a schedule
as follows.
Definition 4 Consider a redistribution with parameters r, s, P , and Q.
ffl The communication grid is a P \Theta Q table with a nonzero entry length(p; q) in position
(p; q) if and only if p has to send a message to q.
ffl A communication step is a collection of pairs
t, and length(p t.
A communication step is complete if senders or all receivers are
active) and is incomplete otherwise. The cost of a communication step is the maximum value
of its entries, in other words, maxflength(p
ffl A schedule is a succession of communication steps such that each nonzero entry in the communication
grid appears in one and only one of the steps. The cost of a schedule may be
evaluated in two ways:
1. the number of steps NS, which is simply the number of communication steps in the
schedule; or
2. the total cost TC, which is the sum of the cost of each communication step (as defined
above).
The communication grid, as illustrated in the tables of Section 2, summarizes the length of the
required communications for a single slice vector, that is, a vector of size Qs). The
motivation for evaluating schedules via their number of steps or via their total cost is as follows:
ffl The number of steps NS is the number of synchronizations required to implement the sched-
ule. If we roughly estimate each communication step involving all processors (a permutation)
as a measure unit, the number of steps is the good evaluation of the cost of the redistribution.
ffl We may try to be more precise. At each step, several messages of different lengths are
exchanged. The duration of a step is likely to be related to the longest length of these
messages. A simple model would state that the cost of a step is ff
where ff is a start-up time and - the inverse of the bandwidth on a physical communication
link. Although this expression does not take hot spots and link contentions into account, it
has proven useful on a variety of machines [4, 6]. The cost of a redistribution, according to
this formula, is the affine expression
ff \Theta NS
with motivates our interest in both the number of steps and the total cost.
4.3.2 A Simple Case
There is a very simple characterization of processor pairs in each class, in the special case where r
and Q, as well as s and P , are relatively prime.
Proposition 3 Assume that
respectively denote the inverses of s and r modulo g).
Proof relatively prime with Qs, hence with g. Therefore
the inverse of r modulo g is well defined (and can be computed by using the extended Euclid algorithm
applied to r and g). Similarly, the inverse of s modulo g is well defined, too. The condition
easily translates into the conditions of the proposition.
In this simple case, we have a very nice solution to our scheduling problem. Assume first that
1. Then we simply schedule communications class by class. Each class is composed
of PQ
processor pairs that are equally distributed on each row and column of the communication
grid: in each class, there are exactly Q
sending processors per row, and P
receiving processors per
column. This is a direct consequence of Proposition 3. Note that g does divide P and Q: under
the hypothesis gcd(r;
To schedule a class, we want each processor
g, to send
a message to each processor
(or equivalently, if we look at the receiving side). In other words, the
processor in position p 0 within each block of g elements must send a message to the processor
in position q 0 within each block of g elements. This can be done in max(P;Q)
complete steps of
messages. For instance, if there are five blocks of senders three blocks
of receivers blocks of senders send messages to 3 blocks of
receivers. We can use any algorithm for generating the block permutation; the ordering of the
communications between blocks is irrelevant.
If we have an all-to-all communication scheme, as illustrated in Example 2, but
our scheduling by classes leads to an algorithm where all messages have the same length at a given
step. If 1. In this case we simply regroup classes
that are equivalent modulo g and proceed as before.
We summarize the discussion by the following result
Proposition 4 Assume that scheduling each
class successively leads to an optimal communication scheme, in terms of both the number of steps
and the total cost.
Proof Assume without loss of generality that P - Q. According to the previous discussion, if
(the number of classes) times P
(the number of steps for each class)
communication steps. At each step we schedule messages of the same class k, hence of same length
vol(k). If times P
communication steps, each composed of messages of the
same length (namely,
processing a given class k 2 [0;
Remark 1 Walker and Otto [21] deal with a redistribution with We have
shown that going from r to Kr can be simplified to going from
the technique described in this section enables us to retrieve the results of [21].
4.4 The General Case
When gcd(s; P entries of the communication grid may not be evenly distributed on the
rows (senders). Similarly, when entries of the communication grid may not be
evenly distributed on the columns (receivers).
Back to Example 3
We have 5. We see in Table 7 that some rows of the communication
grid have 5 nonzero entries (messages), while other rows have 10. Similarly,
hence r 3. Some columns of the communication grid have 6 nonzero entries, while other columns
have 10.
Our first goal is to determine the maximum number of nonzero entries in a row or a column of
the communication grid. We start by analyzing the distribution of each class.
, and in any class class(k), k 2 [0; 1], the processors pairs are
distributed as follows:
ffl There are P 0
entries per column in Q 0 columns of the grid, and none in the remaining columns.
ffl There are Q 0
entries per row in P 0 rows of the grid, and none in the remaining rows.
Proof First let us check that
Since r" is relatively prime with Q 0 (by definition of r 0 ) and with s" (because
have
There are PQ
elements per class. Since all classes are obtained by a translation of class(0),
we can restrict ourselves to discussing the distribution of elements in this class. The formula
in Lemma 1 states that
r
mod
. But
-s mod P can take only those values that are multiple of s 0 and -r mod Q can take only those
values that are multiple of r 0 , hence the result. To check the total number of elements, note that
Let us illustrate Lemma 3 with one of our motivating examples.
Back to Example 3
Elements of each class should be located on P 0
columns of the
processor grid. Let us check class(1) for instance. Indeed we have the following.
Lemma 3 shows that we cannot use a schedule based on classes: considering each class separately
would lead to incomplete communication steps. Rather, we should build up communication steps
by mixing elements of several classes, in order to use all available processors. The maximum number
of elements in a row or column of the communication grid is an obvious lower bound for the number
of steps of any schedule, because each processor cannot send (or receive) more than one message
at any communication step.
Proposition 5 Assume that (otherwise the communication
grid is full). If we use the notation of Lemma 3,
1. the maximum number mR of elements in a row of the communication grid is
d
and
2. the maximum number mC of elements in a column of the communication grid is
d
e:
Proof According to Lemma 1, two elements of class(k) and class(k
are on the same row of the
communication grid if -s in the interval [0; PQ
Necessarily, s 0 , which divides P and
is relatively prime with u. A fortiori s 0 is relatively prime with u. Therefore s 0 divides
share the same rows of the processor grid if they are congruent modulo s 0 . This induces
a partition on classes. Since there are exactly Q 0
elements per row in each class, and since the
number of classes congruent to the same value modulo s 0 is either b r+s\Gamma1
c or d r+s\Gamma1
e, we deduce
the value of mR . The value of mC is obtained similarly.
It turns out that the lower bound for the number of steps given by Lemma 5 can indeed be
achieved.
Theorem 1 Assume that (otherwise the communication grid
is full), and use the notation of Lemma 3 and Lemma 5. The optimal number of steps NS opt for
any schedule is
Proof We already know that the number of steps NS of any schedule is greater than or equal to
g. We give a constructive proof that this bound is tight: we derive a schedule whose
number of steps is maxfmR ; mC g. To do so, we borrow some material from graph theory. We view
the communication grid as a graph
is the set of sending processors, and
is the set of receiving processors; and
only if the entry (p; q) in the communication grid is nonzero.
G is a bipartite graph (all edges link a vertex in P to a vertex in Q). The degree of G, defined as
the maximum degree of its vertices, is g. According to K-onig's edge coloring
theorem, the edge coloring number of a bipartite graph is equal to its degree (see [7, vol. 2, p.1666]
or Berge [2, p. 238]). This means that the edges of a bipartite graph can be partitioned in d G
disjoint edge matchings. A constructive proof is as follows: repeatedly extract from E a maximum
matching that saturates all maximum degree nodes. At each iteration, the existence of such a
maximum matching is guaranteed (see Berge [2, p. 130]). To define the schedule, we simply let the
matchings at each iteration represent the communication steps.
Remark 2 The proof of Theorem 1 gives a bound for the complexity of determining the optimal
number of steps. The best known maximum matching algorithm for bipartite graphs is due to
Hopcroft and Karp [9] and has cost O(jV j 5
there are at most max(P; Q) iterations to
construct the schedule, we have a procedure in O((jP j
2 to construct a schedule whose
number of steps is minimal.
4.5 Schedule Implementation
Our goal is twofold when designing a schedule:
ffl minimize the number of steps of the schedule, and
ffl minimize the total cost of the schedule.
We have already explained how to view the communication grid as a bipartite graph E).
More accurately, we view it as an edge-weighted bipartite graph: the edge of each edge (p; q) is the
length length(p; q) of the message sent by processor p to processor q.
We adopt the following two strategies:
stepwise If we specify the number of steps, we have to choose at each iteration a maximum
matching that saturates all nodes of maximum degree. Since we are free to select any of such
matchings, a natural idea is to select among all such matchings one of maximum weight (the
weight of a matching is defined as the sum of the weight of its edges).
greedy If we specify the total cost, we can adopt a greedy heuristic that selects a maximum
weighted matching at each step. We might end up with a schedule having more than NS opt
steps but whose total cost is less.
To implement both approaches, we rely on a linear programming framework (see [7, chapter
30]). Let A be the jV j \Theta jEj incidence matrix of G, where
ae 1 if edge j is incident to vertex i
Since G is bipartite, A is totally unimodular (each square submatrix of A has determinant 0, 1 or
\Gamma1). The matching polytope of G is the set of all vectors x 2 Q jEj such that
ae
(intuitively, is selected in the matching). Because the polyhedron determined
by Equation 7 is integral, we can rewrite it as the set of all vectors x 2 Q jEj such that
To find a maximum weighted matching, we look for x such that
where c 2 N jEj is the weight vector.
If we choose the greedy strategy, we simply repeat the search for a maximum weighted matching
until all communications are done. If we choose the stepwise strategy, we have to ensure that, at
each iteration, all vertices of maximum degree are saturated. This task is not difficult: for each
vertex v of maximum degree in position i, we replace the constraint (Ax)
translates into Y t is the number of maximum degree vertices and Y 2 f0; 1g jV j
whose entry in position i is 1 iff the ith vertex is of maximum degree. We note that in either case
we have a polynomial method. Because the matching polyhedron is integral, we solve a rational
linear problem but are guaranteed to find integer solutions.
To see the fact that the greedy strategy can be better than the stepwise strategy in terms of
total cost, consider the following example.
Example 5
Consider a redistribution problem with 3. The communication grid
is given in Table 14. The stepwise strategy is illustrated in Table 15: the number of steps is equal
to 10, which is optimal, but the total cost is 20 (see Table 16). The greedy strategy requires more
steps, namely, 12 (see Table 17), but its total cost is only (see Table 18).

Table

14: Communication grid for Message lengths are indicated
for a vector X of size
of msg.
Nbr of msg.
4.5.1 Comparison with Walker and Otto's Strategy
Walker and Otto [21] deal with a redistribution where We know that going
from r to Kr can be simplified to going from we apply the
results of Section 4.3.2 (see Remark 1). In the general case (s are evenly
distributed among the columns of the communication grid (because r 1), but not necessarily
among the rows. However, all rows have the same total number of nonzero elements because s 0
divides In other words, the bipartite graph is regular. And since
maximum matching is a perfect matching.
Because messages have the same length: length(p;
(p; q) in the communication grid. As a consequence, the stepwise strategy will lead to an optimal
schedule, in terms of both the number of steps and the total cost. Note that NS opt = K under
the hypotheses of Walker and Otto: using the notation of Lemma 5, we have
We have
d
s
Note that the same result applies when Because the graph is regular and all
entries in the communication grid are equal, we have the following theorem, which extends Walker
and Otto main result [21].

Table

15: Communication steps (stepwise strategy) for
Stepwise strategy for

Table

Communication costs (stepwise strategy) for
Stepwise strategy for
Step a b c d e f g h i j Total
Cost
Proposition 6 Consider a redistribution problem with arbitrary P , Q and s). The
schedule generated by the stepwise strategy is optimal, in terms of both the number of steps and the
total cost.
The strategy presented in this article makes it possible to directly handle a redistribution from
an arbitrary CYCLIC(r) to an arbitrary CYCLIC(s). In contrast, the strategy advocated by Walker
and Otto requires two redistributions: one from CYCLIC(r) to CYCLIC(lcm(r,s)) and a second
one from CYCLIC(lcm(r,s)) to CYCLIC(s).
5 MPI Experiments
This section presents results for runs on the Intel Paragon for the redistribution algorithm described
in Section 4.

Table

17: Communication steps (greedy strategy) for
Greedy strategy for

Table

Communication costs (greedy strategy) for
Greedy strategy for
Step a b c d e f g h i j k l Total
Cost
5.1 Description
Experiments have been executed on the Intel Paragon XP/S 5 computer with a C program calling
routines from the MPI library. MPI is chosen for portability and reusability reasons. Schedules
are composed of steps, and each step generates at most one send and/or one receive per processor.
Hence we used only one-to-one communication primitives from MPI.
Our main objective was a comparison of our new scheduling strategy against the current re-distribution
algorithm of ScaLAPACK [15], namely, the "caterpillar" algorithm that was briefly
summarized in Section 3.2. To run our scheduling algorithm, we proceed as follows:
1. Compute schedule steps using the results of Section 4.
2. Pack all the communication buffers.
3. Carry out barrier synchronization.
4. Start the timer.
5. Execute communications using our redistribution algorithm (resp. the caterpillar algorithm).
6. Stop the timer.
7. Unpack all buffers.
The maximum of the timers is taken over all processors. We emphasize that we do not take the
cost of message generation into account: we compare communication costs only.
Instead of the caterpillar algorithm, we could have used the MPI ALLTOALLV communication
primitive. It turns out that the caterpillar algorithm leads to better performance than the MPI ALLTOALLV
for all our experiments (the difference is roughly 20% for short vectors and 5% for long vectors).
We use the same physical processors for the input and the output processor grid. Results are
not very sensitive to having the same grid or disjoint grids for senders and receivers.
5.2 Results
Three experiments are presented below. The first two experiments use the schedule presented in
Section 4.3.2, which is optimal in terms of both the number of steps NS and the total cost TC.
The third experiment uses the schedule presented in Section 4.4, which is optimal only in terms of
NS.
Back to Example 1
The first experiment corresponds to Example 1, with 5. The
redistribution schedule requires 7 steps (see Table 3). Since all messages have same length, the
theoretical improvement over the caterpillar algorithm, which as 16 steps, is 7=16 - 0:44. Figure 2
shows that there is a significant difference between the two execution times. The theoretical ratio
is obtained for very small vectors (e.g., of size 1200 double-precision reals). This result is not
surprising because start-up times dominate the cost for small vectors. For larger vectors the ratio
varies between 0:56 and 0:64. This is due to contention problems: our scheduler needs only 7 step,
but each step generates 16 communications, whereas each of the 16 steps of the caterpillar algorithm
generates fewer communications (between 6 and 8 per step), thereby generating less contention.
Back to Example 2
The second experiment corresponds to Example 2, with
Our redistribution schedule requires 16 steps, and its total cost is 6). The
caterpillar algorithm requires 16 steps, too, but at each step at least one processor sends a message
of length (proportional to) 7, hence a total cost of 112. The theoretical gain 77=112 - 0:69 is to be
expected for very long vectors only (because of start-up times). We do not obtain anything better
than 0:86, because of contentions. Experiments on an IBM SP2 or on a Network of Workstations
would most likely lead to more favorable ratios.
Back to Example 4
The third experiment corresponds to Example 4, with
experiment is similar to the first one in that our redistribution schedule requires much fewer steps
than does the caterpillar (12). There are two differences, however: P 6= Q, and our algorithm
is not guaranteed to be optimal in terms of total cost. Instead of obtaining the theoretical ratio
of 4=12 - 0:33, we obtain results close to 0:6. To explain this, we need to take a closer look at
the caterpillar algorithm. As shown in Table 19, 6 of the 12 steps of the caterpillar algorithm are
indeed empty steps, and the theoretical ratio rather is 4=6 - 0:66.
Global size of redistributed vector (64-bit double precision)500015000
Microseconds
caterpillar
optimal scheduling

Figure

2: Comparing redistribution times on the Intel Paragon for

Table

19: Communication costs for with the caterpillar schedule.
Caterpillar for
Step a b c d e f g h i j k l Total
Cost
6 Conclusion
In this article, we have extended Walker and Otto's work in order to solve the general redistribution
problem, that is, moving from a CYCLIC(r) distribution on a P -processor grid to a CYCLIC(s)
distribution on a Q-processor grid. For any values of the redistribution parameters P , Q, r, and s,
we have constructed a schedule whose number of steps is optimal. Such a schedule has been shown
optimal in terms of total cost for some particular instances of the redistribution problem (that
include Walker and Otto's work). Future work will be devoted to finding a schedule that is optimal
in terms of both the number of steps and the total cost for arbitrary values of the redistribution
problem. Since this problem seems very difficult (it may prove NP-complete), another perspective
is to further explore the use of heuristics like the greedy algorithm that we have introduced, and
to assess their performances.
We have run a few experiments, and these generated optimistic results. One of the next releases
of the ScaLAPACK library may well include the redistribution algorithm presented in this article.
Global size of redistributed vector (64-bit double precision)40008000Microseconds
caterpillar
optimal scheduling

Figure

3: Time measurement for caterpillar and greedy schedule for different vector sizes, redistributed
from



--R

A linear algebra framework for static HPF code distribution.
Graphes et hypergraphes.
Generating local addresses and communication sets for data-parallel programs
A portable linear algebra library for distributed memory computers - design issues and performance
Software libraries for linear algebra computations on high performance computers.
Matrix computations.
Handbook of combinatorics.
Compiling array expressions for efficient execution on distributed-memory machines

Processor mapping techniques towards efficient data redistribution.
Efficient address generation for block-cyclic distributions
A linear-time algorithm for computing the memory access sequence in data-parallel programs
Steele Jr.
Algorithmic redistribution methods for block cyclic decompositions.
Efficient block-cyclic data redistribution
MPI the complete reference.
Generating communication for array state- ments: design
Fast address sequence generation for data-parallel programs using integer lattices
An implementation framework for HPF distributed arrays on message-passing parallel computer systems
Redistribution of block-cyclic data distributions using MPI
Redistribution of block-cyclic data distributions using MPI
Runtime performance of parallel array assignment: an empirical study.
--TR

--CTR
Prashanth B. Bhat , Viktor K. Prasanna , C. S. Raghavendra, Block-cyclic redistribution over heterogeneous networks, Cluster Computing, v.3 n.1, p.25-34, 2000
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
Ching-Hsien Hsu , Shih-Chang Chen , Chao-Yang Lan, Scheduling contention-free irregular redistributions in parallelizing compilers, The Journal of Supercomputing, v.40 n.3, p.229-247, June      2007
Hyun-Gyoo Yook , Myong-Soon Park, Scheduling GEN_BLOCK Array Redistribution, The Journal of Supercomputing, v.22 n.3, p.251-267, July 2002
Ching-Hsien Hsu, Sparse Matrix Block-Cyclic Realignment on Distributed Memory Machines, The Journal of Supercomputing, v.33 n.3, p.175-196, September 2005
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
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
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
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
Saeri Lee , Hyun-Gyoo Yook , Mi-Soo Koo , Myong-Soon Park, Processor reordering algorithms toward efficient GEN_BLOCK redistribution, Proceedings of the 2001 ACM symposium on Applied computing, p.539-543, March 2001, Las Vegas, Nevada, United States
Ching-Hsien Hsu , Kun-Ming Yu, A Compressed Diagonals Remapping Technique for Dynamic Data Redistribution on Banded Sparse Matrix, The Journal of Supercomputing, v.29 n.2, p.125-143, August 2004
Emmanuel Jeannot , Frdric Wagner, Scheduling Messages For Data Redistribution: An Experimental Study, International Journal of High Performance Computing Applications, v.20 n.4, p.443-454, November  2006
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
Antoine P. Petitet , Jack J. Dongarra, Algorithmic Redistribution Methods for Block-Cyclic Decompositions, IEEE Transactions on Parallel and Distributed Systems, v.10 n.12, p.1201-1216, December 1999
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
block-cyclic distribution;MPI;distributed arrays;scheduling;HPF;redistribution