Scotch 7.0 installation instructions
====================================
1) Mandatory tools
==================
In order for you to compile Scotch and/or PT-Scotch, you must have
Flex and Bison installed on your system, as well as GNU Make, and
possibly CMake if you prefer this tool. An implementation of the MPI
message-passing library is also mandatory to compile PT-Scotch library
and software.
To check whether Flex and Bison are present, please type:
%prompt% which flex
%prompt% which bison
Note: to implement pure parsers, recent versions of the Flex and
Bison tools are needed (e.g., the 3.4 branch). On MacOs, an older
version is provided by default; users may get an adequate version from
the "HomeBrew" repository, using command "brew install bison".
To check whether GNU Make and/or CMake are installed and are found
first, please type:
%prompt% make --version
%prompt% cmake --version
If some of these are missing, please:
- check your path variable (just in case they are located in
some unusual place, such as /usr/local/bin, /opt/bin,
/opt/local/bin/, /opt/gnu/bin, etc). Tools such as "which",
"locate" or "find" may help you find them;
- ask your system administrator (highly recommended);
- if you have system administrator rights, install the packages
on your system;
- install a local copy of the tools on your own (less recommended,
please ask your system administrator first).
Flex and Bison are available from the FSF website, at:
http://www.gnu.org/software/flex/
http://ftp.gnu.org/non-gnu/flex/
http://www.gnu.org/software/bison/
http://ftp.gnu.org/pub/gnu/bison/ .
CMake is available from its repository, at:
https://cmake.org/download/
GNU Make is available from the FSF website, at:
http://www.gnu.org/software/make/ and
http://ftp.gnu.org/pub/gnu/make/ .
2) Compilation
==============
To compile, test and install Scotch, one can either use CMake, or GNU
Make. The latter option provides most flexibility, but may be more
tedious. Please read the next section ("Configuration and
fine-tuning") to see what options are available, as they may either
favor or hinder the performance of Scotch on your system.
2.1) Compiling with CMake
-------------------------
The following instructions are relevant for a standalone
installation. In order to integrate Scotch as a library in a
third-party software that already uses CMake as its compilation tool,
please refer to the following example:
https://gitlab.inria.fr/solverstack/distrib/-/blob/master/cmake/test/scotch/CMakeLists.txt
which illustrates the necessary CMake variables to use.
### Configuration
To configure all the relevant Makefiles, please type the following
commands from the top-level directory:
%prompt% mkdir build
%prompt% cd build
%prompt% cmake -DCMAKE_INSTALL_PREFIX=/path/to/install -DCMAKE_BUILD_TYPE=Release ..
Some structuring options can be set during this phase, by using the
"-DOPTION:TYPE=VALUE" syntax. The available options are:
- INTSIZE:STRING (default value ""): set this variable to "32" or
"64" to set a prescribed integer size for SCOTCH_Num
integers. Else, the defaut compiler word size will be used
(recommended).
- THREADS:BOOL (default value ON): set this flag to ON to use POSIX
Pthreads within Scotch and PT-Scotch.
- MPI_THREAD_MULTIPLE:BOOL (default value ON): set this flag to ON
to use multi-threaded algorithms in conjunction with MPI, which
requires to use a thread-safe MPI implementation. This option is
relevant only if BUILD_PTSCOTCH is set to ON.
- BUILD_PTSCOTCH:BOOL (default value ON): set this flag to ON to
compile PT-Scotch in addition to Scotch (which is always compiled
by default, as PT-Scotch uses Scotch).
- BUILD_LIBESMUMPS:BOOL (default value ON): set this flag to ON to
build the MUMPS interface component.
- BUILD_LIBSCOTCHMETIS:BOOL (default value ON): set this flag to ON
to compile the libScotchMeTiS compatibility library.
- INSTALL_METIS_HEADERS:BOOL (default value ON): set this flag to ON
to install the libScotchMeTiS header stubs in the
CMAKE_INSTALL_PREFIX directory. Set it to OFF to avoid clobbering
preexisting, original MeTiS headers.
Should you want to define your own CFLAGS, you can override this
variable by defining it in the command line, e.g.:
%prompt% CFLAGS="-Drestrict=" cmake ..
### Compilation
If the previous phase ran without error, please run the compilation
phase, by typing:
%prompt% make -j
(The optional "-j" parameter enables multiple compilation jobs to run
concurrently.)
### Testing
If the previous phase ran without error, please run the test phase, by
typing:
%prompt% ctest
or:
%prompt% make test
In case of an error, more information can be obtained by typing:
%prompt% env CTEST_OUTPUT_ON_FAILURE=1 ctest
### Installation
If the previous phase ran without error, please run the installation
phase, by typing:
%prompt% make install
2.2) Compiling with GNU Make
----------------------------
### Configuration
In order for GNU Make to run, one needs to create a "Makefile.inc"
file containing the proper compilation commands and variables.
Go to the "src/" directory.
Look in its "Make.inc/" subdirectory for a configuration
file which matches your system configuration. If there
is none, build a proper one in the "Make.inc/" subdirectory,
basing on the structure of existing ones.
In particular, the Makefile.inc file contains three variables
which specify which C compiler to use. Their semantic is as
follows:
- The compiler command in variable CCS is used to compile
the sequential (hence the "S" in "CCS") Scotch distribution.
- The compiler command in CCP is used to compile the parallel ("P")
PT-Scotch distribution.
- The compiler command in CCD is used to compile the version of the
"dummysizes" ("D") executable used for compiling PT-Scotch, as
explained below.
Create a symbolic link from the configuration file to the
current "src/" working directory, renaming it as "Makefile.inc":
%prompt% ln -s Make.inc/Makefile.inc.xxxx_xxx_xxx Makefile.inc
If symbolic links are not available on your system, make a
plain copy of the file to a file named "Makefile.inc" in the
current "src/" working directory:
%prompt% cp Make.inc/Makefile.inc.xxxx_xxx_xxx Makefile.inc
Some additional scripts, designed to ease the installation of Scotch
on specific platforms, are also present in subdirectories of the
Make.inc directory. This is for instance the case for the mingw32
platform.
### Compilation
Once the "Makefile.inc" configuration file has been set-up, compile
the Scotch distribution by typing:
%prompt% make -j scotch
or just:
%prompt% make -j
in the current "src/" working directory.
(The optional "-j" parameter enables multiple compilation jobs to run
concurrently.)
To compile the PT-Scotch distribution, please type:
%prompt% make ptscotch
in the same "src/" directory. This can be done in any order. Typing:
%prompt% make ptscotch
will in fact compile both Scotch and PT-Scotch, since PT-Scotch
requires Scotch.
In some cases (e.g. when renaming library objects, see the next
section), you may only want/need to build the libraries and not the
executables. To do so, type:
%prompt% make -j libscotch
or:
%prompt% make -j libptscotch
The most common problem you may encounter when trying to compile
PT-Scotch on a new platform relates to the "dummysizes" and
"ptdummysizes" executables. The purpose of these programs is to
determine, on the target platform, the sizes of the opaque data
structures of Scotch and PT-Scotch, respectively. They have to be
compiled and run before any library function can be compiled. The
sequential case poses no specific problems, as "dummysizes" is always
compiled with the same command as that used to compile the
sequential Scotch package (hence, "CCD=$(CCS)" when executing "make
scotch"). In the parallel case, "ptdummysizes" has to take into
account the sizes of some MPI data structures, such as MPI_Comm, and
the most common way to have access to this information is to use some
flavor of MPI-aware compiler such as "mpicc" which automatically
refers to "mpi.h". Therefore, "CCD=mpicc" will work for most systems
and MPI implementations. Yet, on some platforms, programs compiled for
parallel execution cannot be run interactively. Moreover,
"ptdummysizes" itself does not contain any MPI calls, as it just wants
to know the sizes of the data structures, and the communication
subsystem of the platform may not want to run it. In any of these
cases, compilation will break. It is possible to solve this problem by
specifying, in the CCD variable of "Makefile.inc", how to compile
"ptdummysizes" sequentially but with knowledge of the location of the
"mpi.h" include file, for instance with the following line: "CCD =
my_sequential_cc -I/path/to/my/mpi/implementation/include/dir/".
In case of cross-compilation, e.g. for architectures that have
different word size and/or compiler tools for the front-end and the
compute nodes, it is possible to provide alternate flags, by setting
the "CCDFLAGS" variable.
If no error occurs, all of the relevant header, library and executable
files will be created and copied to the "../include/", "../lib/" and
"../bin/" directories, relatively to your current "src/" working
directory. Headers, libraries and binaries of Scotch and PT-Scotch can
coexist in these directories without any interference.
### Testing
A set of test programs is available in the "src/check" directory. They
serve as non-regression checks for both sequential and parallel
features of Scotch and PT-Scotch. They can be launched by typing:
%prompt% make check
and/or:
%prompt% make ptcheck
in the "src/" directory.
In the case of "ptcheck", programs can be run in debug mode, by
compiling with the "-DSCOTCH_CHECK_NOAUTO" flag set. In this case,
process numbers are printed, so that users can attach a debugger to a
given (set of) process(es), and user action is required for launching
the parallel programs, by typing ENTER whenever necessary.
### Installation
To install the Scotch and/or PT-Scotch files into their destination
directories, please type:
%prompt% make install
This will perform a GNU-like installation, with header, library,
binary and man files copied to the "include", "lib", "bin" and "man"
subdirectories of the path specified in the "prefix" variable, which
is set by default to "/usr/local". For instance, typing:
%prompt% make prefix=/home/myself/usr/ install
will install the Scotch/PT-Scotch files in a subtree of directory
"/home/myself/usr/".
3) Configuration and fine-tuning
================================
3.1) Parser issues
------------------
Since Scotch uses a parser to analyze its strategy strings, it may
happen that the symbols of this parser conflict with those of
another parser used in a third-party library. All "Makefile.inc.*"
platform configuration files which are based on Flex / Bison are
already tailored so as to prevent such conflicts. If you use other
parsing tools, you may have to provide other options.
Since version 7.0, Scotch uses re-entrant versions of the parsers
produced by Flex and Bison. They are inherently thread-safe and free
all their work memory, which was not the case for the previous
"un-pure" versions.
3.2) Integer size issues
------------------------
By default, all integers used in Scotch and PT-Scotch are of the "int"
C type, corresponding to the "INTEGER" type in Fortran. To coerce the
size of the Scotch integer type to 32 or 64 bits, add the "-DINTSIZE32"
or "-DINTSIZE64" flags, respectively, to the C compiler flags in the
Makefile.inc configuration file. If you do so, make sure to use
integer types of equivalent size to declare variables passed to Scotch
routines from caller C and Fortran procedures. Also, when running on
32_64-bit architectures (that is, integer types are 32-bit wide,
while address types are 64-bit wide), some integer array indices
returned by the Fortran interface have to be of a size equivalent to
those of memory addresses, that is, 64 bits. The size of these
variables is determined by the "-DIDXSIZE32" and "-DIDXSIZE64" flags,
respectively. When none of them is provided, the size of the indices
is assumed to be equivalent to that of the Scotch integer type.
For instance, on a 32-bit architecture, you can use 64-bit integers in
Scotch by just setting the "-DINTSIZE64" flag, because addresses will
remain on 32 bits. On a 32_64 architecture, you can use either 32-bit
or 64-bit integers in Scotch, by setting the "-DINTSIZE32" or
"-DINTSIZE64" flags accordingly, but in all cases you must set the
"-DIDXSIZE64" flag in order for some of the routines of the Fortran
interface to operate properly, because the array indices returned by
these routines have to be stored as 64-bit quantities.
Of course, on 64-bit architectures, another possibility is to tune
your C and Fortran compilers to make them interpret all "int" and
"INTEGER" types as 64 bit values. This solution is the simplest one,
as there is no need to use any of the aforementioned flags, nor to
hard-code type lengths in user's code. Yet, it prevents mixing 32 and
64-bit features, and may create problems when linking PT-Scotch if a
corresponding MPI library is not available.
Be careful not to mismatch the 32-bit and 64-bit versions of the
"scotch.h" and "ptscotch.h" include files that are generated at
compile time. When several versions of Scotch are simultaneously
present on a system, Make sure to place the corresponding include and
library files in separate directories. Most Scotch data structures
will have different sizes, depending on integer or pointer
sizes. Consequently, compiling a 64-bit executable with the 32-bit
version of "scotch.h" may lead to unpredictable behavior because of
memory overflow.
3.3) (Re)naming of library objects
----------------------------------
In order to prevent conflicts with third-party software, the following
naming conventions have been defined:
- Public C objects start with "SCOTCH_", and public Fortran objects
start with "SCOTCHF";
- Internal Scotch routines start with "_SCOTCH";
- Some internal routines start with "scotch", e.g. Flex/Bison
routines, see above.
It is possible to make several Scotch versions coexist in the same
application. To do so, libraries must be compiled with adequate
function renaming, by adding an appropriate suffix. For instance,
a "_64" suffix can be appended to routines and data types of a
64-bit version of the library.
To activate this feature, the variable "SCOTCH_NAME_SUFFIX" must be
defined in Makefile.inc (e.g., "SCOTCH_NAME_SUFFIX=_64").
Note that, when libScotch data types are renamed, the programs of the
Scotch package can no longer be compiled. Hence, users can only
compile the libraries of the Scotch package, by running:
%prompt% make libscotch
and/or:
%prompt% make libptscotch
Since error handling routines are generic and belong to a separate
library, suffix transformation is never applied to them. Hence,
application programs that use multiple versions of Scotch can be
linked against a single instance of the error handling library.
Once the library files with renamed objects have been compiled, it is
up to the packager to rename adequately the various files. For
instance, in the case of a 64-bit version, "scotch.h" can be renamed
into "scotch_64.h", etc.
By default, objects such as function option flags are not renamed,
since they can be shared without harm by all library instances of the
same version of Scotch. However, this can pose a risk when two
different versions of Scotch are to be used concurrently. In this
case, it may be necessary to rename these objects as well. It
can be done by defining the "-DSCOTCH_RENAME_ALL" flag.
When two different versions of the Scotch library are used without
any renaming of all of the external objects, the preprocessor symbol
"SCOTCH_WARNING_RENAME_UNSAFE" is defined by the include files
"scotch.h", to be taken into account by the application programmer.
3.4) Portability issues
-----------------------
While most of the code of Scotch poses no compatibility issues, some
features are subject to many diverging implementations, such as
date/time management, pipes, process forking, etc. Some of them are
handled globally, thanks to system-specific flags. Others have to be
finely tuned, depending on your platform.
Some common platform configurations are available in the
"src/Make.inc/" subdirectory.
The compilation flags used to manage portability issues are the
following:
"-DCOMMON_OS_MACOS" tweaks some includes and definitions to resolve
most issues encountered on MacOS platforms.
"-DCOMMON_OS_WINDOWS" tweaks some includes and definitions to resolve
most issues encountered on Windows platforms.
"-DCOMMON_TIMING_OLD" selects the getrusage()-based timing routine,
when "-DCOMMON_OS_WINDOWS" is not set. Else, either clock_gettime() or
gettimeofday() are selected, depending on POSIX compilation flags.
"-DCOMMON_STUB_FORK" provides a stub for the fork() system call on
systems that do not allow process forking.
3.5) Compression libraries
--------------------------
The binaries of the Scotch distribution can handle compressed
graphs in input or output. Three compressed graph formats are
currently supported: bzip2, gzip and xz/lzma. In order for them to be
actually activated, the proper libraries must be available on your
system. On a Linux platform, they are called "libz" for the gzip
format, "libbzip2" for the bzip2 format, and "liblzma" for the lzma
format. Note that it is the "development" version (also called
"-devel" or "-dev", for short, as a post-fix in package names) of
each of these libraries, which is required for the compilation to
succeed. According to the libraries installed on your system, you may
set flags "-DCOMMON_FILE_COMPRESS_BZ2", "-DCOMMON_FILE_COMPRESS_GZ"
and/or "-DCOMMON_FILE_COMPRESS_LZMA" in the CFLAGS variable of your
Makefile.inc configuration file, to have these formats and their
respective extensions ".bz2", ".gz" and ".xz"/".lzma", recognized and
handled by Scotch.
Compression and decompression are handled either by extra threads
or by fork()'ed child processes if threads are not available. On
systems which do not provide a functional fork() system call,
compressed files cannot be handled when the "-DCOMMON_PTHREAD_FILE"
flag is not set (see below).
3.6) Multi-threading
--------------------
Scotch can take advantage of Posix threads when they are
available. They are used in several places:
- To run in a multi-threaded way several key algorithms of the
Scotch (no longer really so) sequential library, such as graph
coarsening and diffusion-based methods. This choice is controlled
by the "-DSCOTCH_PTHREAD" flag (see below). When the
"-DSCOTCH_DETERMINISTIC" flag is also set, Scotch will
automatically prevent itself, by default, from using
multi-threaded versions of some algorithms if this would yield
non-deterministic results;
- To compress and decompress file data. This can be done either by
launching a service thread, or else by creating a separate process
by means of a Posix fork() system call. This choice is controlled
by the "-DCOMMON_PTHREAD_FILE" flag: if it is set, threads will be
used, else fork() calls will be performed. For systems which do
not support the fork() system call, such as the MinGW32 platform,
one can set the "-DCOMMON_STUB_FORK" flag, which creates a stub
fork() routine which always returns an error. Therefore, without
both fork() and threads, one must set the "-DCOMMON_STUB_FORK"
flag without setting "-DCOMMON_PTHREAD_FILE", so that compilation
will successfully complete; however, in this case, compressed
graphs shall not be handled in practice;
- to create distributed graphs in parallel. Since this task involves
concurrent MPI communications, the MPI library must support the
MPI_THREAD_MULTIPLE level. In order to take advantage of these
features, the "-DSCOTCH_PTHREAD_MPI" flag must be set, in addition
to the "-DSCOTCH_PTHREAD" flag. These two flags are completely
independent from the "-DCOMMON_PTHREAD_FILE" flag, which can be
set independently from the others.
Note that if you compile Scotch with the "-DSCOTCH_PTHREAD_MPI"
flag, you will have to initialize your communication subsystem by
using the MPI_Init_thread() MPI call instead of MPI_Init(), and
the provided thread support level value returned by the routine
must be checked carefully to assert it is indeed
MPI_THREAD_MULTIPLE.
Note also that since PT-Scotch calls Scotch routines when
operating on a single process, setting "-DSCOTCH_PTHREAD" but not
"-DSCOTCH_PTHREAD_MPI" will still allow multiple threads to be
used on each MPI process, without interfering with MPI itself. In
this case, the MPI thread level MPI_THREAD_FUNNELED will be
sufficient.
Since v7.0 of Scotch, thread management is dynamic. Scotch standalone
programs and library routines will detect the number of cores
available on the system and will use all of them, unless explicitly
prevented to do so (see the use of the "SCOTCH_PTHREAD_NUMBER"
environment variable below). By default, when the
"-DCOMMON_PTHREAD_AFFINITY_LINUX" flag is set (see below), the
assignment of threads to cores is performed in increasing order,
starting from 0 for the main thread.
The compilation flags used to manage threads are the following:
- "-DSCOTCH_PTHREAD" is mandatory to enable multi-threaded
algorithms in Scotch and/or PT-Scotch. It has to be used in
conjunction with the "-DCOMMON_PTHREAD" flag that enables thread
management at the lower levels of the Scotch implementation.
- "-DSCOTCH_PTHREAD_MPI" enables some algorithms of PT-Scotch that
may make concurrent calls to the MPI communication subsystem. It
has to be used in conjunction with the "-DCOMMON_PTHREAD" flag
(hence also with the "-DCOMMON_PTHREAD" flag). Alternately, the
compilation flag "-DSCOTCH_MPI_ASYNC_COLL" can be used to replace
threaded synchronous communication routines by non-threaded
asynchronous communication routines.
- "-DSCOTCH_PTHREAD_NUMBER=x" (not to be mistaken with the
environment variable of same name, see below) is an optional flag
that sets the default number of threads to be used by Scotch. For
instance, setting it to 1 will make Scotch run sequentially by
default, unless otherwise prescribed at run time by the
SCOTCH_PTHREAD_NUMBER environment variable. Indeed, some
algorithms have had to be reformulated to accommodate for
multi-threading, and will most probably be more efficient than
sequential processing only for a number of threads strictly
greater than 2. Setting "-DSCOTCH_PTHREAD_NUMBER=1" allows the
user to run sequential algorithms by default instead of
multi-threaded ones, while benefiting from multi-threading for
file compression and distributed graph handling. If the user's
platform comprises more than 2 cores, the user can set the
SCOTCH_PTHREAD_NUMBER environment variable to -1, to override the
compilation flag and take advantage of all available cores. When
the "-DSCOTCH_PTHREAD_NUMBER" flag is not set, by default, all the
available cores will be used at run time.
- "-DCOMMON_PTHREAD_AFFINITY_LINUX" enables Linux extensions for
handling thread affinity (see below).
- "-DCOMMON_PTHREAD_BARRIER" creates a replacement for missing
pthread_barrier_t implementations, which unfortunately happens on
some systems.
- "-DCOMMON_PTHREAD_FILE" enables threads for handling compressed
files. This flag does not interfere with the use of threads by
graph algorithms, e.g. for graph partitioning and/or ordering,
which depends on other flags (see below).
When compiling under mingw32 on Windows systems, it is possible to
benefit from multi-threading by including the "semaphore.h" and
"pthread.h" files, included in the "src/misc" subdirectory, at compile
time. These files have been kindly provided by Samuel Thibault, under
the BSD 2-Clause License. These files will not work for Cygwin. This
is not a problem, as Cygwin provides its own implementation of Posix
threads.
When Scotch is compiled with "-DSCOTCH_PTHREAD", it makes use, by
default, of all threads available to it on the platform it is running
on (save for when the "-DSCOTCH_PTHREAD_NUMBER" flag has been used at
compile time, see above). It is possible to influence this mechanism
at run time, by setting the "SCOTCH_PTHREAD_NUMBER=x" environment
variable, where "x" is the prescribed maximum number of threads to be
used. Setting a thread number to 1 will coerce Scotch into using only
purely sequential algorithms (which may differ in nature from their
multi-threaded counterparts). Setting the thread number to -1 will
make Scotch use all available threads, overriding the value possibly
set by using the "-DSCOTCH_PTHREAD_NUMBER" flag at compile time.
When the "-DCOMMON_PTHREAD_AFFINITY_LINUX" flag is set, the number of
threads that are available to run a Scotch routine is determined from
the run-time thread binding: as many threads will be used as the
number of cores to which the main thread is bound. If this flag is not
set, the number of available threads is the number of cores declared
at system level.
3.7) Multi-threading and MPI
----------------------------
Running a multi-threaded version of PT-Scotch on top of MPI requires
great care, not to degrade performance. The key issue is to make sure
that, at run time, MPI processes that run on the same computer are
bound to disjoint subsets of cores.
Indeed, when several MPI processes run on the same computer without
such an exclusive binding, each of the MPI processes will consider it
can use all of the computer cores, and as many threads will be created
and bound to each of the cores as there are MPI processes on the
computer.
In order to solve this problem, three conditions must be met
concurrently:
1- your MPI implementation must support thread binding; and
2- you must launch your parallel program with the appropriate thread
binding options; and
3- the Scotch routines must use thread binding information, i.e.,
Scotch must be compiled with the
"-DCOMMON_PTHREAD_AFFINITY_LINUX" flag set (support for other
binding APIs may be provided in the future, upon request and if
documentation is available).
For instance, regarding the second condition, in the OpenMPI
environment, one may use options such as "--map-by socket", "--bind-to
socket", "--bind-to core", etc. (the result of the binding can be
displayed using "--report-bindings"), e.g.:
% mpirun -np 2 --map-by socket --bind-to socket <program>
% mpirun -np 4 --map-by socket:PE=7 --bind-to core <program>
% mpirun -np 8 --map-by socket:PE=3 --bind-to core <program>
3.8) Monitoring memory allocation
---------------------------------
Some memory allocation information can be aggregated if PT-Scotch is
compiled with the -DCOMMON_MEMORY_TRACE flag. When this flag is set,
the "-va" option will make dgmap, dgord and dgpart output the minimum,
maximum and average peak amount of memory used over all processes.
Several API routines will also be made available to report the current
and maximum amount of memory used by Scotch within the process they
are called: SCOTCH_memCur() and SCOTCH_memMax(), respectively.
A rudimentary memory checking mechanism is available for platforms
that do not have efficient memory checking and debugging tools such as
Valgrind or gdb. It can be activated through the
"-DCOMMON_MEMORY_CHECK=x" flag. This is almost only for internal
debugging purposes. The value of the "-DCOMMON_MEMORY_CHECK" is 1 if
memory checking should be enabled by default, and 0 else. This
mechanism is absolutely NOT thread-safe at the time being.
3.9) Randomness
---------------
Many algorithms in Scotch and PT-Scotch are based on the random
selection of vertices (e.g. seed vertices for graph growing
algorithms, vertices to be mated for coarsening algorithms,
etc.). This selection is performed by using integer pseudo-random
generators to produce seemingly uncorrelated vertex indices.
The advantage of pseudo-randomness over pure randomness is that the
same pseudo-random seed will always yield the same sequence of
pseudo-random numbers. Consequently, while using a different random
seed for each run is likely to explore better the solution space,
using a fixed random seed eases the debugging of programs, because
algorithms behave identically across multiple runs (save for
asynchronicity issues, see next section). When Scotch is compiled
with the "-DCOMMON_RANDOM_FIXED_SEED" flag set, multiple executions of
the same sequential programs will always yield the same results.
Before version 6.0, Scotch relied on the operating system
pseudo-random generator. While this posed no problem for most
sequential programs, parallel runs of PT-Scotch were not reproducible
on some systems, because the MPI implementation also used this
pseudo-random generator for its own purposes. In order to avoid this
problem, Scotch now uses its own pseudo-random generator. The use of
operating system-dependent pseudo-random generators has been
deprecated since version 7.0.
3.10) Deterministic behavior
----------------------------
When Scotch is compiled with the "-DCOMMON_RANDOM_FIXED_SEED"
flag set, multiple executions of the same sequential programs
will always yield the same results. Yet, non-deterministic
multi-threaded and/or parallel algorithms may still introduce
some variability in the produced results, due to operating system
artifacts.
To ease the tracking down of bugs, it is possible to coerce Scotch to
exhibit a deterministic behavior by setting the
"-DSCOTCH_DETERMINISTIC" flag. This option makes sure that two
consecutive runs of Scotch on the same graph and same number of
processes and/or threads will always yield the same result. However,
it does not mean that two executions of Scotch on different numbers of
processes and/or threads will always yield the same result. Indeed,
changing the number of processes impacts graph data distribution and,
consequently, the order in which vertices are processed, leading to
different results.
This option is likely to have adverse impact on performance, since all
non-deterministic multi-threaded algorithms will be disabled. In the
case of Scotch, the multi-threaded matching algorithm for coarsening
will be replaced by its sequential counterpart, whatever the available
number of threads is. In the case of PT-Scotch, point-to-point
messages will be received in a fixed order rather than being processed
on a first-come, first-serve basis.
Setting this flag automatically results in setting the
"-DCOMMON_RANDOM_FIXED_SEED" flag.
3.11) Point-to-point or collective communications
-------------------------------------------------
Since distributed graph vertices can have any initial distribution
across processes, communication rounds are likely to involve all of
the processes in an almost all-to-all scheme. In order to speed-up
running time, most of these communications are performed by means of
asynchronous sends and receives, which allows computations to overlap
with communications. However, for large numbers of processes, this can
lead to the saturation of the communication network of the target
parallel machine. To avoid this, communication consuming routines also
have a collective communication based version. The use of this version
is enabled by default, as it greatly improves scalability for large
numbers of processes. To disable it, set the "-DSCOTCH_PTOP" flag at
compile time.
3.12) MeTiS compatibility library
---------------------------------
In order to ease the adoption of Scotch/PT-Scotch by people who
already developed code based on the MeTiS/ParMeTiS interface, a MeTiS
compatibility library is included in the Scotch package. It provides
compatible routines for the graph partitioning and ordering routines
of MeTiS/ParMeTiS, as well as for most of the service routines that
are available in these two packages. Hence, in most cases, it is
sufficient to link against the proper version of the "libscotchmetis"
library to use Scotch instead of MeTiS, by adding the two libraries in
sequence, plus the adequate Scotch error handling library :
[...] -lscotchmetisvX -lscotch -lscotcherr [...]
Note that there exists a naming conflict between versions v3 and v5 of
the genuine MeTiS library, as some routines have the same name but a
different prototype across the two versions.
Prior to Scotch v7.0, users had to choose which version of the
libscotchmetis to compile, by using either the macro
"-DSCOTCH_METIS_VERSION=3" or "-DSCOTCH_METIS_VERSION=5" when building
the libScotch library. Starting from Scotch v7, both versions of the
libscotchmetis are created simultaneously. Hence, users can link
their existing software by using either "-lscotchmetisv3" or
"-lscotchmetisv5" at link time. However, the
"-DSCOTCH_METIS_VERSION=x" flag is still necessary when compiling
third-party software using the alternate "metis.h" file provided by
Scotch, to expose either the prototypes of the routines of libmetis v3
or those of v5. The same holds for ParMeTiS and the flag
"-DSCOTCH_PARMETIS_VERSION=x", for which only the ParMeTiS v3 API is
available.
An advantage of the Scotch/PT-Scotch stubs over the genuine
MeTiS/ParMeTiS routines is that they can be available in a 64-bit
version. In this case, all int's that were passed to MeTiS/ParMeTiS
routines must be replaced by 64-bit integer values (even the option
configuration values). However, in this case, users will not be able
to link against the service routines of the genuine MeTiS/ParMeTiS
libraries, as the latter are only available as 32-bit implementations.
For people willing to use both the Scotch and MeTiS libraries, that
is, experiment with the graph partitioning features of Scotch while
using the service routines of the genuine MeTiS package, special
measures have to be taken.
A first solution can be to coerce the linker to pick partitioning
routines from the libScotch, and service routines from the
libmetis. This can be done by placing the library names in this order
as arguments to the linker command. Yet, some linkers may report an
error, as some symbols are multiply defined.
Alternately, the names of the compatibility routines can be changed so
as to avoid conflicts. When the "-DSCOTCH_METIS_PREFIX" flag is set at
compile time, all Scotch versions of the MeTiS routines are prefixed
with "SCOTCH_". Of course, this will require an equivalent change in
the user's application code.
In this case, an improved solution can be to call directly the Scotch
versions of these routines. Of course, this will require a change in
the user's application code, but it can be limited to a small set of
"#define's". The advantage of this solution is that it will make the
code insensitive to changes in the MeTiS API, because matching Scotch
routines are prefixed by "SCOTCH_" and by the MeTiS API version
number. This prevents all naming conflicts, such as those which
appeared between MeTiS v3 and MeTiS v5.
4) Using the libScotch and libPTScotch
======================================
Users willing to use the features of the sequential (but possibly
threaded) libScotch library have to include "scotch.h" and to link
against the "libscotch" library, plus an error handling package such
as "libscotcherr" or "libscotcherrexit".
Users willing to use the features of the distributed-memory parallel
libPTScotch library have to include "ptscotch.h" (which itself
includes "scotch.h") and to link against both the "libptscotch" and
"libscotch" libraries (in this order whenever order is significant),
plus an error handling package such as "libptscotcherr" or
"libptscotcherrexit".
In the case of complex programs, which may run as sequential programs
but may also call parallel routines, it is necessary to link only once
against a Scotch error handling routine, and this routine cannot call
MPI routines. Hence, the "libscotcherr" or "libscotcherrexit"
libraries must be used. This will not impact the behavior of the
parallel routines, but process numbers will not be displayed in case
of an error.
5) Documentation and examples
=============================
The Scotch and PT-Scotch user's manuals are located in the "doc/"
directory. They describe how to use the libScotch and libPTScotch
libraries and the standalone programs of the Scotch and PT-Scotch
distribution.
Basic samples of code are provided in the "doc/" directory. The
richest source of sample code is indeed the "src/check/" directory,
which contains the source code of many unit and integration tests for
various library functions. However, some of these programs test
internal features, and interact with the library through non-standard
and non-documented procedures. It is therefore recommended NOT to
imitate these calling practices and rather to follow the guidelines
provided in the Scotch and PT-Scotch user's manuals.
The "src/scotch/" directory, which contains the standalone programs of
the Scotch and PT-Scotch distribution, provides more complex use
cases.
6) Note to packagers
====================
Unlike for the v6.1 and earlier branches, Scotch v7.0 now handles
threads dynamically at run time. Packagers have to decide whether to
compile it with threads enabled or not. Based on the current processor
market, we recommend to compile it with "-DCOMMON_PTHREAD" and
"-DSCOTCH_PTHREAD" enabled (and with "-DCOMMON_PTHREAD_AFFINITY_LINUX"
whenever possible). The penalty for single-threaded CPUs will be
minimal, while hyper-threaded and many-core CPUs will benefit from the
multi-threaded algorithms. Packagers that do not want to activate
threads by default can set the compilation flag
"-DSCOTCH_PTHREAD_NUMBER=1", so that only one thread will be used at
run time by default (hence resorting to the sequential algorithms)
unless explicitly decided by the user by way of the
SCOTCH_PTHREAD_NUMBER environment variable.
Also, when the MPI implementation supports it, we recommend to compile
Scotch with the -DMPI_THREAD_MULTIPLE environment variable set, to
benefit from added performance when several threads are available per
MPI process.
Generated by dwww version 1.15 on Sun Jun 23 20:52:55 CEST 2024.