Scotch 5.1 installation instructions
====================================


1) Mandatory tools
==================

In order for you to compile Scotch and/or PT-Scotch, you must have GNU
Make, Lex and Yacc installed on your system, as well as an
implementation of the MPI message-passing library in the case of
PT-Scotch. There is a possibility to install Scotch without having Lex
or Yacc, but it may require the tuning of sample Flex and Bison (i.e.,
the GNU equivalents of Lex and Yacc) outputs created on a Linux
system, which may need some tricky work to compile on other systems,
because of different C library implementations.

To check if GNU Make is installed and is found first, please
type:

%prompt% make --version

It should read:
% GNU Make x.xx
% Copyright (C) 20xx  Free Software Foundation, Inc.
etc, etc.


Alternatively, if GNU Make is installed but its directory does
not appear first in the PATH variable that is searched for
executables, you can try to locate it using the which command:

%prompt% which make

If several occurences of make are found, one might be GNU Make,
so try to figure out which of them.

To see if lex and yacc are present, type
%prompt% which lex
%prompt% which yacc    (or "bison", the GNU flavor of yacc)

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);
- install a copy of GNU Make of your own (less recommended,
  please ask your system administrator first). GNU Make is
  available from the FSF website, at:
  http://www.gnu.org/software/make/ and
  http://ftp.gnu.org/pub/gnu/make/ .
  A GNU version of lex and yacc is also available from the
  very same 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/ ;
