Dr. Blatt - HPC-Simulation-Software & Services Dr. Blatt

Loadbalancing with PT-Scotch as a replacement for ParMETIS

DUNE, MPI, HPC, PT-Scotch, ParMETIS, graph partitioning, Debian | 29-02-2016 15:58 | Markus Blatt

"The Distributed and Unified Numerics Environment (DUNE)" uses ParMETIS for loadbalancing at various places. For example the parallel algebraic multigrid method uses it to redistribute the coarse level matrices to fewer processes. This helps to keep the ratio of communication per floating point operation / local memory access acceptable. Unfortunately, if using ParMETIS for non-academic purposes is not free. You have to acquire a special license for it. Fortunately, there are also open source graph partitioners like PT-Scotch. It also offers the most prominent functions of ParMETIS. This is sufficient to replace ParMETIS as used in dune-istl, the "Iterative Solver Template Library" of DUNE.

The Debian Way

Installation of PT-Scotch on a Debian System

If you are using Debian then this will save a lot of time. The Debian packages usually are very well maintained and very usable. (Both sentences might also apply to your favorite Linux distribution, too). Debian ships special packages for the METIS/ParMETIS bindings of PT-Scotch than can be easily installed like this:

apt-get install libscotchparmetis-dev libscotchmetis-dev

Now you will have the following headers installed:

/usr/include/parmetis/parmetis.h
/usr/include/parmetis-int32/parmetis.h
/usr/include/parmetis-int64/parmetis.h
/usr/include/parmetis-long/parmetis.h
/usr/include/metis/metis.h
/usr/include/metis-int32/metis.h
/usr/include/metis-int64/metis.h
/usr/include/metis-long/metis.h

You actually get three versions that differ in the size of integer type used to identify the vertices and edges of the graphs. Of course you will also find the complementing libraries on your system:

/usr/lib/libparmetis.a
/usr/lib/parmetis-int32/libparmetis.a
/usr/lib/parmetis-int64/libparmetis.a
/usr/lib/parmetis-long/libparmetis.a
/usr/lib/libmetis.a
/usr/lib/metis-int32/libmetis.a
/usr/lib/metis-int64/libmetis.a
/usr/lib/metis-long/libmetis.a

