Mondriaan

Mondriaan for sparse matrix partitioning

Mondriaan partitioner

Mondriaan is a sequential program written in C that can be used to partition a rectangular sparse matrix, an input vector, and an output vector for parallel sparse matrix-vector multiplication. The program is based on a recursive bipartitioning algorithm that cuts the matrix horizontally and vertically, in a manner resembling some of the famous Mondriaan paintings. The algorithm is multilevel, hypergraph-based, and two-dimensional. It reduces the amount of communication and it spreads both computation and communication evenly over the processors. The program can partition hypergraphs with integer vertex weights and uniform hyperedge costs, but it is primarily intended as a matrix partioner.

Download

Download the latest version of the Mondriaan software, version 2.01 (tar gzipped), released June 9, 2009.

Minor bug-fix version 2.01 (June 9, 2009)

Alexander Gusak from the Belarusian State University, Faculty of Applied Mathematics and Computer Science, found and fixed a few errors: a memory leak, an opened file which was not closed, and an an uninitialised string terminator. He also suggested a few improvements to prevent overflow for huge sparse matrices. These allowed him to partition matrices of 6 million rows and columns and 400 million nonzeros.

New features of version 2.0 (July 14, 2008)

Version 2 contains many improvements compared to version 1 (released May 10, 2002). These are:

New algorithms for vector partitioning, which often achieve the best communication load balance for the given matrix partitioning.
Much faster partitioning, by a factor of 10; this improvement was already incorporated in the minor release v1.02 from 2005.
Better quality of the matrix partitioning. On average, communication volume is reduced by 10%, mainly due to scaling of the inner products of matrix columns in the coarsening phase.
Inclusion of the finegrain partitioning method (proposed by Catalyurek and Aykanat 2001).
Inclusion of a hybrid between the original Mondriaan method and the finegrain method.
Some new hypergraph partitioning capabilities. Mondriaan 2.0 can handle hypergraphs with arbitrary integer vertex weights, but only with uniform hyperedge costs.
Can also handle non-powers of two for the number of processors.
Full documentation of every function. (Total 96 functions.)
A unit test for every function.
Package has been tested on Linux, Mac OS X, Solaris, and using Valgrind for finding memory leaks.
User's guide.
More liberal license: GNU Lesser General Public License

Related papers

The original Mondriaan algorithm and implementation has been published in "A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication", by Brendan Vastenhouw and Rob H. Bisseling, SIAM Review, Vol. 47, No. 1 (2005) pp. 67-95.

The new vector partitioning algorithms and implementation have been published in "Communication balancing in parallel sparse matrix-vector multiplication", by Rob H. Bisseling and Wouter Meesen, Electronic Transactions on Numerical Analysis, Vol. 21 (2005) pp. 47-65, special issue on Combinatorial Scientific Computing.

The hybrid between the original Mondriaan method and the finegrain method will be published in a forthcoming paper "A hybrid 2D method for sparse matrix partitioning" by Rob Bisseling, Tristan van Leeuwen, and Umit Catalyurek. This work has been presented at the 5th International Workshop on Parallel Matrix Algorithms and Applications (PMAA'08) 20-22 June 2008, Neuchatel, Switzerland. Slides

Extensive background reading on the parallel sparse matrix-vector multiplication problem, including a detailed discussion of the Mondriaan algorithm, can be found in Chapter 4 (pp. 163-250) of

Parallel Scientific Computation: A Structured Approach using BSP and MPI, by Rob H. Bisseling, Oxford University Press, March 2004. 324 pages. ISBN 0-19-852939-2. OUP home page of the book.

Trailer

Trailer announcing Mondriaan version 2 by Sarai Bisseling (Quicktime movie, 11.6 MB).

Selected related lectures by Rob Bisseling

CECAM Workshop Open Source Software for Microscopic Calculations, June 19-21, 2002, Lyon, France: Mondriaan, partitioning software for sparse matrix computations (24 transparancies, 719kB, PDF format, generated using Prosper)
A hybrid 2D method for sparse matrix partitioning by Rob Bisseling, Tristan van Leeuwen, and Umit Catalyurek. Lecture at SIAM Conference on Parallel Processing for Scientific Computing San Francisco, February 22-24, 2006. (29 transparancies, 612kB, PDF format).

Copyright

This software is copyrighted (2002, 2008) by Rob Bisseling, Tristan van Leeuwen, Wouter Meesen, and Brendan Vastenhouw. You can use and modify it under the GNU Lesser General Public License, see GNU Licenses. Also see the files, README, COPYING, COPYING.LESSER. Anything free, as usual, comes with no guarantee!

Contributions

Besides the authors mentioned in the copyright notice, others have contributed as well:

Umit Catalyurek: interface to finegrain partitioning
Ken Stanley: visualisation (to be released)
Albert-Jan Yzelman: makefiles, Valgrind testing

Other contributions are welcome!

Roadmap

We intend to make the following available in the future:

Version 2.1 Matlab (TM) interface and visualisation package, contributed by Ken Stanley.
Version 2.2 Interface to PaToH. Interface to make Mondriaan user-callable as a library routine.
Version 2.3 Adding the cut-net metric.
Version 3.0 Adding reordering for cache-oblivious sequential sparse matrix-vector multiplication, see Cache-oblivious sparse matrix-vector multiplication by using sparse matrix partitioning methods by Albert-Jan N. Yzelman and Rob H. Bisseling. SIAM Journal on Scientific Computing, Vol. 31, No. 4 (2009) pp. 3128-3154.

History

The initial version, version 1.0 of Mondriaan, by Brendan Vastenhouw\and Rob Bisseling was released on May 10, 2002.

Version 1.01 from december 2003 repairs a bug for symmetric matrices and solves a few compilation problems.

Version 1.02 from March 2005 is a minor update which improves the speed of the algorithm by a factor of ten. Thanks to Umit Catalyurek for pointing out an inefficiency in the inner product matching.

Test matrices

Most matrices we use in our tests can be obtained from Tim Davis' University of Florida Sparse Matrix Collection. The term-by-document matrices used in the SIAM Review paper are: tbdmatlab.mtx (430171 nonzeros, 3.2 Mbyte) and tbdlinux.mtx (2157675 nonzeros, 18.9 Mbyte), both in gzip-compressed Matrix Market format.

Bugs and previous versions

We maintain a list of compilation problems, bugs etc. You can also find all previous versions of the software here.

Related software

Joris Koster (Utrecht University) has developed an object-oriented package of iterative linear system solvers that can be used after Mondriaan has distributed the matrix and vectors involved. This package can handle every possible matrix and vector distribution, including the Mondriaan distribution. It is written in C++ and can run on top of BSPlib and MPI.
"Parallel templates for numerical linear algebra, a high performance computation library", by Joris Koster, M.Sc. Thesis, Dept. of Mathematics, Utrecht University, July 2002, 77pp.
Software .

Last updated August 3, 2009.
to Home page Rob Bisseling.