Parallel Memory-Independent Communication Bounds for SYRK

Hussam Al Daas (1) , Grey Ballard (2) , Laura Grigori (3) , Suraj Kumar (4) , Kathryn Rouse (5)

1 RAL - STFC Rutherford Appleton Laboratory
2 Wake Forest University
3 ALPINES - Algorithms and parallel tools for integrated numerical simulations
4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
5 Inmar Intelligence

In this paper, we focus on the parallel communication cost of multiplying a matrix with its transpose, known as a symmetric rank-k update (SYRK). SYRK requires half the computation of general matrix multiplication because of the symmetry of the output matrix. Recent work (Beaumont et al., SPAA '22) has demonstrated that the sequential I/O complexity of SYRK is also a constant factor smaller than that of general matrix multiplication. Inspired by this progress, we establish memory-independent parallel communication lower bounds for SYRK with smaller constants than general matrix multiplication, and we show that these constants are tight by presenting communication-optimal algorithms. The crux of the lower bound proof relies on extending a key geometric inequality to symmetric computations and analytically solving a constrained nonlinear optimization problem. The optimal algorithms use a triangular blocking scheme for parallel distribution of the symmetric output matrix and corresponding computation.

Mots clés: Symmetric matrices; Communication costs; Convex optimization

Domaines: Informatique [cs]

Hussam Al Daas, Grey Ballard, Laura Grigori, Suraj Kumar, Kathryn Rouse. Parallel Memory-Independent Communication Bounds for SYRK. SPAA '23 - ACM Symposium on Parallelism in Algorithms and Architectures, Jun 2023, Orlando, United States. ⟨10.1145/3558481.3591072⟩. ⟨hal-04076513⟩