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  |
| Abstract 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. |
| Comments 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 |