Unfortunately, there are two bugs in the Debian packages (#715107 and #715112 that will make your life a bit harder when using the non-default versions. Basically, the symbolic links /usr/lib/(par)metis-int32/lib(par)metis.a are broken and you need to use the following real libraries directly:

/usr/lib/scotch-long/libscotchmetis.so
/usr/lib/scotch-int32/libscotchmetis.so
/usr/lib/scotch-int64/libscotchmetis.so

Finding PT-Scotch with DUNE's CMake build system

If you are using the default version, then DUNE's build system will take care of everything for you. There is no need to specify anything.

If you want to use another version, then you need to tell CMake where to search for the header and library. Just put the directory where the headers reside into the variable CMAKE_PREFIX_PATH and specify the full paths of the libraries in METIS_LIBRARY and PARMETIS_LIBRARY, respectively. For the int64 version use the following settings.

cmake -DCMAKE_PREFIX_PATH="/usr/include/parmetis-int64;/usr/include/metis-int64" \
  -DMETIS_LIBRARY=/usr/lib/scotch-int64/libscotchmetis.so \
  -DPARMETIS_LIBRARY=/usr/lib//scotch-int64/libscotchmetis.so <source-path>

Self Compiled Versions of PT-Scotch

Installation of PT-Scotch From Source Tarballs

We start be downloading and unpacking of the latest version (currently: 6.0.4) from the [PT-Scotch homepage] (http://gforge.inria.fr/frs/?group_id=248 "Official home of Scotch/PT-Scotch"):

wget \
http://gforge.inria.fr/frs/download.php/file/34618/scotch_6.0.4.tar.gz
tar xzf scotch_6.0.4.tar.gz

Using the pristine tarballs is not possible because the provided metis.h and parmetis.h headers are not self-contained. Using the with DUNE will result CMake errors like:

In file included from /home/mblatt/src/dune/current/dune-istl/build-scotch-opt/CMakeFiles/CMakeTmp/CheckIncludeFile.c:1:0:
/home/mblatt/opt/include/metis.h:91:61: error: unknown type name ‘SCOTCH_Num’
 void                        METISNAMEU(METIS_EdgeND) (const SCOTCH_Num * const, const SCOTCH_Num * const, const SCOTCH_Num * const, const SCOTCH_Num * const, const SCOTCH_Num * const, SCOTCH_Num * const, SCOTCH_Num * const);
                                                         ^
/home/mblatt/opt/include/metis.h:91:87: error: unknown type name ‘SCOTCH_Num’
 void                        METISNAMEU(METIS_EdgeND) (const SCOTCH_Num * const, const SCOTCH_Num * const, const SCOTCH_Num * const, const SCOTCH_Num * const, const SCOTCH_Num * const, SCOTCH_Num * const, SCOTCH_Num * const);
                                                                                     ^
/home/mblatt/opt/include/metis.h:91:113: error: unknown type name ‘SCOTCH_Num’
 void                        METISNAMEU(METIS_EdgeND) (const SCOTCH_Num * const, const SCOTCH_Num * const, const SCOTCH_Num * const, const SCOTCH_Num * const, const SCOTCH_Num * const, SCOTCH_Num * const, SCOTCH_Num * const);

and

/home/mblatt/opt/include/parmetis.h:98:67: error: unknown type name ‘SCOTCH_Num’
 void                        METISNAMEU(ParMETIS_V3_NodeND) (const SCOTCH_Num * const, SCOTCH_Num * const, SCOTCH_Num * const, const SCOTCH_Num * const, const SCOTCH_Num * const, SCOTCH_Num * const, SCOTCH_Num * const, MPI_Comm * const);
                                                                   ^
/home/mblatt/opt/include/parmetis.h:98:87: error: unknown type name ‘SCOTCH_Num’
 void                        METISNAMEU(ParMETIS_V3_NodeND) (const SCOTCH_Num * const, SCOTCH_Num * const, SCOTCH_Num * const, const SCOTCH_Num * const, const SCOTCH_Num * const, SCOTCH_Num * const, SCOTCH_Num * const, MPI_Comm * const);
                                                                                       ^
/home/mblatt/opt/include/parmetis.h:98:107: error: unknown type name ‘SCOTCH_Num’
 void                        METISNAMEU(ParMETIS_V3_NodeND) (const SCOTCH_Num * const, SCOTCH_Num * const, SCOTCH_Num * const, const SCOTCH_Num * const, const SCOTCH_Num * const, SCOTCH_Num * const, SCOTCH_Num * const, MPI_Comm * const);

This bug was already reported in bug #19251 with a patch attached. We need to download and apply it before compiling PT-Scotch:

wget http://gforge.inria.fr/tracker/download.php/248/1079/19521/4975/patch \
&& patch -p1 <./patch

Due to some short comings in PT-Scotch's build system we need to specify the MPI compiler when compiling PT-Scotch to make with the CCD variable. To compile and install the software under the subdirectory opt in the current user's home directory, use the following:

cd scotch_6.0.4/src && \
ln -s Make.inc/Makefile.inc.x86-64_pc_linux2 Makefile.inc && \
make scotch && make CCD=mpicc ptscotch && make prefix=~/opt \
         install && \
cp -f ../include/*metis*.h ~/opt/include/
cd ../..

Using the Self-Compiled PT-Scotch with DUNE

Using the patched and self-compiled version of PT-Scotch is a piece of cake. All we need to do is provide CMake with the path we installed PT-Scotch using CMAKE_PREFIX_PATH and provide custom names of the libraries using the DUNE specific variables METIS_LIB_NAME and PARMETIS_LIBNAME either on the command line:

cmake -DCMAKE_PREFIX_PATH="/home/mblatt/opt/" \
 -DMETIS_LIB_NAME=scotchmetis \
 -DPARMETIS_LIB_NAME=ptscotchparmetis <source-dir>

or in a custom option file, e.g.

MAKE_FLAGS=-"j4 all"
CMAKE_FLAGS='-DCMAKE_PREFIX_PATH="/home/mblatt/opt/" -DMETIS_LIB_NAME=scotchmetis -DPARMETIS_LIB_NAME=ptscotchparmetis'
BUILDDIR="build-scotch-opt"