Processor Mapping Techniques Toward Efficient Data Redistribution.
AbstractRun-time data redistribution can enhance algorithm performance in distributed-memory machines. Explicit redistribution of data can be performed between algorithm phases when a different data decomposition is expected to deliver increased performance for a subsequent phase of computation. Redistribution, however, represents increased program overhead as algorithm computation is discontinued while data are exchanged among processor memories. In this paper, we present a technique that minimizes the amount of data exchange for BLOCK to CYCLIC(c) (or vice-versa) redistributions of arbitrary number of dimensions. Preserving the semantics of the target (destination) distribution pattern, the technique manipulates the data to logical processor mapping of the target pattern. When implemented on an IBM SP, the mapping technique demonstrates redistribution performance improvements of approximately 40% over traditional data to processor mapping. Relative to the traditional mapping technique, the proposed method affords greater flexibility in specifying precisely which data elements are redistributed and which elements remain on-processor.
Introduction
In an effort to standardize data-parallel Fortran programming for distributed-memory machines,
the High Performance Fortran Forum, composed of over forty academic, industrial, and governmental
agencies, has proposed HPF (High Performance Fortran) [1]. Many of the concepts originally
proposed in Fortran D [2], Vienna Fortran [3], and other data-parallel Fortran languages have been
incorporated in HPF. A fundamental component of HPF is the specification of the distribution
and alignment of data arrays through compiler directives. Due to the non-uniform memory access
times characteristic of distributed-memory machines, determining an appropriate data decomposition
is critical to the performance of data-parallel programs on these machines. Data distribution
deals with how data arrays should be distributed among processor memories, while data alignment
specifies the collocation of data arrays. The goal of data decomposition is to maximize system
performance by balancing the computational load among the processors and by minimizing remote
memory accesses (or communication messages).
A data distribution that is well-suited for one phase of an algorithm may not be good, in terms of
performance, for a subsequent phase; therefore, HPF supports explicit run-time data redistribution.
Redistribution may also occur (implicitly) at subprogram boundaries or as the result of other run-time
operations, e.g., data realignment. The use of data redistribution represents a performance
tradeoff between the expected higher efficiency of a new distribution for subsequent computation
and the communication cost of redistributing the data among processor memories. Consequently,
minimizing the execution time of data redistribution has obvious merit. Reducing the amount of
data exchanged among processor memories is one possible optimization toward reducing overall
redistribution execution time; this is the subject of this paper.
We present a technique that minimizes the amount of data exchanged among processor memories
for BLOCK to CYCLIC(c) (or vice-versa) redistributions of arbitrary number of dimensions.
Preserving the semantics of the target (destination) distribution pattern, the technique manipulates
the data to logical processor mapping of the target pattern. For clearer presentation of the
mapping technique, we view the data as being static and we manipulate the processor mapping
to the data. The implementation of the technique in a redistribution operation would specify the
mapping of data to processors. Since the mapping technique works within the realm of logical
processors, it is architecture-independent and thus could be incorporated in different redistribution
implementations for various distributed-memory architectures.
Section 2 provides a summary of data redistribution issues and related work. Section 3 presents
the mapping technique applied to one-dimensional data. We prove that the mapping technique
achieves minimal data movement. Section 4 shows the natural extension of the technique to m-dimensional
data. In Section 5, we discuss the impact of using the technique on the programmer
and compiler, respectively. Additionally, we compare the data redistribution execution time performance
of the proposed mapping technique to that of traditional data-processor mappings. Section 6
concludes the paper.
2 Data Redistribution
Many researchers have espoused the utility of incorporating a redistribution capability into data-parallel
languages. The Kali language [4] was one of the first to incorporate run-time data re-distribution
mechanisms. DINO [5] addresses the implicit redistribution of data at subprogram
boundaries. Hall et al. [6] discuss global optimizations that can be employed to a set of redistribution
calls in a Fortran D program. The Hypertasking compiler [7] for data-parallel C programs
incorporated a run-time redistribution facility. Chapman et al. [8] introduce Vienna Fortran's dynamic
data distribution capability and discuss the high-level implementation of it in the Vienna
Fortran Engine (VFE).

Figure

presents a segment of HPF code illustrating the use of data redistribution in HPF.
array of real numbers, A, is initially distributed onto a three-dimensional processor
configuration, P, with distribution patterns *, BLOCK, and CYCLIC applied to the dimensions,
respectively. P contains forty processors and each processor owns 20\Theta12\Theta10= data elements.
Following some amount of computation, A is redistributed with a new set of patterns, CYCLIC,
CYCLIC, BLOCK, onto a different shape logical processor configuration, Q. Figure 2 illustrates the
initial distribution of A (left) and its subsequent redistribution (right). The shaded portions of the
figure depict the data elements of A owned by processor (0,0,0). Whereas (0,0,0) owned data in
globally contiguous locations initially, it owns data in globally non-contiguous locations following
redistribution. Note that processor configuration Q also consists of forty processors; however, P
and Q vary in shape. The example illustrates one redistribution possibility; many more distinct
combinations of source and destination distribution patterns are possible. HPF requires, however,
that the data, processor, and distribution pattern declarations are of equal dimensionality, e.g.,
in Fig. 1, the data, processor, and pattern declarations are all three-dimensional. HPF does not
require that the source and target processor configurations have equal size.
Henceforth, we denote the initial (source) distribution pattern(s) of a program as D s and the
destination (target ) distribution pattern(s) as D t . Similarly, we shall refer to the source and target
processor configurations as P s and P t , respectively. Note that D t and P t are embedded in the
primitive in Fig. 1.
REAL,
. (computation)
. (computation)

Figure

1. Example of !HPF$

Figure

