Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs
| George Karypis and Vipin Kumar |
| Supercomputing, 1996 |
Download Paper  |
| Abstract 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 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 higher than the time taken for re-arrangement of the graph among processors according to the new partition. Experiments with a variety of finite element graphs show that our parallel formulation produces high quality partitioning in small amount of time. For example, an 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 produced partitions are 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. |
| Comments This paper describes the parallel algorithm used in early versions of [hlink:[metis/parmetis/overview][ParMETIS]]. |
| Research topics: Graph partitioning | Parallel processing | ParMETIS |