A Coarse-Grain Parallel Formulation of Multilevel k-way Graph Partitioning Algorithm

George Karypis and Vipin Kumar
8th SIAM Conference on Parallel Processing for Scientific Computing, 1997
Download Paper
In this paper we present a parallel formulation of a multilevel k-way graph partitioning algorithm, that is particularly suited for message-passing libraries that have high latency. The multilevel k-way partitioning algorithm reduces the size of the graph by successively collapsing vertices and edges (coarsening phase), finds a k-way partitioning of the smaller graph, and then it constructs a k-way partitioning for the original graph by projecting and refining the partition to successively finer graphs (uncoarsening phase). Our algorithm is able to achieve a high degree of concurrency, while maintaining the high quality partitions produced by the serial algorithm.
This paper describes the strategy used to parallelize the graph partitioning problem in the current implementation of [hlink:[metis/parmetis/overview][ParMETIS]].
Research topics: Graph partitioning | Parallel processing | ParMETIS