Scalable parallel graph partitioning
Authors:
Open Access
- 17 November 2013
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-10
Abstract
We consider partitioning a graph in parallel using a large number of processors. Parallel multilevel partitioners, such as Pt-Scotch and ParMetis, produce good quality partitions but their performance scales poorly. Coordinate bisection schemes such as those in Zoltan, which can be applied only to graphs with coordinates, scale well but partition quality is often compromised. We seek to address this gap by developing a scalable parallel scheme which imparts coordinates to a graph through a lattice-based multilevel embedding. Partitions are computed with a parallel formulation of a geometric scheme that has been shown to provide provably good cuts on certain classes of graphs. We analyze the parallel complexity of our scheme and we observe speed-ups and cut-sizes on large graphs. Our results indicate that our method is substantially faster than ParMetis and Pt-Scotch for hundreds to thousands of processors, while producing high quality cuts.Keywords
Funding Information
- National Science Foundation (0821527, 0963839, 1017882)
This publication has 12 references indexed in Scilit:
- Scalable Force Directed Graph Layout Algorithms Using Fast Multipole Methods2012
- SSDE: Fast Graph Drawing Using Sampled Spectral Distance Embedding2006
- A unified geometric approach to graph separators2002
- Graph partitioning models for parallel computingParallel Computing, 2000
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- A multilevel algorithm for partitioning graphs1995
- A Cartesian Parallel Nested Dissection AlgorithmSIAM Journal on Matrix Analysis and Applications, 1995
- A Partitioning Strategy for Nonuniform Problems on MultiprocessorsIEEE Transactions on Computers, 1987
- Some simplified NP-complete problems1974
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970