Brief Announcement: Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds

Brief Announcement: Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds
复制标题

简短公告：严格的内存独立并行矩阵乘法通信下界

DOI：
10.1145/3490148.3538552
复制
发表时间：
2022
期刊：
Proceedings of the 34th Annual ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
通讯作者：
Rouse, Kathryn
Rouse, Kathryn
中科院分区：
--
文献类型：
--
作者：
Al Daas, Hussam;Ballard, Grey;Grigori, Laura;Kumar, Suraj;Rouse, Kathryn

文献摘要

相似文献

矩阵乘法算法的通信下限早已确定。然而，大多数渐近分析方法要么忽略了常数因子，要么没有获得最严格的可能值。这项工作的主要结果是为并行矩阵乘法建立具有严格常数的独立于内存的通信下界。我们的常数在三种情况下都改进了以前的工作，这三种情况取决于矩阵纵横比的相对大小和处理器的数量。
Communication lower bounds have long been established for matrix multiplication algorithms. However, most methods of asymptotic analysis have either ignored constant factors or not obtained the tightest possible values. The main result of this work is establishing memory-independent communication lower bounds with tight constants for parallel matrix multiplication. Our constants improve on previous work in each of three cases that depend on the relative sizes of the matrix aspect ratios and the number of processors.