Projects and software on Graph Partitioning

• CHACO (Hendrickson and Leland)
  Before a calculation can be performed on a parallel computer, it must first be decomposed into tasks which are assigned to different processors. Researchers at Sandia Labs have developed a variety of innovative algorithms for this decomposition problem and implemented them in a software package called Chaco. This code is being used at most of the major parallel computing centers to simplify the development of parallel applications.
• JOSTLE (Walshaw)
  JOSTLE is a software package designed to partition unstructed meshes arising in finite element or finite volume analysis. The package is conceived for use on distributed memory parallel computers. It can also be used to repartition existing partitions (such as those deriving from adaptive refined meshes).
• MeTiS (Karypis and Kumar)
  This is a Family of Multilevel Partitioning Algorithms. The interest is on parallel computing. Besides tools for graph partitionig, hypergraph partitionig and sparse matrix ordering are also covered. Parallel versions of the graph partitioning procedures are also supplied.
• UCLA VLSI CAD Bookshelf Slots and Entries, with Partitioning
• PARTY The PARTY partitioning library by Preis and Diekmann serves a variety of different partitioning methods in a very simple and easy way. The data-structures used as interface to PARTY are simple. Several research projects currently use the PARTY partitioning library to solve the partitioning problem.
• SCOTCH (Pellegrini)
  SCOTCH is a project carried out at the Laboratoire Bordelais de Recherche en Informatique (LaBRI) of the Université Bordeaux I, by the ALiENor (ALgorithmics and ENvironments for parallel computing) team. Its goal is to study static mapping by the means of graph theory, using a divide and conquer approach.

More Partitioning Software for Parallel Computing

• PadFEM is an OO environment supporting and implementing parallel adaptive finite element simulations in 2D (and soon in 3D). PadFEM includes GUI's, mesh generators, partitioning algorithms, FE-formulations for Poisson- and Navier-Stokes-Problems, different solvers based on domain decomposition, error estimators, mesh refinement algorithms, and dynamic load balancers.
• The CHAOS Project has developed methods to map a broad range of challenging applications onto high performance computer architectures. A major focus of this work is development of parallelization techniques for irregular scientific problems -- problems that are unstructured, sparse, adaptive or block-structured. This project works extensively with application developers in many disciplines and with parallel compiler v.
• Graph Partitioners must separate the vertices of a graph into almost equal-sized components such that the number of edges between components is minimized. This amounts to reduce the communication among processors in a parallel machine. Three graph partitioners are provided: coordinate bisection, geometric random circles, and spectral. The first two algorithms require geometric information about locations of the vertices, while the third does not. All three algorithms rely on recursive bisection.
• Scalable Libraries for Graph Partitioning Sanjay Ranka and Geoffrey Fox from the Syracuse University offer a library of partitioners which aim to find good suboptimal solutions in parallel. The initial target use of these partitioning methods are for runtime support of data parallel compilers (HPF).
• NHSE Software Catalog The software catalog of the National HPCC Software Exchange.

Circuit Partitioning

• Stanford University: Digital Systems Computer-Aided Design.
  The graph partitioning problem is a central issue in the design of VLSI circuits. We supply the starting point for exploring Stanford University's research efforts in the area of Digital Systems Computer-Aided Design. From here one can enter the whole WWW on circuit partitioning. Digital Systems CAD involves specification, synthesis, verification, and simulation of both synchronous and asynchronous circuits and systems.

More Goodies

• A multilevel graph partitioning algorithm acts as follows:
  First, a sequence of smaller and smaller graphs is created from the original graph. Second, the smallest graph in the sequence is partitioned carefully. And third, the partition is propagated back through the sequence of grids, with an occasional local refinement.
  The algorithm proposed looks at the following generality: in parallel computing the overhead due to a message may depend upon how far apart the communicating processors are. By Hendrickson and Leland.
• Implementations of several graph partitioning heuristics, including Kernighan-Lin, Simulated Annealing, and Path Optimization. It was used to generate the empirical data described in "Path Optimization for Graph Partitioning Problems" by Berry and Goldberg.

