A Parallel Hill-Climbing Refinement Algorithm for Graph Partitioning
| Dominique LaSalle and George Karypis |
| 45th International Conference on Parallel Processing (ICPP), 2016 |
Download Paper  |
| Abstract Graph partitioning is an important step in distributing workloads on parallel compute systems, sparse matrix re-ordering, and VLSI circuit design. Refinement algorithms are used to improve existing partitionings, and are traditionally difficult to parallelize. Existing parallel refinement algorithms make concessions in terms of quality in order to extract concurrency. In this work we present a new shared-memory parallel k-way method of refining an existing partitioning that can break out of local minima. This allows our method, unlike previous approaches, to both scale well in terms of the number of threads and produce clusterings of quality equal to serial methods. Our method achieves speedups of 5.7?16.7× using 24 threads, while exhibiting only 0.52% higher edgecuts than when run serially. This is 6.3× faster and 1.9% better quality than other parallel refinement methods which can break out of local minima. |
| Comments This is an extended version of the ICPP paper. |
| Research topics: Graph partitioning | METIS | Parallel processing | Scientific computing |