Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a new distributed algorithm for computing the symmetric rank-$k$ update (SYRK) of sparse matrices, which significantly optimizes performance by leveraging the symmetry in both inputs and outputs. By partitioning the output blocks and only computing the lower triangular portion, the method reduces communication and computation overhead compared to existing algorithms like Sparse SUMMA. On the Perlmutter supercomputer, the proposed approach achieves a 2x speedup on relevant datasets, demonstrating its effectiveness in enhancing the efficiency of distributed sparse matrix multiplication tasks.
Achieving a 2x speedup in distributed sparse matrix multiplication by exploiting symmetry could redefine performance benchmarks in large-scale machine learning applications.
The symmetric rank-$k$ update (SYRK), $\C = \A\A^\top$, computes the dot product between each pair of rows of $\A$, producing the Gram matrix $\C$. Its sparse variant underpins similarity search in machine learning, graph analytics, and genomics, including Jaccard similarity on datasets too large for a single node. Yet, despite the symmetry in its inputs and outputs, existing distributed sparse matrix multiplication algorithms, such as Sparse SUMMA, treat sparse SYRK as generic multiplication, leaving performance untapped. In this paper, we present distributed sparse SYRK approaches that leverage symmetry. The approach partitions the off-diagonal blocks of the output between the upper and lower triangular portions of the process grid and computes only the lower-triangular part of each diagonal block, reducing per-process communication and computation compared with state-of-the-art distributed SpGEMM. A second variant reorders communication to avoid materializing $\A^\top$. On 32 nodes of the Perlmutter supercomputer, the algorithm achieves a $2\times$ speedup over an optimized Sparse SUMMA on matrices where local multiplication dominates the runtime; the advantage narrows on communication-bound inputs, a dependence the cost model predicts from the arithmetic intensity. Our variant rectifies this and consistently achieves superior scaling at high process counts. The approach is a drop-in replacement for any application computing $\C = \A \A^\top$ via a distributed SpGEMM routine, and its triangular output can be consumed directly by subsequent operations, reducing both compute and memory footprint.