Existing Partitioning Softwares

In choosing a partitioning algorithm, it is necessary to balance the benefit of the reduction in communication cost, against that of the cost of generating the partitioning. If the parallel computer has slow communication, or the application is fine-grained where there is no large chunk of computation to ``shield'' the cost of communication, it is very important to have a partition of good quality. On the other hand, if the parallel computer has very fast communication, or the application is coarse grained where there is a lot of computation in between communication, a big reduction of the communication cost will only result in a fractional reduction of the overall cost, and in such a case a simple and cheap partitioning algorithm, such as the greedy algorithm, is quite adequate. Some of the most recent parallel partitioning codes [49,83] give very good quality partitions. They are scalable in memory and yet are comparable in cost to the very simple algorithms such as the greedy algorithm.

A number of packages are publicly available. Many of them are constantly being updated. Further details should be checked from the contact addresses listed.

• CHACO (http://www.cs.sandia.gov/CRF/chac.html)
  perhaps the first publicly available package. The latest version CHACO 2.0 uses multilevel combined with a number of available methods such as K-L refinement, spectral bisection. Available by request.

• JOSTLE (http://www.gre.ac.uk/jostle/)
  multilevel graph partitioning using $p$-way refinement. Both the sequential and parallel version are available free for academic use as an executable, after signing an agreement.

• METIS (http://www.cs.umn.edu/~karypis/metis/metis.html)
  multilevel graph partitioning using $p$-way refinement. Both the sequential and the parallel version are available free for down-load.

• PARTY (http://www.uni-paderborn.de/fachbereich/AG/monien/RESEARCH/ PART/party.html)
  sits on top of existing packages, offers greedy, multilevel spectral bisection, coordinate bisection, inertia bisection and other algorithms. Version 1.1 is available after signing a license.

• PMRSB ( stb@renaissance.cray.com)
  parallel multilevel spectral bisection. Available only on CRAY platforms.

• S-HARP [77] (http://www.cs.njit.edu/sohn/sharp/)
  multilevel graph partitioning using multiple eigenvectors and (spectral) inertia bisection on the coarsest level.

• SCOTCH (http://www.labri.u-bordeaux.fr/Equipe/ALiENor/membre/ pelegrin/scotch/)
  multilevel implementation of a number of algorithms including K-L. The code is free for down-load for academic use.

• TOP/DOMDEC [21] ( charbel@boulder.colorado.edu)
  Greedy algorithm, recursive coordinate and graph bisection, recursive inertia bisection, multilevel spectral bisection algorithm with tabu search, simulated annealing and stochastic evolution as smoothers.

• WGPP [31,32]
  multilevel graph partitioning. Similar to METIS with some new features.