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 ] pairs-file output-
file-prefix
DESCRIPTION
Allows multiple processes, possibly running on 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.
Note: This program is well suited for running on a formal
cluster-like infrastructure. For a more ad-hoc census manager
that does not rely on such infrastructure, see the tricensus-
manager utility instead.
In preparing a census to be distributed 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). Note that the face pairings generated by tricensus
--genpairs are guaranteed to satisfy these conditions.
Note: Whereas tricensus-mpi uses a single large face pairings
file (with MPI handling the distribution of pairings to
individual processes), the alternative tricensus-manager uses
many small face pairings files (with individual processes
claiming individual files to work on).
This 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 each 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, where
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 write no output file.
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 is able
to parse this log and produce a shorter human-readable summary.
Tip: Once the census is complete, the regconcat command may be
used to combine the many small output files into one large
topology data file for easier handling.
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 to a slave for processing, one after another.
In other words, each slave task is the entire subcensus for a single
face pairing.
· 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. If all slaves finish
together this is quite efficient, but if the finish times are
staggered then the census may become very inefficient towards the end
(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 inefficiency of several slaves sitting idle as
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 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 have identical behaviour
to those same options when passed to tricensus. See the tricensus
reference for further details.
Note that some tricensus options 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 through tricensus
--genpairs.
The remaining options specific to tricensus-mpi 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 for 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 value of a dry run is
in the log file, 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 given 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, where the census is optimised for prime
minimal P2-irreducible triangulations (and in particular, some
triangulations that are not prime, minimal and P2-irreducible may be
left out).
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 command for running a distributed census on 10 processors for the
MPICH implementation of MPI is as follows.
example$ mpirun -np 10 /usr/bin/tricensus-mpi -Nnf 6.pairs 6-nor
example$
The current state of processing can be watched in the controller log
6-nor.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
Census still running, last activity: Sun Mar 19 17:14:41 2006
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.
SEE ALSO
regconcat, sigcensus, tricensus, tricensus-manager, tricensus-mpi-
status, regina-kde.
AUTHOR
Regina was written by Ben Burton <bab@debian.org> with help from
others; see the documentation for full details.
12 May 2009