Load Plus Communication Balancing of Contiguous Sparse Matrix Partitions

We partition to parallelize multiplication of one or more dense vectors by a sparse matrix (SpMV or SpMM). We consider contiguous partitions, where the rows (or columns) of a sparse matrix with $N$ nonzeros are split into $K$ parts without reordering. We propose exact and approximate contiguous partitioners that minimize the maximum runtime of any processor under a diverse family of cost models that combine work and hypergraph communication terms in symmetric or asymmetric settings. This differs from traditional partitioning models which minimize total communication, or from traditional load balancing models which only balance work. One can view our algorithms as optimally rounding one-dimensional embeddings of direct $K$-way noncontiguous partitioning problems. Our algorithms use linear space. Our exact algorithm runs in linear time when $K^2$ is $O(N^C)$ for $C < 1$. Our $(1 + \epsilon)$-approximate algorithm runs in linear time when $K\log(c_{\text{high}}/(c_{\text{low}}\epsilon))$ is $O(N^C)$ for $C < 1$, where $c_{\text{high}}$ and $c_{\text{low}}$ are upper and lower bounds on the optimal cost. We also propose a simpler $(1 + \epsilon)$-approximate algorithm which runs in a factor of $\log(c_{\text{high}}/(c_{\text{low}}\epsilon))$ from linear time, but is faster in practice. We empirically demonstrate that all of our algorithms efficiently produce high-quality contiguous partitions.