Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication

Abstract

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. The scaling of existing parallel implementations of SpGEMM is heavily bound by communication. Even though 3D (or 2.5D) algorithms have been proposed and theoretically analyzed in the flat MPI model on Erdos-Renyi matrices, those algorithms had not been implemented in practice and their complexities had not been analyzed for the general case. In this work, we present the first ever implementation of the 3D SpGEMM formulation that also exploits multiple (intra-node and inter-node) levels of parallelism, achieving significant speedups over the state-of-the-art publicly available codes at all levels of concurrencies. We extensively evaluate our implementation and identify bottlenecks that should be subject to further research.

References in corpus (1)

• A Framework for General Sparse Matrix-Matrix Multiplication on GPUs and Heterogeneous Processors

Cited by in corpus (20)

• SpArch: Efficient Architecture for Sparse Matrix Multiplication
• A Systematic Survey of General Sparse Matrix-Matrix Multiplication
• Novel Graph Processor Architecture, Prototype System, and Results
• Increasing the Efficiency of Sparse Matrix-Matrix Multiplication with a 2.5D Algorithm and One-Sided MPI
• The Parallelism Motifs of Genomic Data Analysis
• Locality-aware parallel block-sparse matrix-matrix multiplication using the Chunks and Tasks programming model
• Fast Feasible and Unfeasible Matrix Multiplication
• Prior-preconditioned conjugate gradient method for accelerated Gibbs sampling in "large $n$ & large $p$" Bayesian sparse regression
• Efficient Parallel Linear Scaling Method to get the Response Density Matrix in All-Electron Real-Space Density-Functional Perturbation Theory
• Distributed Triangle Counting in the Graphulo Matrix Math Library
• RDMA-Based Algorithms for Sparse Matrix Multiplication on GPUs
• High-performance sparse matrix-matrix products on Intel KNL and multicore architectures
• Bandwidth-Optimized Parallel Algorithms for Sparse Matrix-Matrix Multiplication using Propagation Blocking
• SAGE: A Storage-Based Approach for Scalable and Efficient Sparse Generalized Matrix-Matrix Multiplication
• Parallelization and scalability analysis of inverse factorization using the Chunks and Tasks programming model
• Efficient computation of the density matrix with error control on distributed computer systems
• Implementing Push-Pull Efficiently in GraphBLAS
• pylspack: Parallel algorithms and data structures for sketching, column subset selection, regression and leverage scores
• AIRES: Accelerating Out-of-Core GCNs via Algorithm-System Co-Design
• Parallel GPU-Enabled Algorithms for SpGEMM on Arbitrary Semirings with Hybrid Communication