Brief announcement: strong scaling of matrix multiplication algorithms and memory-independent communication lower bounds
Brief announcement: strong scaling of matrix multiplication algorithms and memory-independent communication lower bounds
复制标题
简短公告：矩阵乘法算法的强大扩展和与内存无关的通信下界
DOI：
10.1145/2312005.2312021
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
O. Schwartz
中科院分区：
文献类型：
--
作者：
Grey Ballard;J. Demmel;Olga Holtz;Benjamin Lipshitz;O. Schwartz
一个并行算法具有完美的强可标度性，如果它在$P$处理器上的运行时间在$1/P$中是线性的，包括所有的通信费用。最近才发现具有完美强缩放的矩阵乘法的分布式存储并行算法，一种是基于经典矩阵乘法（Solomonik and Demmel，2011），另一种是基于斯特拉森的快速矩阵乘法（Ballard，Demmel，Holtz，Lipshitz，and Schwartz，2012）。这两种算法都可以完美地扩展，但只能扩展到处理器间通信不再扩展的处理器数量。我们得到了一个内存独立的通信成本的经典和基于Strassen的分布式存储矩阵乘法算法的下界。这些界限意味着，没有经典的或基于Strassen的并行矩阵乘法算法可以强大的规模完全超出上述两个并行算法已经达到的范围。记忆无关的边界和强缩放边界推广到其他算法。
A parallel algorithm has perfect strong scaling if its running time on $P$ processors is linear in $1/P$, including all communication costs. Distributed-memory parallel algorithms for matrix multiplication with perfect strong scaling have only recently been found. One is based on classical matrix multiplication (Solomonik and Demmel, 2011), and one is based on Strassen's fast matrix multiplication (Ballard, Demmel, Holtz, Lipshitz, and Schwartz, 2012). Both algorithms scale perfectly, but only up to some number of processors where the inter-processor communication no longer scales. We obtain a memory-independent communication cost lower bound on classical and Strassen-based distributed-memory matrix multiplication algorithms. These bounds imply that no classical or Strassen-based parallel matrix multiplication algorithm can strongly scale perfectly beyond the ranges already attained by the two parallel algorithms mentioned above. The memory-independent bounds and the strong scaling bounds generalize to other algorithms.