Parallel multilevel k-way partitioning scheme for irregular graphs

ABSTRACT

In this paper we present a parallel formulation of a multilevel k-way graph partitioning algorithm. The multilevel k-way partitioning algorithm reduces the size of the graph by collapsing vertices and edges (coarsening phase), finds a k-way partition of the smaller graph, and then it constructs a k-way partition for the original graph by projecting and refining the partition to successively finer graphs (uncoarsening phase). A key innovative feature of our parallel formulation is that it utilizes graph coloring to effectively parallelize both the coarsenin and the refinement during the uncoarsening phase. Our algorithm is able to achieve a high degree of concurrency, while maintaining the high quality partitions produced by the serial algorithm. We test our scheme on a large number of graphs from finite element methods, and transportation domains. Our parallel formulation on Cray T3D, produces high quality 128-way partitions on 128 processors in a little over two seconds, for graphs with a million vertices. Thus our parallel algorithm makes it possible to perform dynamic graph partition in adaptive computations without compromising quality.

REFERENCES

• 1: Stephen T. Barnard, PMRSB: parallel multilevel recursive spectral bisection, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.27-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224227]
• 2: Stephen T. Barnard and Horst Simon. A parallel implementation of multilevel recursive spectral bisection for application to adaptive unstructured meshes. In Proceedings of the seventh SIAM conference on Parallel Processing for Scientific Computing, pages 627-632, 1995.
• 3: Stephen T. Barnard and Horst D. Simon. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. In Proceedings of the sixth SIAM conference on Parallel Processing for Scientific Computing, pages 711-718, 1993.
• 4: T. Bui and C. Jones. A heuristic for reducing fill in sparse matrix factorization. In 6th SIAM Conf. Parallel Processing for Scientific Computing, pages 445-452, 1993.
• 5: Chung-Kuan Cheng and Yen-Chuen A. Wei. An improved two-way partitioning algorithm with stable performance. IEEE Transactions on Computer Aided Design, 10(12):1502-1511, December 1991.
• 6: Pedro Diniz, Steve Plimpton, Bruce Hendrickson, and Robert Leland. Parallel algorithms for dynamically partitioning unstructured grids. In Proceedings of the seventh SIAM conference on Parallel Processing for Scientific Computing, pages 615-620, 1995.
• 7: J. Garbers, H. J. Promel, and A. Steger. Finding clusters in VLSI circuits. In Proceedings of IEEE International Conference on Computer Aided Design, pages 520-523, 1990.
• 8: A. George. Nested dissection of a regular finite-element mesh. SIAM Journal on Numerical Ananlysis, 10:345-363, 1973.
• 9: John R. Gilbert , Earl Zmijewski, A parallel graph partitioning algorithm for a message-passing multiprocessor, International Journal of Parallel Programming, v.16 n.6, p.427-449, December 1987 [doi>10.1007/BF01388998]
• 10: Anshul Gupta , George Karypis , Vipin Kumar, Highly Scalable Parallel Algorithms for Sparse Matrix Factorization, IEEE Transactions on Parallel and Distributed Systems, v.8 n.5, p.502-520, May 1997 [doi>10.1109/71.598277]
• 11: Anshul Gupta , Vipin Kumar, A scalable parallel algorithm for sparse Cholesky factorization, Proceedings of the 1994 conference on Supercomputing, p.793-802, December 1994, Washington, D.C., United States
• 12: Lars Hagen and Andrew Kahng. Fast spectral methods for ratio cut partitioning and clustering. In Proceedings of IEEE International Conference on Computer Aided Design, pages 10-13, 1991.
• 13: Lars Hagen , Andrew B. Kahng, A new approach to effective circuit clustering, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.422-427, November 1992, Santa Clara, California, United States
• 14: Michael T. Heath , Padma Raghavan, A Cartesian Parallel Nested Dissection Algorithm, SIAM Journal on Matrix Analysis and Applications, v.16 n.1, p.235-253, Jan. 1995 [doi>10.1137/S0895479892238270]
• 15: Bruce Hendrickson and Robert Leland. A multilevel algorithm for partitioning graphs. Technical Report SAND93-1301, Sandia National Laboratories, 1993.
• 16: Bruce Hendrickson and Robert Leland. The chaco user's guide, version 2.0. Technical Report SAND94-2692, Sandia National Laboratories, 1994.
• 17: Bruce Hendrickson and Edward Rothberg. Improving the runtime and quality of nested dissection ordering. Technical Report CS-96-000, Sandia National Laboratories, 1996.
• 18: Zdenek Johan, Kapil K. Mathur, S. Lennart Johnsson, and Thomas J. R. Hughes. Finite element methods on the connection machine cm-5 system. Technical report, Thinking Machines Corporation, 1993.
• 19: G. Karypis and V. Kumar. Analysis of multilevel graph partitioning. Technical Report TR 95-037, Department of Computer Science, University of Minnesota, 1995. Also available on WWW at URL http://www.cs.umn.edu/~karypis/papers/mlevel_analysis.ps. A short version appears in Supercomputing 95.
• 20: G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. Technical Report TR 95-035, Department of Computer Science, University of Minnesota, 1995. Also available on WWW at URL http://www.cs.umn.edu/~karypis/papers/mlevel_serial.ps. A short version appears in Intl. Conf. on Parallel Processing 1995.
• 21: G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Technical Report TR 95-064, Department of Computer Science, University of Minnesota, 1995. Also available on WWW at URL http://www.cs.umn.edu/~karypis/papers/mlevel_kway.ps.
• 22: George Karypis , Vipin Kumar, Parallel Multilevel Graph Partitioning, Proceedings of the 10th International Parallel Processing Symposium, p.314-319, April 15-19, 1996
• 23: George Karypis , Vipin Kumar, Graph partitioning and its applications to scientific computing, 1996
• 24: George Karypis and Vipin Kumar. Fast sparse Cholesky factorization on scalable parallel computers. Technical report, Department of Computer Science, University of Minnesota, Minneapolis, MN, 1994. A short version appears in the Eighth Symposium on the Frontiers of Massively Parallel Computation, 1995. Available on WWW at URL http://www.cs.umn.edu/~karypis/papers/frontiers95.ps.
• 25: B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 1970.
• 26: Vipin Kumar , Ananth Grama , Anshul Gupta , George Karypis, Introduction to parallel computing: design and analysis of algorithms, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• 27: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 28: Gary L. Miller, Shang-Hua Teng, W. Thurston, and Stephen A. Vavasis. Automatic mesh partitioning. In A. George, John R. Gilbert, and J. W.-H. Liu, editors, Sparse Matrix Computations: Graph Theory Issues and Algorithms. (An IMA Workshop Volume). Springer-Verlag, New York, NY, 1993.
• 29: Gary L. Miller , Shang-Hua Teng , Stephen A. Vavasis, A unified geometric approach to graph separators, Proceedings of the 32nd annual symposium on Foundations of computer science, p.538-547, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185417]
• 30: B. Nour-Omid, A. Raefsky, and G. Lyzenga. Solving finite element equations on concurrent computers. In A. K. Noor, editor, American Soc. Mech. Eng, pages 291-307, 1986.
• 31: N. Mansour , R. Ponnusamy , A. Choudhary , G. C. Fox, Graph contraction for physical optimization methods: a quality-cost tradeoff for mapping data on parallel computers, Proceedings of the 7th international conference on Supercomputing, p.1-10, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165942]
• 32: Padma Raghavan, Line and plane separators, University of Illinois at Urbana-Champaign, Champaign, IL, 1993
• 33: Padma Raghavan, Parallel Ordering Using Edge Contraction, University of Tennessee, Knoxville, TN, 1995
• 34: Edward Rothberg. Performance of panel and block approaches to sparse Cholesky factorization on the iPSC/860 and Paragon multicomputers. In Proceedings of the 1994 Scalable High Performance Computing Conference, May 1994.
• 35: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Parallel Graph Partitioning, Multilevel Partitioning Methods, Spectral Partitioning Methods, Kernighan-Lin Heuristic, Parallel Sparse Matrix Algorithms