On Supernode Transformation with Minimized Total Running Time.
AbstractWith the objective of minimizing the total execution time of a parallel program on a distributed memory parallel computer, this paper discusses how to find an optimal supernode size and optimal supernode relative side lengths of a supernode transformation (also known as tiling). We identify three parameters of supernode transformation: supernode size, relative side lengths, and cutting hyperplane directions. For algorithms with perfectly nested loops and uniform dependencies, for sufficiently large supernodes and number of processors, and for the case where multiple supernodes are mapped to a single processor, we give an order n polynomial whose real positive roots include the optimal supernode size. For two special cases, 1) two-dimensional algorithm problems and 2) n-dimensional algorithm problems, where the communication cost is dominated by the startup penalty and, therefore, can be approximated by a constant, we give a closed form expression for the optimal supernode size, which is independent of the supernode relative side lengths and cutting hyperplanes. For the case where the algorithm iteration index space and the supernodes are hyperrectangular, we give closed form expressions for the optimal supernode relative side lengths. Our experiment shows a good match of the closed form expressions with experimental data.
Introduction
Supernode partitioning is a transformation technique that groups a number of iterations
in a nested loop in order to reduce the communication startup cost. This paper
addresses the problem of finding the optimal grain size and shape of the supernode
transformation so that the total running time, which is the sum of communication
time and computation time, is minimized.
A problem in distributed memory parallel systems is the communication startup
cost, the time it takes a message to reach transmission media from the moment of its
This research was supported in part by the National Science Foundation under Grant CCR-9502889
and by the Clare Boothe Luce Assistant Professorship from Henry Luce Foundation.
y Supported by HaL Computer Systems, 1315 Dell Ave., Campbell, CA 95008.
initiation. The communication startup cost is usually orders of magnitude greater
than the time to transmit a message across transmission media or to compute data in
a message. Supernode transformation has been studied [4, 5, 6, 7, 8, 9, 15] to reduce
the number of messages sent between processors by grouping multiple iterations into
supernodes. 1 After the supernode transformation, several iterations are grouped into
one supernode and this supernode is assigned to a processor as a unit for execution.
The data of the iterations in the same supernode, which need to be sent to another
processor, are grouped as a single message so that the number of communication
startups is reduced from the number of iterations in a supernode to one. A supernode
transformation is characterized by the hyperplanes which slice the iteration index
space into parallelepiped supernodes, the grain size of the supernode and the relative
lengths of the sides of a supernode. All the three factors mentioned above affect the
total running time. A larger grain size reduces communication startup cost more,
but may delay the computation of other processors waiting for the message. Also,
a square supernode may not be as good as a rectangular supernode with the same
grain size. In this paper, how to find an optimal grain size and an optimal relative
side length vector, or an optimal shape of a supernode is addressed.
Algorithms considered in this paper are nested loops with uniform dependences
[12]. Such an algorithm can be described by its iteration index space consisting of all
iteration index vectors of the loop nest and a dependence matrix consisting of all uniform
dependence vectors as its columns. Two communication models are considered.
In the one parameter communication model, communication cost is approximated by
a constant startup penalty and in the two parameter model, communication cost is
a function of the startup penalty and the message size. The first model can be used
for the case where the startup penalty dominates the communication cost and the
second model is for the case where the message size is too large to be ignored.
The approach in this paper is as follows. Unlike other related work where a supernode
transformation is specified by n side lengths of the parallelepiped supernode, and
the n partitioning hyperplanes, a supernode transformation in this paper is specified
by a grain size g of a supernode, the relative side length vector R which describes the
side lengths of a supernode relative to the supernode size, and n partitioning hyper-planes
described by matrix H which contains the normal vectors of the n independent
hyperplanes as rows. This approach allows us, for given partitioning hyperplanes, to
find the optimal grain size and the optimal shape separately in our formulation.
Based on our formulation, we derived a closed form analytical expression for the optimal
supernode size for the one parameter model and the two parameter model with
doubly nested loops. A closed form expression for the optimal relative length vector
is also provided for the one parameter model with constant bounded loop iteration
space.
The rest of the paper is organized as follows. Section 2 presents necessary defi-
nitions, assumptions, terminology, and models. Section 3 discusses a general model
transformation is conceptually similar to LSGP (Locally Sequential Globally Parallel) partitioning
[4, 7, 8, 9, 11, 15], where a group of iterations is assigned to a single processing element for sequential
execution while different processing elements execute respectively assigned computations in parallel.
of the total running time and how its components depend on different parameters.
Section 4 briefly presents our results on how to find the optimal grain size and shape
of a supernode transformation assuming one parameter communication model. Section
5 discusses how to find the optimal supernode size assuming two parameter
communication model where communication cost is modeled as an affine function of
the amount of data to be transferred. Section 6 briefly describes related work and
the contribution of this work compared to previous work. Section 7 concludes this
paper.
Basic definitions, models and assumptions
In a distributed memory parallel computer, each processor has access only to its
local memory and is capable of communicating with other processors by passing
messages. The cost of sending a message can be modeled by t s s is the
startup time, b is the amount of data to be transmitted, and t t is the transmission
rate, i.e., the transmission time per unit data. The computation speed of a single
processor in a distributed memory parallel computer is characterized by the time it
takes to compute a single iteration of a nested loop. This parameter is denoted by
t c .
We consider algorithms which consist of a single nested loop with uniform dependences
[12]. Such algorithms can be described by a pair (J; D), where J is an iteration
index space and D is an n \Theta m dependence matrix. Each column in the dependence
matrix represents a dependence vector. We assume that m - n, matrix D has full
rank (which is equal to the number of loop nests n), and the determinant of the Smith
normal form of D is equal to one. As discussed in [13], if the above assumptions are
not satisfied, then the iteration index space J contains independent components and
can be partitioned into several independent sub-algorithms with the above assumptions
satisfied. Furthermore, we assume that only true loop carried dependences [14]
are included in matrix D since only those dependences cause communication, while
other types of dependences can be eliminated using known transformation techniques
(e.g. variable renaming).
In a supernode transformation, the iteration space is sliced by n independent families
of parallel equidistant hyperplanes. These hyperplanes partition the iteration
index space into n-dimensional parallelepiped supernodes. Hyperplanes can be defined
by the normal vectors orthogonal to each of the hyperplanes. The n \Theta n matrix
containing the n normal vectors as rows is denoted by H which is of full rank because
these hyperplanes are independent. Supernodes can be defined by matrix H
and distances between adjacent parallel hyperplanes. Let l i be the distance of two
adjacent hyperplanes with normal vector H i and the supernode side length vector
The grain size, or supernode volume, denoted by g, is defined as
the number of iterations in one supernode. The supernode volume and the length l i
are related as follows:
Y
l i
depends on the angles between hyperplanes. For example, when
supernodes are cubes, 1. We also define the supernode relative side length vector,
s
and clearly
Y
Vector R describes side lengths of a supernode relative to the supernode size. For
example, then the supernode is a square. A supernode transformation
is completely specified by H, R, and g, and denoted by (H; R; g).
After the supernode transformation, we obtain a new dependence structure (J s ; D s )
where each node in the supernode index space J s is a supernode. The supernode
dependence matrix D s in general is different from D. As discussed in [6], partitioning
hyperplanes defined by matrix H have to satisfy HD - 0, i.e., each entry in the
product matrix is greater than or equal to zero, in order to have (J s ; D s ) computable.
That is, all dependence vectors in D s are contained in a convex cone. Matrix
is a matrix of extreme vectors of dependence vectors. In other words, each dependence
vector d i
in D s can be expressed as a non-negative linear combination of columns
in E. Also, the n columns of E are the n vectors collinear with the n sides of the
parallelepiped supernode.
For an algorithm A = (J; D), a linear schedule [12] is defined as oe
that
disp(-)
Jg. A linear schedule assigns each node j 2 J an execution step
with dependence relations respected. The length of a linear schedule is defined as
Note that j 1
for which oe - (j 1
is maximum are always extreme points
in the iteration index space.
The execution of an algorithm (J; D) is as follows. We apply a supernode transformation
(H; R; g) and obtain (J s ; D s ). An optimal linear schedule - can be found for
execution based on the linear schedule alternates between computation
phases and communication phases. That is, in step i, we assign supernodes
with the same oe - to available processors. After each processor finishes all the
computations of a supernode, processors communicate to pass messages. After the
communication is done, we go to step i+1. The total amount of data to be transferred
in a communication phase by a single processor is denoted by V (g; R). Hence, the
total running time of an algorithm depends on all of the following: (J; D), H, g, R, -,
T be the total running time. The problem of finding an optimal
supernode transformation is an optimization problem of finding parameters H,
g, R, and -, such that the total running time, T ((J; D); H;

Figure

1. The iteration index space before supernode transformations.
is minimized. This paper addresses the problems of how to find an optimal grain
size g and optimal supernode relative length vector R. How to find an optimal linear
schedule for (J s ; D s ) can be found in [1, 12]. How to find an optimal H in general
remains open, and discussed in [6, 7].
Once the supernode partitioning parameters are chosen, the optimal number of
processors in a system can be determined as the maximum number of independent
supernodes in a computation phase, which is the maximum number of supernodes to
which the linear schedule oe - assigns the same value:
where i is the constant assigned by the linear schedule oe - to all supernodes in the
same phase, and J s is the supernode index space.
Example 2.1 To illustrate the notions introduced above, we show an example
of supernode transformation applied to an algorithm and how it affects algorithm's
total running time. Let's assume t 0:1-s. Consider
algorithm (J; D) where
The algorithm consists of two loops with three dependence vectors:
and
. The optimal linear schedule vector for this algorithm is 1). The length
of the schedule is -

Figure

1 shows the iteration index
space with linear schedule wave fronts. If a supernode consists of only one iteration,
then, in the execution of the algorithm, there are 299 computation phases and 298
communication phases. One computation phase takes t 10-s. Assuming that each
iteration produces one eight byte data item, and that there are 50 bytes of header
overhead, communication time takes t s 305:8-s. The

Figure

2. The supernode index space where each supernode is a square containing
four iterations.
total running time is: processors.
The sequential running time is T 200ms.
Consider now a supernode transformation applied to the algorithm. Let the hyperplane
matrix
Matrix H defines two families of lines parallel to the two axes. For this matrix H,
because the two lines are orthogonal. Let
the length vector and each supernode is a square containing four iterations.

Figure

1 shows one supernode outlined with a dashed square. The supernode index
space and dependence matrix are then J
which is shown in Figure 2 and D D. The optimal linear schedule vector for
this (J s ; D s ) is and the schedule length is -

Figure

shows supernode index space with the linear schedule wave fronts. The
computations of one supernode take gt 40-s. Communication in one phase takes
300+0:1 \Theta assuming a processor has to send two data items to the
neighboring processor. The total running time is
with 50 processors. In this simple example speedup between T 1 and T 2 is close to 2.
Note that supernode transformation parameters are chosen arbitrarily and are not
optimal. Later, it is shown that the total running time can be improved further by
an optimal solution.
3 The total running time
This section discusses a total running time model and how its components depend
on the grain size and shape of a supernode transformation.
ct
@
@
\Theta
\Theta
\Theta
schedule
vector
which
p and q
distance size shape size
shape shape size

Figure

3. Dependences between the total running time components and the supernode
size and shape.
The total running time is a sum of the computation time and the communication
time which are multiples of the number of phases in the execution. The linear
schedule length, as defined in the previous section, corresponds to the number of communication
phases in the execution. The number of computation phases is, usually,
one more than the number of communication phases. Supernode transformations often
generate supernodes containing fewer iterations at the boundary of index space.
Thus, the first and/or the last computation phases are often shorter than other computation
phases. For this reason, we will assume that the number of computation
phases and the number of communication phases are equal, and are equal to the
linear schedule length, denoted by P . The total running time is then the sum of the
computation time T comp and communication time T comm in one phase, multiplied by
the number of phases

Figure

3 shows how the components in the total running time depend on the
supernode grain size and shape. Computation time T comp depends on supernode
size g only. Communication time T comm in a single communication phase depends
on c, the number of different neighbors which a processor has to send a message
to, and V (g; R), the total amount of data transmitted by a single processor in a
communication phase. The number of messages c depends on H, the algorithm,
and how supernodes are assigned to processors. V , in general, depends on both the
supernode size and shape. The scheduling length P is a function of the schedule vector
(a point in J such that (a point in J such that
and the distance between p and q. As proven later in this section, -,
p and q depend on the shape only. In other words, for two supernode transformations
(as relative points of the supernode index space)
should be the same with possible different distances between p and q.
Consider algorithm A space J s and dependence
matrix D s obtained by applying a supernode transformation (H; R; g) to algorithm
D). According to [6], in a valid supernode transformation with hyperplanes
H, all dependence vectors d 2 D should be contained in the convex cone of the n
extreme directions forming the parallelepiped supernode. Hence, if the supernode
grain size is reasonably large, and the components of d 2 D are reasonably small,
then all dependence vectors d 2 D, if originating at the extreme point of the convex
cone of the parallelepiped supernode, should be contained inside the parallelepiped
supernode. Therefore, it is reasonable to assume in this paper that the components
of the dependence matrix D s are 0; 1, or \Gamma1. The following lemma gives sufficient
conditions for this assumption to be true:
Lemma 3.1 Components of dependence matrix D s , in the transformed algorithm,
the j-th component of vector Hd.
Consider two supernode transformations, (H; R; with the same
H and R, and different supernode sizes, g 1 and g. Let J s1 and J s be the corresponding
supernode index spaces. Lemma 3.2 shows how an index space changes as the
supernode size changes.
Lemma 3.2 Let J bg be the supernode index set with g 1 and J s be
the supernode index set with g. Then
s
where n is the number of loop nests in the original algorithm.
The dependence matrix does not change as supernode size changes from g 1 to g.
This follows from the assumption that components of dependence vectors in transformed
algorithm take values from f0; 1; \Gamma1g and from the fact that supernode shape
defined by H and R does not change. The following lemma shows that an optimal
linear schedule does not change as supernode size g changes.
Lemma 3.3 Optimal linear schedule vectors for two supernode transformations
which differ only in supernode size, are identical.
The proofs of the above three lemmas can be found in [2].
4 One parameter communication model
In this section we briefly summarize how to find the optimal grain size g and relative
length vector R when the one parameter communication model is used. This model
applies to the cases where message startup time is much larger than data transmission
time, and data transmission can be overlapped by other useful processing. In this
case, the total running becomes T ct s ). Proofs of theorems and detailed
derivation can be found in [2].
Theorem 4.1 For an algorithm (J; D) and supernode transformation with H and
R, the optimal supernode size is:
ct s
The shape of supernodes is defined by two supernode transformation parameters:
H and R. For a given H and an optimal grain size g o , the problem of finding an
optimal R for general cases is formulated as a nonlinear programming problem [2].
The Optimal relative length vector R and optimal linear schedule vector are given in
the following for a special case where index set J is constant-bounded (loop bounds
are constant), and the partitioning hyperplane matrix I, the identity
matrix, i.e., both the index space and the supernodes are hyperrectangles. Also, let
1 be a vector whose components are all one.
Theorem 4.2 Consider algorithm (J; D) where
supernode transformation (H; R; g) and transformed algorithm (J s ; D s ). If
I, the identity matrix, and I ' D s , then an optimal linear schedule vector, -, and
supernode relative length vector, are given by:
or
The above theorem implies that the optimal supernode shape is similar to the
shape of the original index set J so that the resulting supernode index set J s is a
hypercube with equal sides.
As derived in [2], the optimal grain size for the algorithm in Example 2.1 is
and the optimal relative length vector is
2).

Table

shows how the total
running time varies for different supernode grain sizes with a fixed square supernode
shape. The total running time is the shortest at the optimal grain size. Further
improvement in the total running time is achieved when an optimal relative side
length vector is used, as shown in Table 2 where the total running time is computed
for different supernode relative vectors with the supernode size close to the optimal.
Note that the values for supernode size and supernode side lengths computed
based on Theorems 4.1 and 4.2 may not be integral. We should choose approximate
integral values for supernode side lengths, L, such that they are close to the optimal
values and the volume of the resulting supernode is close to the optimal grain size.
A simple heuristic is to use approximate values for L such that the volume of the
resulting supernode is greater than or equal to g o , because the total running time
increases faster for values of g ! g o and slower for values g ? g o . Alternatively, the
total running time can be evaluated for different approximate values and the best
approximation should be used.
L Processors Time

Table

1. Total running time for different supernode sizes and square supernode
shape (or close to square).
L Processors Time
28 ( 4

Table

2. Total running time for different supernode shapes and supernode sizes
close to 30.
5 Two parameter communication model
This section discusses how to find the optimal grain size and shape when the two
parameter communication model is used. In this model, the communication cost is
modeled by an affine function of the amount of data to be transferred by a single
processor in a communication phase.
The amount of data to be transferred V (g; R), in general, is a complicated function
of both the supernode size and supernode shape [7]. To simplify the problem, we
consider the amount of data to be transferred as a function of the supernode size only.
Intuitively, neighboring supernodes may need data from the surface of a supernode.
In general, the amount of data should be proportional to the area of surfaces of all
dimensionalities of a supernode. Thus we use the following expression as the amount
of data to be transferred:
where ff's are constant. Hence the amount of data to be transferred depends on the
supernode size only and the total running time of supernode transformation (H; R; g)
is:
ct
According to Lemmas 3.1, 3.2 and 3.3, in section 3, the number of phases P
where P g1 is the scheduling length of supernode transformation (H; R; g 1 ).
To find the optimal supernode size, we solve equation @T
s
ct
@g
@g
ct
@g
ct
)ct
ct
Substituting
ct
ct
A real positive root of equation (6) to the power n will give the optimal supernode
size.
In case of two dimensional algorithm, 2, the optimal supernode size becomes:
ct s
Example 5.1 For the algorithm in Example 2.1, assuming V
g,
with the optimal supernode size is g
Taking approximate supernode size 5), we get supernode computation time
of 309-s and the
total running time of T and we need 20 processors.

