Parallel Memory-Independent Communication Bounds for SYRK
Parallel Memory-Independent Communication Bounds for SYRK
复制标题
SYRK 的并行内存独立通信范围
DOI：
10.1145/3558481.3591072
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Rouse, Kathryn
中科院分区：
文献类型：
--
作者：
Al Daas, Hussam;Ballard, Grey;Grigori, Laura;Kumar, Suraj;Rouse, Kathryn
在本文中，我们重点研究了矩阵与其转置相乘的并行通信开销，称为对称秩k更新(SYRK)。由于输出矩阵的对称性，SYRK的计算量是一般矩阵乘法的一半。最近的工作(Beaumont等人，SPAA‘22)证明了SYRK的顺序I/O复杂性也是一个小于一般矩阵乘法的常数。受此启发，我们建立了SYRK的与内存无关的并行通信下界，其常数比一般矩阵乘法小，并且我们通过给出通信优化算法证明了这些常数是紧的。下界证明的关键在于将一个关键的几何不等式推广到对称计算和解析求解一个约束非线性优化问题。最优算法使用三角分块方案来并行分配对称输出矩阵和相应的计算。
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.
登录
查看更多内容
矩阵乘法的严格 I/O 下界
DOI：
10.1145/3362694
发表时间：
2017
期刊：
ACM Transactions on Mathematical Software (TOMS)
影响因子：
--
作者：
T. Smith;R. A. van de Geijn
通讯作者：
R. A. van de Geijn
IOOpt：自动推导仿射程序的 I/O 复杂度界限
DOI：
10.1145/3453483.3454103
发表时间：
2021
期刊：
42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Olivry, Auguste;Iooss, Guillaume;Tollenaere, Nicolas;Rountev, Atanas;Sadayappan, P.;Rastello, Fabrice
通讯作者：
Rastello, Fabrice
DOI：
10.1145/3385412.3385989
发表时间：
2020
期刊：
41st ACM SIGPLAN International Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Olivry, Auguste;Langou, Julien;Pouchet, Louis-Noël;Sadayappan, P.;Rastello, Fabrice
通讯作者：
Rastello, Fabrice
简短公告：矩阵乘法算法的强大扩展和与内存无关的通信下界
DOI：
10.1145/2312005.2312021
发表时间：
2012
期刊：
ArXiv
影响因子：
--
作者：
Grey Ballard;J. Demmel;Olga Holtz;Benjamin Lipshitz;O. Schwartz
通讯作者：
O. Schwartz
严格的内存独立并行矩阵乘法通信下界
DOI：
10.48550/arxiv.2205.13407
发表时间：
2022
期刊：
ArXiv
影响因子：
--
作者：
Hussam Al Daas;Grey Ballard;L. Grigori;Suraj Kumar;Kathryn Rouse
通讯作者：
Kathryn Rouse