User's guide MondriaanOpt
Whereas Mondriaan uses heuristics to obtain good partitionings for sparse matrixvector multiplication for any number of processors, MondriaanOpt calculates an optimal solution to this partitioning problem with 2 processors. More precisely, it calculates a partitioning with minimum communication volume among all solutions that obey the imbalance constraint.
A database with already solved problems with use of MondriaanOpt can be found online.
How to install MondriaanOpt
MondriaanOpt comes packaged with the Mondriaan software. Refer to this page for
instructions on using Mondriaan. MondriaanOpt is automatically compiled when you compile Mondriaan. The executable
is then available at tools/MondriaanOpt
.
How to run MondriaanOpt
The MondriaanOpt program has the following interface:
% ./tools/MondriaanOpt matrix [P [eps]] [options]
One, two or three parameters may be passed, after which further options may be given. Either [eps], e or k must be passed, and it is advised to pass v (see options). Take note that while MondriaanOpt may be called with the same parameters as Mondriaan, the actual problem being solved may be slightly different.
Some equivalent examples are:
% ./tools/MondriaanOpt tests/arc130.mtx 2 0.03 v 17
% ./tools/MondriaanOpt tests/arc130.mtx e 0.03 v 17
% ./tools/MondriaanOpt tests/arc130.mtx k 660 v 17
The above examples partition the arc130.mtx
matrix (Matrix Market file format)
for 2 processors with at most 3% load imbalance, knowing that solutions must exist with
volume at most 17. The matrix should be the full relative path; in the above example
output is saved in the Mondriaan tests folder (../tests/
).
Output
The MondriaanOpt
tool yields, after a successful run on an input matrix,
various output files. All possible output files are described below. Typically,
the output filenames are that of the input matrix filename, modified with a small
descriptor and the number of parts (=2).
Formats with free nonzeros
All assigned nonzeros are assigned a processornumber to be assigned to, either 1 or 2.
All free nonzeros will be assigned index 3.
(Free nonzeros are nonzeros that are not assigned to a processor because assigning
it to either one will not influence communication volume.)
To stress the potential presence of free nonzeros, the number of processors (2) in the
filename is followed by a suffix f
.
Processor indices (I2f
)
The MondriaanOpt
program writes the processor indices of each
nonzero to the Matrix Market file input2f.mtx
where the value of each
nonzero is replaced by the processor index to which the nonzero has been assigned.
Graphical output (2f.svg
)
If the option svg
is given, at the end of the algorithm an SVG graphic is written to the file input2f.svg
,
containing a visualisation of the partitioning.
Formats without free nonzeros
Here, the free nonzeros of a partitioning are distributed among the two processors in
such a way that load imbalance is kept at a minimum.
Note that whenever we write P
for the number of processors below, it implicitly equals 2.
Distributed matrix (P2
)
The MondriaanOpt
program
writes the distributed matrix to a file called inputP2
,
where input
is the name of the input matrix.
We use an adapted Matrix Market format, with this structure:
%%MatrixMarket distributedmatrix coordinate real general
( this should be 0 )
m n nnz P
Pstart[0]
...
...
...
Pstart[P]
( this should be nnz )
A.i[0] A.j[0] A.value[0]
...
...
...
A.i[nnz1] A.j[nnz1] A.value[nnz1]
Here, Pstart[k]
points to the start of the nonzeroes
of processor k.
Processor indices (I2
)
The MondriaanOpt
program
also writes the processor indices of each nonzero to the Matrix Market file inputI2
where the value of each nonzero is replaced by the processor index to which
the nonzero has been assigned. The order of the nonzeroes is exactly that of the distributed matrix (P2
).
Cartesian submatrices (C2
)
The program writes the row index sets I(q)
and column index sets J(q) of the Cartesian submatrix I(q) x J(q)
for the processors q=1,...,P to the file called inputC2
.
This file is additional information, useful e.g. for visualisation,
and you may not need it.
Graphical output (2.svg
)
If the option svg
is given, at the end of the algorithm an SVG graphic is written to the file input2.svg
,
containing a visualisation of the partitioning.
Output to stdout
/stderr
In a successful run, at the end of execution general statistics are written to stdout
.
Also, during such a run, every 2^23 = 8388608
iterations the current depth in the tree is written to stderr
, in the format `current depth`/`maximum depth`
.
Last but not least, every time a new solution is found which improves on the previous solution regarding total volume, a message is written to stderr
reporting the newly found volume and load distribution in the format `load P0`, `load P1`, `load Free`
.
Program options
The MondriaanOpt program has the following interface:
% ./tools/MondriaanOpt matrix [P [eps]] [options]
One, two or three parameters may be passed, after which further options may be given. An overview of the available parameters and options is given below.
Parameters
Parameter  Name  Description 

matrix 
Matrix file  Required. The input matrix file in Matrix Market (.mtx) format 
P 
Number of processors  Present for consistency with other Mondriaan* commands. This parameter, if given, must be equal to 2. 
eps 
Load imbalance  The maximum allowed load imbalance 
Options
Apart from the matrix, at least one of [eps], e or k must be given, defining the maximum allowed load imbalance.
Option  Value  Description 

v  Volume 
Recommended. The starting upper bound volume.
This defaults to min(m,n)+1 , with m and n denoting the dimensions of the matrix to be partitioned.
While this is a valid upper bound, you may wish to pass a tighter upper bound to reduce computing time.

e  Load imbalance  The maximum allowed load imbalance 
k  Number of nonzeros  The maximum allowed number of nonzeros per part 
t  Seconds  Max running time in seconds 
h  None  Show help 
svg  None  Write visualisations of the partitioning to .svg files 
Difference in imbalance constraints
While the command line interface of MondriaanOpt can be used just as Mondriaan, there is a subtle difference in the problem being solved in these two.
More precisely, with N
being the total number of nonzeros, p
being the total number of processors (which equals 2) and
load
the number of nonzeros assigned to a processor, compare:
 the imbalance constraint
load <= (1+epsilon) (N/p)
which is used in Mondriaan (In the code, this amounts tofloor( ((1+epsilon)*N)/p )
.), and  the imbalance constraint
load <= (1+epsilon) ceil(N/p)
which is used in MondriaanOpt.
As p=2
, this difference may only be of importance whenever N
is odd.
In [1,p.2] it is explained that this different choice was made to ensure feasibility of the problem, even if epsilon=0
.
Using MondriaanOpt in MATLAB
For more information about MATLAB usage, please see the Mondriaan MATLAB guide.
MondriaanOpt is available in Matlab using the MatlabMondriaanOpt
MEX routine. Example matlab files
are given as mondriaanOpt.m
and mondriaanOptPlot.m
.
References
[1] An exact algorithm for sparse matrix bipartitioning, Daniel M. Pelt and Rob H. Bisseling, Journal of Parallel and Distributed Computing, 85 (2015) pp. 7990.
Last updated: November 4, 2016.
November 4, 2016 by Marco van Oort.
To
the Mondriaan package home page.