This major release (codename « Sankara »), fruition of six years of development, brings many major improvements. Notably:
Thread management is now fully dynamic: Scotch automatically adapts its behavior to the number of available cores. An existing thread pool can be imported from a caller software, so as not to create unnecessary threads and to improve computation locality.
Many algorithms have been rewritten to benefit from shared-memory parallelism, including some algorithms of PT-Scotch, which now benefit from a hybrid « MPI+threads » parallelism.
Execution options, such as the fact to select between deterministic algorithms that allow for computational reproducibility or faster, non-deterministic algorithms, can now be selected dynamically and no longer at compile time.
A new class of objects is available: execution contexts. Contexts allow users to encapsulate a thread pool, execution options, and a private pseudo-random generator, so as to execute concurrently (and in a fully reproducible way) any Scotch computation (mapping, partitioning, ordering, etc.) on the same graph or on different graphs.
To ease migration from the MeTiS software, two distinct versions of our compatibility library are now simultaneously provided: v3 and v5.
The CMake tool is now supported.
And even more...
Great news: on the occasion of the 30 years of Scotch, a consortium is being put in place. A draft of text describing the consortium is available. A poll to better know the Scotch user community is also available.
SCOTCH is available from the Inria GitLab repository.
Following the decommissioning of the Inria Gforge service, the Inria GitLab repository becomes the only official source for the SCOTCH software. Please update your download references.
Thanks to all the users who place their trust in our software, which has been the sixth most downloaded software from Inria Gforge.
Version 6.1 of SCOTCH is out!
Like the previous ones, it is available as free/libre software under the CeCILL-C license.
Exactly 20 years after, to the day, the first line of SCOTCH was written, version 6.0 of SCOTCH, aka « the 20 y.o. SCOTCH » edition, is released. This version offers many new features:
sequential graph repartitioning;
sequential graph partitioning with fixed vertices;
sequential graph repartitioning with fixed vertices;
new, fast, direct k-way partitioning and mapping algorithms;
multi-threaded, shared memory algorithms in the (formerly) sequential part of the library;
exposure in the API of many distributed graph handling routines;
embedded pseudo-random generator for improved reproducibility;
and even more...
Revision 5.1.10 of SCOTCH breaks the « 32-bit barrier » in parallel.
Revision 5.1.10 is the first to be able to handle in parallel graphs
of more than two billion vertices (limit of representation for 32-bit
wide signed integers). PT-SCOTCH has been able to bipartition,
in 76 seconds, a 3D graph of more than 2.4 billion vertices and 7.3
billion edges, distributed across 2048 processors of
machine platine
at CCRT.
The sequential SCOTCH library is also fully capable of handling 64-bit values, since revision 5.1.8 for all of its routines.
Version 5.1 of SCOTCH is available as free/libre software under the CeCILL-C license.
Version 5.1 is the first one to provide parallel graph partitioning features in PT-SCOTCH.
Version 5.0 of SCOTCH is available as free/libre software under the CeCILL-C license.
Version 5.0 is the first one to include PT-SCOTCH, the parallel version of SCOTCH. Its new features comprise:
a distributed graph structure, which allows users to handle dynamically very large graphs, by means of either compact or disjoint edge arrays. Disjoint edge arrays are useful for handling adaptive graphs, as they allow for the updating of graph structures without copying the whole vertex and edge arrays;
a set of routines that enable users to distribute centralized SCOTCH graphs, or to centralize distributed graphs;
parallel graph ordering routines for distributed graphs;
new sequential graph partitioning methods, comprising a diffusion method yielding smoother interfaces;
a compatibility library which provides stubs for the main routines of the MeTiS library, to allow MeTiS users to try Scotch without having to modify their source code.
Version 4.0 of SCOTCH is available as LGPL'ed free/libre software.
Version 4.0 is the first free/libre release of SCOTCH. It is a major rewriting of version 3.4, which comprises many new features:
an improved graph structure, which allows users to use either compact or disjoint edge arrays, at no additional cost;
a native mesh structure, which allows to handle meshes that would not fit into memory on the form of nodal graphs;
efficient memory usage, to process larger graphs and meshes without incurring out-of-memory faults;
an improved strategy interpreter, for dynamically evaluating arithmetic expressions on graph properties.
SCOTCH is a project carried out within the Satanas research department of the Laboratoire Bordelais de Recherche en Informatique (LaBRI). It is part of the works of the team TADaaM of INRIA Bordeaux - Sud-Ouest.
Its purpose is to apply graph theory, with a divide and conquer approach, to scientific computing problems such as graph and mesh partitioning, static mapping, and sparse matrix ordering, in application domains ranging from structural mechanics to operating systems or bio-chemistry.
The SCOTCH distribution is a set of programs and libraries which implement the static mapping and sparse matrix reordering algorithms developed within the SCOTCH project.
SCOTCH has many interesting features:
Its capabilities can be used through a set of stand-alone programs as well as through the libSCOTCH library, which offers both C and Fortran interfaces.
It provides algorithms to partition graph structures, as well as mesh structures defined as node-element bipartite graphs and which can also represent hypergraphs.
The SCOTCH library dynamically takes advantage of POSIX threads to speed-up its computations. The PT-SCOTCH library, used to manage very large graphs distributed across the nodes of a parallel computer, uses the MPI interface as well as POSIX threads.
It 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 for the mapping of programs onto disconnected subparts of a parallel architecture made up of heterogeneous processors and communication links.
It computes amalgamated block orderings of sparse matrices, for efficient solving using BLAS routines.
Its running time is linear in the number of edges of the source graph, and logarithmic in the number of vertices of the target graph for mapping computations.
It can handle indifferently graph and mesh data structures created within C or Fortran programs, with array indices starting from 0 or 1.
It offers extended support for adaptive graphs and meshes through the handling of disjoint edge arrays.
It is dynamically parametrizable thanks to strategy strings that are interpreted at run-time.
It uses system memory efficiently, to process large graphs and meshes without incurring out-of-memory faults;
It is highly modular and documented. Since it has been released under the CeCILL-C free/libre software license, it can be used as a testbed for the easy and quick development and testing of new partitioning and ordering methods.
It 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.
It provides many tools to build, check, and display graphs, meshes and matrix patterns.
It is written in C and uses the POSIX interface, which makes it highly portable.
Current versions of SCOTCH are distributed as free/libre software, under the terms of the CeCILL-C license. Please refer to the Resources section below to see how to download the newest revisions of the sources of SCOTCH and its documentation.
SCOTCH can also be distributed under other types of licenses and conditions to parties willing to embed it into closed, proprietary software. Please contact us if you are considering this option.
To ease the development, diffusion, and circulation of information regarding the SCOTCH project, most of its resources are now hosted on the Inria GitLab platform. This forge provides many services to people interested in the project.
The old Gforge instance (see below) will be maintained concurrently, up to the decommission of this platform.
Formerly, the resources regarding the SCOTCH project were hosted on the InriaGforge platform.