Table

3 shows the total running time computed for different supernode sizes. It shows
that the total running time is shorter for supernode sizes closer to the optimal value.
Since we assumed the data amount to be transferred depend on the supernode
size only, an optimal supernode shape can be computed using the nonlinear program
discussed for the case of constant communication time. The nonlinear program and
its derivation is given in [2].
L Processors Time
34.3

Table

3. Total running time for different supernode sizes and square supernode
shape (or close to square).
6 Related work
In this section we give a brief overview of previous related work. Irigoin and Triolet
[4] proposed the supernode partitioning technique for multiprocessors in 1988. The
idea was to combine multiple loop iterations in order to provide vector statements,
parallel tasks and data reference locality. Ramanujam and Sadayappan [6] studied
tiling multidimensional iteration spaces for multiprocessors. They showed the equivalence
between the problem of finding a partitioning hyperplane matrix H, and the
problem of finding a cone for a given set of dependence vectors, i.e., finding a matrix
of extreme vectors E. They presented an approach to determining partitioning
hyperplanes to minimize communication volume. They also discussed a method for
finding an optimal supernode size. Reference [7] discusses the choice of cutting hyper-planes
and supernode shape with the goal of minimizing the communication volume
in a scalable environment. It includes a very good description of the tiling technique.
In [5], the optimal tile size is studied under different model and assumptions. It is
assumed that an N 1 \Theta ::: \Theta N n hypercube index space is mapped to a P 1 \Theta ::: \Theta P
processor space and the optimal side lengths of the hypercube tile are given as N i
for certain kind of dependence structure. In [8], an approach to optimizing tile size
and shape in two dimensional algorithms, based on the space-time mapping used in
systolic synthesis. In [2], we give a detailed analysis of optimal supernode size and
shape in a model with constant communication time.
Compared to the related work, our optimization criterion is to minimize the total
running time, rather than communication volume or ratio between communication
and computation volume, further we used a different approach where we specify a
supernode transformation by a grain size of supernodes, the relative side length vector
R and n partitioning hyperplanes so that the three variables become independent
(their optimal values are interdependent in general though).
Hence our method can be applied to find the optimal grain size for any uniform
dependence algorithm with any partitioning hyperplanes. After we have the optimal
grain size, we can determine the optimal shape and the partitioning hyperplanes.
7 Conclusion
In this paper, how to find the optimal supernode size and shape is studied, in the
context of supernode transformations, with the goal of minimizing the total running
time. A general model of the total running time is described. We derived closed form
analytical expressions for the optimal supernode size for the one parameter model
and the two parameter model with doubly nested loops. A closed form expression for
the optimal relative length vector is also provided for the one parameter model with
constant bounded loop iteration space. A nonlinear program formulation which can
be solved by numeric methods is provided for general cases. The results can be used
by a parallelizing compiler for a distributed computer system to decide the grain size
and shape when breaking a task into subtasks.



