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.