SCOTCH: Static Mapping and Graph Partitioning Package
We announce the release of the SCOTCH software package for static
mapping and graph partitioning
Release 3.1 is now available via WWW and ftp.
Static mapping has extensive applications in many areas, including scienti-
fic computing, scheduling, and VLSI layout. The problem is to map the verti-
ces of a source graph onto the vertices of a target graph such that the
weight of the source graph vertices is balanced with respect to the weights
of the target graph vertices, and such that some communication function is
minimized. Static mapping is very important for finite element computations
on parallel machines, since good mappings significantly increase the perfor-
mance by reducing the communication overhead, particularly long-distance
communication. When the target machine is assumed to have a communication
network in the shape of a complete graph, the static mapping problem turns
into the graph partitioning problem, which has also been intensively studied
in the context of domain decomposition techniques.
What SCOTCH is
SCOTCH is a project carried out at the Laboratoire Bordelais de Recherche en
Informatique (LaBRI) of the Universite Bordeaux I, by the ALiENor (ALgorith-
mics 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. This work has resulted in the development of the Dual Recursive
Bipartitioning (or DRB) mapping algorithm and the analysis of several graph
The SCOTCH software package for static mapping embodies all the algorithms
and graph bipartitioning heuristics developed within the SCOTCH project. Its
principal features are outlined below.
-> SCOTCH can map any weighted source graph onto any weighted target graph.
The source and target graphs may have any topology, and their vertices
and edges may be weighted. Moreover, both source and target graphs may be
disconnected. This feature allows the mapping of programs onto disconnec-
ted subparts of a parallel architecture made up of processors and commun-
ication links of different nature.
-> SCOTCH provides high quality mappings.
The mappings computed by SCOTCH are consistently better than the ones
computed by Recursive Spectral Bissection followed by refinment
algorithms such as Cyclic Pairwise Exchange.
The graph partitions obtained when mapping onto the complete graph are
in most cases of better quality than the ones obtained with MeTiS and
Chaco on a wide variety of graphs.
-> SCOTCH is fast.
The running time of the SCOTCH mapper is linear in the number of edges of
the source graph and logarithmic in the number of vertices of the target
-> SCOTCH can be easily interfaced to other programs.
The programs comprising the SCOTCH project have been designed to run in
command-line mode without any interactive prompting, so that they can be
called easily from other programs by means of ``system ()'' or
``popen ()'' calls, or piped together on a single command line.
Moreover, vertex labeling capabilities allow for easy renumbering of
-> SCOTCH offers many tools to build, check, and display graphs.
Version 3.1 represents a major update of version 3.0, and implements several
-> A multi-level graph bipartitioning method boosts the performance of local
optimization algorithms such as the Fiduccia-Mattheyses algorithm.
-> An advanced handling of bipartitioning strategies allows the selection of
different graph partitioning methods according to the topological proper-
ties of the subgraphs to partition.
How to get SCOTCH
The SCOTCH academic distribution may be obtained via WWW from the SCOTCH
or by anonymous ftp at
The 3.1 academic distribution file is labeled
Most of the documentation regarding SCOTCH is available by WWW from the
aforementioned SCOTCH web page. Should you have any questions or problems on
obtaining SCOTCH, please send e-mail to