2. Redistribution from (*,BLOCK,CYCLIC) to (CYCLIC,CYCLIC,BLOCK)
The previous example illustrates that data redistribution results in changing the mapping of
data to processors, thus necessitating data exchange among the processors. From the perspective of
the sending processors, the data exchange is viewed as the simultaneous scattering of data elements
from P s to P t , i.e., each processor in P s performs a one-to-many send operation with different data
for each recipient in P t . Alternately, from the perspective of receiving processors, data exchange
is viewed as the simultaneous gathering of data elements to P t from P s , i.e., each processor in
performs a many-to-one receive operation with distinct data from each sender in P s . Figure 3
illustrates the communication pattern when jP s each processor participates
in all scatter and gather operations, then the data exchange is viewed as all-to-all personalized
communication [9]. In order to perform data redistribution between D s and D t , a processor must
determine the identity of the processors from which it is to receive data as well as the identity
of processors to which it must send data. Once these sets are computed, processors exchange
their data. Recall that we have defined redistribution between logical processors; therefore, the
logical to physical processor mapping dictates the actual data movement among the memories of
the machine. For example, logical processors mapped to the same physical node would obviously
not require message-passing to exchange data.
s

Figure

3. Redistribution communication pattern
Several research efforts have focused on efficient methods for determining the send and receive
processor sets for redistribution. Gupta et al. [10] derive closed form expressions for these
communication sets based on Fortran D's (BLOCK), (CYCLIC), and (BLOCK-CYCLIC) distribution
patterns. In this approach, global array (or template) indices combined with knowledge of D s and
D t are used to compute the send and receive sets. An alternative approach is for each node to
scan its local data array once, determine the destination processor for each element and place the
element in a message packet bound for that processor [11]. One-dimensional data redistribution is
performed by distinct algorithms for different combinations of distribution patterns for D s and D t .
Multi-dimensional redistributions are implemented as a series of (sequential) one-dimensional redis-
tributions. Stichnoth et al. [12] propose methods for computing ownership sets for array assignment
statements. Due to the similarity of determining send and receive sets, they advocate computing
these together on the sending processor and communicating the information together with the data
to a receiver. While this approach is chiefly intended for communicating right-hand side operands
of array assignment statements, it can be incorporated into data redistribution. PITFALLS [13] is
a mathematical representation for regular distributions that facilitates determining the processor
sets for data redistribution. PITFALLS robustly handles arbitrary source and target processor
configurations and arbitrary number of data array dimensions. PITFALLS is being developed for
inclusion in the PARADIGM [14] compiler project at the University of Illinois.
The research presented in [10, 11, 12, 13] focus on the efficiency of computing send/receive
processor sets rather than on the efficiency of the actual data exchange portion of redistribution.
We have found that the latter operation can be several orders of magnitude more costly, in terms of
execution time than send and receive set determination [15]. Data exchange on distributed-memory
machines can be performed with either point-to-point or collective communication message-passing
primitives. Techniques for efficient multiple scatter and gather operations are presented in [16].
McKinley et al. [17] survey issues regarding all-to-all communication in wormhole-routed machines.
The efficiency of the simultaneous redistribution of data among physical processors is affected
by the topology, routing, and switching mechanisms of the underlying machine. A technique for
communication-efficient data redistribution which addresses message contention for certain topologies
is presented in [18]. The authors propose a data redistribution communication cost model
which parameterizes the number of messages and their sizes. Network contention is modeled by
expressing the communication as a sequence of permutations which may be executed in a fixed
number of (contention-free) steps. Multi-phase redistribution is defined as redistributing data to
intermediate distribution patterns, eventually arriving at the destination distribution. The model is
used in conjunction with multi-phase redistribution to show that lower overall cost can be achieved
as compared to single-phase redistribution. Reshaping perfect power-of-two sized arrays on hypercubes
is discussed in [19].
The earliest work on optimizing data redistribution through minimization of data exchange between
regular HPF distribution patterns is presented in [20]. A related redistribution optimization
strategy was proposed by Wakatani and Wolfe [21]; they explore logical to physical processor mapping
in redistribution to reduce communication overhead. Their technique assumes an underlying
torus topology and maps the data in such a way that communicating processors are partitioned
into non-overlapping sets. Thus, by keeping communication local to a group, message contention
on the physical network is reduced. The drawback of this approach is that the logical to physical
data mapping is based on "local" information. In other words, the technique imparts a mapping
based solely on what is best to optimize redistribution. However, if redistribution is part of a larger
data-parallel program, then the logical to physical data mapping must remain consistent through-out
the execution of the program. If the logical to physical processor mapping is determined by
the redistribution operation, it may not be the best mapping for overall performance of the entire
application. We assert that the compiler, privy to global information, ought to determine the logical
to physical processor mapping. It is possible, however, to manipulate the data element/logical
processor mapping in the target, i.e., the mapping of P t on D t , so long as the semantics of the
target distribution pattern are not violated. This is the topic of the remainder of the paper.
One-Dimensional Logical Processor Mapping
We begin by illustrating the utility of the proposed mapping technique for one-dimensional data.

Figure

4 illustrates an initial BLOCK distribution of a sixteen element data array, A, onto eight
logical processors and a subsequent redistribution of the array using the CYCLIC pattern. The
mapping of the initial distribution of data onto the physical nodes of the machine is established
at program initialization; see arrow labeled (1). Subsequent redistribution among processors must
retain a consistent logical to physical processor mapping; see arrow labeled (2). Logical processor
IDs (lpids) are in bold italics and are superimposed over the data. Each processor 1 owns two
contiguous elements under BLOCK, but two non-contiguous elements, with a stride of p, the number
of processors, under CYCLIC. The lpids are mapped in increasing numerical order as specified in
[1]. We claim that this is an unnecessary restriction as any permutation of the lpids, 0.7, can
conform to the semantics of the CYCLIC pattern since data distribution to processors in HPF does
not require a specific "ordering" of processors. CYCLIC requires only that the global data elements
owned by a processor have global indices that are separated by a stride of p.

Figure

