A Framework for Integrating Data Alignment, Distribution, and Redistribution in Distributed Memory Multiprocessors.
AbstractParallel architectures with physically distributed memory provide a cost-effective scalability to solve many large scale scientific problems. However, these systems are very difficult to program and tune. In these systems, the choice of a good data mapping and parallelization strategy can dramatically improve the efficiency of the resulting program. In this paper, we present a framework for automatic data mapping in the context of distributed memory multiprocessor systems. The framework is based on a new approach that allows the alignment, distribution, and redistribution problems to be solved together using a single graph representation. The Communication Parallelism Graph (CPG) is the structure that holds symbolic information about the potential data movement and parallelism inherent to the whole program. The CPG is then particularized for a given problem size and target system and used to find a minimal cost path through the graph using a general purpose linear 0-1 integer programming solver. The data layout strategy generated is optimal according to our current cost and compilation models.
Introduction
The increasing availability of massively parallel computers composed of a large number
of processing nodes is far from being matched by the availability of programming models
and software tools that enable users to get high levels of performance out of these systems.
The proliferation of small and medium-size parallel systems (such as desktop multiprocessor
PCs and workstations with a few processors or systems with a modest number of
processors with shared memory) has broadened the use of parallel computing in scientific
and engineering environments in which the user does not need to consider the underlying
system characteristics to get a reasonable performance. In this case, ease of programming
and portability are the main aspects to consider and this has favored the popularity of
shared-memory programming models.
A thorough understanding of the complexities of the target parallel system is required
to scale these applications to run on large systems composed of hundreds of processors
with NUMA interconnects. Although the availability of programming models such as
High Performance Fortran [18] offers a significant step towards making these systems truly
usable, the programmer is forced to design parallelization and data mapping strategies
which are heavily dependent on the underlying system characteristics. The combination of
HPF and shared-memory paradigms, which is common when targeting the multiple levels
of parallelism offered by current systems composed of SMP nodes, does not necessarily
reduce the complexity of the problem. These strategies are designed to find a balance
between the minimization of data movement and the maximization of the exploitable
parallelism. Using these strategies, the compiler generates a Single Program Multiple Data
(SPMD) program [16] for execution on the target machine. In a software-coherent NUMA
architecture the compiler translates the global references in HPF into local and non-local
references satisfied by the appropriate message-passing statements, usually respecting
the owner-computes rule (i.e., the processor owning a piece of data is responsible for
performing all computations that update it).
The best choice for a data mapping depends on the program structure, the characteristics
of the underlying system, the number of processors, the optimizations performed
by the supporting compilation system and the problem size. Crucial aspects such as data
movement, parallelism and load balancing have to be taken into consideration in a unified
way to efficiently solve the data mapping problem. Automatic data distribution tools
may play an important role in making massively parallel systems truly usable. They are
usually offered as source-to-source tools, which annotate the original program with data
mapping directives and executable statements offered by the data-parallel extensions of
current shared-memory programming models. Automatic data distribution maps arrays
onto the distributed-memory nodes of the system, according to the array access patterns
and parallel computation done in the application. The applications considered for automatic
optimization solve regular problems, i.e., use dense arrays as their main data
structures. These problems allow computation and communication requirements to be
derived at compile time.
1.1 Traditional Methods
Most automatic data mapping methods split the static data mapping problem into two
main independent steps: alignment and distribution. The alignment step attempts to
relate the dimensions of different arrays, minimizing the overall overhead of inter-processor
data movement. In [24] the authors prove that the alignment problem is NP-complete.
The distribution step decides which of the aligned dimensions are distributed, the number
of processors assigned to each of them, and the distribution pattern. Usually arrays are
distributed either in a BLOCK or CYCLIC fashion, although some tools also consider the
BLOCK-CYCLIC distribution, assigning blocks of consecutive elements to each processor
in a round-robin fashion. A good distribution maximizes the potential parallelism of the
application, balances the computational load, and offers the possibility of further reducing
data movement by serializing. However, these two steps are not independent: there is a
trade-off between minimizing data movement and exploiting parallelism.
When there is a single layout for the whole program, the mapping is said to be static.
However, for complex problems, remapping actions between code blocks can improve the
efficiency of the solution. In this case, the mapping is said to be dynamic. Note that a
dynamic data mapping requires data movement to reorganize the data layout between
code blocks. In order to solve the dynamic data mapping problem, most approaches
consider a set of reasonably good solutions (alignment and distribution) for each code
block and, in an additional step, one solution is selected for each code block that maximizes
the global behavior. Again, note that this approach may discard some solutions for each
phase that could lead to a global optimal solution. Kremer demonstrates in [19] that the
optimal selection of a mapping for each phase is again NP-complete, and Anderson and
Lam show in [2] that the dynamic data mapping problem in the presence of control flow
statements between phases is NP-hard.
1.2 Our Proposal
In this paper we propose a new framework to automatically determine the data mapping
and parallelization strategy for a Fortran 77 program, in the context of a parallelizing
environment for DMM systems. Our main interest has been to develop an approach to
find an optimal solution for the data mapping problem, given some characteristics of the
target architecture and assuming a predetermined compilation model.
Compared to previous approaches, our algorithm combines data distribution and dynamic
redistribution with parallelism information in a single graph representation: the
Communication-Parallelism Graph (CPG). The CPG contains information about data
movement and parallelism within phases, and possible data movement due to remapping
between them. All this information is weighted in time units representing data movement
and computation costs. This allows the alignment, distribution, and redistribution
problems to be solved together.
We use the CPG to model the data mapping problem as a minimal cost path problem
with a set of additional constraints that ensure the correctness of the solution. General
purpose linear 0-1 integer programming techniques, which guarantee the optimality of
the solution provided, are used to solve the minimal cost path problem. These techniques
have been proven to be effective in solving a variety of compilation problems [21].
The data mapping strategies considered are static and dynamic, one and two-dimensional,
with both BLOCK and CYCLIC distribution patterns, and the effects of control flow statements
between phases are considered by the framework. Our cost model is based on
profiling information obtained from a previous serial execution. In addition, some parameters
of the target system, such as the number of processors, the parallel thread creation
overhead, and the communication latency and bandwidth, have to be provided.
The generated data mapping strategy is used to annotate the original Fortran program
using HPF data mapping and loop parallelization directives. Note that the considered
strategies are based on the HPF model, therefore the optimality of the solution is conditioned
by the capabilities of the target HPF compiler and the accuracy of our cost model.
In our current implementation we do not handle communication optimization or pipelined
computation. Therefore we assume an HPF compiler that generates an SPMD code according
to the owner-computes rule, and that no loop transformation or communication
optimization is performed by the compiler.
The rest of the paper is organized as follows. In Section 2 we use a motivating example
to describe some related work. In order to simplify the presentation of the CPG, Section
3 describes the information required to model one-dimensional data mappings. This
model is extended in Section 4 to support two-dimensional data mappings. Section 5
describes the formulation of the minimal cost path problem used to find an optimal
data mapping. Several experiments have been performed to validate the accuracy and
feasibility of the model; these are presented in Section 6. And finally, some concluding
remarks are summarized in Section 7.
Related Work and Motivation
A large number of researchers have addressed the problem of automatic data distribution
in the context of regular applications. Due to the complexity of this problem, all
related work splits the global problem into several independent steps, usually alignment,
distribution, and remapping. In addition, most of them also perform a second level of
simplification by using heuristic algorithms to solve each step. Finally, another common
difference between the proposed methods is the cost model adopted.
Several Steps
Although data mapping can be specified by means of three attributes (alignment, distribution
and remapping), an automatic data mapping framework should not solve them
independently. Let us first motivate the coupling of the alignment and distribution sub-
problems. When they are solved independently (Li and Chen [24], Gupta et al. [15],
Kremer and Kennedy [20], Chatterjee et al. [8], Ayguad'e et al. [3]) the alignment step
may impose some constraints, in terms of parallelism exploitation, to the distribution
step. For instance, assume the simple example shown in Figure 1. The loop includes
two statements in its body: an assignment of matrix B to matrix A, and an assignment
of matrix B transposed to matrix C. An alignment algorithm will easily determine a perfect
alignment of arrays A and B and a transposition of array C, so that the solution is
communication free. However, this alignment forces the distribution step to partition a
different loop in the nest for each statement in the body (following the owner-computes
rule). This does not lead to any loop parallelization unless loop distribution is applied,
which may not be possible if the statements that cause the conflict are involved in a data
dependence cycle.
As a result of the alignment and distribution steps, all the previously referenced proposals
end up with a set of candidate static mappings for each phase. These candidate
mappings are the input to a final independent step that evaluates the usefulness of dy-
do

Figure

1: Simple example for alignment and distribution.
namic mappings [27, 20, 9, 3]. For instance, Figure 2 shows an excerpt of the Adi
integration kernel. The code consists of two phases: a sequence of sweeps along rows
in the first phase, followed by sweeps up and down columns in the second phase. If
these phases are analyzed in isolation, a row layout has the best performance in the first
phase, and a column layout has the best performance in the second phase. Note that the
solution for one phase leads to the sequentialization of the other phase, and that the sequentialization
of a parallelizable phase is far from being considered the best strategy for
a phase in isolation. Therefore, the remapping step will propose a dynamic transposition
of arrays between the two phases, but this requires data reorganization. Other proposals
export a set of solutions of each phase to the rest of the phases [20]. In this case, the
remapping step would consider the possibility of applying a static row or column layout
for the whole sequence of phases. Depending on the characteristics of the target system
(for instance, low bandwidth) this could be a better global solution even when one phase
is sequentialized. However, these proposals do not consider solutions that are not part
of the initial set of candidate solutions for each phase. This may lead to a situation in
which, for instance, a static two-dimensional distribution of rows and columns for both
phases (which may be skipped because of its performance in each isolated phase) is the
best global solution [5].
In fact, some later related work also claims for a simultaneous alignment and distribution
step [11, 7], in order to preserve parallelism while minimizing data movements.
do
do
c(i,
do
do
c(i,

Figure

2: Simple example for dynamic mapping.
However, they still propose an additional step to solve the dynamic data mapping problem

Algorithms
The alignment problem has been proven to be NP-complete; for this reason, Li and Chen
[24] (and other authors working from modifications of this initial work [15, 3]) propose a
heuristic algorithm to solve this problem. Other researchers propose the use of algorithms
based on dynamic programming [8]; however, in [20] they find an optimal solution to their
alignment problem by using 0-1 integer programming techniques. In order to solve the
distribution problem, an exhaustive search is usually performed. In [25] the authors
describe a model that exhaustively explores all distribution options, based on pattern
matching between the reference pattern of an assignment statement and a predefined set
of communication primitives. In [15] they use a constraint-based approach assuming a
default distribution. Furthermore, the authors in [1] combine mathematical and graph-based
problem representations to find a communication-free alignment. Then they use a
heuristic to eliminate the largest potential communication costs while still maintaining
sufficient parallelism.
The dynamic data mapping problem is again NP-complete. This is solved in [9] using
a divide-and-conquer approach. In [27] the authors use dynamic-programming techniques:
starting from a static solution, they recursively decompose it employing their cost model.
A dynamic-programming algorithm is also used in [23] to determine the best combination
of candidate layouts in a sequence of phases. In [3] a controlled exhaustive search is
considered to find the solution to the same problem. Finally, the authors in [20] formulate
the dynamic data partitioning problem as another 0-1 integer programming problem that
selects a single candidate data layout from a predetermined set of layout candidates.
Cost Model
All approaches need a cost model to make decisions in each step. Performance estimates
have to be precise enough to be able to distinguish the considered search space of possible
data mappings. With a communication/no communication [24] or a cheap/expensive [1]
cost model it is quite simple to obtain reliable solutions in complex programs. Another
option is to estimate performance through symbolic analysis of the code [25, 15, 3]; how-
ever, array data sizes have to be known at compile time, as well as the number of loop
iterations and the probabilities of conditional statements. This information has to be
provided by the user or obtained through profiling. In contrast, training sets [6] obtain
good performance estimations for the set of reported programs, although it is difficult
to build a training set general enough to guarantee that all possible source programs are
considered.
In general, it is difficult for an optimizing tool to make best guesses at compile time
with incomplete information. Thus, running the program serially first and obtaining some
profiling information is a common strategy adopted by many commercial optimizers, especially
when the quality of the solution depends heavily on the characteristics of the
source program.
Although some attempts have been made to add interaction between the three steps,
the solution proposed in this paper improves the related work in two main aspects: (i) we
present a unified representation that allows the compiler to explore solutions that would
not be obtained from isolated analysis; and (ii) we use linear 0-1 integer programming
techniques to find the optimal solution to the whole problem. Obviously, these improvements
trade off the computation time required to get an optimal solution; however, an
expensive technique can be an important tool for a compiler if it is applied selectively in
cases where the optimal solution is expected to result in a significant performance gain.
3 One-dimensional Data Mapping
A valid data mapping strategy in the one-dimensional data mapping case distributes, at
most, one dimension of each array over a one-dimensional grid of processors, in either
BLOCK or CYCLIC fashion. The distribution derived may be static or dynamic.
The number of processors N of the target architecture is assumed to be known at
compile time. The sequential execution of the original Fortran 77 program must be
profiled in order to obtain some problem-specific parameters, such as array sizes, loop
bounds and execution times, and probabilities of conditional statements.
3.1 The Communication-Parallelism Graph
In our framework, we define a single data structure that represents the effects of any
data mapping strategy allowed in our model. The name of this data structure is the
Communication-Parallelism Graph (CPG), and it is the core of our approach. The CPG is
an undirected graph G(V; E; H) that contains all the information about data movement
and parallelism in the program under analysis. It is created from the analysis of all
assignment statements within loops that reference at least one array. The set V of nodes
represents distributable array dimensions, the set E of edges represents data movement
constraints, and the set H of hyperedges 1 represents parallelism constraints. Edges and
hyperedges are labeled with symbolic information which is later used to obtain weights
following a particular cost model.
Programs are initially decomposed into computationally intensive code blocks named
phases. Each phase has a static data mapping strategy, and realignment or redistribution
actions can occur only between phases. In our approach we have adopted the following
definition of phase, made in [17]:
A phase is a loop nest such that for each induction variable occurring
in a subscript position of an array reference in the loop body,
the phase contains the surrounding loop that defines the induction
variable. This operational definition does not allow the overlapping
or nesting of phases.
3.1.1 Nodes
Nodes in G are organized in columns. There is a column V i in G associated with each
array i in each phase. If one array is used in several phases, there will be a column for each
phase in which this array appears. Each column contains as many nodes as the maximal
dimensionality d of all arrays in the program. V i [j] denotes, for j 2 f1::dg, the th
dimension of array i. Thus, each node represents a distributable array dimension. If one
array has dimensionality d 0 ! d, the array is embedded onto a d-dimensional template.
In this case, the additional nodes (d \Gamma d dimensions used to represent
data mappings where the array is not distributed.
3.1.2 Edges
Edges in G reflect possible alignment choices between pairs of array dimensions. Edges
connect dimensions of different arrays. An edge connecting dimension j 1 of array i 1 to
hyperedge is the generalization of an edge, as it can connect more than two nodes.
dimension j 2 of array i 2 (say edge
represents the effects, in terms of data
movement, of aligning and distributing these dimensions.
For each phase p in the program, the data movement information is obtained by
performing an analysis of reference patterns between pairs of arrays within the scope of p.
Reference patterns are defined in [24], and represent a collection of dependences between
arrays on both sides of an assignment statement. For each reference pattern between
with d \Theta d edges is added connecting each node of V i 1
to each
node of V i 2
. This set of edges represents the behavior of all alignment alternatives between
dimensions of both arrays. If (self-reference pattern) then only d self-edges are
added in V i 1
, one for each node.
Edges are labeled with data movement primitives, representing the type of data movement
performed if the corresponding array dimensions are distributed. The data movement
primitives considered in our framework include 1to1, 1toN, Nto1, and NtoN. A 1to1
primitive is defined as a data movement from one processor to another processor (shift
or copy). Similarly, a 1toN primitive is defined as a data movement from one processor
to several processors (broadcast). An Nto1 primitive is defined as a data movement from
several processors to one processor (reduction). Finally, an NtoN primitive is defined as
a data movement from several processors to several processors (multicast).
Remapping information, which has an impact on data movement, is included in G in
terms of data movement edges between phases. Data flow analysis detects whether an
array i in a phase p 1 (named used in a later phase, say p In this case,
with d \Theta d edges is added, connecting each node of the column associated with
array i at phase p 1 to each one associated with array i at phase p 2 . The label assigned
to each edge represents the data movement to be performed (a remapping)
if the corresponding dimensions are distributed. The dynamic model is further described
in [14].
Control flow statements between phases have to be considered when performing the
data flow analysis. Entry or exit points, conditional or iterative statements, can modify
the execution flow of a program and therefore cause a sequencing of the phases in the
program different from the lexicographic order. A control flow analysis is used to weight
the costs (as explained in the cost model) of the remapping edges set. This analysis is
further described in [13].
3.1.3 Hyperedges
Hyperedges in G reflect opportunities for parallelism. Each candidate parallel loop k has
a hyperedge H k in G, connecting all array dimensions that have to be distributed for the
loop to be parallelized. In distributed memory machines a loop can be fully parallelized
if it does not carry any data flow dependence [28]. Data-dependence analysis detects
the set of loops that are candidates for parallelization. According to the owner-computes
rule, the processor that owns a datum is responsible for performing all computations to
update it. Therefore, if a candidate parallel loop has to be parallelized, all left-hand side
array dimensions inside that loop subscripted with the loop control variable have to be
distributed.
This means that hyperedge H k links all those nodes V i [j] such that: 1) array i is
updated in the loop body enclosed by loop k (i.e., it appears on the left-hand side of the
assignment statement), and 2) the induction variable of loop k is used in the subscript expression
in dimension j. In this case, hyperedge H k is labeled with information associated
with the corresponding candidate parallel loop.
3.1.4 CYCLIC Information
CYCLIC distributions are useful for balancing the computational load of triangular iteration
spaces; however, if neighbor communication patterns appear in the code, a CYCLIC
distribution incurs excessive data movement.
In our framework we assume a BLOCK distribution by default, meaning that edge and
hyperedge labels in the CPG are assigned assuming a BLOCK distribution. However, if
the code contains triangular loops and it does not contain any neighbor communication,
then the CYCLIC distribution is assumed, meaning that labels in the CPG are assigned
assuming a CYCLIC distribution. In the event of conflict, both alternatives are considered
by duplicating the CPG. Labels in the first CPG copy are assigned assuming a BLOCK dis-
tribution, and labels in the second CPG copy are assigned assuming a CYCLIC distribution
(note that the cost model, described in section 3.3, is different according to whether the
distribution is BLOCK or CYCLIC). In this case, some data movement edges connecting
both CPG copies have to be added in order to allow arrays to change distribution pattern
between phases. Further details of this model are fully described in [12].
3.1.5 An Example

Figure

3 shows a simple code that is used as a working example throughout this paper.
The code consists of two loop nests that, following the assumed definition of phase, are
identified as phases.
do
do
A(i,
do
do

Figure

3: Sample code.
The maximum dimensionality of all arrays in the code is 2, therefore each column in
remap
Phase 1 Phase 2
loop j
loop i
remap

Figure

4: CPG for the sample code.
G has two nodes. In the first phase there are four columns, say corresponding to
arrays A, B, C, and D. Similarly, in the second phase there are three columns, say
corresponding to arrays C, D, and E. This can be seen in Figure 4. Note that although
array E is one-dimensional, its corresponding column V 7 has two nodes.
From the first assignment statement in the first phase, one reference pattern between
arrays A and B is identified:
This reference pattern indicates that if the first dimension of both arrays is distributed,
then a 1to1 data movement is needed (each processor has to send its last row to the
following processor). However, if the second dimension of both arrays is distributed, the
array accesses require no data movement. In addition, if the first dimension of array A
and the second dimension of array B (or vice versa) are aligned and distributed, an NtoN
data movement is necessary (this is a transposition, i.e., all processors send a block of
the array to all processors). A similar analysis is performed for each reference pattern in
each phase of the program. This information is shown in Figure 4, in which dotted edges
represent no data movement.
Remapping edges connect uses of the same array in different phases. For instance,
columns 3 and 5 in Figure 4 represent the same array C but in different phases. Edges
connecting the same dimension of these columns mean that the same distribution holds
between both phases and, therefore, no data movement is required. Edges connecting
different dimensions of these columns represent the effects of changing the distribution of
that array, i.e., a remapping.
Finally, a data dependence analysis detects that the do j loop in the first phase and
the do i loop in the second phase are candidates for parallelization. For the do j loop to
be parallelized, the second dimension of arrays A, B, and D have to be distributed in the
first phase. Therefore, a hyperedge connecting these nodes is inserted in G, and labeled
with information about this loop. Similarly, a hyperedge connecting the first dimension
of arrays C and D in the second phase is inserted. In this case, the hyperedge is labeled
with information about this loop, as can be seen in Figure 4.
3.2 Data Mapping with the CPG
The CPG contains all the information required in our model to estimate the performance
effects of the program for different mapping strategies. A valid data mapping strategy in
the one-dimensional case includes one node V i [j] from each column V i in G. This set of
nodes determines the array dimension j for each array i distributed in each phase. Note
that by selecting a set of nodes to be distributed, the alignment between them is implicitly
specified.
The performance effects for the selected data mapping strategy are estimated from the
set of edges and hyperedges that remain inside the selected set of nodes. Edges represent
data movement actions and hyperedges represent loops that can be effectively parallelized.
For instance, Figure 5 shows a valid data mapping strategy in which the second dimension
of arrays A, B, C, and D are aligned and distributed in the first phase, and the
first dimension of arrays C, D, and E are aligned and distributed in the second phase. The
effects of this data mapping strategy in the first phase are that there will be an NtoN
data movement of array C and that the do j loop will be parallelized. Similarly in the
second phase there will be an NtoN data movement of array E and the do i loop will be
parallelized. In addition, arrays C and D will be remapped between the two phases.
remap
Phase i Phase i+1
loop j
loop i
remap

Figure

5: Valid dynamic mapping in the CPG for the sample code.
3.3 Cost Model
In order to select an appropriate data mapping strategy, cost functions labeling edges and
hyperedges in the CPG are replaced by constant weights. Note that the accuracy of the
cost model is an orthogonal issue with respect to the framework presented in this paper:
the CPG could be weighted either with simple binary cost functions (cheap or expensive)
or by performing a complex performance prediction analysis.
The performance estimation is machine dependent; therefore, it has to be aimed at
a specific architecture. In our framework there is a configuration file with parameters
of the target system, such as the number of processors, the data movement latency and
bandwidth, and the parallel thread creation overhead. In addition, our cost model is based
on profiling information that provides array data sizes and the sequential computation
time for each loop.
The cost assigned to a data movement edge is computed as a function of the number
of bytes interchanged through remote memory accesses, and the machine specific latency
and bandwidth. Each reference pattern is matched to a set of predefined data movement
routines as defined in [25]. The routines considered in our framework, as introduced in
the previous section, are 1to1, 1toN, Nto1, and NtoN. According to the owner-computes
rule, the processor that owns the data on the left-hand side of an assignment statement
is responsible for computing that statement; therefore, the data to be moved is the non-local
data from the right-hand side of the statement. Given a data movement routine, the
number of processors, and the distribution pattern (BLOCK or CYCLIC), we can estimate
the block size of the data to move, and therefore the data movement time.
A hyperedge, associated with a candidate parallel loop, is weighted with the computation
time saved if that loop is effectively parallelized. Given the sequential computation
time of the loop and the shape of the iteration space, the number of processors and the
parallel thread creation overhead, and given a distribution pattern, this time can be easily
estimated.
For instance, in order to estimate the execution time for the first phase of the sample
code with the data mapping strategy illustrated in Figure 5 (distribute the second dimension
of each array in a BLOCK fashion), assume that the number of elements in each array
dimension is size (32 bit floating point per element), and that the sequential computation
time for the j loop is time seq. In addition, consider a target system with NP processors,
a data movement latency of LT seconds, a bandwidth of BW bytes/second, and a parallel
thread creation overhead of PT seconds.
There is an NtoN data movement of array C; therefore, the block size BS of the data
to move is computed (in bytes) as:
size \Theta
According to the features of the target system, the data movement time is estimated as:
seconds
In addition the do j loop in this phase can be parallelized, therefore the computation
time is estimated as:
And the total estimated time is, thus, move time plus comp time.
Note that all cost weights in the CPG are expressed in time units. This uniform
cost representation allows an estimation of the trade-offs between data movement and
parallelization gains. With this estimation, the CPG can be used as the main data
structure either in a performance estimation tool or in an automatic data mapping tool.
Further details of the cost model can be found in [12].
4 Two-dimensional Data Mapping
In this section we describe how to extend the CPG in order to support two-dimensional
distributions. We believe that for most scientific programs, restricting the number of
distributed dimensions of a single array to two does not lead to any loss of effective
parallelism. Even when higher-dimensional arrays show parallelism in each dimension,
restricting the number of distributed dimensions does not necessarily limit the amount of
parallelism that can be exploited [15].
The number of available processors N is known at compile time, and it is assumed to
be a number power of 2, i.e., two-dimensional processor topology is defined
by a grid of n 1 \Theta n 2 processors, where data mapping strategy in
the two-dimensional data mapping model distributes one or two dimensions of the arrays
over a two-dimensional grid of processors. The distribution may be static or dynamic,
and the processor topology may change according to the preferences of the program.
For simplicity in the explanation, we will initially assume that the n 1 \Theta n 2 processor
topology is fixed and known at compilation time (single topology). Although this is not
a realistic case, it allows us to introduce the general case, in which multiple processor
topologies are considered.
4.1 Single Topology
In this first case, we assume that the processor topology is two-dimensional, static,
and known at compilation time. Therefore, a valid data mapping strategy, in the two-dimensional
data mapping case with single topology, distributes two dimensions of the
arrays over a fixed n 1 \Theta n 2 grid of processors.
To this end, the CPG is made up of two undirected graph copies that are identical
except for their weights. In the first copy, named G 1 , all weights are computed assuming
processors. Likewise, in the second copy, named G 2 , all weights are computed assuming
processors. One G b copy (for b 2 f1; 2g), therefore, represents the effects of distributing
array dimensions over the b th dimension of the grid of processors. In order to distribute
dimension j of array i across the first dimension of the grid of processors (G 1 ), the node
has to be selected in G 1 (say V 1
[j]). Alternatively, to distribute dimension j of
array i across the second dimension of the grid of processors (G 2 ), the node V i [j] has to
be selected in G 2 (say V 2
[j]). This allows any array dimension to be mapped on any
dimension of the grid of processors.
According to this model, a valid data mapping strategy for the two-dimensional distribution
with a single topology problem contains one node V b
i [j] for each column V b
i in each
copy, with the additional restriction that one dimension j 1 selected in V 1
has to be
different from the dimension j 2 selected in V 2
The data movement and parallelization
effects for the selected two-dimensional data mapping strategy is estimated from the set
of edges and hyperedges that remain inside the selected set of nodes.
In

Figure

6 there is an example of a valid data mapping, in which the first dimension
of all arrays is distributed along the first dimension of the n 1 \Theta n 2 grid of processors, and
the second dimension of all arrays is distributed along the second dimension of the same
grid of processors. According to this data mapping, note that the do j loop in the first
phase is parallelized with n 2 processors and that the do i loop in the second phase is
parallelized with n 1 processors. Note also that the one-dimensional array E is distributed
only along the first dimension of the grid of processors. For this reason, as replication is
not considered in our framework, there is a 1toN data movement to satisfy the assignment
statement of array E to array D in the second phase.
loop i
loop j

Figure

solution in a two-dimensional CPG with n 1 \Theta n 2 topology.
Cost functions in the two-dimensional model have to be modified with respect to the
one-dimensional case. Data movement costs at each CPG copy are estimated assuming
that two array dimensions are distributed. In order to estimate the computation time for
nested loops, some edges connecting both CPG copies are inserted. These modifications
are fully described in [12].
4.2 Multiple Topologies
In order to consider any two-dimensional topology in our model, the idea is to build the
CPG with as many two-dimensional G copies as topologies may be considered. The symbolic
information contained at each copy is identical, but weights are computed according
to the number of processors assumed in the corresponding topology. For regularity, the
one-dimensional data mapping is modeled as a two-dimensional N \Theta 1 grid of processors.
Assuming that G ab is the graph copy corresponding to the b th dimension of the a th
topology, a valid data mapping strategy in the general two-dimensional distribution problem
has to select one node V ab
i [j] for each column V ab
i in each G ab copy within a single a
two-dimensional topology. As in the previous model, a dimension j 1 selected in V a 1
has to be different from dimension j 2 selected in V a 2 i [j 2 ]. The topology a selected for
one phase has to be the same for all arrays at that phase. However, the topology may
change between phases if necessary. One change in the distribution topology of an array
requires a redistribution, therefore additional data movement edges have to be inserted in
the CPG allowing this kind of remapping, and estimating the effects of the corresponding
data movement primitive.
Our current implementation is limited to two different topologies: the one-dimensional
N \Theta 1 topology, and a squared two-dimensional n 1 \Theta n 2 topology with
2 . If
m is an odd number, then n 1 is set to 2 \Theta n 2 . The extension to more than two topologies
is straightforward, and further details can be found in [12].
For instance, Figure 7 contains a valid general two-dimensional data mapping strategy.
In this case, the second dimension of all arrays in phase p 1 are aligned and distributed
on the one-dimensional grid of processors with N processors. The arrays C and D are
redistributed, and the first dimension of all arrays in phase p 2 are aligned and distributed
on the first dimension of the n 1 \Theta n 2 grid of processors, and the second dimension of all
arrays are aligned and distributed on the second dimension of the same two-dimensional
grid of processors.
Note that all nodes selected in phase p 1 belong to a single topology copy (the one-dimensional
topology), while all nodes selected in phase p 2 belong to another topology
copy (the two-dimensional one). this means that the distribution in the first phase is
one-dimensional, and the distribution in the second phase is two-dimensional.
loop j
G 11
procs
loop i
G 21
G 22
Phase

Figure

7: Valid solution in a general two-dimensional CPG.
5 Minimal Cost Path Problem Formulation
Given a valid data mapping strategy, the summation of weights of the edges that remain
inside the selected set of nodes is the data movement time estimation. The summation of
weights of the hyperedges that remain inside the selected set of nodes is the estimation
of the computation time saved due to parallelization. The total execution time of the
parallelized program is estimated as the sequential execution time plus the data movement
time minus the computation time saved due to parallelization. The optimal data mapping
strategy for the problem is that which minimizes the estimated parallel execution time.
In order to find the optimal data mapping strategy, according to our model, we translate
our data mapping problem into a minimal cost path problem. Some constraints have
to be added to guarantee the validity of the solution. In this section we describe the
formulation of our data mapping problem as a minimal cost path problem with a set of
additional constraints that guarantees the validity of the solution.
Linear programming (LP) provides a set of techniques that study those optimization
problems in which both the objective function and the constraints are linear functions.
Optimization involves maximizing or minimizing a function, usually with many variables,
subject to a set of inequality and equality constraints [26]. A linear pure integer programming
problem is an LP in which variables are subject to integrality restrictions. In
addition, in several models the integer variables are used to represent binary choices, and
therefore are constrained to be equal to 0 or 1. In this case the model is said to be a
linear programming problem.
In our framework, we model the whole data mapping problem as a linear 0-1 integer
programming problem, in which a 0-1 integer variable is associated with each edge and
hyperedge. The final value for each binary variable indicates whether the corresponding
edge or hyperedge belongs to the optimal solution. The objective function to minimize
is specified as the estimated execution time of the parallelized version of the original
program. Our problem is not purely a minimal cost path problem as several additional
restrictions have to be added to the path selection.
The 0-1 Variables
Assuming that G ab is the graph copy corresponding to the b th dimension of the a th topol-
ogy, let e ab
PQ denote the set of variables in G ab associated with edges connecting nodes in
column P to nodes in column Q. Note that according to our current implementation,
a 2g. Each set e ab
PQ contains d \Theta d elements. Let e ab
PQ [i; j] be
the variable in G ab associated with the edge connecting node i in column P to node j
in column Q. Its value is one if the corresponding edge belongs to the path, and zero
otherwise. Note that, as the graph is undirected, e ab
PQ [i; j] is equivalent to e ab
QP [j; i].
Redistribution edges behave like regular data movement edges; however, as they connect
different G ab copies, the sets of 0-1 integer variables associated with redistribution
edges are called r for simplicity in the notation of subscripts. Therefore, let r ab
PQ [i; j] be
the variable associated with the redistribution edge connecting node i of column P at G ab
to node j of column Q at G a 0 b , where a 0 denotes the alternate topology.
Finally, if an index k is assigned to each hyperedge, h ab
k will denote the 0-1 integer
variable in G ab associated to the k th hyperedge. Similarly, its value will be one if all the
nodes it links belong to the path, and zero otherwise.
The Model
Assume the D-dimensional data mapping problem, with T different topologies, each with
dimensionality D. A valid solution for this problem includes D nodes for each array, one
from each column, with the restriction that all nodes selected within a phase belong to a
single topology.
Some points should be noted about G before going into the details of the linear 0-1
integer programming model.
ffl All pairs of edges connecting the same two nodes can be replaced by a single edge
with weight equal to the addition of the weights of the original ones.
ffl There is a path between any pair of columns in G. If a set of columns is not
connected, then this set can be analyzed independently and assigned a different
data distribution strategy.
In order to guarantee the validity of the solution in the minimal cost path problem
formulation, some constraints have to be specified. These constraints can be organized in
the following sets:
The solution is a set of D paths.
Nodes selected in each path are distinct.
Each path within a single phase selects nodes of a different dimension (1
in a single topology.
Each path visits one node in each column.
connecting selected nodes are included in the solution.
connecting selected nodes are included in the solution.
The set of constraints C1 guarantees that a path in a G copy is connected. Thus for
each column Q connected to more than one column P and R, if one edge leading to a
node in Q is selected in the set e ab
PQ (or in the set r a 0 b
PQ when it exists), one edge leaving
this same node must be selected in the set e ab
QR (or in the set r ab
QR when it exists).
In terms of the variables and their values, it can be stated at each G ab copy that for
each node i of each column Q connected to more than one column P and R, the sum of
the values of variables associated with the edges that connect this node to column P must
be equal to the sum of the values of variables associated with the edges that connect this
node to column R:
d
e ab
d
e ab
The set of constraints C2 guarantees that paths do not have nodes in common, or in
other words, that the same array dimension is not distributed more than once. this can
be achieved by ensuring that the number of selected edges connecting each node in all
G ab copies to any other column is lower than or equal to one.
In terms of variables and their values, for each node i in column P connected to
another column Q by e ab
or r ab
PQ , the summation of the values of the variables associated
with the edges that connect this node to column Q at any G ab copy has to be lower than
or equal to one:X
d
e ab
The set of constraints C3 forces each selected path to belong to different dimensions
of the same topology. this can be modeled, for each topology a, by ensuring that the
number of selected edges in one dimension b of the topology equals the number of selected
edges in the alternate dimension b 0 of the same topology.
In terms of variables and their values, for each set of edges e ab
PQ and for each topology
a, the summation of the values of the variables associated with the edges in G ab must be
equal to the summation of the values of the variables associated with the edges in G ab 0
d
d
e ab
d
d
e ab 0
The sets of constraints C4 and C5 can be specified together, and these can be modeled
by forcing one edge to be selected in each dimension of a single topology. this can be
stated, in terms of variables and their values, by assuming the summation of each set of
edges e ab
PQ and r ab
PQ to be equal to one, for each dimension b of all topologies a.X
d
d
e ab
Finally, the set of constraints C6 ensures that one hyperedge is selected only when all
nodes connected by it have been selected. According to this model, a node i in column P
is selected in G ab if one edge e ab
PQ [i; j] or r ab
PQ [i; j] that connects it to any other column Q
has been selected. Assume that hyperedge h ab
connects n nodes in G ab , say nodes
from columns respectively. It can be stated, in terms of variables and their
values, that:
this must be accomplished for each hyperedge k at each G ab copy.
Example
For instance, assume the first phase of the one-dimensional CPG shown in Figure 4. There
are four columns, say (in the figure A, B, C, and D respectively); and three sets of
connecting these columns. In addition, one hyperedge (say
in the one-dimensional case, both a
and b equal 1 and, therefore, redistribution edges between CPG copies are not required.
The set of constraints C1 guarantees that the path in CPG is connected. Columns
and C are connected to more than one column, so one constraint is added for each
column:
The sets of constraints C2 and C3 guarantee the compatibility of the different paths
in the multi-dimensional CPG; therefore, they are not necessary in this example. The set
of constraints C4 and C5 are specified together, and force the selection of one edge to
each set of edges:
And the set of constraints C6 ensures the correct selection of the hyperedge:
Note that as the graph is undirected, the third constraint could also be specified as:
6 Experimental Results
Several experiments have been performed in order to validate different aspects of our
framework. First of all, we show the complexity in terms of computational time spent
in finding the optimal solution for a set of programs from different benchmark suites.
Secondly, the accuracy of the predictions is illustrated to demonstrate the validity of the
model.
6.1 Complexity of the Approach
The programs selected to evaluate the complexity of the model are the Alternating Direction
Implicit (Adi) integration kernel, the Erlebacher program developed by Thomas
Eidson at ICASE, programs Shallow, Tomcatv, and x42 from the xHPF benchmark
set 2 , and routine Rhs from the APPSP NAS benchmark set. For the purpose of this
evaluation, programs Erlebacher, Shallow, and Baro have been inlined (i.e., each
call has been replaced by the actual code), and routine Rhs has been transformed into a
single program.

Table

includes information about the number of code lines, the total number of
loops, the number of loops that are candidates for parallelization, the number of phases
in each program, the number of different arrays and their dimensionality, and the number
of different reference patterns between arrays. These characteristics are the parameters
that can determine the complexity of the final optimization problem.

Table

2 shows the number of 0-1 integer variables and the number of constraints
required (according to the model described in section 5) to formulate the minimal cost
path problem for one-dimensional data mappings. The last column shows the total CPU
time (in seconds) required to find the optimal solution. All CPU times were obtained
using a Sun UltraSparc. The model was built assuming a multiprocessor system with 8
2 xHPF is available by anonymous ftp at ftp.infomall.org in directory tenants/apri/Benchmarks
Program Lines Loops Parall Phases Arrays Dims Patts
Rhs 535 37 37 4 4 4 24
Tomcatv 178
Baro 1153 98 86 24 38 2 428
Shallow

Table

1: Characteristics of the selected programs.
processors and a bandwidth of 2 Mbytes per second.
Program edges hyper constr time
Erlebacher 1359 68 804 3.4
Rhs 336 37 176 0.5
Baro 1484 83 1608 10.4
Shallow 936 38 1004 3.9

Table

2: Characteristics of the one-dimensional model.
The most time-consuming application is Baro with 10.4 seconds. Shallow, Er-
lebacher, and X42 need 3.9, 3.4, and 3.1 seconds respectively, and all other programs
need half a second to be optimized.
In the two-dimensional data mapping problem assuming a single topology, the number
of CPG copies is duplicated, as well as the number of 0-1 integer variables. However,
the number of constraints required to model the problem is more than double because
additional constraints have to be added to relate the two CPG copies. Table 3 shows the
number of edges, hyperedges, constraints, and the total computation time spent to find
the optimal solution.
Programs Baro and Erlebacher require about two minutes to reach a solution,
Shallow, x42, and Rhs require between 32 and 46 seconds, and Tomcatv and Adi
need two and one seconds respectively.
Program edges hyper constr time
Erlebacher 2718 136 2014 117.6
Rhs 672 74 543 32.7
Tomcatv 496 20 583 2.0
Baro 2968 166 3703 125.7
Shallow 1872 76 2335 46.1

Table

3: Characteristics of the two-dimensional model with constant topology.
Finally, in Table 4 the number of edges, hyperedges, and constraints for the general
two-dimensional model is shown, together with the computation times required to find
the optimal solution.
Program edges hyper constr time
Erlebacher 8892 272 4065 3156.6
Rhs 2048 148 922 985.6
x42 4304 116 3481 2455.5
Baro 8944 332 7315 6354.5
Shallow 6160 152 4726 1636.7

Table

4: Characteristics of the general two-dimensional model for the selected programs.
In this model, the structure of the minimal cost path problem is harder to solve. Program
Baro requires almost two hours, while programs Erlebacher, x42, and Shallow
need between half an hour and one hour. Program Rhs needs 16 minutes, and the other
programs require just a few seconds.
Discussion
According to our experiments, only a few seconds are required to solve the one-dimensional
data mapping problem. However, in the two-dimensional case, the computation time
required is greater. Note that we decide alignment, distribution, parallelization of loops,
and dynamic changes in this strategy, for all phases of all routines in the program, together
in the same step. The number of data mapping candidates considered becomes 2 210 for
Baro, while the number of candidates for Erlebacher becomes 3 109 . Although the
longest computation time required to find an optimal data mapping was observed to
be up to two hours, it must be considered that the tool provides the optimal solution.
Therefore, this computation time is an investment that can be considered to be paid off
within each program run.
In order to reduce these computation times, note that the longest times are usually
for programs that have been inlined, i.e., programs Baro, Shallow, and Erlebacher.
The complexity of an inlined program becomes greater, as all routines are considered
together. We analyzed each routine of these programs in isolation. One routine from
program Baro requires two minutes, and all other routines need less than half a minute.
The analysis of each routine from program Shallow requires just a few seconds, and
all routines from program Erlebacher need less than one and a half minutes. These
results encourage us to consider inter-procedural analysis as a way to reduce the current
complexity.
Finally, we also observed that linear 0-1 integer programming solvers tend to find the
optimal solution, or at least some near-optimal solutions, at the beginning of the search,
although it requires many more iterations to explore the whole search space. The number
of iterations performed by the solver can be provided by the user as a parameter to limit
the search space. We obtained suboptimal solutions for Baro, Erlebacher, x42, and
Shallow in less than 10 minutes. The estimated performance of these solutions is higher
than 85% of the optimal estimated performance.
6.2 Accuracy of the Predictions
In order to test the accuracy of the predictions given by our model, some of the solutions
predicted were compared to the actual execution of the parallelized program on a Silicon
Graphics Origin 2000 with up to 32 processors. The Origin 2000 is a cache-coherent
non-uniform memory access multiprocessor with physically distributed memory, and a
high capacity 4 Mbyte cache memory for each processor. We distributed the arrays across
the caches, so that caches might act as a first level distributed memory. In this case, cache
memory accesses with higher latency. The programs selected
for these experiments are the Adi integration kernel, the Erlebacher program, the
Shallow benchmark, and the routine Rhs. As before, for the purpose of this evaluation,
programs Erlebacher and Shallow were inlined, and routine Rhs was transformed
into a program. Profiling information was obtained by executing the sequential code on
a single processor of the same Origin 2000 system. In all predictions we assumed a
bandwidth of 100 Mbytes per second.
We performed several experiments, trying different data mapping strategies and changing
the number of processors. Our framework is implemented as part of another automatic
data distribution tool (DDT [3]). this generates a file with the linear 0-1 integer programming
problem, that is the input to a general purpose solver. From the output of
this solver, we manually generate the parallel code. In order to control the scheduling of
the loop iterations according to the owner-computes rule, we strip-mined the distributed
loops. Details about these loop transformations can be found in [12]. The parallel code is
compiled using the native MIPSpro F77 compiler, but all compiler parallel optimizations
were disabled to avoid any change in our parallelization strategy. In order to generate the
model, all data movement costs were estimated assuming the caching effects, i.e., data is
transferred in cache lines.
In the first experiment, we compare the optimal solution suggested by our tool for the
set of selected programs with the actual execution on the Origin 2000 system, trying
different data mapping strategies and different numbers of processors, for each program.
With this experiment we intend to show that the proposed solution actually yields the
best result (among the executed strategies), and that predictions are close to the actual
measured executions.
The Adi program defines a two-dimensional data space and consists of a sequence of
initialization loops, followed by an iterative loop (with 6 phases) that performs the com-
putation. In each loop iteration, forward and backward sweeps along rows and columns
are done in sequence. The solution suggested by our tool is a dynamic one-dimensional
data mapping, distributing arrays by rows in the first computation flow and by columns
in the second computation flow. The resulting predicted parallel times of the optimal
solution using 2, 4, 8, 16, and 32 processors can be seen in the dotted line of Figure 8.
The solid lines show the measured execution times for the static one-dimensional row and
column distributions, and the dynamic one-dimensional strategy. The predicted parallel
times were performed using a profiled sequential execution time of 13.793 seconds. All
times in the Figure are expressed in seconds. Note that all predictions are within a 10%
of the actual measured execution times for the dynamic strategy (except in the execution
with processors, where the code falls into false sharing when arrays are distributed by
rows).
Number of Processors515
Execution
Time
Measured 1st dim
Measured 2nd dim
Measured dynamic
Predicted

Figure

8: Predicted and measured execution times for Adi.
The Erlebacher program is a 3D tridiagonal solver based on the Adi integration
kernel. The inlined program consists of 38 phases that perform symmetric forward and
backward computations along each dimension of four main three-dimensional arrays. In
[10] the authors point out that the best performance achieved for this program was obtained
with static two-dimensional distributions and pipelining computations. However,
pipelining computations are not considered in our model. Therefore the parallelization
strategy suggested by our tool is to distribute the third dimension of the arrays in the
first and second computation flows, and to redistribute before the third computation flow,
leaving the second dimension of the arrays distributed. The dotted line in Figure 9 shows
the predicted parallel times using 2, 4, 8, 16, and processors. Predicted parallel times
for a problem size 128 \Theta 128 \Theta 128 were performed using a profiled sequential execution
time of 5.855 seconds. The solid lines show the measured parallel times for the static
distribution of the first, second, and third dimensions, and the dynamic parallelization
strategy. Note that the actual measured execution times of the dynamic strategy are
within 10% of our predicted times.
Number of Processors26
Execution
Time
(secs) Measured 1st dim
Measured 2nd dim
Measured 3rd dim
Measured dynamic
Predicted

Figure

9: Predicted and measured execution times for Erlebacher.
The Shallow water equations model defines a set of 512 \Theta 512 sized arrays. The
inlined program consists of 27 phases, most of them within an iterative loop of NCYCLES
iterations. The optimal data mapping strategy suggested by the tool is the static one-dimensional
column distribution of all the arrays. The resulting predicted parallel times
of the optimal data distribution strategy can be seen in Figure 10, together with the
measured parallel times for the static row and column data distributions. Predicted
parallel times were computed using a profiled sequential execution time of 45.152 seconds.
Note that predicted times in this example are within 5% of the actual measured execution
times, although all executions obtain a similar performance.
Number of Processors103050
Execution
Time
Measured 1st dim
Measured 2nd dim
Predicted

Figure

10: Predicted and measured execution times for Shallow.
The Rhs routine defines a set of 5 \Theta 64 \Theta 64 \Theta 64 four-dimensional arrays. It consists
of four phases (36 loops) performing flux differences in the second, third and fourth di-
rections. The solution suggested by our tool is a dynamic one-dimensional data mapping,
where arrays are distributed in the fourth dimension in the first three phases, and in the
third dimension in the fourth phase. The predicted parallel times of the optimal solution,
together with the measured times for the static distribution of the second, third, and
fourth dimensions, and the dynamic strategy are shown in Figure 11. Predicted parallel
times were computed using a profiled sequential execution time of 165.413 seconds.
In our last experiment, we forced our tool to generate a fixed strategy for the Adi code,
in order to analyze the performance predictions with different data distribution strategies.
In

Table

5 the predicted and measured execution times (in seconds) of several strategies
are listed. Row and Col correspond to the static one-dimensional row and column
Number of Processors50150
Execution
Time
(secs) Measured 2nd dim
Measured 3rd dim
Measured 4th dim
Measured dynamic
Predicted

Figure

11: Predicted and measured execution times for Rhs.
distributions respectively. Dyn is the dynamic one-dimensional strategy, and 2-d is the
squared static two-dimensional data distribution strategy. All these implementations were
predicted and executed with a different number of processors, ranging from 2 to 32.
Predicted 10.82 9.32 8.58 8.20 8.02
ROW Measured 9.90 8.87 8.75 8.22 15.11
Predicted 9.88 7.91 6.93 6.43 6.19
COL Measured 9.97 7.90 6.93 6.70 6.64
Predicted 7.68 4.03 2.07 1.05 0.52
DYN Measured 6.85 4.00 2.26 1.18 1.85
Predicted 9.88 6.89 3.94 3.48 1.88
Measured 9.97 6.63 4.13 3.73 2.19

Table

5: Comparison of measured and predicted execution times for row, column, dynamic,
and two-dimensional data mappings with the Adi code.
Predictions were performed using a profiled sequential time for the Adi code of 13.793
seconds. Note that all predictions for each data mapping strategy are within 10% of the
actual measured parallel execution time (except codes that fall into false sharing 3 ).
3 False sharing occurs in executions with processors when arrays are distributed by rows (one-
Conclusions
Automatic data distribution tools in the context of distributed memory multiprocessor
systems usually decompose the parallelization problem into three independent steps:
alignment, distribution, and remapping; however, these steps are not really independent.
In addition, most algorithms used to solve each of these steps are based on heuristics. The
work presented in this paper represents the first automatic data mapping and parallelization
prototype that provides an optimal solution, according to our cost and compilation
models. The contributions of this proposal with respect to the previous work are:
ffl Definition of a model that represents the whole data mapping problem. this allows
the alignment, distribution, and remapping problems to be solved within a single
step.
ffl Formulation of a minimal cost path problem that provides a solution to the model.
The use of linear 0-1 integer programming techniques guarantee that the solution
provided is optimal.
Our framework is based on the definition of a single data structure, named the
Communication-Parallelism Graph (CPG), that integrates all the data movement and
parallelism related information inherent in each phase of the program, plus additional information
denoting remapping possibilities between them. The data mappings considered
in the framework can be one or two-dimensional, static or dynamic, BLOCK or CYCLIC, and
take into account the effects of control flow statements between phases. Our cost model
is based on profiling information obtained from a previous serial execution.
Experiments show that the cost model is fairly accurate (usually within 10%) in predicting
the performance of different data mapping strategies. In addition, we have shown
the complexity of our approach in terms of computation time spent to find an optimal
dimensional row distribution, and dynamic distribution in phases where arrays are distributed by rows).
solution. Although in the one-dimensional case the time required to find an optimal solution
to our benchmark set is a matter of seconds, in the general two-dimensional case this
time can increase up to two hours, trading off the quality of the solution and the computation
time of the analysis. However, we have shown that these times can be dramatically
reduced if near-optimal solutions are accepted. In this case our model can succumb to
the same problem as previous work, since some data mappings would be missed from the
search space. In summary, integrating sufficient information to solve automatic data mapping
in a single graph is ambitious; however, an expensive technique can be an important
tool if it is applied selectively.
A large number of additional aspects should be considered in the model definition
in order to extend the capabilities of the framework, and consequently the quality of
the solutions generated. As part of our future work we plan to include in the model
information that reflects data movement optimizations, such as detection and elimination
of redundant communication and overlapping of communication and computation, and
information that estimates the cache effects of data distributions. In addition to this, the
development of an inter-procedural analysis module may reduce the computation time
required to find an optimal solution. The set of solutions considered in our model is
currently limited to those that generate either parallel or sequential loops. As shown in
[4, 22, 10], better solutions can be obtained by handling pipelining computations. this
feature could be modeled in our framework through appropriately weighted hyperedges.



--R

Automatic Computation and Data Decomposition for Multiprocessors.
Global optimizations for parallelism and locality on scalable parallel machines.

Data distribution and loop parallelization for shared-memory multiprocessors
Tools and techniques for automatic data layout: A case study.
A static performance estimator to guide data partitioning decisions.

The alignment-distribution graph
Array distribution in data-parallel programs
Towards compiler support for scalable parallelism using multipartitioning.
Automatic data decomposition for message-passing machines
Automatic Data Distribution for Massively Parallel Processors.
Dynamic data distribution with control flow analysis.
A framework for automatic dynamic data mapping.
Automatic Data Partitioning on Distributed Memory Multicomputers.
Programming for parallelism.
Automatic data layout for High Performance Fortran.
The High Performance Fortran Handbook.

Automatic Data Layout for Distributed Memory Machines.
Optimal and near-optimal solutions for hard compilation problems
Fortran red - a retargetable environment for automatic data layout
Efficient algorithms for data distribution on distributed memory parallel computers.
Index domain alignment: Minimizing cost of cross-referencing between distributed arrays
Compiling communication-efficient programs for massively parallel machines
John Wiley
Automatic selection of dynamic partitioning schemes for distributed-memory multicomputers
An Optimizing Fortran D Compiler for Distributed-Memory Machines
--TR

--CTR
Minyi Guo , Yi Pan , Zhen Liu, Symbolic Communication Set Generation for Irregular Parallel Applications, The Journal of Supercomputing, v.25 n.3, p.199-214, July
Skewed Data Partition and Alignment Techniques for Compiling Programs on Distributed Memory Multicomputers, The Journal of Supercomputing, v.21 n.2, p.191-211, February 2002
Bjorn Franke , Michael F. P. O'Boyle, A Complete Compiler Approach to Auto-Parallelizing C Programs for Multi-DSP Systems, IEEE Transactions on Parallel and Distributed Systems, v.16 n.3, p.234-245, March 2005
loop parallelization;linear 0-1 integer programming;distribution;distributed-memory multiprocessor;automatic data mapping;performance prediction;redistribution;alignment