ParCubed: Fast Graph Partitioner for use with Inspector/Executor Strategies
The ParCubed graph partitioner is designed to quickly partition graphs expressed as CSR sparse matrices using shared memory. It typically generates results with an edge cut within 10% of that produced by METIS. It is, however, many times faster than serial METIS on a 8 core system. ParCubed was introduced at LCPC 2012 in Tokyo, Japan. The full paper is here. The work was partially funded by the PIES project.The entire partitioner consists of only a few files. Two make up the partitioner itself, which is a C++ class. The other two are the parallel Disjoint Set (also known as a Union-Find) data structure. The code includes an OpenMP version and a Threading Building Blocks (TBB) version. You will need to either remove the TBB code or else compile the code with TBB. TBB is freely available from the TBB website. The other files are some simple CSR sparse matrix data structures and a simple top level example. Data files for use with the example can be downloaded from the University of Florida Sparse Matrix Collection in "Matrix Market" format. The necessary METIS files are available from Karypis Lab. METIS dependencies can be removed if you don't need convenient head to head comparisons with METIS results.
The tarball contains a simple example and a tiny sparse matrix (5x5 band matrix) for testing purposes. A makefile is also included, which you will most likely have to modify for your machine. ParCubed has been built under linux and MacOSX/Darwin.
History:
May 2013: Updated. Includes minor fix permitting it to complete in some cases with specific topology.Sept 2012: Initial Release
Code:
Source Code Tarball