Theory Gallery

• Improved approximation algorithms for MAX k-CUT and MAX BISECTION
  Polynomial-time approximation algorithms with non-trivial performance guarantees are presented for the problems of (a) partitioning the vertices of a weighted graph into k blocks so as to maximise the weight of crossing edges, and (b) partitioning the vertices of a weighted graph into two blocks of equal cardinality, again so as to maximize the weight of crossing edges. The approach, pioneered by Goemans and Williamson, is via a semidefinite relaxation.
• Partitioning and Optimization of Digital Integrated Circuits
  Partitioning and Optimization of Digital Integrated Circuits --
  Doctoral Thesis of Roman Kuznar
  University of Ljubljana -- Faculty of Electrical Engineering. See also the mirror . A comprehensive update on Latest Partitioning Results based on a subset of Benchmarks from Partitioning93 is available, as well as Benchmark Newsletters. Newsletters concerning CBL and its benchmarking project.
• Graph partitioning based sparse matrix orderings for interior point algorithms. By Anshul Gupta -IBM Journal of Research and Development, 41(1/2):171-184, 1997. see also ftp://ftp.cs.umn.edu/users/kumar/anshul/Graph-Ordering.ps.
• Abstract of three papers from the University of Texas.
  They focus on the area of circuit clustering and partitioning.
• CS267: Notes for Lectures 20 and 21, Mar 21 1996 and Apr 2 1996
  Table of Contents -- Introduction to Graph Partitioning -- Overview of Partitioning Heuristics -- Graph Partitioning Software -- Edge Separators and Vertex Separators -- Partitioning Graphs with Coordinate Information -- Partitioning Planar Graphs -- Inertial Partitioning -- Partitioning with Random Lines and Circles -- Partitioning Graphs Without Coordinate Information -- Breadth First Search -- Kernighan/Lin Algorithm.

Test graphs

• Internet-Based Partitioning Contest 1996
• Collaborative Benchmarking Laboratory , part of the Department of Computer Science at North Carolina State University
• NASA NAS Graph Collection
  WWW page for numerous aerodynamics matrices, at various formats.
• Harwell-Boeing Collection
  Contains a variety of matrices in Harwell-Boeing format, from different application domains.
• SCOTCH Graph Collection
  Contains graphs gathered from various sites and people (Steve Hammond, the Harwell-Boeing collection, Bruce Hendrickson, and Horst Simon), stored in SCOTCH format.
• University of Florida Collection
  Contains large sparse matrices related to finite-elements, circuit simulation, chemical engineering, and linear programming problems.
• University of Minnesota Collection
  Contains some large graphs coming from the AEM Finite Element Group at the AHPCRC, stored in CHACO format.
• MP-TESTDATA - Min-Cut Clustering Problem Instances

Sites and people

• FRANC BRGLEZ, Collaborative Benchmarking Laboratory
• Ulrich Elsner
  He gives a lot of useful references for graph partitionig.
• Chris Walshaw's WWW Page
  Chris Walshaw is the father of JOSTLE. His homepage contains plenty of useful links for parallel computing, partitioning and load balancing.
• Charles J. Alpert CHEESE
  Research Staff Member IBM Austin Research Laboratory IBM Research Division .
• Ralf Diekmann
  University of Paderborn.
• Prof. Dr. rer. nat. Burkhard Monien
  University of Paderborn.
• Carnegie Mellon University
  The Carnegie Mellon University home page.
• David A. Bader's List of Parallel Computing Sites
  A very complete and frequently updated list of sites related to parallel processing.
• Faculté Polytechnique de Mons
  The Faculté Polytechnique de Mons home page.
• ICASE home page
  The ICASE home page.
• NASA Ames Research Center home page
  The NASA Ames Research Center home page.
• ORAP home page
  The ORAP home page.
• Sandia National Laboratories
  The Sandia National Laboratories home page.