Authors: Qi Wang (National University of Defense Technology (NUDT)); Shengguo Li (National University of Defense Technology (NUDT), College of Computer Science and Technology); Xiaojian Yang and Deshun Bi (National University of Defense Technology (NUDT)); Chen Wang and Song Wang (Tsinghua University); and Tiejun Li, Yujuan Tan, and Bo Yang (National University of Defense Technology (NUDT))
Abstract: Distributed sparse matrix–dense matrix multiplication (SpMM) is often bottlenecked by communication and performs poorly under irregular sparsity patterns. We propose a unified task–data parallel (TDP) framework that jointly models task decomposition and data distribution, enabling communication analysis across the SpMM design space. Within this framework, we identify two complementary 2D submodels, $mn\text{-}r_A r_B$ and $kn\text{-}c_A r_C$, with distinct sparsity-dependent communication costs, and develop a fused MNKN algorithm that partitions the sparse matrix into tiles and assigns each tile to the lower-cost submodel using lightweight sparsity-aware metrics. This design enables fine-grained dense-side communication avoidance without additional storage overhead while naturally overlapping communication and computation. Experiments on large-scale SuiteSparse matrices show performance gains on 68% of 135 matrices, including up to an order-of-magnitude speedup over 2D SUMMA and an average speedup of 2.4x over the sparsity-aware CRP baseline on 10 representative matrices. We further demonstrate its effectiveness in polynomial-filtering eigensolvers.
Presentation: file