Mesh Partitioning for Efficient Use of Distributed Systems.
Mesh partitioning for homogeneous systems has been studied extensively; however, mesh partitioning for distributed systems is a relatively new area of research. To ensure efficient execution on a distributed system, the heterogeneities in the processor and network performance must be taken into consideration in the partitioning process; equal size subdomains and small cut set size, which results from conventional mesh partitioning, are no longer the primary goals. In this paper, we address various issues related to mesh partitioning for distributed systems. These issues include the metric used to compare different partitions, efficiency of the application executing on a distributed system, and the advantage of exploiting heterogeneity in network performance. We present a tool called PART, for automatic mesh partitioning for distributed systems. The novel feature of PART is that it considers heterogeneities in the application and the distributed system. Simulated annealing is used in PART to perform the backtracking search for desired partitions. While it is well-known that simulated annealing is computationally intensive, we describe the parallel version of simulated annealing that is used with PART. The results of the parallelization exhibit superlinear speedup in most cases and nearly perfect speedup for the remaining cases. Experimental results are also presented for partitioning regular and irregular finite element meshes for an explicit, nonlinear finite element application, called WHAMS2D, executing on a distributed system consisting of two IBMSPs with different processors. The results from the regular problems indicate a 33 to 46 percent increase in efficiency when processor performance is considered as compared to the conventional even partitioning. The results indicate a 5 to 15 percent increase in efficiency when network performance is considered as compared to considering only processor performance; this is significant given that the optimal improvement is 15 percent for this application. The results from the irregular problem indicate up to 36percent increase in efficiency when processor and network performance are considered as compared to even partitioning.
Introduction
Distributed computing has been regarded as the future of high performance computing. Nation-wide
high speed networks such as vBNS [25] are becoming widely available to interconnect high-speed
computers, virtual environments, scientific instruments and large data sets. Projects such
as Globus [15] and Legion [20] are developing software infrastructure that integrates distributed
computational and informational resources. In this paper, we present a mesh partitioning tool for
distributed systems. This tool, called PART, takes into consideration the heterogeneity in processors
and networks found in distributed systems as well as heterogeneities found in the applications.
Mesh partitioning is required for efficient parallel execution of finite element and finite difference
applications, which are widely used in many disciplines such as biomedical engineering, structural
mechanics, and fluid dynamics. These applications are distinguished by the use of a meshing
procedure to discretize the problem domain. Execution of a mesh-based application on a parallel
or distributed system involves partitioning the mesh into subdomains that are assigned to individual
processors in the parallel or distributed system.
Mesh partitioning for homogeneous systems has been studied extensively [2, 4, 14, 31, 36, 37, 41];
however, mesh partitioning for distributed systems is a relatively new area of research brought about
by the recent availability of such systems. To ensure efficient execution on a distributed system, the
heterogeneities in the processor and network performance must be taken into consideration in the
partitioning process; equal size subdomains and small cut set size, which results from conventional
mesh partitioning, are no longer desirable. PART takes advantage of the following heterogeneous
system features: (1) processor speed; (2) number of processors; (3) local network performance; and
wide area network performance. Further, different finite element applications under consideration
may have different computational complexity, different communication patterns, and different
element types, which also must be taken into consideration when partitioning.
In this paper, we discuss the major issues in mesh partitioning for distributed systems. In
particular, we identify a good metric to be used to compare different partitioning results, present
a measure of efficiency for a distributed system, and discuss optimal number of cut sets for remote
communication. The metric used with PART to identify good efficiency is estimated execution
time.
We also present a parallel version of PART that significantly improves performance of the
partitioning process. Simulated annealing is used in PART to perform the backtracking search for
desired partitions. However, it is well known that simulated annealing is computationally intensive.
In the parallel PART, we use the asynchronous multiple Markov chain approach of parallel simulated
annealing [21]. PART is used to partition six irregular meshes into 8, 16, and 100 subdomains using
up to 64 client processors on an IBM SP2 machine. The results show superlinear speedup in most
cases and nearly perfect speedup for the rest. The results also indicate that the parallel version of
PART produces partitions consistent with the sequential version of PART.
Using partitions from PART, we ran an explicit, 2-D finite element code on two geographically
distributed IBM SP machines. We used Globus software for communication between the two SPs.
We compared the partitions from PART with that generated using the widely-used partitioning tool,
METIS [26], which considers only processor performance. The results from the regular problems
indicate a increase in efficiency when processor performance is considered as compared to
the conventional even partitioning; the results indicate 5 \Gamma 15% increase in efficiency when network
performance is considered as compared to considering only processor performance; this is significant
given that the optimal is 15% for this application. The result from the irregular problem indicate up
to 36% increase in efficiency when processor and network performance are considered as compared
to even partitioning.
The remainder of the paper is organized as follows: Section 2 provides background. Section 3
discusses issues. Section 4 describes PART in detail. Section 5 is experimental results. Section 6
gives previous work and finally conclusion.
Background
2.1 Mesh-based Applications
Finite element method has been the fundamental numerical analysis technique to solve partial
differential equations in the engineering community for the past three decades [24, 3]. There are
three basic procedures in the finite element method. The problem is first formulated in variational or
weighted residual form. In the second step, the problem domain is discretized into complex shapes
called elements. The last major step is to solve the resulting system of equations. The procedure of
discretizing the problem domain is called meshing. Applications that involve a meshing procedure
are referred to as mesh-based applications.
Mesh-based applications are naturally suitable for parallel or distributed systems. Implementing
the finite element method in parallel involves partitioning the global domain of elements into
connected subdomains that are distributed among P processors; each processor executes the
numerical technique on its assigned subdomain. The communication among processors is dictated
by the types of integration method and solver method. Explicit integration finite element problems
do not require the use of a solver since a lumped matrix (which is a diagonal matrix) is used.
Therefore, communication only occurs among neighboring processors that have common data and
is relatively simple. For implicit integration finite element problems, however, communication is
determined by the type of solver used in the application. The application used in this paper is
an explicit, nonlinear finite code, called WHAMS2D [6], which is used to analyze elastic plastic
materials. While we focus on the WHAMS2D code, the concept can be generalized to implicit as
well as other mesh-based applications.
2.2 Distributed System
Distributed computing consists of a platform with a network of resources. These resources may be
clusters of workstations, cluster of personal computers, or parallel machines. Further, the resources
maybe located at one site or distributed among different sites. Figure 1 shows an example of
a distributed system. Distributed systems provide an economical alternative to costly massively
parallel computers. Researchers are no longer limited by the computing resources at individual sites.
The distributed computing environment also provides researchers opportunities to collaborate and
share ideas through the use of collaboration technologies.
In a distributed system, we define "group" as a set of processors that share one interconnection
network and have the same performance. A group can be an SMP, a parallel computer, or a cluster
of workstations or personal computers. Communication occurs both within a group and between
groups. We refer to communication within a group as local communication; and those between
processors in different groups as remote communication. The number of groups in the distributed
system is represented by the term S.
Supercomputer
SMPs NOW
Supercomputer

