Distributed-Memory Parallel Algorithms for Sparse Matrix and Sparse Tall-and-Skinny Matrix Multiplication

本文考虑了一个稀疏矩阵乘法（SpGEMM）的场景，其中一个矩阵是方阵，另一个是高而瘦的矩阵。这个特殊的变体称为TS-SpGEMM，在多源广度优先搜索、影响最大化、稀疏图嵌入和代数多重网格求解器等方面具有重要应用。不幸的是，像稀疏SUMMA这样的流行分布式算法在TS-SpGEMM方面的性能表现不佳。为了解决这个问题，我们开发了一种专门针对TS-SpGEMM的新型分布式内存算法。我们的方法针对所有涉及的矩阵采用定制的一维分区，并利用稀疏感知的平铺来实现高效的数据传输。此外，它通过同时包含本地和远程计算来最小化通信开销。平均而言，我们的TS-SpGEMM算法比2D和3D SUMMA获得了5倍的性能提升。此外，我们使用我们的算法来实现多源广度优先搜索和稀疏图嵌入算法，并在NERSC Perlmutter上展示了它们在512个节点（或65,536个核心）上的可扩展性。

优化TS-SpGEMM的分布式算法

使用1D分区和稀疏感知的平铺来优化数据传输，同时结合本地和远程计算以减少通信开销

论文提出的TS-SpGEMM算法相较于2D和3D SUMMA平均获得了5倍的性能提升。实验展示了该算法在多源广度优先搜索和稀疏图嵌入中的可扩展性，并在NERSC Perlmutter上进行了测试。

最近的相关研究包括《Efficient Sparse Matrix-Matrix Multiplication on GPUs using the CSR Storage Format》和《Efficient Sparse Matrix-Matrix Multiplication on Intel Xeon Phi Coprocessors》等。