Evaluating Sparse Collective Communication Algorithms for Structured Graphs and Matrices

Abstract

Efficient collective communication is a key challenge for scaling applications on distributed memory architectures. Prior analyses have largely focused on dense matrix computations, where data often moves in predictable ways. However, many real-world problems are expressed in terms of graphs whose adjacency matrices are sparse. The structure and storage format of these matrices can introduce irregular communication patterns in distributed networks. This thesis looks into the study of how matrix size, sparsity pattern, and storage format affect the performance of parallel communication collectives and sparse matrix multiplication. Using the SUMMA algorithm as a baseline, we evaluate communication and computation costs across a range of matrix aspect ratios, sparsity patterns, and sparse storage formats, including CSR and CSC. Our experiments use both synthetic matrices with controlled density and structure, as well as Kronecker-generated graphs, and are implemented using collective communication primitives in MPI. Furthermore, we look to determine the limitations imposed by matrix shape and sparsity on statistics such as memory bandwidth, communication overhead, and overall multiplication performance.