Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds
Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds
复制标题
严格的内存独立并行矩阵乘法通信下界
DOI：
10.48550/arxiv.2205.13407
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Kathryn Rouse
中科院分区：
文献类型：
--
作者：
Hussam Al Daas;Grey Ballard;L. Grigori;Suraj Kumar;Kathryn Rouse
对于矩阵乘法算法，通信下界早已建立。然而，大多数渐近分析方法要么忽略了常数因素，要么没有得到最接近的可能值。最近的研究表明，更仔细的分析可以改善一些经典矩阵乘法下界的已知常数，并有助于确定更有效的算法，使其准确匹配下界中的首阶项，从而提高实际性能。这项工作的主要成果是建立了具有紧常数的并行矩阵乘法的与内存无关的通信下界。我们的常数在依赖于矩阵长宽比的相对大小的三种情况下都比以前的工作有所改进。
Communication lower bounds have long been established for matrix multiplication algorithms. However, most methods of asymptotic analysis have either ignored the constant factors or not obtained the tightest possible values. Recent work has demonstrated that more careful analysis improves the best known constants for some classical matrix multiplication lower bounds and helps to identify more efficient algorithms that match the leading-order terms in the lower bounds exactly and improve practical performance. The main result of this work is the establishment of 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 aspect ratios of the matrices.
矩阵化张量时间 Khatri-Rao 产品的通信下界
DOI：
10.1109/ipdps.2018.00065
发表时间：
2018
期刊：
2018 IEEE International Parallel and Distributed Processing Symposium
影响因子：
--
作者：
Ballard, Grey;Knight, Nicholas;Rouse, Kathryn
通讯作者：
Rouse, Kathryn
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
影响因子：
3.7
作者：
Grey Ballard;Kathryn Rouse
通讯作者：
Grey Ballard;Kathryn Rouse