Parallel Incremental Graph Partitioning.
AbstractPartitioning graphs into equally large groups of nodes while minimizing the number of edges between different groups is an extremely important problem in parallel computing. For instance, efficiently parallelizing several scientific and engineering applications requires the partitioning of data or tasks among processors such that the computational load on each node is roughly the same, while communication is minimized. Obtaining exact solutions is computationally intractable, since graph partitioning is an NP-complete.For a large class of irregular and adaptive data parallel applications (such as adaptive graphs), the computational structure changes from one phase to another in an incremental fashion. In incremental graph-partitioning problems the partitioning of the graph needs to be updated as the graph changes over time; a small number of nodes or edges may be added or deleted at any given instant.In this paper, we use a linear programming-based method to solve the incremental graph-partitioning problem. All the steps used by our method are inherently parallel and hence our approach can be easily parallelized. By using an initial solution for the graph partitions derived from recursive spectral bisection-based methods, our methods can achieve repartitioning at considerably lower cost than can be obtained by applying recursive spectral bisection. Further, the quality of the partitioning achieved is comparable to that achieved by applying recursive spectral bisection to the incremental graphs from scratch.
Introduction
Graph partitioning is a well-known problem for which fast solutions are extremely important in parallel
computing and in research areas such as circuit partitioning for VLSI design. For instance, parallelization
of many scientific and engineering problems requires partitioning data among the processors in such a
fashion that the computation load on each node is balanced, while communication is minimized. This
is a graph-partitioning problem, where nodes of the graph represent computational tasks, and edges describe
the communication between tasks with each partition corresponding to one processor. Optimal partitioning
would allow optimal parallelization of the computations with the load balanced over various processors
and with minimized communication time. For many applications, the computational graph can be derived
only at runtime and requires that graph partitioning also be done in parallel. Since graph partitioning is
NP-complete, obtaining suboptimal solutions quickly is desirable and often satisfactory.
For a large class of irregular and adaptive data parallel applications such as adaptive meshes [2], the
computational structure changes from one phase to another in an incremental fashion. In incremental
graph-partitioning problems, the partitioning of the graph needs to be updated as the graph changes over
time; a small number of nodes or edges may be added or deleted at any given instant. A solution of the
previous graph-partitioning problem can be utilized to partition the updated graph, such that the time
required will be much less than the time required to reapply a partitioning algorithm to the entire updated
graph. If the graph is not repartitioned, it may lead to imbalance in the time required for computation on
each node and cause considerable deterioration in the overall performance. For many of these problems the
graph may be modified after every few iterations (albeit incrementally), and so the remapping must have
a lower cost relative to the computational cost of executing the few iterations for which the computational
structure remains fixed. Unless this incremental partitioning can itself be performed in parallel, it may
become a bottleneck.
Several suboptimal methods have been suggested for finding good solutions to the graph-partitioning
problem. For many applications, the computational graph is such that the vertices correspond to two-
or three-dimensional coordinates and the interaction between computations is limited to vertices that are
physically proximate. This information can be exploited to achieve the partitioning relatively quickly by
clustering physically proximate points in two or three dimensions. Important heuristics include recursive
coordinate bisection, inertial bisection, scattered decomposition, and index based partitioners [3, 6, 12, 11, 14,
16]. There are a number of methods which use explicit graph information to achieve partitioning. Important
heuristics include simulated annealing, mean field annealing, recursive spectral bisection, recursive spectral
multisection, mincut-based methods, and genetic algorithms [1, 4, 5, 7, 8, 9, 10, 13]. Since, the methods use
explicit graph information, they have wider applicability and produce better quality partitioning.
In this paper we develop methods which use explicit graph information to perform incremental graph-
partitioning. Using recursive spectral bisection, which is regarded as one of the best-known methods for
graph partitioning, our methods can partition the new graph at considerably lower cost. The quality of
partitioning achieved is close to that achieved by applying recursive spectral bisection from scratch. Further,
our algorithms are inherently parallel.
The rest of the paper is outlined as follows. Section 2 defines the incremental graph-partitioning problem.
Section 3 describes linear programming-based incremental graph partitioning. Section 4 describes a multilevel
approach to solve the linear programming-based incremental graph partitioning. Experimental results of our
methods on sample meshes are described in Section 5, and conclusions are given in Section 6.
Problem definition
Consider a graph represents a set of vertices, E represents a set of undirected edges, the
number of vertices is given by and the number of edges is given by jEj. The graph-partitioning
problem can be defined as an assignment scheme that maps vertices to partitions. We denote
by B(q) the set of vertices assigned to a partition q, i.e., qg.
The weight w i corresponds to the computation cost (or weight) of the vertex v i . The cost of an edge
given by the amount of interaction between vertices v 1 and v 2 . The weight of every partition
can be defined as
The cost of all the outgoing edges from a partition represent the total amount of communication cost
and is given by
We would like to make an assignment such that the time spent by every node is minimized, i.e.,
represents the ratio of cost of unit computation/cost of unit communication
on a machine. Assuming computational loads are nearly balanced (W (0) - W (1) -
the second term needs to be minimized. In the literature
P C(q) has also been used to represent the
communication.
Assume that a solution is available for a graph G(V; E) by using one of the many available methods in
the literature, e.g., the mapping function M is available such that
and the communication cost is close to optimal. Let G 0 be an incremental graph of G(V; E)
i.e., some vertices are added and some vertices are deleted. Similarly,
i.e., some edges are added and some are deleted. We would like to find a new mapping
that the new partitioning is as load balanced as possible and the communication cost is minimized.
The methods described in this paper assume that G 0 sufficiently similar to G(V; E) that this
can be achieved, i.e., the number of vertices and edges added/deleted are a small fraction of the original
number of vertices and edges.
3 Incremental partitioning
In this section we formulate incremental graph partitioning in terms of linear programming. A high-level
overview of the four phases of our incremental graph-partitioning algorithm is shown in Figure 1. Some
notation is in order.
Let
1. P be the number of partitions.
2. represent the set of vertices in partition i.
3. - represent the average load for each partition
The four steps are described in detail in the following sections.
1: Assign the new vertices to one of the partitions (given by M 0 ).
Step 2: Layer each partition to find the closest partition for each vertex (given by L 0 ).
Step 3: Formulate the linear programming problem based on the mapping of Step 1 and balance loads (i.e., modify M 0 ) minimizing
the total number of changes in M 0 .
Step 4: Refine the mapping in Step 2 to reduce the communication cost.

Figure

1: The different steps used in our incremental graph-partitioning algorithm.
3.1 Assigning an initial partition to the new nodes
The first step of the algorithm is to assign an initial partition to the nodes of the new graph (given by
simple method for initializing M 0 (V ) is given as follows. Let
For all the vertices
d(v; x) is the shortest distance in the graph G 0 For the examples considered in this paper we assume
that G 0 is connected. If this is not the case, several other strategies can be used.
is connected, this graph can be used instead of G for calculation of M 0 (V ).
connected, then the new nodes that are not connected to any of the old
nodes can be clustered together (into potentially disjoint clusters) and assigned to the partition that
has the least number of vertices.
For the rest of the paper we will assume that M 0 (v) can be calculated using the definition in (7), although
the strategies developed in this paper are, in general, independent of this mapping. Further, for ease of
presentation, we will assume that the edge and the vertex weights are of unit value. All of our algorithms
can be easily modified if this is not the case. Figure 2 (a) describes the mapping of each the vertices of a
graph.

Figure

(b) describes the mapping of the additional vertices using the above strategy.
3.2 Layering each partition
The above mapping would ordinarily generate partitions of unequal size. We would like to move vertices
from one partition to another to achieve load balancing, while keeping the communication cost as small as
possible. This is achieved by making sure that the vertices transferred between two partitions are close to
the boundary of the two partitions. We assign each vertex of a given partition to a different partition it is
close to (ties are broken arbitrarily).
(b)

Figure

2: (a) Initial Graph (b) Incremental Graph (New vertices are shown by "*").
where x is such that
min
is is the shortest distance in the graph between v and x.
A simple algorithm to perform the layering is given in Figure 3. It assumes the graph is connected. Let
the number of such vertices of partition i that can be moved to partition j. For the example
case of Figure 3, labels of all the vertices are given in Figure 4. A label 2 of vertex in partition 1 corresponds
to the fact that this vertex belongs to the set that contributed to ff 12 .
3.3 Load balancing
the number of vertices to be moved from partition i to partition j to achieve load balance.
There are several ways of achieving load balancing. However, since one of our goals is to minimize communication
cost, we would like to minimize
l ij , because this would correspond to a minimization of the
amount of vertex movement (or "deformity") in the original partitions. Thus the load-balancing step can be
formally defined as the following linear programming problem.
Minimize X
subject to
Constraint 12 corresponds to the load balance condition.
The above formulation is based on the assumption that changes to the original graph are small and
the initial partitioning is well balanced, hence moving the boundaries by a small amount will give balanced
partitioning with low communication cost.
f map[v[j]] represents the mapping of vertex j. g
represents the j th element of the local adjacent list in partition i. g
represents the starting address of vertex j in the local adjacent list of partition i. g
i represents the set of vertices of partition i at a distance k from a node in partition j.
f Neighbor i represents the set of partitions which have common boundaries with partition i. g
For each partition i do
For vertex do
For do
Count
if
l
Add v[j] into S (tag;0)
f where
level := 0
repeat
For do
For vertex v[j] 2 S (k;level)
do
For l /\Gamma xadj i [v[j]] to xadj do
count
Add v[j] into tmpS
level
For vertex v[j] 2 tmpS do
Add v[j] into S (tag;level)
f where count i
until
For do
0-k!level

Figure

3: Layering Algorithm
(b)

Figure

4: Labeling the nodes of a graph to the closest outside partition; (a) a microscopic view of the layering
for a graph near the boundary of three partitions; (b) layering of the graph in Figure 2 (b); no edges are
shown.
Constraints in (11):
l
Constraints in (12):
\Gammal
\Gammal
Solution using the Simplex Method
l
all other values are zero.

Figure

5: Linear programming formulation and its solution, based on the mapping of the graph in Figure 2;
(b) using the labeling information in Figure 4 (b).
There are several approaches to solving the above linear programming problem. We decided to use the
simplex method because it has been shown to work well in practice and because it can be easily parallelized. 1
The simplex formulation of the example in Figure 2 is given in Figure 5. The corresponding solution is l
and l 1. The new partitioning is given in Figure 6.
20Initial partitions
Incremental partitions

Figure

The new partition of the graph in Figure 2 (b) after the Load Balancing step.
The above set of constraints may not have a feasible solution. One approach is to relax the constraint in
(11) and not have l ij constraint. Clearly, this would achieve load balance but may lead to major
modifications in the mapping. Another approach is to replace the constraint in (12) by
Assuming would not achieve load balancing in one step, but several such steps can be
applied to do so. If a feasible solution cannot be found with a reasonable value of \Delta (within an upper bound
C), it would be better to start partitioning from scratch or solve the problem by adding only a fraction of
the nodes at a given time, i.e., solve the problem in multiple stages. Typically, such cases arise when all the
new nodes correspond to a few partitions and the amount of incremental change is greater than the size of
one partition.
3.4 Refinement of partitions
The formulation in the previous section achieves load balance but does not try explicitly to reduce the number
of cross-edges. The minimization term in (10) and the constraint in (11) indirectly keep the cross-edges to
a minimum under the assumption that the initial partition is good. In this section we describe a linear
programming-based strategy to reduce the number of cross-edges, while still maintaining the load balance.
This is achieved by finding all the vertices of partitions i on the boundary of partition i and j such that
the cost of edges to the vertices in j are larger than the cost of edges to local vertices (Figure 7), i.e., the
total cost of cross-edges will decrease by moving the vertex from partition i to j, which will affect the load
We have used a dense version of simplex algorithm. The total time can potentially be reduced by using sparse representation.
local
non-local edge to partition
non-local edge to partition = 3
(a)

Figure

7: Choosing vertices for refinement. (a) Microscopic view of a vertex which can be moved from
partition P i to P j , reducing the number of cross edges; (b) the set of vertices with the above property in the
partition of Figure 6.
balance. In the following a linear programming formulation is given that moves the vertices while keeping
the load balance.
mapping of each vertex after the load-balancing step. Let out(k;
represent the number of edges of vertex k in partition M 00 (k) connected to partition j(j 6= M 00 (k)), and let
represent the number of vertices a vertex k is connected to in partition M 00 (k). Let b ij represent the
number of vertices in partition i which have more outgoing edges to partition j than local edges.
We would like to maximize the number of vertices moved so that moving a vertex will not increase the
cost of cross-edges. The inequality in the above definition can be changed to a strict inequality. We leave
the equality, however, since by including such vertices the number of points that can be moved can be larger
(because these vertices can be moved to satisfy load balance constraints without affecting the number of
cross-edges).
The refinement problem can now be posed as the following linear programming problem:
Maximize X
such that
This refinement step can be applied iteratively until the effective gain by the movement of vertices is
small. After a few steps, the inequalities (l ij need to be replaced by strict inequalities (l ij
Constraint (15)
l
Load Balancing Constraint (16)
\Gammal
\Gammal
Solution using Simplex Method
l

Figure

8: Formulation of the refinement step using linear programming and its solution.
otherwise, vertices having an equal number of local and nonlocal vertices may move between boundaries
without reducing the total cost. The simplex formulation of the example in Figure 6 is given in Figure 8,
and the new partitioning after refinement is given in Figure 9.
20Incremental partitions
Refined partitions

Figure

9: The new partition of the graph in Figure 6 after the Refinement step.
3.5 Time complexity
Let the number of vertices and the number of edges in a graph be given by V and E, respectively. The time
for layering is O(V +E). Let the number of partitions be P and the number of edges in the partition graph 2
Each node of this graph represents a partition. An edge in the super graph is present whenever there are any cross edges
from a node of one partition to a node of another partition.
be R. The number of constraints and variables generated for linear programming are O(P +R) and O(2R),
respectively.
Thus the time required for the linear programming is O((P +R)R). Assuming R is O(P ), this reduces to
The number of iterations required for linear programming is problem dependent. We will use f(P
to denote the number of iterations. Thus the time required for the linear programming is O(P 2 f(P )). This
gives the total time for repartitioning as O(E
The parallel time is considerably more difficult to analyze. We will analyze the complexity of neglecting
the setup overhead of coarse-grained machines. The parallel time complexity of the layering step depends on
the maximum number of edges assigned to any processor. This could be approximated by O(E=P ) for each
level, assuming the changes to the graph are incremental and that the graph is much larger than the number
of processors. The parallelization of the linear programming requires a broadcast of length proportional to
O(P ). Assuming that a broadcast of size P requires b(P ) amount of time on a parallel machine with P
processors, the time complexity can be approximated by O( E
4 A multilevel approach
For small graphs a large fraction of the total time spent in the algorithm described in the previous section
will be on the linear programming formulation and its solution. Since the time required for one iteration
of the linear programming formulation is proportional to the square of the number of partitions, it can be
substantially reduced by using a multilevel approach. Consider the partitioning of an incremental graph
for partitions. This can be completed in two stages: partitioning the graph into 4 super partitions and
partitioning each of the 4 super partitions into 4 partitions each. Clearly, more than two stages can be used.
The advantage of this algorithm is that the time required for applying linear programming to each stage
would be much less than the time required for linear programming using only one stage. This is due to a
substantial reduction in the number of variables as well as in the constraints, which are directly dependent
on the number of of partitions. However, the mapping initialization and the layering needs to be performed
from scratch for each level. Thus the decrease in cost of linear programming leads to a potential increase in
the time spent in layering.
The multilevel algorithm requires combining the partitions of the original graph into super partitions.
For our implementations, recursive spectral bisection was used as an ab initio partitioning algorithm. Due
to its recursive property it creates a natural hierarchy of partitions. Figure 10 shows a two-level hierarchy
of partitions. After the linear programming-based algorithm has been applied for repartitioning a graph
that has been adapted several times, it is possible that some of the partitions corresponding to a lower level
subtree have a small number of boundary edges between them. Since the multilevel approach results in
repartitioning with a small number of partitions at the lower levels, the linear programming formulations
may produce infeasible solutions at the lower levels. This problem can be partially addressed by reconfiguring
the partitioning hierarchy.
A simple algorithm can be used to achieve reconfiguration. It tries to group proximate partitions
to form a multilevel hierarchy. At each level it tries to combine two partitions into one larger parti-
tion. Thus the number of partitions is reduced by a factor of two at every level by using a procedure
FIND UNIQUE NEIGHBOR(P ) (Figure 11), which finds a unique neighbor for each partition such that the
number of cross-edges between them is as large as possible. This is achieved by applying a simple heuristic

Figure

12) that uses a list of all the partitions in a random order (each processor has a different order). If
more than one processor is successful in generating a feasible solution, ties are broken based on the weight
and the processor number. The result of the merging is broadcast to all the processors. In case none of the

Figure

10: A two-level hierarchy of 16 partitions
partitions g
represents the number of edges from partition i to partition j. g
global success := FALSE
trial := 0
While (not global success) and (trial ! T ) do
For each processor i do
list of all partitions in a random order
Weight := 0
FIND PAIR(success;Mark;Weight; Edge)
global success := GLOBAL OR(success)
if (not global success) then
FIX PAIR(success;Mark;Weight; Edge)
global success := GLOBAL OR(success)
if (global success) then
winner := FIND WINNER(success;Weight)
f Return the processor number of maximum Weight g
f Processor winner broadcast Mark to all the processors g
return(global success)
else
trial := trial+1

Figure

Reconstruction Algorithm
FIND PAIR(success; Mark;W eight; Edge)
success := TRUE
for
Find a neighbor k of j where (Mark[k] !
if k exists then
Weight
else
success := FALSE
FIX PAIR(success; Mark;W eight; Edge)
success := TRUE
While (j ! P ) and (success) do
if a x exists such that (Mark[x] ! 0), (x is a neighbor of l), is a neighbor of
Mark[x] := l Mark[l] := x
Weight
else
success := FALSE
else

Figure

12: A high level description of the procedures used in FIND UNIQUE NEIGHBOR.
processors are successful, another heuristic (Figure 12) is applied that tries to modify the partial assignments
made by heuristic 1 to find a neighbor for each partition. If none of the processors are able to find a feasible
solution, each processor starts with another random solution and the above step is iterated a constant
number (L) times. 3 Figure 11 shows the partition reconfiguration for a simple example.
If the reconfiguration algorithm fails, the multilevel algorithm can be applied with a lower number of
levels (or only one level).
Random_list
Random_list
Random_list
Random_list
(a) (b) (a)
(d) (e) (f)

Figure

13: A working example of the reconstruction algorithm. (a) Graph with 4 partitions; (b) partition
(c) adjacency lists; (d) random order lists; (e) partition rearrangement; (f) processor 3 broadcasts
the result to the other processors; (g) hierarchy after reconfiguration.
3 In practice, we found that the algorithm never requires more than one iteration.
4.1 Time complexity
In the following we provide an analysis assuming that reconfiguration is not required. The complexity of
reconfiguration will be discussed later. For the multilevel approach we assume that at each level the number
of partitions done is equal and given by k. Thus the number of levels generated is log k P . The time required
for layering increases to O(Elog k P ). The number of linear programming formulations can be given by
O( P
Thus the total time for linear programming can be given by O( P
f(k)). The total time required
for repartitioning is given by O(Elog k P value of k would minimize the sum of
the cost of layering and the cost of the linear programming formulation. The choice of k also depends on the
quality of partitioning achieved; increasing the number of layers would, in general, have a deteriorating effect
on the quality of partitioning. Thus values of k have to be chosen based on the above tradeoffs. However, the
analysis suggests that for reasonably sized graphs the layering time would dominate the total time. Since the
layering time is bounded by O(ElogP ), this time is considerably lower than applying spectral bisection-based
methods from scratch.
Parallel time is considerably more difficult to analyze. The parallel time complexity of the layering step
depends on the maximum number of edges any processor has for each level. This can be approximated by
each level, assuming the changes to the graph are incremental and that the graph is much larger
than the number of processors. As discussed earlier, the parallelization of linear programming requires a
broadcast of length proportional to O(k). For small values of k, each linear programming formulation has to
be executed on only one processor, else the communication will dominate the total time. Thus the parallel
time is proportional to O( E
The above analysis did not take reconfiguration into account. The cost of reconfiguration requires O(kd 2 )
time in parallel for every iteration, where d is the average number of partitions to which every partition is
connected. The total time is O(kd 2 log P ) for the reconfiguration. This time should not dominate the total
time required by the linear programming algorithm.
5 Experimental results
In this section we present experimental results of the linear programming-based incremental partitioning
methods presented in the previous section. We will use the term "incremental graph partitioner" (IGP) to
refer to the linear programming based algorithm. All our experiments were conducted on the 32-node CM-5
available at NPAC at Syracuse University.
Meshes
We used two sets of adaptive meshes for our experiments. These meshes were generated using the DIME
environment [15]. The initial mesh of Set A is given in Figure 14 (a). The other incremental meshes are
generated by making refinements in a localized area of the initial mesh. These meshes represent a sequence
of refinements in a localized area. The number of nodes in the meshes are 1071, 1096, 1121, 1152, and 1192,
respectively.
The partitioning of the initial mesh (1071 nodes) was determined using recursive spectral bisection. This
was the partitioning used by algorithm IGP to determine the partitioning of the incremental mesh (1096
nodes). The repartitioning of the next set of refinement (1121, 1152, and 1192 nodes, respectively) was
achieved using the partitioning obtained by using the IGP for the previous mesh in the sequence. These
meshes are used to test whether IGP is suitable for repartitioning a mesh after several refinements.

Figure

14: Test graphs set A (a) an irregular graph with 1071 nodes and 3185 edges; (b) graph in (a) with
additional nodes; (c) graph in (b) with 25 additional nodes; (d) graph in (c) with 31 additional nodes;
graph in (d) with 40 additional nodes.

Figure

15: Test graphs Set B (a) a mesh with 10166 nodes and 30471 edges; (b) mesh a with 48 additional
nodes; (c) mesh a with 139 additional nodes; (d) mesh a with 229 additional nodes; (e) mesh a with 672
Results
Initial Graph - Figure 14 (a)
Total Cutset Max Cutset Min Cutset
Figure 14 (b)
Partitioner Time-s Time-p Total Cutset Max Cutset Min Cutset
Spectral Bisection 31.71 - 733 56 33
IGP 14.75 0.68 747 55 34
IGP with Refinement 16.87 0.88 730 54 34
Figure 14 (c)
Partitioner Time-s Time-p Total Cutset Max Cutset Min Cutset
Spectral Bisection 34.05 - 732 56 34
IGP 13.63 0.73 752 54 33
IGP with Refinement 16.42 1.05 727 54 33
Figure 14 (d)
Partitioner Time-s Time-p Total Cutset Max Cutset Min Cutset
Spectral Bisection 34.96 - 716 57 34
IGP 15.89 0.92 757 56 33
IGP with Refinement 18.32 1.28 741 56 33
Partitioner Time-s Time-p Total Cutset Max Cutset Min Cutset
Spectral Bisection 38.20 - 774 63 34
IGP 15.69 0.94 815 63 34
IGP with Refinement 18.43 1.26 779 59 34
Time unit in seconds. p - parallel timing on a 32-node CM-5. s - timing on 1-node CM-5.

Figure

Incremental graph partitioning using linear programming and its comparison with spectral bisection
from scratch for meshes in Figure 14 (Set A).
The next data set (Set B) corresponds to highly irregular meshes with 10166 nodes and 30471 edges.
This data set was generated to study the effect of different amounts of new data added to the original mesh.

Figures

17 (b), 17 (c), 17 (d), and 17 (e) correspond to meshes with 68, 139, 229, and 672 additional nodes
over the mesh in Figure 15.
The results of the one-level IGP for Set A meshes are presented in Figure 16. The results show that, even
after multiple refinements, the quality of partitioning achieved is comparable to that achieved by recursive
spectral bisection from scratch, thus this method can be used for repartitioning several stages. The time
required by repartitioning is about half the time required for partitioning using RSB. The algorithm provides
speedup of around 15 to 20 on a 32-node CM-5. Most of the time spent by our algorithm is in the solution
of the linear programming formulation using the simplex method. The number of variables and constraints
generated by the one-level linear programming algorithm for the load-balancing step for meshes in Figure
partitions are 188 and 126, respectively.
For the multilevel approach, the linear programming formulation for each subproblem at a given level
Initial Graph - Figure 15 (a)
Total Cutset Max Cutset Min Cutset
(b) Initial assignment by IGP using the partition of Figure 15 (a')
Partitioner Time-s Time-p Total Cutset Max Cutset Min Cutset
Spectral Bisection 800.05 - 2137 178 90
IGP before Refinement 13.90 1.01 2139 186 84
IGP after Refinement 24.07 1.83 2040 172 82
(c) Initial assignment by IGP using the partition of Figure 15 (a')
Partitioner Time-s Time-p Total Cutset Max Cutset Min Cutset
Spectral Bisection 814.36 - 2099 166 87
IGP before Refinement 18.89 1.08 2295 219 93
IGP after Refinement 29.33 2.01 2162 206 85
(d) Initial assignment by IGP using the partition of Figure 15 (a')
Partitioner Time-s Time-p Total Cutset Max Cutset Min Cutset
Spectral Bisection 853.35 - 2057 169 94
IGP before Refinement (2) 35.98 2.08 2418 256 92
IGP after Refinement 43.86 2.76 2139 190 85
Initial assignment by IGP using the partition of Figure 15 (a')
Partitioner Time-s Time-p Total Cutset Max Cutset Min Cutset
Spectral Bisection 904.81 - 2158 158 94
IGP before Refinement (3) 76.78 3.66 2572 301 102
IGP after Refinement 89.48 4.39 2270 237 96
Time unit in seconds. p - parallel timing on a 32-node CM-5. s - timing on 1-node CM-5.

Figure

17: Incremental graph partitioning using linear programming and its comparison with spectral bisection
from scratch for meshes in Figure 15 (Set B).
was solved by assigning a subset of processors. Table 19 gives the time required for different algorithms and
the quality of partitioning achieved for different numbers of levels. A 4 \Theta 4 \Theta 2-based repartitioning implies
that the repartitioning was performed in three stages with decomposition into 4, 4, 2 partitions, respectively.
The results are presented in Figure 19. The solution qualities of multilevel algorithms show an insignificant
deterioration in number of cross edges and a considerable reduction in total time.
The partitioning achieved by algorithm IGP for Set B meshes in Figure 18 using the partition of mesh
in

Figure

15 (a) is given in Figure 17. The number of stages required (by choosing an appropriate value of
\Delta, as described in section 2.3) were 1, 1, 2, and 3, respectively. 4 It is worth noting that, although the load
imbalance created by the additional nodes was severe, the quality of partitioning achieved for each case was
close to that of applying recursive spectral bisection from scratch. Further, the sequential time is at least
an order of magnitude better than that of recursive spectral bisection. The CM-5 implementation improved
the time required by a factor of 15 to 20. The time required for repartitioning Figure 17 (b) and Figure 17
(c) is close to that required for meshes in Figure 14. The timings for meshes in Figure 17 (d) and 17 (e) are
larger because they use multiple stages. The time can be reduced by using a multilevel approach (Figure 20).
However, the time reduction is relatively small (from 24.07 seconds to 6.70 seconds for a two-level approach).
Increasing the number of levels increases the total time as the cost of layering increases. The time reduction
for the last mesh (10838 nodes) is largely due to the reduction of the number of stages used in the multilevel
algorithm (Section 3.3). For almost all cases a speedup of 15 to 25 was achieved on a 32-node CM-5.

Figure

21 and Figure 22 show the detailed timing for different steps for the mesh in Figure 14 (d) and
mesh in Figure 15 (b) of the sequential and parallel versions of the repartitioning algorithm, respectively.
Clearly, the time spent in reconfiguration is negligible compared to the total execution time. Also, the time
spent for linear programming in a multilevel algorithm is much less than that in a single-level algorithm.
The results also show that the time for the linear programming remains approximately the same for both
meshes, while the time for layering is proportionally larger. For the multilevel parallel algorithm, the time for
layering is comparable with the time spent on linear programming for the smaller mesh, while it dominates
the time for the larger mesh. Since the layering term is O(levels E
results support the complexity
analysis in the previous section. The time spent on reconfiguration is negligible compared to the total time.
6 Conclusions
In this paper we have presented novel linear programming-based formulations for solving incremental graph-partitioning
problems. The quality of partitioning produced by our methods is close to that achieved by
applying the best partitioning methods from scratch. Further, the time needed is a small fraction of the
latter and our algorithms are inherently parallel. We believe the methods described in this paper are of
critical importance in the parallelization of adaptive and incremental problems.
4 The number of stages chosen were by trial and error, but can be determined by the load imbalance.
(b

Figure

Partitions using RSB; (b 0 ) partitions using IGP starting from a using IGP
starting from a 0 ; (d 0 ) partitions using IGP starting from a 0 ; using IGP starting from a 0 .
Graph Level Description Time-s Time-p Total Cutset
Time unit in seconds on CM-5.

Figure

19: Incremental multilevel graph partitioning using linear programming and its comparison with
single-level graph partitioning for the sequence of graphs in Figure 14.
Graph Level Description Time-s Time-p Total Cutset
Time unit in seconds on CM-5.

Figure

20: Incremental multilevel graph partitioning using linear programming and its comparison with
single-level graph partitioning for the sequence of meshes in Figure 15.
in Figure 14 (d)
Level Reconfiguration Layering Linear programming Total
Figure 15 (b)
Level Reconfiguration Layering Linear programming Total
Time in seconds
Balancing. R - Refinement. T - Total.

Figure

21: Time required for different steps in the sequential repartitioning algorithm.
in Figure 14 (d)
Level Reconfiguration Layering Linear programming Data movement Total
Figure 15 (b)
Level Reconfiguration Layering Linear programming Data movement Total
Time in seconds
Balancing. R - Refinement. T - Total.

Figure

22: Time required for different steps in the parallel repartitioning algorithm (on a 32-node CM-5).



--R

Solving Problems on Concurrent Processors
Software Support for Irregular and Loosely Synchronous Problems.
Heuristic Approaches to Task Allocation for Parallel Computing.
Load Balancing Loosely Synchronous Problems with a Neural Network.
Solving Problems on Concurrent Processors
Graphical Approach to Load Balancing and Sparse Matrix Vector Multiplication on the Hypercube.
An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations.
Multidimensional Spectral Load Balancing.
Genetic Algorithms for Graph Partitioning and Incremental Graph Partitioning.
Physical Optimization Algorithms for Mapping Data to Distributed-Memory Multi- processors
Solving Finite Element Equations on Current Computers.
Fast Mapping And Remapping Algorithm For Irregular and Adaptive Problems.
Partitioning Sparse Matrices with Eigenvectors of Graphs.
Partitioning of Unstructured Mesh Problems for Parallel Processing.
DIME: Distributed Irregular Mesh Enviroment.
Performance of Dynamic Load-Balancing Algorithm for Unstructured Mesh Calcula- tions
--TR

--CTR
Sung-Ho Woo , Sung-Bong Yang, An improved network clustering method for I/O-efficient query processing, Proceedings of the 8th ACM international symposium on Advances in geographic information systems, p.62-68, November 06-11, 2000, Washington, D.C., United States
Mark J. Clement , Glenn M. Judd , Bryan S. Morse , J. Kelly Flanagan, Performance Surface Prediction for WAN-Based Clusters, The Journal of Supercomputing, v.13 n.3, p.267-281, May 1999
Don-Lin Yang , Yeh-Ching Chung , Chih-Chang Chen , Ching-Jung Liao, A Dynamic Diffusion Optimization Method for Irregular Finite Element Graph Partitioning, The Journal of Supercomputing, v.17 n.1, p.91-110, Aug. 2000
Ching-Jung Liao , Yeh-Ching Chung, Tree-Based Parallel Load-Balancing Methods for Solution-Adaptive Finite Element Graphs on Distributed Memory Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.10 n.4, p.360-370, April 1999
John C. S. Lui , M. F. Chan, An Efficient Partitioning Algorithm for Distributed Virtual Environment Systems, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.193-211, March 2002
Yeh-Ching Chung , Ching-Jung Liao , Don-Lin Yang, A Prefix Code Matching Parallel Load-Balancing Method for Solution-Adaptive Unstructured Finite Element Graphs on Distributed Memory Multicomputers, The Journal of Supercomputing, v.15 n.1, p.25-49, Jan. 2000
Umit Catalyurek , Cevdet Aykanat, A hypergraph-partitioning approach for coarse-grain decomposition, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.28-28, November 10-16, 2001, Denver, Colorado
Umit Catalyurek , Cevdet Aykanat, Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication, IEEE Transactions on Parallel and Distributed Systems, v.10 n.7, p.673-693, July 1999
Cevdet Aykanat , B. Barla Cambazoglu , Ferit Findik , Tahsin Kurc, Adaptive decomposition and remapping algorithms for object-space-parallel direct volume rendering of unstructured grids, Journal of Parallel and Distributed Computing, v.67 n.1, p.77-99, January, 2007
Y. F. Hu , R. J. Blake, Load balancing for unstructured mesh applications, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
remapping;mapping;refinement;parallel;linear-programming