Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs

George Karypis and Vipin Kumar
SIAM Review, Vol. 41, No. 2, pp. 278 - 300, 1999
Download Paper
In this paper we present a parallel formulation of a multilevel k-way graph partitioning
algorithm. A key feature of this parallel formulation is that it is able to achieve a high
degree of concurrency while maintaining the high quality of the partitions produced by
the serial multilevel k-way partitioning algorithm. In particular, the time taken by our
parallel graph partitioning algorithm is only slightly longer than the time taken for rearrangement
of the graph among processors according to the new partition. Experiments
with a variety of finite element graphs show that our parallel formulation produces highquality
partitionings in a short amount of time. For example, a 128-way partitioning of
graphs with one million vertices can be computed in a little over two seconds on a 128-processor Cray T3D. Furthermore, the quality of the partitions produced is comparable
(edge-cuts within 5%) to those produced by the serial multilevel k-way algorithm. Thus
our parallel algorithm makes it feasible to perform frequent repartitioning of graphs in
dynamic computations without compromising the partitioning quality.
Research topics: Graph partitioning | Parallel processing | ParMETIS