Distributed-Memory Parallel Algorithms for Sparse Matrix and Sparse Tall-and-Skinny Matrix Multiplication
<|reference_start|>Distributed-Memory Parallel Algorithms for Sparse Matrix and Sparse Tall-and-Skinny Matrix Multiplication: We consider a sparse matrix-matrix multiplication (SpGEMM) setting where one matrix is square and the other is tall and skinny. This special variant, called 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.<|reference_end|>
@article{ranawaka2024distributed-memory,
    title={Distributed-Memory Parallel Algorithms for Sparse Matrix and Sparse
  Tall-and-Skinny Matrix Multiplication},
    author={Isuru Ranawaka, Md Taufique Hussain, Charles Block, Gerasimos
  Gerogiannis, Josep Torrellas, Ariful Azad},
    journal={arXiv preprint arXiv:2408.11988},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.11988},
    primaryClass={cs.DC}
}