Figure

1: A distributed system.
2.3 Problem Formulation
Mesh partitioning for homogeneous systems can be viewed as a graph partitioning problem. The
goal of the graph partitioning problem is to find a small vertex separator and equal sized subsets.
Mesh partitioning for distributed system, however, is a variation of the graph partitioning problem;
the goal differs from regular graph partitioning problem in that equal sized subsets may not be
desirable. The distributed system partitioning problem can be stated as follows:
Given a graph E) of jV
and the maximum of a
cost function f over all V i is minimized:
Min
In this paper, the cost function f is the estimate of execution time of a given application on a
distributed system. This function is discussed further in Section 4.
Graph partitioning has been proven to be NP-complete. The mesh partitioning problem for
distributed system is also NP-complete as proven in Appendix 1. Therefore, we focus on heuristics
to solve this problem.
3 Major Issues
In this section, we discuss the following major issues related to the mesh partitioning problem for
distributed systems: comparison metric, efficiency, and number of cuts between groups.
3.1 Comparison Metric
The de facto metric for comparing the quality of different partitions for homogeneous parallel
systems has been equal subdomains and minimum interface (or cut set) size. Although there have
been objections and counter examples [14], this metric has been used extensively in comparing the
quality of different partitions. It is obvious that equal subdomain size and minimum interface is
not valid for comparing partitions for distributed systems.
One may consider an obvious metric for a distributed system to be unequal subdomains (pro-
portional to processor performance) and small cut set size. The problem with this metric is that
heterogeneity in network performance is not considered. Given the local and wide area networks
are used in distributed system, it is the case that there will be a big difference between local and
remote communication, especially in terms of latency.
We argue that the use of an estimate of execution time of the application on the target heterogeneous
system will always lead to a valid comparison of different partitions. The estimate is used for
relative comparison of different partition methods. Hence a coarse approximation of the execution
is appropriate for the comparison metric. It is important to make the estimate representative of
the application and the system. The estimate should include parameters that correspond to system
heterogeneities such as processor performance, local and remote communication. It should also
reflect the application computational complexity.
3.2 Efficiency
The efficiency for the distributed system is equal to the ratio of the relative speedup to the effective
number of processors, V . This ratio is given below:
(1)
where E(1) is the sequential execution time on one processor and E is the execution time on the
distributed system. The term V is equal to the summation of each processor's performance relative
to the performance of the processor used for sequential execution. This term is as follows:
(2)
where k is the processor used for sequential execution. For example, with two processors having
processor performance F 2, the efficiency would be
if processor 1 is used for sequential execution; the efficiency is
if processor 2 is instead used for sequential execution.
3.3 Network Heterogeneity
It is well-known that heterogeneity of processor performance must be considered with distributed
systems. In this section, we identify conditions for which heterogeneity in network performance
must be considered.
For a distributed system, recall that we define a group to be a collection of processors that
have the same performance and share a local interconnection network. Remote communication
corresponds to communication between two groups. Given that some processors require remote
and local communication, while others only require local communication, there will be a disparity
between the execution times of these processors corresponding to the difference in remote and local
communications (assuming equal computational loads).
3.3.1 Ideal Reduction in Execution Time
A retrofit step is used with the PART tool to reduce the computational load of processor with local
and remote communication to equalize the execution time among the processors in a group. This
step is described in detail in Section 6.2. The reduction in execution time that occurs with this
retrofit is demonstrated by considering a simple case, stripe partitioning, for which communication
occurs with at most two neighboring processors. Assume there exists two groups having the same
processor and local network performance; the groups are located at geographically distributed sites
requiring a WAN for interconnection. Figure 2 illustrates one such case.
G processors
local communication
local communication
remote communication

Figure

