NAME¶
tricensus-mpi - Distribute a triangulation census amongst several machines using
MPI
SYNOPSIS¶
tricensus-mpi [
-D, --depth=levels ] [
-x,
--dryrun ] [
-o, --orientable |
-n, --nonorientable ] [
-f, --finite |
-d, --ideal ] [
-m, --minimal |
-M,
--minprime |
-N, --minprimep2 ] [
-s, --sigs= ]
pairs-file output-file-prefix
DESCRIPTION¶
Allows multiple processes, possibly running on a cluster of different machines,
to collaborate in forming a census of 3-manifold triangulations. Coordination
is done through MPI (the Message Passing Interface), and the entire census is
run as a single MPI job. This program is well suited for high-performance
clusters.
To prepare a census for distribution amongst several processes or machines, the
census must be split into smaller pieces. Running
tricensus with option
--genpairs (which is very fast) will create a list of face pairings,
each of which must be analysed in order to complete the census.
The full list of face pairings should be stored in a single file, which is
passed on the command-line as
pairs-file. This file must contain one
face pairing per line, and each of these face pairings must be in canonical
form (i.e., must be a minimal representative of its isomorphism class). The
face pairings generated by
tricensus --genpairs are guaranteed
to satisfy these conditions.
The
tricensus-mpi utility has two modes of operation: default mode, and
subsearch mode. These are explained separately under modes of operation below.
In both modes, one MPI process acts as the controller and the remaining
processes all act as slaves. The controller reads the list of face pairings
from
pairs-file, constructs a series of tasks based on these, and farms
these tasks out to the slaves for processing. Each slave processes one task at
a time, asking the controller for a new task when it is finished with the
previous one.
At the end of each task, if any triangulations were found then the slave
responsible will save these triangulations to an output file. The output file
will have a name of the form
output-file-prefix_p.rga in default mode
or
output-file-prefix_p-s.rga in subsearch mode. Here
output-file-prefix is passed on the command line,
p is the
number of the face pairing being processed, and
s is the number of the
subsearch within that face pairing (both face pairings and subsearches are
numbered from 1 upwards). If no triangulations were found then the slave will
not write any output file at all.
The controller and slave processes all take the same
tricensus-mpi
options (excluding MPI-specific options, which are generally supplied by an
MPI wrapper program such as
mpirun or
mpiexec). The different
roles of the processes are determined solely by their MPI process rank (the
controller is always the process with rank 0). It should therefore be possible
to start all MPI processes by running a single command, as illustrated in the
examples below.
As the census progresses, the controller keeps a detailed log of each slave's
activities, including how long each slave task has taken and how many
triangulations have been found. This log is written to the file
output-file-prefix.log. The utility
tricensus-mpi-status can
parse this log and produce a shorter human-readable summary.
Important: It is highly
recommended that you use the --sigs option. This will keep output
files small, and will significantly reduce the memory footprint of
tricensus-mpi itself.
MODES OF OPERATION¶
As discussed above, there are two basic modes of operation. These are default
mode (used when
--depth is not passed), and subsearch mode (used when
--depth is passed).
- •
- In default mode, the controller simply reads the
list of face pairings and gives each pairing to a slave for processing,
one after another.
- •
- In subsearch mode, more work is pushed to the
controller and the slave tasks are shorter. Here the controller reads one
face pairing at a time and begins processing that face pairing. A fixed
depth is supplied in the argument --depth; each time that depth is
reached in the search tree, the subsearch from that point on is given as a
task to the next idle slave. Meanwhile the controller backtracks (as
though the subsearch had finished) and continues, farming the next
subsearch out when the given depth is reached again, and so on.
The modes can be visualised as follows. For each face pairing, consider the
corresponding recursive search as a large search tree. In default mode, the
entire tree is processed at once as a single slave task. In subsearch mode,
each subtree rooted at the given depth is processed as a separate slave task
(and all processing between the root and the given depth is done by the
controller).
The main difference between the different modes of operation is the lengths of
the slave tasks, which can have a variety of effects.
- •
- In default mode the slave tasks are quite long. This means
the parallelisation can become very poor towards the end of the census,
with some slaves sitting idle for a long time as they wait for the
remaining slaves to finish.
- •
- As we move to subsearch mode with increasing depth, the
slave tasks become shorter and the slaves' finish times will be closer
together (thus avoiding the idle slave inefficiency described above).
Moreover, with a more refined subsearch, the progress information stored
in the log will be more detailed, giving a better idea of how long the
census has to go. On the other hand, more work is pushed to the
single-process controller (risking a bottleneck if the depth is too great,
with slaves now sitting idle as they wait for new tasks). In addition the
MPI overhead is greater, and the number of output files can become
extremely large.
In the end, experimentation is the best way to decide whether to run in
subsearch mode and at what depth. Be aware of the option
--dryrun,
which can give a quick overview of the search space (and in particular, show
how many subsearches are required for each face pairing at any given depth).
OPTIONS¶
The census options accepted by
tricensus-mpi are identical to the options
for
tricensus See the
tricensus reference for details.
Some options from
tricensus are not available here (e.g., tetrahedra and
boundary options), since these must be supplied earlier on when generating the
initial list of face pairings.
There are new options specific to
tricensus-mpi, which are as follows.
- -D, --depth=levels
- Indicates that subsearch mode should be used (instead of
default mode). The argument levels specifies at what depth in the
search tree processing should pass from the controller to a new slave
task.
The given depth must be strictly positive (running at depth zero is
equivalent to running in default mode).
See the modes of operation section above for further information, as well as
hints on choosing a good value for levels.
- -x, --dryrun
- Specifies that a fast dry run should be performed, instead
of a full census.
In a dry run, each time a slave accepts a task it will immediately mark it
as finished with no triangulations found. The behaviour of the controller
remains unchanged.
The result will be an empty census. The benefit of a dry run is the log file
it produces, which will show precisely how face pairings would be divided
into subsearches in a real census run. In particular, the log file will
show how many subsearches each face pairing produces (the utility
tricensus-mpi-status can help extract this information from the
log).
At small subsearch depths, a dry run should be extremely fast. As the depth
increases however, the dry run will become slower due to the extra work
given to the controller.
This option is only useful in subsearch mode (it can be used in default
mode, but the results are uninteresting). See the modes of operation
section above for further details.
EXAMPLES¶
Suppose we wish to form a census of all 6-tetrahedron closed non-orientable
triangulations, optimised for prime minimal P2-irreducible triangulations (so
some non-prime, non-minimal or non-P2-irreducible triangulations may be
omitted).
We begin by using
tricensus to generate a full list of face pairings.
example$ tricensus --genpairs -t 6 -i > 6.pairs
Total face pairings: 97
example$
We now use
tricensus-mpi to run the distributed census. A wrapper program
such as
mpirun or
mpiexec can generally be used to start the MPI
processes, though this depends on your specific MPI implementation. The
following command runs a distributed census on 10 processors using the MPICH
implementation of MPI.
example$ mpirun -np 10 /usr/bin/tricensus-mpi -Nnf 6.pairs 6-nor
example$
The current state of processing is kept in the controller log
6-nor.log.
You can watch this log with the help of
tricensus-mpi-status.
example$ tricensus-mpi-status 6-nor.log
Pairing 1: done, 0 found
...
Pairing 85: done, 0 found
Pairing 86: done, 7 found
Pairing 87: running
Pairing 88: running
Still running, 15 found, last activity: Wed Jun 10 05:57:34 2009
example$
Once the census is finished, the resulting triangulations will be saved in files
such as
6-nor_8.rga,
6-nor_86.rga and so on.
MACOS X AND WINDOWS USERS¶
This utility is not shipped with the drag-and-drop app bundle for
MacOS X or with the
Windows installer.
SEE ALSO¶
regconcat, sigcensus, tricensus, tricensus-mpi-status, regina-gui.
AUTHOR¶
This utility was written by Benjamin Burton <bab@debian.org>. Many people
have been involved in the development of Regina; see the users' handbook for a
full list of credits.