Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments

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 memory-efficient 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.

References in corpus (1)

• Minimizing Communication in Linear Algebra

Cited by in corpus (22)

• Mathematical Foundations of the GraphBLAS
• Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication
• A Framework for General Sparse Matrix-Matrix Multiplication on GPUs and Heterogeneous Processors
• Understanding the geometry of transport: diffusion maps for Lagrangian trajectory data unravel coherent sets
• A Systematic Survey of General Sparse Matrix-Matrix Multiplication
• SMASH: Co-designing Software Compression and Hardware-Accelerated Indexing for Efficient Sparse Matrix Operations
• Graphs, Matrices, and the GraphBLAS: Seven Good Reasons
• Graphulo Implementation of Server-Side Sparse Matrix Multiply in the Accumulo Database
• Graph-based linear scaling electronic structure theory
• Scalable Task-Based Algorithm for Multiplication of Block-Rank-Sparse Matrices
• A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs
• Novel Graph Processor Architecture, Prototype System, and Results
• The Parallelism Motifs of Genomic Data Analysis
• Locality-aware parallel block-sparse matrix-matrix multiplication using the Chunks and Tasks programming model
• Properties of Healthcare Teaming Networks as a Function of Network Construction Algorithms
• Graph-based Quantum Response Theory and Shadow Born-Oppenheimer Molecular Dynamics
• An N-Body Solution to the Problem of Fock Exchange
• Vertical, Temporal, and Horizontal Scaling of Hierarchical Hypersparse GraphBLAS Matrices
• Parallelization and scalability analysis of inverse factorization using the Chunks and Tasks programming model
• CB-SpMV:A Data Aggregating and Balance Algorithm for Cache-Friendly Block-Based SpMV on GPUs
• SAGE: A Storage-Based Approach for Scalable and Efficient Sparse Generalized Matrix-Matrix Multiplication
• Parallel GPU-Enabled Algorithms for SpGEMM on Arbitrary Semirings with Hybrid Communication