Close

Presentation

Distributed-Memory Parallel Algorithms for Sparse Matrix and Sparse Tall-and-Skinny Matrix Multiplication
DescriptionWe consider a sparse matrix-matrix multiplication (SpGEMM) setting where one matrix is square and the other is tall and skinny. This special variant, which we call TS-SpGEMM, has important applications in multi-source breadth-first search, influence maximization, sparse graph embedding, and algebraic multigrid solvers. Unfortunately, popular distributed algorithms like sparse SUMMA deliver suboptimal performance for TS-SpGEMM. To address this limitation, we
develop a novel distributed-memory algorithm tailored for TS-SpGEMM.
Our approach employs customized 1D partitioning for all matrices involved and leverages sparsity-aware tiling for efficient data transfers. In addition, it minimizes communication overhead by incorporating both local and remote computations. On average, our TS-SpGEMM algorithm attains 5X performance gains over 2D and 3D SUMMA. Furthermore, we use our algorithm to implement multi-source breadth-first search and sparse graph embedding algorithms
and demonstrate their scalability up to 512 Nodes (or 65,536 cores) on NERSC Perlmutter.
Event Type
Paper
TimeWednesday, 20 November 202410:30am - 11am EST
LocationB311
Tags
Algorithms
Artificial Intelligence/Machine Learning
Graph Algorithms
Linear Algebra
Registration Categories
TP