--R

"Linear Scheduling is Close to Optimality,"

"Modeling Optimal Granularity When Adapting Systolic Algorithms to Transputer Based Supercomputers,"
"Supernode Partitioning,"
"Optimal Tile Size Adjustment in Compiling General DOACROSS Loop Nests,"
"Tiling Multidimensional Iteration Spaces for Multicom- puters,"
"(Pen)-Ultimate Tiling"
"Optimal Tiling,"
"Automatic Blocking of Nested Loops"
"Evaluating Compiler Optimizations for Fortran D,"
New Jersey
"Time Optimal Linear Schedules for Algorithms With Uniform Dependencies,"
"Independent Partitioning of Algorithms with Uniform Depen- dencies,"
Supercompilers for Parallel and Vector Computers
"More Iteration Space Tiling,"
--TR

--CTR
Panayiotis Tsanakas , Nectarios Koziris , George Papakonstantinou, Chain Grouping: A Method for Partitioning Loops onto Mesh-Connected Processor Arrays, IEEE Transactions on Parallel and Distributed Systems, v.11 n.9, p.941-955, September 2000
Jingling Xue , Wentong Cai, Time-minimal tiling when rise is larger than zero, Parallel Computing, v.28 n.6, p.915-939, June 2002
Maria Athanasaki , Aristidis Sotiropoulos , Georgios Tsoukalas , Nectarios Koziris, Pipelined scheduling of tiled nested loops onto clusters of SMPs using memory mapped network interfaces, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-13, November 16, 2002, Baltimore, Maryland
N. Koziris , A. Sotiropoulos , G. Goumas, A pipelined schedule to minimize completion time for loop tiling with computation and communication overlapping, Journal of Parallel and Distributed Computing, v.63 n.11, p.1138-1151, November
Georgios Goumas , Nikolaos Drosinos , Maria Athanasaki , Nectarios Koziris, Automatic parallel code generation for tiled nested loops, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
R. Andonov , S. Balev , S. Rajopadhye , N. Yanev, Optimal semi-oblique tiling, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.153-162, July 2001, Crete Island, Greece
Rashmi Bajaj , Dharma P. Agrawal, Improving Scheduling of Tasks in a Heterogeneous Environment, IEEE Transactions on Parallel and Distributed Systems, v.15 n.2, p.107-118, February 2004
Georgios Goumas , Nikolaos Drosinos , Maria Athanasaki , Nectarios Koziris, Message-passing code generation for non-rectangular tiling transformations, Parallel Computing, v.32 n.10, p.711-732, November, 2006
Edin Hodzic , Weijia Shang, On Time Optimal Supernode Shape, IEEE Transactions on Parallel and Distributed Systems, v.13 n.12, p.1220-1233, December 2002
Maria Athanasaki , Aristidis Sotiropoulos , Georgios Tsoukalas , Nectarios Koziris , Panayiotis Tsanakas, Hyperplane Grouping and Pipelined Schedules: How to Execute Tiled Loops Fast on Clusters of SMPs, The Journal of Supercomputing, v.33 n.3, p.197-226, September 2005
Peizong Lee , Zvi Meir Kedem, Automatic data and computation decomposition on distributed memory parallel computers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.1, p.1-50, January 2002
distributed memory multicomputer;supernode partitioning;minimizing running time;parallelizing compilers;tiling