Abstract. Generalized sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high performance graph algorithms as well as for some linear solvers, such as algebraic multigrid. Here we show that SpGEMM also yields efficient algorithms for general sparse-matrix indexing in distributed memory, provided that the underlying SpGEMM implementation is sufficiently flexible and scalable. We demonstrate that our parallel SpGEMM methods, which use two-dimensional block data distributions with serial hypersparse kernels, are indeed highly flexible, scalable, and memoryefficient in the general case. This algorithm is the first to yield increasing speedup on an unbounded number of processors; our experiments show scaling up to thousands of processors in a variety of test scenarios. Key words. Parallel computing, numerical linear algebra, sparse matrix-matrix multiplication, SpGEMM, sparse matrix indexing, sparse matrix assignment, 2D data decomposition, hypersparsity, graph algorithms, sparse SUMMA, subgraph extraction, graph contraction, graph batch update. AMS subject classifications. 05C50, 05C85, 65F50, 68W10 1. Introduction. We describe scalable parallel implementations of two sparse matrix kernels. The first, SpGEMM, computes the product of two sparse matrices over a general semiring. The second, SpRef, performs generalized indexing into a sparse matrix: Given vectors I and J of row and column indices, SpRef extracts the submatrix A(I, J). Our novel approach to SpRef uses SpGEMM as its key subroutine, which regularizes the computation and data access patterns; conversely, applying SpGEMM to SpRef emphasizes the importance of an SpGEMM implementation that handles arbitrary matrix shapes and sparsity patterns, and a complexity analysis that applies to the general case. Our main contributions in this paper are: first, we show that SpGEMM leads to a simple and efficient implementation of SpRef; second, we describe a distributedmemory implementation of SpGEMM that is more general in application and more flexible in processor layout than before; and, third, we report on extensive experiments with the performance of SpGEMM and SpRef. We also describe an algorithm for sparse matrix assignment (SpAsgn), and report its parallel performance. The SpAsgn operation, formally A(I, J) = B, assigns a sparse matrix to a submatrix of another sparse matrix. It can be used to perform streaming batch updates to a graph. Parallel algorithms for SpGEMM and SpRef, as well as their theoretical performance, are described in Sections 3 and 4. We present the general SpGEMM algorithm and its parallel complexity before SpRef since the latter uses SpGEMM as a subroutine and its analysis uses results from the SpGEMM analysis. Section 3.1 summarizes our earlier results on the complexity of various SpGEMM algorithms on distributed memory. Section 3.3 presents our algorithm of choice, Sparse SUMMA, in a more formal way than before, including a pseudocode general enough to handle
The distributed SpGEMM implementation of HipMCL uses the Sparse SUMMA algorithm REF .
Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments
SIAM J. Sci. Comput., 34(4), 170 - 191, 2012
Computer Science