Algorithms and Software for Partitioning Graphs


Graph partitioning is an NP hard problem with numerous applications. It appears in various forms in parallel computing, sparse matrix reordering, circuit placement and other important disciplines. I worked with Rob Leland for several years on heuristic methods for partitioning graphs, with a particular focus on parallel computing applications. Our contributions include:

  • Development of multilevel graph partitioning. This widely imitated approach has become the premiere algorithm combining very high quality with short calculation times.
  • Extension of spectral partitioning to enable the use of 2 or 3 Laplacian eigenvectors to quadrisect of octasect a graph.
  • Generalization of the Kernighan-Lin/Fiduccia-Mattheyses algorithm to handle weighted graphs, arbitrary number of sets and lazy initiation.
  • Development of terminal propagation to improve the mapping of a graph onto a target parallel architecture.
  • The widely used Chaco partitioning tool which includes multilevel, spectral, geometric and other algorithms.
  • More recently, I have worked with Tammy Kolda on alternatives to the standard graph partitioning model. A critique of the standard approach and a discussion of alternatives can be found below. I have also been working with Karen Devine and a number of other researchers on dynamic load balancing. Dynamic load balancing is fundamentally harder than static partitioning. Algorithms and implementations must run quickly in parallel without consuming much memory. Interfaces need to be subroutine calls instead of file transfers. And since the data is already distributed, the new partition should be similar to the current one to minimize the amount of data that needs to be redistributed. We are working to build a tool called Zoltan to address this plethora of challenges. Zoltan is designed to be extensible to different applications, algorithms and parallel architectures. For example, it is data-structure neutral - an object oriented interface separates the application data structures from those of Zoltan. The tool will also support a very general model of a parallel computer, facilitating the use of heterogeneous machines.

    Closely related to Zoltan, I have been interested in the software challenges inherent in parallelizing unstructured computations. I feel that well-designed tools and libraries are the key to addressing this problem. I have also worked with Ali Pinar and Steve Plimpton on algorithms for some of the kernel operations which arise in this setting, and relevant papers can be found here.


    Graph Partitioning Algorithms and Tools

  • The Chaco User's Guide: Version 2.0, Bruce Hendrickson and Robert Leland. Sandia Tech Report SAND94--2692, 1994.
    Paper, Abstract
  • Dynamic Load Balancing in Computational Mechanics, Bruce Hendrickson and Karen Devine. Comp. Meth. Applied Mechanics & Engineering. 184(2-4):485-500, 2000.
    Paper, Abstract
  • A Multilevel Algorithm for Partitioning Graphs, Bruce Hendrickson and Robert Leland. In Proc. Supercomputing '95. (Formerly, Technical Report SAND93-1301, 1993).
    Paper, Abstract
  • Partitioning for Complex Objectives, Ali Pinar and Bruce Hendrickson. In Proc. Irregular '01.
    Paper, Abstract
  • An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations, Bruce Hendrickson and Robert Leland. SIAM J. Sci. Stat. Comput., 16(2):452-469, 1995.
    Paper, Abstract
  • Multidimensional Spectral Load Balancing, Bruce Hendrickson and Robert Leland. In Proc. 6th SIAM Conf. Parallel Proc., 953-961, 1993.
    Paper, Abstract
  • Skewed Graph Partitioning, Bruce Hendrickson, Robert Leland and Rafael Van Driessche. In Proc. Eighth SIAM Conf. Parallel Processing for Scientific Computing.
    Paper, Abstract
  • Enhancing Data Locality by Using Terminal Propagation, Bruce Hendrickson, Robert Leland and Rafael Van Driessche. In Proc. 29th Hawaii Intl. Conf. System Science, 1996.
    Paper, Abstract
  • An Empirical Study of Static Load Balancing Algorithms, Robert Leland and Bruce Hendrickson. In Proc. Scalable High-Performance Comput. Conf., 1994.
    Paper, Abstract
  • Parallel Algorithms for Dynamically Partitioning Unstructured Grids, Pedro Diniz, Steve Plimpton, Bruce Hendrickson and Robert Leland. In Proc. 7th SIAM Conf. Parallel Proc., 1995.
    Paper, Abstract

  • Alternatives to Standard Graph Partitioning

    More recently, I have become disenchanted with the graph partitioning abstraction as it is applied to parallel computing. Some of my concerns and an effort to address them can be found in the following papers and talks.
  • Load Balancing Fictions, Falsehoods and Fallacies, Bruce Hendrickson. Appl. Math. Modelling. 25:99-108, 2000.
    powerpoint, and HTML version of overheads from Plenary talk at the 3rd DRAMA Steering Workshop, September, 1999.
    Paper, Abstract
  • Graph Partitioning and Parallel Solvers: Has the Emperor No Clothes?, Bruce Hendrickson. Lecture Notes in Computer Science, 1457, pp. 218-225, 1998. Copyright Springer-Verlag.
    Paper, Abstract
  • Graph Partitioning Models for Parallel Computing, Bruce Hendrickson and Tamara G. Kolda. Parallel Computing. 26:1519-1534, 2000.
    Paper, Abstract
  • Partitioning Rectangular and Structurally Nonsymmetric Sparse Matrices for Parallel Processing, Bruce Hendrickson and Tamara G. Kolda. SIAM J. Sci. Comput. 21(6):2048-2072, 2000.
    Paper, Abstract

  • Algorithms for Unstructured Applications

    Many unstructured computations can be built from simpler, common components. Methods for doing so, along with efficient algorithms for some of these kernels can be found in the following papers.
  • Tinkertoy Parallel Programming: A Case Study with Zoltan Karen Devine and Bruce Hendrickson. International Journal of Computational Science and Engineering 1:64-72, 2005.
    Paper, Abstract
  • Tinkertoy Parallel Programming: Complicated Applications from Simple Tools, Bruce Hendrickson and Steve Plimpton. In Proc. 10th SIAM Conf. Parallel Processing for Scientific Computing, March '01.
    Paper, Abstract
  • Improving Load Balance with Flexibly Assignable Tasks, Ali Pinar and Bruce Hendrickson. IEEE Transactions on Parallel & Distributed Systems 16(10):956-965, 2005. (Earlier version in SPAA'02)
    Paper, Abstract
  • Interprocessor Communication with Limited Memory, Ali Pinar and Bruce Hendrickson. In IEEE Transactions on Parallel & Distributed Systems 15:606-616, 2004 (Earlier version in Proc. SPAA'00).
    Paper, Abstract
  • Communication Support for Adaptive Computation, Ali Pinar and Bruce Hendrickson. In Proc. 10th SIAM Conf. Parallel Processing for Scientific Computing, March '01.
    Paper, Abstract

  • Chaco

    Rob Leland and I have developed a widely used graph partitioning tool called Chaco, which is available under a GNU open source license. The code is used at over 300 institutions for parallel computing, sparse matrix reordering, circuit placement and a range of other applications. The Chaco web page has more information about the capabilities of the software and how to download it.

    Other Graph Partitioning Web Sites

  • METIS (Karypis and Kumar)
  • PARTY (Preis)
  • JOSTLE (Walshaw)
  • SCOTCH (Pellegrini)

  • Return to Bruce's home page