Accelerating the Mondriaan sparse matrix partitioning package

Abstract

We consider a number of modifications to the Mondriaan package for sparse matrix partitioning, with as main goal to improve run times of the software. Two new algorithms are considered, one of which aims at reducing load imbalance to enable Mondriaan to find partitionings with less communication volume, while the other aims at finding solutions with zero communication volume more quickly than Mondriaan currently does. The other modifications include an improved sorting function, an improvement in a data structure used in a core component of Mondriaan, and two modifications in the PGA matching algorithm implementation used in Mondriaan. We compare the performance of each modification against the previous version, Mondriaan 4.1, and we will discuss which modifications are suitable to include into a new version, Mondriaan 4.2. Experiments with a candidate version for Mondriaan 4.2 show a mean run time improvement of 25% compared to Mondriaan 4.1, while also significantly reducing the mean load imbalance and slightly reducing the mean communication volume.