- use the "last resort" files placed in a directory judiciously
  called "last_resort", located in subdirectory "src/libscotch".
  These files are:
  . parser_ll.c
  . parser_ly.h
  . parser_yy.c .
  They should be copied in the directory where object files are
  created, and "touch"ed so that their modification date is more
  recent than the ones of the corresponding "parser_ll.l" and
  "parser_yy.y" files. Then cross your fingers and hope it
  compiles properly on your system. Else, you will have to dig in
  their code to have them compile properly...
  The Makefile of the libScotch library has been designed so as
  to copy the last_resort/* files automatically when the lex or
  yacc tools are not found.
  In this case, depending on your platform, you may also have to set
  the "-DSCOTCH_RENAME_PARSER" flag in order for all symbols to be
  properly redefined (see Section 2.2).


2) Configuration
================

2.1) Creating the "Makefile.inc" file
-------------------------------------

Go to the "src/" directory.

Look in the "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 set in the variable CCS is used to compile
the sequential (hence the "S" in "CCS") Scotch distribution. The
compiler set in CCP is used for the parallel ("P") PT-Scotch
distribution. The compiler set in CCD is used by both to compile
the "dummysizes" ("D") executable, 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.


2.2) Parser symbol conflicts
----------------------------

Since Scotch uses a parser to analyze its strategy strings, it may
happen that the symbols of this parser conflict with the ones of
another parser used in a third-party library. All "Makefile.inc.*"
platform configuration files which base 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. Another solution is to
use the pre-processed parser files of the "src/libscotch/last_resort"
subdirectory (corresponding operation instructions are given in
Section 1).


2.3) 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 INTSIZE32
or INTSIZE64 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, some integer array indices returned by the
Fortran interface have to be of a size equivalent to the one of the
memory addresses, that is, 64 bits. The size of these variables is
determined by the IDXSIZE32 and IDXSIZE64 flags, respectively. When
none of them is provided, the size of the indices is assumed to be
equivalent to the one 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. Since some of their fields are
of different sizes, most Scotch data structures 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.


2.4) 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 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 "zlib" for the gzip
format, "libbz2" for the bzip2 format, and "liblzma" for the lzma
format. Note that it is the "development" version (also called
"devel", for short, within 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 COMMON_FILE_COMPRESS_BZ2, COMMON_FILE_COMPRESS_GZ and/or
COMMON_FILE_COMPRESS_LZMA in the CFLAGS variable of your Makefile.inc
configuration file, to have these formats and their respective
extensions ".bz2", ".gz" and ".lzma", recognized and handled by
Scotch.


2.5) Threads issues
-------------------

Scotch can also take advantage of Posix threads when they are
available. They are used in two places:

- to compress and uncompress 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 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 return an error. Therefore,
  without both fork() and threads, one must set the COMMON_STUB_FORK
  flag without setting COMMON_PTHREAD, 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 taks involves
  concurrent MPI communications, the MPI library must support the
  MPI_THREAD_MULTIPLE level. The use of threads within Scotch itself
  is controlled by the SCOTCH_PTHREAD flag, which is completely
  independent from the COMMON_PTHREAD flag. Any of them can be set
  without setting the other.
  Note that if you compile Scotch with the -DSCOTCH_PTHREAD flag,
  you will have to initialize your communication subsystem by using
  the MPI_Init_thread() MPI call, not MPI_Init(), and the provided
  thread support level value returned by the routine must be
  checked carefully.
  If you have doubts on the stability of your MPI implementation, it
  is better not to set -DSCOTCH_PTHREAD. For instance, on Linux
  platforms, concurrency problems have been experienced with MPICH2
  versions prior to 1.0.7 using TCP; consequently, if the MPI
  implementation on your platform is based on an older MPICH2 version,
  do not set the SCOTCH_PTHREAD flag.


2.6) Monitoring memory allocation
---------------------------------

Some memory allocation information can be aggregated if PT-Scotch is
compiled with the -DCOMMON_MEMORY_TRACE flag. If it is the case, the
"-va" option will make dgmap, dgord and dgpart output the minimum,
maximum and average peak amount of memory used over all processors.


2.7) Deterministic behavior
---------------------------

To ease the tracking down of bugs, it is possible to coerce PT-Scotch
to have a deterministic behavior by setting the -DSCOTCH_DETERMINISTIC
flag. This option may have a small impact on performance, since some
asynchronous messages are received in a fixed order rather than being
processed on a first-come first-serve basis. It will also impact the
results, since the order in which messages are received is significant
to some key algorithms such as the parallel coarsening phase. Setting
this flag is also equivalent to setting the -DCOMMON_RANDOM_FIXED_SEED
flag in the sequential routines.


2.8) 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 processors. To disable it, set the -DSCOTCH_PTOP flag at
compile time.


2.9) 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
stubs for the graph partitioning and ordering routines of
MeTiS/ParMeTiS, but not for the service routines that are comprised
in this package. Consequently, for people willing to use both
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 still
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.


3) Compilation
==============

Once you have performed the configuration of the "Makefile.inc" file,
compile the Scotch distribution by typing "make scotch", or just
"make", in the current "src/" working directory. To compile the
PT-Scotch distribution, type "make ptscotch" in the same "src/"
directory. This can be done in any order.

The most common problem you may encounter when trying to compile
PT-Scotch on a new platform relates to the "dummysizes" executable.
The purpose of this program is to determine, on the target platform,
the size of the opaque data structures of Scotch, and it has to be
compiled and run before any library function can be compiled. In the
parallel case, it 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 compilers such
as "mpicc" which automatically refer to "mpi.h". Yet, on some
platforms, programs compiled for parallel execution cannot be run
interactively. Moreover, "dummysizes" itself does not contain any MPI
calls, as it just wants to know the sizes of the data structures, and
the communication susbystem 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 "dummysizes" 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/


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. Since headers, libraries and binaries of Scotch and
PT-Scotch can coexist in these directories, you can compile both in
sequence, in any order.

Because Scotch and PT-Scotch share some of their sources, with
distinct data structures, both must be fully compiled from scratch.
This is why you may see the same files be compiled twice, and why all
object files are cleaned before any compilation process.


Further typing "make install" 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".


4) Documentation and use
========================

The Scotch and PT-Scotch user's manuals are available in the "doc/"
directory. They describe how to use the libscotch and ptlibscotch
libraries, as well as the standalone programs of the Scotch and
PT-Scotch distributions.