2: Communication Pattern for Stripe Partitioning.
Processor i (as well as processor local and remote communication. The difference
between the two communication times is:
where x is the percentage of the difference of CR and CL in the total execution time E. Assume
that E represents the execution time taking into consideration only processor performance. Since
it is assumed that all processors have the same performance, this entails an even partition of the
mesh. This time can be written as:
Now consider the case of partitioning to take into consideration the heterogeneity in network
performance. This is achieved by decreasing the load assigned to processor i and increasing the
loads of the processors in group 1. The same applies to processor j in group 2. The amount
of the load to be redistributed is CR \Gamma CL or x%E and this amount is distributed to G processors.
This is illustrated in Figure 6, which is discussed with the retrofit step of PART. The execution
time is now:
G
The difference between E and E 0 is:
x
G
G
Therefore, by taking the network performance into consideration when partitioning, the percentage
reduction in execution time is approximately x%E(denoted as \Delta(1; G)) which includes the following:
(1) the percentage of communication in the application and (2) the difference in the remote and
local communication. Both factors are determined by the application and the partitioning. If the
maximum number of processors among the groups that have remote communication is -, then the
reduction in execution time is as follows:
G
\Delta(-;
For example, for the WHAMS2D application in our experiments, we calculated the ideal reduction
to be 15% for the regular meshes with 8. For those partitions, only one processor
in each group has local and remote communication, therefore, it is relatively easy to calculate the
ideal performance improvement.
3.3.2 Number of Processors in a Group with Local and Remote Communication
The major issue to be addressed with the reduction is how to partition the domain assigned to a
group to maximize the reduction. In particular, this issue entails a tradeoff between the following
two scenarios:
1. Many processors in a group having local and remote communication, resulting in small message
sizes for which the execution time without the retrofit step is smaller than that for case 2.
However, given that many processors in a group have remote and local communication, there
are fewer processors that are available for redistribution of the additional load. This is illustrated
in Figure 3 where a mesh of size n \Theta 2n is partitioned into 2P blocks. Each block
oe -?
oe -?

Figure

3: A size n \Theta 2n mesh partitioned into 2P blocks.
is n
\Theta n
assuming all processors have equal performance. The mesh is partitioned into
two groups, each group having P processors. Processors on the group boundary incur remote
communication as well as local communication. Part of the computational load of these
processors need to be moved to processors with only local communication to compensate for
the longer communication times. Assume there is no overlap in communication messages and
message aggregation is used for the communication of one node to the diagonal processor, the
communication time for a processor on the group boundary is approximately:
local+remote
For a processor with only local communication, the communication time is approximately
(again, message aggregation and no overlapping is assumed):
local
Therefore, the communication time difference between a processor with local and remote
communication and a processor with only local communication is approximately:
local
There are a total of
P number of processors with local and remote communication. There-
fore, using Equation 1, the ideal reduction in execution time in Group 1 (and Group 2)
-:
. n

Figure

4: A size n \Theta 2n mesh partitioned into 2P stripes.
is:
blocks
2. Only one processor in a group has local and remote communication, resulting in large message
sizes which result in the execution time without the retrofit step larger than that for case 1.
However, there are more processors that are available for redistribution of additional load.
This is illustrated in Figure 4 where the same mesh is partitioned into stripes; there is only
one processor in each group that have local and remote communication. Following a similar
analysis as in Figure 3, the communication time difference between a processor with both local
and remote communication and a processor with only local communication is approximately:
local
There is only one processor with remote communication in each group. Hence, using Equation
1, the ideal reduction in execution time is:
stripes
comm (stripes) (15)
Therefore, the total execution time for stripe and block partitioning are:
stripes
reduction
blocks
reduction
The difference in total execution time between block and stripe partition is:
\DeltaT blocks\Gammastripes
ff L
A
Therefore, the difference in total execution time between block and stripe partitioning is determined
by . The term A and C are positive since P ? 1; while the term B is negative
4, the block partition has a higher execution time, i.e., the stripe
partitioning is advantageous. If P ? 4, however, block partitioning will still have a higher execution
time unless n is so large that the absolute value of term B is larger than the sum of the absolute
values of A and C. Note that ff L and ff R are one to two orders of magnitude larger than fi L . In our
experiments, we calculated that block partitioning has a lower execution time only if n ? 127KB.
In the meshes that we used, however, the largest n is only about 10KB.
4 Description of PART
PART considers heterogeneities in both the application and the system. In particular, PART
takes into consideration that different mesh based applications may have different computational
complexities and the mesh may consist of different element types. For distributed systems, PART
takes into consideration heterogeneities in processor and network performance.

Figure

5 shows a flow diagram of PART. PART consists of an interface program and a simulated
annealing program. A finite element mesh is fed into the interface program and produces the
proposed communication graph, which is then fed into a simulated annealing program where the
final partitioning is computed. This partitioned graph is translated to the required input file format
for the application. This section describes the initial interface program and the steps required to
partition the graph.
Problem domain
# of groups
# of processors per group
Computational models
Communication models
Partitioned data
Finite element mesh Interface
program graph Simulated
Annealing
Partitioned
graph Interface
program
Input to
processors

Figure

5: PART flowchart.
4.1 Mesh Representation
We use a weighted communication graph to represent a finite element mesh. This is a natural
extension of the communication graph. As in the communication graph, vertices represent elements
in the original mesh. A weight is added to each vertex to represent the number of nodes within
the element. Same as in communication graph, edges represent the connectivity of the elements in
the weighted communication graph. A weight is also added to each edge to represent the number
of nodes of which information need to be exchanged between the two neighboring elements.
4.2 Partition Method
PART entails three steps to partition a mesh for distributed systems. These steps are:
1. Partition the mesh into S subdomains for the S groups, taking into consideration heterogeneity
in processor performance and element types.
2. Partition each subdomain into G parts for the G processors in a group, taking into consideration
heterogeneity in network performance and element types.
3. If necessary, globally retrofit the partitions among the groups, taking into consideration heterogeneity
in the local networks among the different groups.
Each of the above steps is described in detail in the following subsections. Each subsection
includes a description of the objective function used with simulated annealing.
The key to a good partitioning by simulated annealing is the cost function. The cost function
used by PART is the estimate of execution time. For one particular supercomputer, let E i be the
execution time for the i-th processor (1 - i - p). The goal here is to minimized the variance of the
execution time for all processors.
While running the simulated annealing program, we found that the best cost function is:
instead of the sum of the
2 . So (20) is the actual cost function used in the simulated annealing
program. In this cost function, Ecomm includes the communication cost for the partitions that have
elements that need to communicate with elements on a remote processor. Therefore, the execution
time will be balanced. - is the parameter that needs to be tuned according to the application and
problem size.
Partition
The first step generates a coarse partitioning for the distributed systems. Each group gets a
subdomain that is proportional to its number of processors, the performance of the processors, and
the computational complexity of the application. Hence computational cost is balanced across all
the groups.
The cost function is given by:
where S is the number of groups in the system.
4.2.2 Step 2: Retrofit
In the second step, the subdomain that is assigned to each group from Step 1 is partitioned among
its processors. Within each group, simulated annealing is used to balance the execution time.
In this step, variance in network performance is considered. Processors that entails inter group
communication will have reduced computational load to compensate for the longer communication
time.
The step is illustrated in Figure 6 for two supercomputers, SC1 and SC2. In SC1, four processors
are used; and two processors are used in SC2. Computational load is reduced for P3 since it
communicates with a remote processor. The amount of reduced computational load is represented
as ffi. This amount is equally distributed to the other three processors. Assuming the cut size
remains unchanged, the communication time will not change, hence the execution time will be
balanced after this shifting of computational load.
comm.
comp. comm.
p3
p3
comp.
retrofit
d
d/4

Figure

An illustration of the retrofit step for two supercomputers assuming only two nearest
neighbor communication.
This step entails generating imbalanced partitions in group i that take into consideration that
some processors communicate locally and remotely and other processors communicate only locally.
The imbalance is represented with the term \Delta i . This term is added to processors that require
local and remote communication. Adding this term results in a decrease in Ecomm i
as compared to
processors requiring only local communication. The cost function is given by the following equation:
where p is the number of processors in a given group; \Delta i is the difference in the estimation of local
and remote communication time. For processors that only communicate locally,
4.2.3 Step 3: Global Retrofit
The third step addresses the global optimization, taking into consideration differences in the local
interconnect performance of various groups. Again, the goal is to minimize the variance of the
execution time across all processors. In this step, elements on the boundaries of partitions are
moved according to the execution time variance between neighboring processors. This step is only
executed if there is a large difference in the performance of the different local interconnects. For
the case when a significant number of elements are moved between the groups in Step 3, the second
step is executed again to equalize the execution time in a group given the new computational load.
After Step 2, processors in each group will have a balanced execution time. However, execution
time of the different groups may not be balanced. This may occur when there is a large difference
in the communication time of the different groups. To balance the execution among all the groups,
we take the weighted average of execution times from all the groups. The weight
for each group equals to the computing power of that group versus the total computing power.
The computing power for a particular group is the multiplication of the ratio of the processor
performance with respect to the slowest one among all the groups and the number of processors used
from that group. We denote this weighted average as -
E. Under the assumption that communication
time will not change much (i.e., the separators from Step 1 will not incur a large change in size),
E is the optimal execution time that can be achieved. To balance the execution time so that each
group will have an execution time of -
E, we first compute the difference of E i with -
E:
This \Gamma i is then added to each E comp i
in the cost function. The communication cost Ecomm i
is
now again the remote communication cost for group i. The cost function is therefore given by:
where S is the number of groups in the system. For groups whose the domain will increase;
for groups whose the domain will decrease. If Step 3 is necessary, then Step 2 is performed
again to partition within each group.
5 Parallel Simulated Annealing
PART uses simulated annealing to partition the mesh. Figure 7 shows the serial version of the
simulated annealing algorithm. This algorithm uses the Metropolis criteria (line 8 to 13 in Figure 7)
to accept or reject moves. The moves that reduce the cost function are accepted; the moves that
increase the cost function may be accepted with probability e \Gamma \DeltaE
avoiding being trapped
in local minima. This probability decreases when the temperature is lowered. Simulated Annealing
is computationally intensive, therefore, a parallel version of simulated annealing is used in the
parallel version of PART. There are three major classes of parallel simulated annealing [19]: serial-
like [32, 39], parallel moves [1], and multiple Markov chains [5, 21, 34]. Serial like algorithms
essentially break up each move into subtasks and parallelize the subtasks (parallelizing line 6 and
7 in

Figure

7). For the parallel moves algorithms, each processor generates and evaluates moves
cost function calculation may be inaccurate since processors are not aware of moves
by other processors. Periodic updates are normally used to address the effect of cost function error.
Parallel moves algorithms essentially parallelize the for loop in Figure 7 (line 5 to 14). For the
multiple Markov chains algorithm, multiple simulated annealing processes are started on various
processors with different random seeds. Processors periodically exchange solutions and the best is
selected and given to all the processors to continue their annealing processes. In [5], the multiple
Markov chain approach was shown to be most effective for VLSI cell placement. For this reason,
the parallel version of PART uses the multiple Markov chain approach.
Given P processors, a straightforward implementation of the multiple Markov chain approach
would be initiating simulated annealing on each of the P processors with a different seed. Each
processor performs moves independently and then finally the best solution from those computed by
1. Get an initial solution S
2. Get an initial temperature T ? 0
3. While stopping criteria not met f
4. number of moves per temperature
5. for
6. Generate a random move
7. Evaluate changes in cost function: \DeltaE
8. if (\DeltaE !
9. accept this move, and update solution S
10. g else f
11. accept with probability
12. update solution S if accepted
13. g
14. g /*end for loop*/
15.
16.g /*end while loop */

Figure

7: Simulated annealing.
all processors is selected. In this approach, however, simulated annealing is essentially performed
P times which may result a better solution but not speedup.
To achieve speedup, P processors perform an independent simulated annealing with a different
seed, but each processor performs only M=P moves (M is the number of moves performed by
the simulated annealing at each temperature). Processors exchange solutions at the end of each
temperature. The exchange of data occurs synchronously or asynchronously. In the synchronous
multiple Markov chain approach, the processors periodically exchange solutions with each other.
In the asynchronous approach, the client processors exchange solutions with a server processor. It
has been reported that the synchronous approach is more easily trapped in a local optima than
the asynchronous [21], therefore the parallel version of PART uses the asynchronous approach.
During solution exchange, if the client solution is better, the server processor is updated with the
better solution; if the server solution is better, the client gets updated with the better solution and
continues from there. Each processor exchanges solution with the server processor at the end of
each temperature.
To ensure that each subdomain is connected, we check for disconnected components at the
end of PART. If any subdomain has disconnected components, the parallel simulated annealing
is repeated with a different random seed. This process continues until there are no disconnected
subdomains or the number of trials exceed three times. A warning message is given in the output
if there are disconnected subdomains.
6 Experiments
In this section, we present the results from two different experiments. The first experiment focuses
on the speedup of the parallel version of PART. The second experiment focuses on the quality of
the partitions generated with PART.
6.1 Speedup Results

Table

1: Parallel PART execution time (seconds): 8 partitions.
# of proc. barth4 barth5 inviscid labarre spiral viscous
4 44.4 54.7 46.6 32.4 41.2 53.7
2.1 2.2 2.4 2.5 1.5 2.9
PART is used to partition six 2D irregular meshes with triangular elements: barth4 (11451
labarre (14971 elem.), spiral (1992 elem.), and
viscous (18369 elem. The running time of partitioning the six irregular meshes into 8, and 100
Parallel PART Speedup: 8 partitions2060100140
barth4 barth5 inviscid labarre spiral viscous

Figure

8: Parallel PART speedup for 8 partitions.
subdomains are given in Tables 1 and 2, respectively. It is assumed that the subdomains will be
executed on a distributed system consisting of two IBM SPs, with equal number of processors but
different processor performance. Further, the machines are interconnected via vBNS for which the
performance of the network is given in Table 4 (discussed in Section 6.2). In each table, column 1 is
the number of client processors used by PART, and columns 2 to 6 are the running time of PART
in seconds for the different meshes. The solution quality of using two or more client processors is
within 5% of that of using one client processor. In this case, the solution quality is the estimate of
the execution time of WHAMS2D.

Figures

8 and 9 are graphical representations of the speedup of the parallel version of PART
relative to one client processor. The figures show that when the meshes are partitioned into 8
subdomains, superlinear speedup occurs in all cases. When the meshes are partitioned into 100
subdomains, superlinear speedup occurs only in the cases of two smallest meshes, spiral and inviscid.
Other cases show slightly less than perfect speedup. This superlinear speedup is attributed to the
use of multiple client processors conducting a search, for which all the processors benefit from the
results. Once a good solution is found by any one of the clients, this information is given to other
clients quickly, thereby reducing the effort of continuing to search for a solution. The superlinear

Table

2: Parallel PART execution time (seconds): 100 partitions.
# of proc. barth4 barth5 inviscid labarre spiral viscous
4 3982.2 4666.4 3082.3 4273.5 1304.4 3974.0
288.3 426.3 192.8 291.2 62.7 391.7
speedup results are consistent with that reported in [33].
6.2 Quality of Partition
6.2.1 Regular Meshes
PART was applied to an explicit, nonlinear finite code, called WHAMS2D [6], that is used to
analyze elastic plastic materials. The code uses MPI built on top of Nexus for interprocessor
communication within a supercomputer and between supercomputers. Nexus is a runtime system
that allows for multiple protocols within an application. The computational complexity is linear
with the size of the problem.
The code was executed on the IBM SP machines located at Argonne National Laboratory and
the Cornell Theory Center. These two machines were connected by the Internet. Macro benchmarks
were used to determine the network and processor performance. The results of the network
performance analysis are given in Table 3. Further, experiments were conducted to determine that
the Cornell nodes were 1.6 times faster than the Argonne nodes.
The problem mesh consists of 3 regular meshes. The execution time is given for 100 time steps
corresponding to 0.005 seconds of application time. Generally, the application may execute for
10; 000 to 100; 000 time steps. The recorded execution time represents over 100 runs, taking the
data from the runs with standard deviation less than 3%. The regular problems were executed on
Parallel PART Speedup: 100 partitions1030507090barth4 barth5 inviscid labarre spiral viscous

Figure

9: Parallel PART speedup for 100 partitions.

Table

3: Values of ff and fi for the different networks.
Argonne SP Vulcan Switch ff
a machine configuration of 8 processors (4 at ANL IBM SP and 4 at CTC IBM SP).

Table

4 presents the results for the regular problems. Column 1 is the mesh configuration.
Column 2 is the execution time resulting from the conventional equal partitioning. In particular,
we used Chaco's spectral bisection. Column 3 is the result from the partitioning taken from the
end of the first step for which the variance in processor performance and computational complexity
are considered. Column 4 is the execution time resulting from the partitioning taken from the end
of the second step for which the variance in network performance is considered. The results in

Table

4 shows that approximately increase in efficiency can be achieved by balancing the
computational cost; another 5 \Gamma 16% efficiency increase can be achieved by considering the variance
in network performance. The small increase in efficiency by considering the network performance

Table

4: Execution time using the Internet 8 processors: 4 at ANL, 4 at CTC
Case Chaco Proc. Perf. Local Retrofit
9 \Theta 1152 mesh 102.99 s 78.02 s 68.81 s
efficiency 0.46 0.61 0.71
efficiency 0.47 0.61 0.68
36 \Theta 288 mesh 103.88 s 73.21 s 70.22 s
efficiency 0.46 0.67 0.70
is due to communication being a small component of the WHAMS2D application. However, recall
that the optimal increase in performance is 15% for the regular problem as described earlier.
The global optimization step, which is the last step of PART that balances execution time across
all supercomputers, did not give significant increase in efficiency (it is not included in Table 4).
This is expected since the two supercomputers we used, the Argonne IBM SP and the Cornell
IBM SP, both have interconnection networks that have very similar performance as indicated in

Table

3. The results indicate the performance gains achievable with each step in comparison to
conventional methods that evenly partition the mesh. Given that it is obvious that considering
processor performance results in significant gains, the following section on irregular meshes only
considers performance gains resulting from considering network performance.
6.2.2 Irregular Meshes
The experiments on irregular meshes were performed on the GUSTO testbed, which is not available
when we experimented on the regular meshes. This testbed includes two IBM SP machines, one
located at Argonne National Laboratory (ANL) and the other located at the San Diego Supercomputing
Center (SDSC). These two machines are connected by vBNS (very high speed Backbone
Network Service). We used Globus [15, 16] software to allow multimodal communication within the
application. Macro benchmarks were used to determine the network and processor performance.
The results of the network performance analysis are given in Table 5. Further, experiments were
conducted to determine that the SDSC SP processors nodes were 1.6 times as fast as the ANL
ones.

Table

5: Values of ff and fi for the different networks.
ANL SP Vulcan Switch ff
SDSC SP Vulcan Switch ff
PART is used to partition five 2D irregular meshes with triangular elements: barth4 (11451
labarre (14971 elem.), viscous (18369 elem.), and inviscid (6928
(called PART without restriction). A sightly modified version of PART (called PART with
restriction) is used to partition the meshes so that only one processor has remote communication
in each group. METIS 3.0 [26] is used to generate partitions that take into consideration processor
performance (each processor's compute power is used as one of the inputs).
These three partitioners are used to identify the performance impact of considering heterogeneity
of networks in addition to that with processors. Further, the three partitioners highlight the
difference when forcing remote communication to occur on one processor in a group versus having
multiple processors with remote communication in a group. We consider 6 configurations of the
two machines: 4 at ANL and 4 at SDSC, 8 at ANL and 8 at SDSC, and 20 at ANL and 20 at SDSC.
The two groups correspond to the two IBM SPs at ANL and SDSC. We used up to 20 processors
from each SP due to limitations in co-scheduling computing resources. The execution time is given
for 100 time steps. The recorded execution time represents an average of 10 runs, and the standard
deviation is less than 3%.

Tables

6 to Table 8 show the experimental results from the 3 configurations. Column one
identifies the irregular meshes and the number of elements in each mesh (included in parenthesis).
Column two is the execution time resulting from the partitions from PART with the restriction that
only one processor per group entails remote communication. For Columns 2 to 4, the number -
indicates the number of processors that has remote communication in a group. Column three
is similar to Column two except that the partition does not have the restriction that remote
communication be on one processor. Column four is the execution time resulting from METIS
which takes computing power into consideration (each processor's compute power is used as one of

Table

Execution time using the vBNS on 8 processors: 4 at ANL, 4 at SDSC.
Mesh PART w/ restriction PART w/o restriction Proc. Perf. (METIS)
efficiency
viscous (18369 elem.) 150.0s (-=1) 169.0s (-=3) 170.0s (-=3)
efficiency 0.86 0.75 0.75
labarre (14971 elem.) 133.0s (-=1) 142.0s (-=2) 146.0s (-=3)
efficiency 0.79 0.73 0.71
efficiency 0.79 0.68 0.68
inviscid (6928 elem.) 73.2s (-=1) 85.5s (-=3) 88.5s(-=3)
efficiency 0.66 0.56 0.55
the inputs to the METIS program).
The results show that by using PART without restrictions, a slight decrease (1-3%) in execution
time is achieved as compared to METIS. By forcing all the remote communication on one
processor, the retrofit step can achieve more significant reduction in execution time. The results
in

Tables

6 to Table 8 show that efficiency is increased by up to 36% as compared to METIS, and
the execution time is reduced by up to 30% as compared to METIS; This reduction comes from
the fact that even on a high speed network such as the vBNS, the difference of message start up
cost on remote and local communication is very large. From Table 5, we see this difference is two
orders of magnitude for message start up as compared to approximately one order of magnitude
for bandwidth. Restricting remote communication on one processor allows PART to redistribute
the load among more processors thereby achieving close to the ideal reduction in execution time.
7 Previous Work
The problem of domain partitioning for finite element meshes is equivalent to partitioning the
graph associated with the finite element mesh. Graph partitioning has been proven to be an

Table

7: Execution time using the vBNS on processors: 8 at ANL, 8 at SDSC.
Mesh PART w/ restriction PART w/o restriction Proc. Perf. (METIS)
efficiency 0.72 0.62 0.59
viscous (18369 elem.) 82.9s(-=1) 100.8s(-=4) 106.0s(-=5)
efficiency 0.77 0.64 0.61
labarre (14971 elem.) 75.8s(-=1) 83.7s(-=3) 88.6s(-=3)
efficiency 0.69 0.62 0.59
efficiency 0.74 0.50 0.48
inviscid (6928 elem.) 42.2s(-=1) 62.8s(-=3) 67.2s(-=4)
efficiency 0.57 0.39 0.36
NP-complete problem [17]. Many good heuristic static partitioning methods have been proposed.
Kernighan-Lin [31] proposed a locally optimized partitioning method. Farhat [13, 14] proposed an
automatic domain decomposer based on Greedy algorithm. Berger and Bokhari [4] proposed Recursive
Coordinate Bisection (RCB) which utilizes spatial nodal coordinate information. Nour-Omid
et al. [35, 40] proposed Recursive Inertial Bisection (RIB). Simon [37] proposed Recursive Spectral
Bisection (RSB) which computes the Fiedler vector for the graph using the Lanczos algorithm and
then sorts vertices according to the size of the entries in Fiedler vector. Recursive Graph Bisection
(RGB) is proposed by George and Liu [18], which uses SPARSPAK RCM algorithm to compute
a level structure and then sort vertices according to the RCM level structure. Barnard et al. in
[2] proposed a multilevel version of RSB which is faster. Hendrickson and Leland [23, 22] also
reported a similar multilevel partitioning method. Karypis and Kumar [27, 28, 30] proposed a new
coarsening heuristic to improve the multilevel method.
Most of the aforementioned decomposition methods are available in one of three automated
tools: Chaco [22], METIS [26, 29] and TOP/DOMDEC [38]. Chaco, the most versatile, implements
inertial, spectral, Kernighan-Lin, and multilevel algorithms. These algorithms are used to

Table

8: Execution time using the vBNS on 40 processors: 20 at ANL, 20 at SDSC.
Mesh PART w/ restriction PART w/o restriction Proc. Perf. (METIS)
efficiency 0.69 0.54 0.45
viscous (18369 elem.) 38.7s(-=1) 58.6s(-=5) 64.9s(-=7)
efficiency 0.67 0.44 0.40
labarre (14971 elem.) 33.8s(-=1) 51.2s(-=3) 53.5s(-=6)
efficiency 0.62 0.41 0.40
efficiency 0.39 0.34 0.32
inviscid (6928 elem.) 33.5(-=1) 34.7s(-=4) 46.8s(-=5)
efficiency
recursively bisect the problem into equal sized subproblems. METIS uses the method for fast partitioning
of the sparse matrices, using a coarsening heuristic to provide the speed. TOP/DOMDEC
is an interactive mesh partitioning tool. All these tools produce equal size partitions. These tools
are applicable to systems with the same processors and one interconnection network. Some tools
such as METIS, can produce partitions with unequal weights. However, none of these tools can
take network performance into consideration in the partitioning process. For this reason, these
tools are not applicable to distributed systems.
Crandall and Quinn [7, 8, 9, 10, 11, 12] developed a partitioning advisory system for network
of workstations. The advisory system has three built-in partitioning methods (contiguous row,
contiguous point, and block). Given information about the problem space, the machine speed, and
the network, the advisory system provides ranking of the three partitioning methods. The advisory
system takes into consideration of variance in processor performance among the workstations. The
problem, however, is that linear computational complexity is assumed for the application. This
is not the case with implicit finite element problems, which are widely used. Further, variance in
network performance is not considered.
8 Conclusion
In this paper, we addressed issues in mesh partitioning problem for distributed systems. These
issues include comparison metric, efficiency, and cut sets. We present a tool, PART, for automatic
mesh partitioning for distributed systems. The novel feature of PART is that it considers heterogeneities
in both the application and the distributed system. The heterogeneities in the distributed
system include processor and network performance; the heterogeneities in the application include
computational complexity. We also demonstrate the use of a parallel version of PART for distributed
systems. The novel part of the parallel PART is that it uses the asynchronous multiple
Markov chain approach of parallel simulated annealing for mesh partitioning. The parallel PART
is used to partition 6 irregular meshes into 8, 16, and 100 subdomains using up to 64 client processors
on an IBM SP2 machine. Results show superlinear speedup in most cases and nearly perfect
speedup for the rest.
We used Globus software to run an explicit, 2-D finite element code using mesh partitions
from the parallel PART. Our testbed includes two geographically distributed IBM SP machines.
Experimental results are presented for 3 regular meshes and 4 irregular finite element meshes for the
WHAMS2D application executing on a distributed system consisting of two IBM SPs. The results
from the regular problems indicate a increase in efficiency when processor performance is
considered as compared to even partitioning; the results also indicate an additional 5 \Gamma 16% increase
in efficiency when network performance is considered. The result from the irregular problem indicate
a 38% increase in efficiency when processor and network performance are considered as compared
to even partitioning. Experimental results from the irregular problems also indicate up to 36%
increase in efficiency compared with using partitions that only take processor performance into
consideration. This improvement comes from the fact that even on a high speed network such as
the vBNS, the message start up cost on remote and local communication still has a large difference.


Appendix

1: Proof of NP-complete of the Mesh Partitioning Problem for Distributed
Systems
partitioning problem for distributed systems is NP-complete.
Proof 1 We transform a proven NP-Complete problem, MINIMUM SUM OF SQUARES [17], to
the Partition problem for distributed systems. Let set A , with
for each a 2 A be an arbitrary instance of MINIMUM SUM OF SQUARES. We shall construct a
graph the desired partition exists for G if and only if A has a
sum of squares.
The basic units of MINIMUM SUM OF SQUARES instance are a n. The local
replacement substitute for each a i 2 A is the collection E i of 3 edges shown in Figure 10. Therefore,
E) is defined as the following:
a
a [2]
a [1]

Figure

10: Local replacement for a i 2 A for transforming MINIMUM SUM OF SQUARES to the
Partition problem for distributed systems.
It is easy to see this instance of Partition problem for distributed systems can be constructed in
polynomial time from the MINIMUM SUM OF SQUARES instance.
are the disjoint k partitions of A such that the sum of squares is minimized,
then the corresponding k disjoint partitions of V is given by taking fa i [1]; a i [2]; a i g for each a i in
every subset of A. We also restrict the cost function f i to be the same as is in MINIMUM SUM
OF SQUARES:
and a 2 A i . This ensures that the partition sum of squares of the cost
function.
Conversely, if is a disjoint k partition of G with minimum sum of squares of the
cost function, the corresponding disjoint k partition of set A is given by choosing those vertices a i
such that fa i [1]; a i [2]; a i Hence the minimum sum of squares for the cost
function over k disjoint partitions ensures that the sum of squares of s(a) on k disjoint set of A is
also minimized. We conclude that the Partition problem for distributed systems is NP-Complete.


Appendix

2: Nomenclature
Estimated execution time on processor i.
Estimated computational time on processor i.
Estimated communication time on processor i.
Performance of processor i as measured by a computation kernel.
ff L - Per message cost of local communication.
message cost of remote communication.
cost of local communication.
cost of remote communication.
- Size of message.
CL - Local communication time for a processor.
CR - Remote communication time for a processor.
- The difference between CR and CL for one processor.
The difference between CR and CL for processor i.
- The maximum number of processors in a group that have
both local and remote communication.
Coefficient of computational complexity.
Parameter used to equalize the contribution of the computation
and communication to execution time.
Number of elements in partition i.
- Number of processors in the system.
Number of processors in group i.
G - Number of processors in a particular group (same as P i ).
- Number of groups in the system.
The i-th group in the system.
The ratio of the speed of processors in S i relative to the
slowest processor in the system.



--R

Parallel simulated annealing algorithms for cell placement on hypercube multiprocessors.
A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems.
Finite Element Procedures in Engineering Analysis.
A partitioning strategy for non-uniform problems on multiproces- sors
An evaluation of parallel simulated annealing strategies with application to standard cell placement.
WHAMS3D project progress report PR-2
Data partitioning for networked parallel processing.
Problem decomposition in parallel networks.
Block data partitioning for partial-homogeneous parallel networks

Evaluating decomposition techniques for high-speed cluster computing
A partitioning advisory system for networked data-parallel processing
A simple and efficient automatic fem domain decomposer.
Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics.
Managing multiple communication methods in high-performance networked computing systems
Software infrastructure for the i-way meta-computing experiment
Computers and Intractability: A Guide to the Theory of NP- Completeness
Computer Solution of Large Sparse Positive Definite Systems.
Parallel simulated annealing techniques.
the Legion team.
Simulated annealing based parallel state assignment of finite state machines.
The chaco user's guide.
A multilevel algorithm for partitioning graphs.
The Finite Element Method.
The internet fast lane for research and education.
A fast and high quality multilevel scheme for partitioning irregular graphs.
A fast and high quality multilevel scheme for partitioning irregular graphs.
Multilevel k-way partitioning scheme for irregular graphs
Multilevel k-way partitioning scheme for irregular graphs
Parallel multilevel k-way partitioning scheme for irregular graphs
An efficient heuristic procedure for partitioning graphs.
Placement by simulated annealing on a multiprocessor.
Introduction to Parallel Computing: Design and Analysis of Algorithms.
Asynchronous communication of multiple markov chain in parallel simulated annealing.
Solving finite element equations on concurrent computers.
Partitioning sparse matrices with eigenvectors of graphs.
Partitioning of unstructured problems for parallel processing.
Top/domdec: a software tool for mesh partitioning and parallel processing.
Parallel n-ary speculative computation of simulated annealing
A study of the factorization fill-in for a parallel implementation of the finite element method
A retrofit based methodology for the fast generation and optimization of large-scale mesh partitions: Beyond the minimum interface size criterion
--TR
A partitioning strategy for nonuniform problems on multiprocessors
Partitioning sparse matrices with eigenvectors of graphs
Parallel simulated annealing techniques
Introduction to parallel computing
Three-dimensional grid partitioning for network parallel processing
The Legion vision of a worldwide virtual computer
Managing multiple communication methods in high-performance networked computing systems
Simulated annealing based parallel state assignment of finite state machines
Computer Solution of Large Sparse Positive Definite
Computers and Intractability
Parallel Simulated Annealing Algorithms for Cell Placement on Hypercube Multiprocessors
Parallel N-ary Speculative Computation of Simulated Annealing
Mesh Partitioning for Distributed Systems
Problem Decomposition in Parallel Networks

--CTR
Kyungmin Lee , Dongman Lee, A scalable dynamic load distribution scheme for multi-server distributed virtual environment systems with highly-skewed user distribution, Proceedings of the ACM symposium on Virtual reality software and technology, October 01-03, 2003, Osaka, Japan
Zhiling Lan , Valerie E. Taylor , Greg Bryan, Dynamic load balancing of SAMR applications on distributed systems, Scientific Programming, v.10 n.4, p.319-328, December 2002
Zhiling Lan , Valerie E. Taylor , Greg Bryan, Dynamic load balancing of SAMR applications on distributed systems, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.36-36, November 10-16, 2001, Denver, Colorado
simulated annealing;distributed systems;mesh partitioning