INSTALL.txt

Scotch 7.0 installation instructions
====================================

0) Documentation
================

The "doc/" directory contains several documents that may be useful to
users, packagers and maintainers of Scotch:

- the "Scotch and PT-Scotch Hands-On Guide", which provides ueful
  information to installers and users, as well as some troubleshooting
  instructions in case of unexpected crash;

- The "Scotch User's Guide" and the "PT-Scotch User's Guide", which
  provide thorough information about the Scotch and PT-Scotch APIs;

- The "Scotch Maintainer's Guide", which gives insights about the
  internals of Scotch and the Scotch coding style.


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

Because pure parsers are needed to ensure thread safety when handling
strategy strings, versions of the Flex and Bison tools at least equal
to 2.6.4 and 3.8.2, respectively, are required. On MacOS, an older
version is provided by default; users may get an adequate version from
the "HomeBrew" repository, using command "brew install bison". On
Windows, a recent version is available in the chocolatey package
repository, using command "choco install winflexbison3".

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.

Since the Scotch source code makes use of some C99 constructs (e.g.,
format constants for the fprintf family of functions, such as
"PRIu64"), C compilers must be parametrized so as to accept them
(e.g., using the "-std=c99" option for gcc).


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

  - IDXSIZE:STRING (default value ""): set this variable to "32" or
    "64" to set a prescribed integer size for SCOTCH_Idx integers.
    Indeed, this index data type should be able to index any byte in
    the virtual memory of the computer. Consequently, on modern
    architectures, this variable should always refer to 64-bit
    integers. If it is not set, the defaut compiler word size will be
    used (recommended for 64-bit platforms).

  - THREADS:BOOL (default value ON): set this flag to ON to use
    threads within Scotch and PT-Scotch. POSIX Pthreads and native
    Windows threads are supported.

  - MPI_THREAD_MULTIPLE:BOOL (default value ON): set this flag to ON
    to use multi-threaded algorithms in conjunction with MPI. In case
    this option is activated and PT-Scotch is linked against a
    thread-safe MPI library, it will take advantage of it to run some
    threaded algorithms in parallel across compute nodes. This option
    is relevant only if BUILD_PTSCOTCH is set to ON.

  - SCOTCH_DETERMINISTIC:STRING (default value FIXED_SEED): set this
    flag to NONE to use faster, non-deterministic algorithms in
    Scotch, and a variable random seed; FIXED_SEED to use these
    algorithms with a fixed random seed; FULL, to use fully
    deterministic algorithms with a fixed random string, enabling
    fully deterministic behavior with any number of threads and the
    same number of MPI processes. These three levels are obtained by a
    combination of the Make compilation flags
    "-DCOMMON_RANDOM_FIXED_SEED" and "-DSCOTCH_DETERMINISTIC"; see
    sections 3.9) and 3.10) of this document.

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

  - BUILD_FORTRAN:BOOL (default value ON): set this flag to ON
    to compile the Fortran test programs for the libScotch and
    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 ..

On Windows platform where a Unix-like Make is not available, CMake can
generate Microsoft NMAKE Makefiles:

%prompt% cmake -G "NMake Makefiles" -DCMAKE_BUILD_TYPE=Release ..


### 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.)

On Windows platform using NMAKE:

%prompt% nmake


### 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 C compiler command in variable CCS is used to compile
    the sequential (hence the "S" in "CCS") Scotch distribution.
  - The C compiler command in CCP is used to compile the parallel ("P")
    PT-Scotch distribution, using the MPI interface.
  - The C compiler command in CCD is used to compile the version of the
    "dummysizes" ("D") executable used for compiling PT-Scotch, as
    explained below.
  - The optional Fortran compiler command FCS is used to compile
    Fortran tests.

Create a custom "src/Makefile.inc" file, or create a symbolic link
from a sample 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, data types and symbols of
a 64-bit version of the library.

To activate this feature, the variable "SCOTCH_NAME_SUFFIX" must be
defined in Makefile.inc, either as an environment variable (e.g.,
"export SCOTCH_NAME_SUFFIX=_64"), or as a definition in the CFLAGS
variable (e.g., "-DSCOTCH_NAME_SUFFIX=_64").

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() and waitpid()
system calls 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 or Windows threads when they are
available. They are used in several places:

  - To run in a multi-threaded way several key algorithms of the
    Scotch centralized 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 stub
    fork() and waitpid() routines which always return 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 cannot be handled internally by Scotch;

  - 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 for PT-Scotch to run the
    threaded version of the algorithms. 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().

    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_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 setting the "-DCOMMON_THREAD_WIN32"
flag at compile time. This flag is not needed for Cygwin, which
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.

From version v7.0, Scotch allows to parameterize the behavior of the
libScotch library (and of the Scotch programs that use it) at run
time, by way of environment variables which, when set, supersede
compile-time definitions. The "SCOTCH_RANDOM_FIXED_SEED" environment
variable may be set to 0 for setting a new, dynamically-changing
pseudo-random seed at every run, and 1 for a fixed pseudo-random
seed.


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.

From version v7.0, Scotch allows to parameterize the behavior of the
libScotch library (and of the Scotch programs that use it) at run
time, by way of environment variables which, when set, supersede
compile-time definitions. The "SCOTCH_DETERMINISTIC" environment
variable may be set to 0 to allow for the use of faster,
non-deterministic, multi-threaded algorithms, and 1 for a fully,
albeit sometimes slower, deterministic multi-threaded behavior.


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:
C routines are prefixed with "SCOTCH_", and Fortran routines with
"scotchf" (lowercase form) or "SCOTCHF" (uppercase form), with no
following separating underscore. 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.


3.13) Source fortification
--------------------------

Recent developments in applied software engineering for code
robustness have resulted in the implementation, in some compilers, of
features which generate extra code for checking at run time the
compliance of the parameters of relevant library function calls. The
activation and intrusiveness of these checks is conditioned by a
specific compiler macro, called "_FORTIFY_SOURCE", the value of which
ranges from 0 (no checks) to 3 (most intrusive checks).

In the case of Scotch, while values from 0 to 2 have proven innocuous
to date, setting "_FORTIFY_SOURCE" to 3 leads to false positives that
abort the program. Consequently, packagers and installers are
requested not to use this latter level.


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, we recommend to compile Scotch with the -DMPI_THREAD_MULTIPLE
environment variable set, to benefit from added performance when
Scotch is liked against a MPI library that provides the
MPI_THREAD_MULTIPLE thread support level.