5 illustrates the benefit of permuting the lpids when mapping them to data elements.
Using the same sixteen element array of Fig. 4, we show two alternatives for redistributing the
array cyclically. Choice 1 shows the conventional cyclic mapping of lpids to data. This results in
only two of sixteen data elements (marked with filled rectangles) remaining on the same processor
following redistribution. We call this the number of data hits among all processors. Choice 2 shows
an alternative cyclic mapping with the lpids permuted, 0,4,1,5,2,6,3,7, which results in a total
of eight data elements, one per processor, remaining on their original memories. This eliminates
the exchange of six data elements among processors. Another advantage is that processors 1,.,6
must send data to two processors when using Choice 1, but only one processor each when using
Choice 2, thus reducing the number of destinations. Each of these factors reduces interprocessor
communication overhead. The reduction in redistribution cost for the example in Fig. 5 is small
given the size of the example. If we extend A to be sixteen million data elements with the same
permutation of lpids, we eliminate the exchange of six million data elements across processors. 2
3.1 Processor Mapping Technique
To consistently minimize the size of data transfer for arbitrary data block and processor set sizes, we
develop a systematic method for determining a permutation of lpids to map to the data. The tech-
1 Henceforth logical processor unless otherwise stated.
2 Assuming the number of processors is kept the same, the block size in BLOCK is two million, and the block size in
CYCLIC(c) is one million.
physical nodes141012145715141012145715
logical processor IDs
ONTO P(8)
ONTO P(8)
Initial distribution of data
to physical nodes;
performed by compiler135713502466
Redistribution of
data performed
at run-time
bold italics
in
(1) (2)

Figure

4. Data distribution and redistribution onto physical nodes
nique ensures that each processor retains the maximum amount of data possible while conforming
to the semantics of the source and target distribution patterns, D s and D t .
We establish the upper bound on the ratio of the amount of data that can be retained on p
processors to the total number of data elements, n. We present a function for determining an lpid
to data mapping for redistribution from BLOCK to CYCLIC(c)
3 that achieves the upper bound. We
make the following assumptions:
1. Let p be the number of processors numbered 0::p \Gamma 1, and n be the total number of data
elements, numbered 0::n \Gamma 1, distributed over p. We assume each processor owns b elements,
thus
2. We consider redistribution between BLOCK and CYCLIC(c)patterns; the BLOCK(b) pattern,
where b is a variable, is not considered; by assumption 1. For CYCLIC(c), we assume
that c divides b, i.e., for an integer z.
3 Redistribution is symmetric in terms the amount of data movement among processors, i.e., redistribution from
BLOCK to CYCLIC(c) or redistribution from CYCLIC(c) to BLOCK results in an equal amount of data movement.
Direction
of redistribution
Choice 1 Choice 2

Figure

