SCOTCH Static Mapping and Graph Partitioning package v3.1 is out

SCOTCH Static Mapping and Graph Partitioning package v3.1 is out

Post by Francois PELLEGRI » Wed, 04 Sep 1996 04:00:00

            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.

Application domains

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
bipartitioning heuristics.

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
new features.

-> 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
page at
or by anonymous ftp at
in directory
  /pub/Local/Info/Software/Scotch .
The 3.1 academic distribution file is labeled
  scotch_3.1A.tar.gz .

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