tricensus-mpi - Online in the Cloud

PROGRAM:

NAME

tricensus-mpi - Distribute a triangulation census amongst several machines using MPI

SYNOPSIS

tricensus-mpi [ -D, --depth=levels ] [ -x, --dryrun ] [ -2, --dim2 ] [ -o, --orientable |
-n, --nonorientable ] [ -f, --finite | -d, --ideal ] [ -m, --minimal | -M, --minprime |
-N, --minprimep2 | -h, --minhyp ] [ -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 or 2-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.

The default behaviour is to enumerate 3-manifold triangulations. If you wish to enumerate
2-manifold triangulations instead, you must pass --dim2.

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.

Use tricensus-mpi online using onworks.net services