5. Logical processor to data mapping alternatives
3. If the data is initially distributed among p processors, then we assume that the data is
redistributed among p processors.
r as the number of data elements of the global array that remain (data hits)
on their original processors following redistribution between BLOCK and CYCLIC(c). Define HitRatio
as r : n and MaxHitRatio as the upper bound on HitRatio.
and c be the block sizes in the BLOCK and CYCLIC(c) patterns, respectively. If
z is an integer, then
MaxHitRatio.
is an integer. For every cycle of cp data elements, each
maps to c contiguous data elements with CYCLIC(c). Since are
complete cycles of lpids that map to one complete data block owned by lpid j under the BLOCK
pattern. Processor lpid j will map to exactly ic of the elements, i.e., there are ic data hits. For p
processors, the number of data hits is
cp ecp. HitRatio is d b
Case 2: is an integer. Since b ! icp, there cannot be i complete
cycles of lpids mapped to lpid 0
original block of data under BLOCK. Thus, the number of hits can
be no greater than i for each lpid; consequently, the number of hits across all processors can be no
greater than icp. The remainder of the proof follows as in Case 1. 2
MaxHitRatio is achieved with any permutation of lpids when z is an integer multiple of the
number of processors, i.e., when z = ip. However, our goal is to achieve the upper bound for
all values z where (i ip. In order to satisfy this aim, we must consider different
permutations of the lpids to maximize the number of data hits. Figure 5 demonstrates that not all
permutations of lpids yield MaxHitRatio. Next, using the semantics of D t , we define a function for
determining a permutation of lpids to map to the data array.
3.2 Mapping Function
Define a p-tuple, (q place holders. Let f be a function that maps
lpid i to place holder q j for 0 - An assignment of each lpid to a place holder specifies
a permutation of the lpids and represents a mapping of lpids to data elements for the CYCLIC(c)
distribution pattern. There are p! possible permutations for p processors and it may be the case
that many of the permutations yield a ratio of MaxHitRatio. However, exhaustively testing each
permutation to determine whether it produces the ratio would be impractical since this would
require an exponential amount of computation for general p. Therefore, we present a function for
determining a permutation that achieves MaxHitRatio for b; p and c. Each lpid
maps to a unique q f(i) . Equation (1) specifies the function that maps lpid i to q f(i) .
The intuition behind the mapping function is to first view the place holders, q j , as a circular
list. The function maps lpid 0 to place holder q 0 , maps lpid 1 z places from lpid 0 , maps lpid 2 z places
from lpid 1 , and so on. In general, we map lpid i+1 , (z mod p) places from lpid i . Figure 6 illustrates
the behavior of f applied to different values of z and p. For simplicity, we choose
reduces D t to CYCLIC. Part (a) shows an example for
the case for 4. The mapping is broken into rows to better illustrate the distance
consecutive lpids. The distinction between the two examples is that
one-to-one in part (a), but f is not one-to-one in part (b); that is, in part (b), more than one lpid
maps to some locations, while no lpids map to other place holders. More formally, depending on
the values of z and p, it is possible that While f yields one permutation for part
(a), it produces six possible permutations 4 for part (b): since lpid 0 and lpid 3 map to q 0 , it turns
4 all optimal in terms of MaxHitRatio
out that we can arbitrarily map the two lpids to place holders q 0 and q 1 . The same holds true for
lpid 2 and lpid 5 to place holders q 2 and q 3 and for lpid 1 and lpid 4 to place holders q 4 and q 5 . We
shall prove this result in a later lemma.

Figure

6. Mapping lpids to place holders
3.3 Optimality of Mapping Function
Given arbitrary z and p, the gcd(z; p) determines whether f is one-to-one or not. Lemmata 2 and
3 establish this. Lemmata 4 and 5 establish that f achieves MaxHitRatio whether or not it is
one-to-one.
and z be natural numbers and z = b=c. Let gcd(z; p) be the greatest common
divisor of z and p. If gcd(z; establishes a one-to-one mapping between
place holder q In other words, if gcd(z;
Proof: Proof by contradiction. Assume gcd(z;
and choose k ? j. Recall that the mapping function, f , maps each lpid i+1 , (z mod p) places from
lpid i . Let is mapped a distance of r(z mod p) place holders from lpid j . Since
map to the same place holder, so their distance, modp,
is zero, i.e., r(z mod must be that z mod This implies that the
our assumption that
Lemma 3 Let p and z be natural numbers and z = b=c. If gcd(z;
to q f(i) for
Proof: Show that
divides z, jz p
m. mp mod arbitrary m. Thus, the second
term of the sum, (jz p
so we are left with
established two lemmas that capture the behavior of f in Equation (1) for natural
and shown the relationship of gcd(z; p) to the function f . In Fig. 6 (a),
thus f is one-to-one, while in part (b), gcd(z; maps two lpids
to place holders q Next we establish two lemmas that show f will produce permutations
that always yield MaxHitRatio.
Lemma 4 Let p and z be natural numbers and z = b=c. If gcd(z; determines a
single permutation of lpids that achieves MaxHitRatio.
Proof: Since f maps lpid i+1 z places from lpid i , each lpid will map, under CYCLIC, to the
first data element of its data block under BLOCK. Figure 7 illustrates the situation for arbitrary
lpid i . Thus, there is always at least one data hit per lpid.
Case 1: If z - p, then there are exactly c data hits per lpid. The mapping cycle begins with
ensuring c data hits. Since z - p, which is equivalent to b - cp, lpid i cannot map to another
c data elements of the b-sized data block. If it did, this would violate the semantics of a cyclic
mapping. Thus, there are exactly c hits per processor, cp hits over all processors. It follows that
Case 2: If z ? p, then there are at least c data hits per lpid as established above. Since lpid i
maps to the first element of the data block, it will also map to the (cp 1)th element as well since
z ? p, see Fig. 7. Let (integer division), then lpid i will map to elements numbered
a total of cj elements 5 . Thus, there are
cp ec
data hits per lpid and d b
cp ecpdata hits over all lpids. Again, d b
c
cp
elements
data

Figure

7. lpid i is mapped to first element of its data block
Lemma 5 Let p and z be natural numbers and z = b=c. If then the
k lpids that map to q ik under f can be remapped, in any of k! ways, to the place holders
permutations yield MaxHitRatio.
Proof: In Lemma 3, we established that if k ? 1, then k lpids, namely lpid i+j(p=k) for
to the same place holder, q f(i) . Consequently, k lpids map to the first data
element of lpid 0
data block under BLOCK.
Case 1: If z - p, then b - cp, and there are exactly c data hits per lpid. Figure 8 illustrates the
situation. If z - p, then k - z. Thus, ck - cz and b. Furthermore, the k lpids with c data
elements each can "fit" into lpid 0
b-sized data block. Each lpid that mapped to place holder q f(i)
can be remapped to one of the first ck data elements regardless of the permutation of the k lpids.
Since lpid i is in this group, there are c data hits for it. lpid i cannot appear again within the data
block since b - cp. Therefore, there are exactly c data hits for lpid i , cp =d b
cp ecp data hits total
among all p processors.
Case 2: If z ? p, then b ? cp and there are at least c data hits per lpid as established above.
For some integer m, if mcp 1)cp, then there are mc data hits for lpid i ; since all p lpids
5 Data elements are numbered 0::b \Gamma 1 for the data block owned by lpid i .
c
data
data
elements
elements

Figure

8. z - p
map at least m cycles to a b-sized data block. We claim that there are (m + 1)c data hits, even
Figure 9 illustrates the situation. There are m groups of p processors mapping
c-sized blocks to lpid 0
data block under BLOCK. We must show that lpid i maps to one of the last
elements of the data block. In other words, show ck - b \Gamma mcp. Proof by contradiction.
Assume ck There exist two integers, s, such that z = rk and
ck
c
z
z
z ?
z
Since p=k - 1, we have a contradiction. Thus, c(gcd(z; mcp. Given this result, lpid 0
c-sized block must appear within the last b \Gamma mcp elements of the data block regardless of
permutation order. Therefore we have (m data hits per lpid; (m + 1)cp for p processors. 2
cp
cp
(b - mcp) < cp
groups
elements
data

Figure

9. z ? p
Lemmata 1 through 5 prove the following result.
Theorem 1 For redistribution from BLOCK to CYCLIC(c), where b and c are the respective block
for an integer z, p is the number of processors, and is the number of global
data array elements, the logical processor mapping function in Equation (1) achieves MaxHitRatio
Multidimensional Logical Processor Mapping
This section extends the logical processor mapping technique presented in Section 3 to m-dimensional
data arrays. Specifically, we extend the technique to optimizing the logical
processor mapping when redistributing from (BLOCK, BLOCK,., BLOCK) to (CYCLIC(c 0 ),
Additionally, we demonstrate the approach for redistribution
of two-dimensional data that is (1) initially distributed in both dimensions and subsequently
redistributed in only one dimension, e.g., (BLOCK,BLOCK) to (CYCLIC, *), and (2) initially
distributed in one dimension and then redistributed in both dimensions, e.g., (BLOCK, *) to
4.1 m-dimensional redistribution
We extend the technique by applying the one-dimensional lpid mapping to each dimension of the
global data array. Let A be a m-dimensional data array with n 0 \Theta n 1 \Theta n 2 \Theta ::: \Theta nm\Gamma1 data elements.
The PROCESSORS directive in HPF declares a processor arrangement specifying the name, rank, and
extent in each dimension. Let be the processor arrangement over which A is
distributed. be the set of block sizes and cyclic
block sizes respectively for each dimension of A. We extend Equation (1) to Equation (2) to map
the rectilinear set of lpids p j to the n j data elements in the j-th dimension for
For m-dimensional data redistribution, MaxHitRatio is very similar to the ratio presented in
Section 3; it is the product of the MaxHitRatios for each of the m dimensions. We present a lemma
to substantiate this result.
Lemma 6 MaxHitRatio for a m-dimensional global array A as defined above is (d b 0
c and the mapping function in Equation (2) achieves the
upper bound.
Proof: Lemmata 1 through 5 established that d b
is the MaxHitRatio for one-dimensional
data and that the mapping function, f , achieved the upper bound. For m-dimensional
data, the product of the upper bounds in each dimension yields the maximum data hit ratio for
the m-dimensional array. The function g is a generalization of f . By applying g respectively to
each dimension, the upper bounds are achieved. 2

Figure

applied to an data matrix distributed across a 3 \Theta 4 processor
grid; lpids are in bold italics 6 . We redistribute the data matrix from (BLOCK,BLOCK)to
(CYCLIC(3),CYCLIC(2)). The lpid to data mappings for D s in both dimensions is marked Block.
The traditional cyclic mapping of lpids to data is indicated with Trad, while the optimized technique
using g is shown with Opt. The key to the right of the figure indicates data hits following
redistribution for the traditional and optimized mappings. The traditional mapping yields HitRatio
12. The mapping using g results in HitRatio d 6
reduces to 1 : 4, a three-fold increase in the number of data hits over the traditional mapping.
Theorem 1 and Lemma 6 prove the following result.
6 Subscripts in the Figure label denote the number of processors in the given dimension.
Theorem 2 For redistribution from (BLOCK, BLOCK,., BLOCK) to (CYCLIC(c 0
,., are the respective block sizes, z for an integer z i ,
is the number of processors, and n is the number of data elements in dimension
the logical processor mapping function in Equation (2) achieves
::: \Theta d b
c
O
O
O O O O
O O O O
O O
O
Block
Opt
Trad0000
mappings
Data Hits
Data Hits
data
elements
Trad
Opt

Figure

10. (BLOCK 3 ,BLOCK 4 ) to (CYCLIC 3 (3),CYCLIC 4 (2)) redistribution
4.2 Two-dimensional to one-dimensional redistribution
Redistribution of an m-dimensional array need not necessarily involve redistribution in all m dimen-
sions. For instance, a data matrix may initially be distributed (BLOCK,BLOCK) and redistributed
to (CYCLIC,*) in which only the row dimension is distributed. We extend the mapping technique
to these cases. We define a vector of Equation (3) defines a
new function that maps a Cartesian lpid to a placeholder.
Lemma 7 establishes MaxHitRatio for two-dimensional to one-dimensional redistribution. Based
on the value of gcd(z; p 0 ), Lemmata 8 and 9 establish that the mapping function h achieves Max-
HitRatio.
Lemma 7 For redistribution between (BLOCK,#) 7 and (CYCLIC(c 0 ),*), let b 0 be the block size in
the row dimension of D s and c 0 be the cyclic block size in D t .
for an n 0 \Theta n 1 data matrix.
Proof: The proof is quite similar to the proof of Lemma 1. Here, the two-dimensional
grid of processors is remapped into a vector of place holders since D t is distributed in only one
dimension. We substitute p 0 p 1 for p in Lemma 1 and the remainder of the proof follows from that
point. Thus d b 0
counts the number of hits in the row dimension. This number is then
multiplied by the block size in the column dimension, b 1 , to obtain the total number of data hits. 2
We prove that the mapping function, h, yields MaxHitRatio by first establishing the correspondence
between lpids and place holders and then showing the mapping yields the given ratio. Since
the column coordinate, s, of an lpid is not relevant to the value computed by h, all lpids with the
same row coordinate, r, map to the same place holder, q h(r) . Since are exactly
lpids for each that map to the same place holder. Thus, no greater than p 0
place holders are mapped to under h. Lemma 8 establishes that h achieves MaxHitRatio when only
lpids with the same row coordinate r map to the same place holder while Lemma 9 establishes the
result when kp 1 lpids map to the same place holder.
Lemma 8 Let z be a natural number such that exactly p 0 place
holders are mapped by h(r; s). The p 1 lpids that map to place holder q h(r;s) can be remapped in any
of ways to place holders q h(r;s) ; q h(r;s)+1 ; q h(r;s)+2 ; :::; q permutations yield
Proof: The first conjecture of the lemma follows directly from Lemma 2. The proof of
the second part of the lemma is similar to the proof of Lemma 5. Instead of
mapping to the same place holder as in Lemma 5, we have p 1 lpids mapping to the same place
7 # denotes any HPF distribution pattern
holder as established previously. The remainder of the proof follows after making this substitution.
MaxHitRatio is the same result as in Lemma 5 except that b 1 must be a factor since the number
of data elements in a row contribute to the number of data hits. 2
Lemma 9 Let z be a natural number such that place holders
are mapped by h(r; s). h(r; s) maps lpid r+j(p 0 =k);s to place holder q h(r;s) for
1. The lpids that map to place holder q h(r;s) can be remapped in any of (p 1 k)!
ways to place holders q permutations yield
Proof: The first portion of the lemma follows directly from Lemma 3. The proof of the
second part of the lemma is similar to the proofs of Lemmata 5 and 8. In the current situation,
we have lpids that map to the same place holder. The remainder of the proof follows after
making this substitution. MaxHitRatio is the same as in Lemma 8. 2

Figure

11 demonstrates the mapping function, h, applied to a 24 \Theta 16 matrix. The matrix is
originally distributed (BLOCK,BLOCK) on a 3 \Theta 2 processor grid and is redistributed (CYCLIC(2),*)
on a six processor vector. lpids are in bold italics as before. lpid r;s identifies a processor in the
Cartesian system; 1. The block size in the row dimension of
(BLOCK,BLOCK) is eight (b the cyclic block size in (CYCLIC(2),*) is two.
In Fig. 11, we do not show a "traditional" mapping since mapping from a set of Cartesian
lpids to a vector of lpids is undefined in HPF. Using h to map the lpids produces a HitRatio of
4. The distribution for columns of D s is inconsequential to the number of data
hits that can be achieved since only rows are distributed in D t . In other words, redistribution
from (BLOCK, CYCLIC(c)) to (CYCLIC,*) would result in the same number of data hits as the
redistribution of (BLOCK,BLOCK) to (CYCLIC,*). Additionally, any of the lpids with the same
row index, r, could be permuted and the same data hit ratio is achieved; e.g., lpid 0;0 and lpid 0;1 .

Figure

12 shows an example of when gcd(z; Processors lpid 0;s and lpid 2;s for
could be permuted in any of the 6! possible ways and the optimal data hit ratio would be obtained.
Lemmata 7 through 9 prove the following result.
Theorem 3 For redistribution from (BLOCK,#) to (CYCLIC(c 0 ),*), where b 0 and c 0 are the respective
block sizes in the row dimension, for an integer z, b 1 is the block size in the column
dimension, defines the grid of processors for D s , n 0 \Theta n 1 is the number of global data array
Block
data elements
Data Hits

Figure

11. (BLOCK 3 ,BLOCK 2 ) to (CYCLIC 6 (2),*) redistribution
elements the logical processor mapping function in Equation (3) achieves
4.3 One-dimensional to two-dimensional redistribution
Another possibility is to have a data matrix initially distributed in one dimension and then redistributed
in two dimensions. We derive a new mapping function, Equation (4), for redistribution
from (BLOCK,*) to (CYCLIC(c 0 ),#). Since D t specifies a two-dimensional data distribution, we
declare a two-dimensional grid of place holders, q 1. The function,
maps a processor lpid i , to a place holder q [r;s] ; thus, '(i) computes an ordered pair.
establishes MaxHitRatio for one-dimensional to two-dimensional redistribution. Based
on the value of gcd(z; p 0 ), Lemmata 11 and 12 prove that ' achieves MaxHitRatio.
(1,0)=6
(2,1)=4
(2,0)=3
(0,2)=2
(0,0)=01216200246811141822
Block
data
elements
Data Hits

Figure

12. (BLOCK 4 ,BLOCK 3 ) to (CYCLIC 12 (1),*) redistribution
redistribution between (BLOCK,*) and (CYCLIC(c 0 ),#), let b 0 be the block size in
the row dimension of D s and c 0 be the cyclic block size in D t .
for an n 0 \Theta n 1 data matrix.
Proof: The proof is quite similar to the proofs of Lemmata 1 and 7. In the single dimension
case of Lemma 1, the redistribution between BLOCK and CYCLIC(c) is considered. In the current
situation, the first dimension of both D s and D t is BLOCK and CYCLIC(c); thus, the proof of
Lemma 1 can be applied. As with Lemma 7, we must include the factor b 1 for the second
dimension. 2
Lemma 11 Let z be a natural number such that place
holders are mapped by '(i) and the mapping yields MaxHitRatio =(d b 0
Proof: The proof is similar to the proof of Lemma 4 since '(i) maps lpid i+1 z places from
thus each lpid will be mapped to the first row of its data block under the (BLOCK,*) pattern.
Since lpid i owns b 1 elements in the second dimension, this factor contributes to MaxHitRatio. 2
Lemma 12 Let z be a natural number such that
place holders are mapped by '(i). All place holders in the p 1 dimension are mapped, while
only place holders in the p 0 dimension are mapped. Exactly k lpids map to each place holder.
The k lpids that map to place holder q [r;s] can be remapped to place holders q
in any of k! ways and achieve MaxHitRatio =(d b 0
Proof: The proof is similar to the proof of Lemma 5 and Lemma 9. In the current situation,
there is a second, p 1 , processor dimension and all place holders in this dimension are mapped. The
dimension in this case is the same as the one-dimensional mapping in Lemma 5. Since lpid i
owns b 1 elements in the second dimension, this factor contributes to MaxHitRatio. 2

Figure

13 illustrates the lpid mapping function, ', applied to a 24 \Theta 24 matrix. The matrix
is initially distributed (BLOCK,*) across six processors, and redistributed (CYCLIC(2), BLOCK)
across a 3 \Theta 2 processor grid. lpids (in bold italics) are superimposed on the matrix. The data hit
ratio, using the mapping function is d 4
is an example of when gcd(z; Fig. 14 illustrates a situation where gcd(z; 2.
The latter figure demonstrates the flexibility of permuting lpids. For instance, processors lpid 0 and
lpid 2 could be permuted and the same data hit ratio would be achieved.
Lemmata prove the following result.
Theorem 4 For redistribution from (BLOCK,*) to (CYCLIC(c 0 ),#), where b 0 and c 0 are the respective
block sizes in the row dimension, for an integer z, b 1 is the block size in the column
dimension, defines the grid of processors for D s , n 0 \Theta n 1 is the number of global data array
elements the logical processor mapping function in Equation (4) achieves
5 Analysis and Performance
In this section, we discuss the possible impacts on the data-parallel programmer and the compiler,
respectively, when using the optimal mapping technique. We present the execution time benefit
Block
data
Data Hits

Figure

13. (BLOCK 6 ,*) to (CYCLIC 3 (2),BLOCK 2 ) redistribution
of the optimal mapping technique compared to the traditional mapping technique for a number of
data redistribution cases.
5.1 Effect of optimal mapping on the programmer
Permuting lpids with the optimal mapping functions in Sections 3 and 4 may incur undesired side
effects and thus may not be suitable in all redistribution instances. For instance, the programmer
may lose "neighboring data" relationships. In Fig. 5, under the traditional cyclic mapping, lpids
and 1 are neighbors 8 while under the optimized mapping, lpids 0 and 4 are neighbors. Suppose
a programmer imparts a particular logical to physical processor mapping for a given program
and utilizes this information for maintaining neighboring data relationships for physical processors.
In order to preserve these relationships, a programmer may favor the traditional processor-data
8 A processor is a neighbor if it owns data elements that are adjacent from the perspective of the global data.
data
elements
Data Hits

Figure

14. (BLOCK 12 ,*) to (CYCLIC 4 ,BLOCK 3 ) redistribution
mappings over the optimal mapping in a call to data redistribution. Figure 15 illustrates static,
i.e., not varying from one program execution to another, logical to physical processor mappings:
logical processor i always maps to physical node pi. In (a), the traditional mapping, i.e., 0,1,2,3,
preserves the neighboring processor relationships while in (b) neighboring data relationships on the
physical nodes is corrupted when using the optimal mapping, i.e., 0,2,1,3 makes p0 and p2 become
neighbors where previously p0 and p1 were neighbors.
When a compiler or run-time system uniquely determines the logical to physical processor
mappings, however, the programmer is unable to maintain neighboring data relationships on the
physical nodes. Indeed, indirect-network multicomputers, e.g., IBM SP-x, or most workstation
clusters have no concept of "neighboring nodes." Furthermore, the allocation of parallel jobs, and
thus data, may vary for distinct executions of the program since different physical processors may be
allocated to each job. Figure 16 illustrates a number of program executions where the allocation of
logical processors to physical nodes is different for each invocation. The top part of Fig.
Logical Physical13
p3
(a) Traditional
Logical Physical3
p3
(b) Optimal

Figure

15. Traditional and optimal mappings when physical node mapping is static
the traditional processor-data mapping for three distinct program executions; the bottom portion
of Fig. 16 illustrates the optimal processor-data mapping for three distinct program executions.
From the perspective of the physical nodes of the machine, the permutation of the lpids, whether
traditional or optimal, is transparent to the programmer. We argue that in these situations, the
use of the optimal mapping is always justified since neighboring data relationships on the physical
nodes cannot be maintained, or exploited, by the programmer.
Logical Physical3 p3
(b) Second execution
Logical Physical13
p3
(a) First execution
Logical Physical32
(c) Third execution
p3
Optimal
Logical Physical
p3
(a) First execution
Logical Physical
(c) Third execution
p3
Logical Physical
p3
(b) Second execution

Figure

16. Traditional and optimal mappings when physical node mapping is dynamic
Permuting lpids can also facilitate greater flexibility: the programmer may want to influence
which data elements are redistributed to other processors and which remain on-processor. Under
the traditional mapping technique, the programmer has but one choice, i.e., lpids are mapped in
increasing numerical order. With the optimized mapping technique, there are often several options
since a number of lpids may map to the same place holder; see Fig. 6(b). If the compiler supports
programmer-specification of lpid permutations, then the user has inherently greater control over
the data to processor mapping. Such flexibility may become even more significant when data
alignments are introduced. In such a situation, a number of data elements may map to some local
indices while fewer data elements map to other indices. Therefore, being able to influence which
indices are redistributed and which indices remain on-processor could enhance overall performance.
5.2 Effect of optimal mapping on the compiler
The loss of neighboring data relationships may complicate the role of the compiler in generating
SPMD node programs from the HPF source code. Let us examine a simple example. Let A be
a 16-element array that is initially distributed with BLOCK, and then redistributed CYCLIC; see
Fig. 5. Assume that the following reference pattern appears in the compiler-generated SPMD code
following the call redistributing A to CYCLIC.
Using the traditional mapping technique, the compiler generates the following communication
paradigm to obtain off-processor elements: Excluding the boundary processors, each lpid i communicates
with lpid i\Gamma1 and lpid i+1 . Under the optimal mapping technique, neighboring processor
relationships are not maintained, thus the above communication paradigm cannot be used. For
example, lpid 3 communicates with lpid 6 and lpid 7 , while lpid 4 communicates with lpid 0 and lpid 1 .
This problem can be easily overcome, however, if the compiler utilizes the place holder mapping
information determined by the optimal mapping function. Let 7 be the array
of place holders of the lpids as generated by Equation (1). Under the optimal mapping, the compiler
would specify neighboring communication for non-boundary processors as follows: for lpid i
in place holder q j , communicate with lpids in q j \Gamma1 and q j+1 . Essentially, the compiler performs a
table lookup to determine neighboring lpid relationships. The extension to boundary processors is
straightforward and is excluded from the present discussion.
5.3 Performance
We have integrated the optimal mapping technique into a data redistribution library, DaReL [15],
which is written in C using MPI-F [22]. The performance results were obtained on the IBM
SP-x at Argonne National Laboratory [23]. To assess the run-time performance of the optimal
mapping technique, we compare data redistribution execution times using the optimal technique
with redistribution execution times using the traditional mapping.

Figures

through 19 illustrate various performance comparisons of the two mapping tech-
niques. Figure 17 shows (BLOCK,*) to (CYCLIC(c),*) redistributions on 8 nodes over a range of
matrix sizes: 32-thousand to 34-million 4-byte floating point elements. The block size of the
CYCLIC(c) pattern (row dimension) was maintained at one-half the block size, b, of the BLOCK
distribution. The optimal mapping technique, applied to only the row dimension of the matrix,
demonstrates significantly lower execution times over the traditional mapping. The optimal technique
achieves the same redistribution result in roughly 60% of the time needed for redistribution
using the traditional technique. The larger the value of c with respect to b the greater the effect
of the optimized mapping technique on overall execution time because significantly more data hits
occur relative to the traditional mapping. With smaller values of c relative to b, the benefit of the
optimal technique is lessened since the relative difference in the number of data hits is reduced.
For all redistribution instances, regardless of block sizes (b and c) or global data size, we find the
optimal technique outperforms or equals the traditional mapping.

Figures

and 19 demonstrate (BLOCK,BLOCK) to (CYCLIC(c),CYCLIC(c)) redistributions on 12
(logically 4 \Theta 3) and 24 (logically 6 \Theta 4) processor configurations, respectively. Matrix sizes ranged up
to 91-million floating point numbers. In these performance plots, the mapping technique is applied
to both dimensions of the matrices. As before, the optimal mapping redistributions outperform
the traditional mapping in all cases. The block size c was maintained at one-sixth and one-eighth
of the respective block sizes in the row and column dimensions of the matrices. The execution
time advantage of the optimal mapping technique remains consistent for larger (? 24) processor
configurations as well.
The computation of the send and receive processor sets is included in all of the execution time
plots shown. Execution time attributable to these calculations represented a small fraction of the
overall total, i.e., on the order of hundreds of micro-seconds for small data sizes and on the order
of tens of milliseconds for the largest data sizes plotted. See [15] for more details.
6 Conclusion
When distinct computational phases of an algorithm perform more efficiently with different data
distribution patterns, efficient run-time redistribution can enhance overall algorithm performance.
The effective use of data redistribution in data-parallel programs is promoted by minimizing the
run-time cost of performing data exchange among the nodes of the machine. An important aspect
in reducing redistribution cost is minimizing the amount of data to be moved among processor
memories without violating the semantics of the distribution patterns.
This paper presented a technique for mapping logical processor IDs to data elements for data
redistribution. We proved that the technique maximizes the ratio between data retained locally
Traditional
Optimal
Matrix size (4-byte floats)
Time
(sec)

Figure

17. (BLOCK,*) to (CYCLIC(c),*) on 8 \Theta 1 processors
Traditional
Optimal
Matrix size (4-byte floats)
Time
(sec)

Figure

18. (BLOCK,BLOCK) to (CYCLIC(c),CYCLIC(c)) on 4 \Theta 3 processors
Traditional
Optimal
Matrix size (4-byte floats)
Time
(sec)

Figure

19. (BLOCK,BLOCK) to (CYCLIC(c),CYCLIC(c)) on 6 \Theta 4 processors
and the total amount of data exchanged among processors when performing redistributions between
BLOCK and CYCLIC(c) of arbitrary number of dimensions. The architecture-independent technique
improves data redistribution execution time performance by approximately 40% over a wide range
of data sizes. We examined the impact of the technique on the data-parallel programmer and
compiler, respectively. We believe that minimizing the amount of interprocessor data exchange is
an effective optimization for data redistribution in data-parallel programs.
More work remains on generalizing our technique to arbitrary block sizes which are not necessarily
integer multiples of the number of processors. Padding of the data array so that it becomes
an integer multiple of the number of processors is one possibility. Additionally, extending our technique
to redistribution between different size processor sets and redistribution between CYCLIC(c 1 )
and are areas of future study.

Acknowledgment

We are grateful to Argonne National Laboratory and its staff for the use of their IBM SP-x. We
also thank the anonymous referees for their constructive comments.



--R

"High Performance Fortran Language Specification (version 1.0, draft),"
"Fortran D language specification,"
A Language Specification (Version 1.1)
Programming Distributed Memory Architectures Using Kali
"The DINO parallel programming language,"
"Interprocedural compilation of Fortran D for MIMD machines,"
"Hypertasking support for dynamically redistributable and resizeable arrays on the iPSC,"
"Dynamic data distributions in
"Distributed routing algorithms for broadcasting and personalized communication in hypercubes,"
"On the generation of efficient data communications for distributed-memory machines,"
"Runtime array redistribution in HPF programs,"
"Generating communication for array statements: Design implementation, and evaluation,"
"Automatic generation of efficient array redistribution routines for distributed memory multicomputers,"
"Communication optimizations used in the PARADIGM compiler for distributed-memory multicomputers,"
"DaReL: A portable data redistribution library for distributed-memory machines,"
"Efficient algorithms for the index operation in message-passing systems,"
"A survey of collective communication in wormhole-routed massively parallel computers,"
"An approach to communication-efficient data redistribution,"
"The complexity of reshaping arrays on boolean cubes,"
"Processor mapping techniques toward efficient data redistribution,"
"Optimization of the redistribution of arrays for distributed memory multicomputers,"
"MPI on IBM SP1/SP2: Current status and future directions,"

--TR

--CTR
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
Wang , Minyi Guo , Daming Wei, A Divide-and-Conquer Algorithm for Irregular Redistribution in Parallelizing Compilers, The Journal of Supercomputing, v.29 n.2, p.157-170, August 2004
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
Frddric Desprez , Cyril Randriamaro , Jack Dongarra , Antonie Petitet , Yves Robert, Scheduling Block-Cyclic Array Redistribution, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.192-205, February 1998
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
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, Sparse Matrix Block-Cyclic Realignment on Distributed Memory Machines, The Journal of Supercomputing, v.33 n.3, p.175-196, September 2005
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
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
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
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
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
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
data redistribution;data-parallel programming;data decomposition;processor mapping;distributed-memory architectures;High Performance Fortran