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

graph.

-> 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

vertices.

-> 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

http://www.labri.u-bordeaux.fr/~pelegrin/scotch/

or by anonymous ftp at

ftp.u-bordeaux.fr

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