A Tight I/O Lower Bound for Matrix Multiplication
A Tight I/O Lower Bound for Matrix Multiplication
复制标题
矩阵乘法的严格 I/O 下界
DOI：
10.1145/3362694
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
R. A. van de Geijn
中科院分区：
文献类型：
--
作者：
T. Smith;R. A. van de Geijn
建立了在具有两层存储器的处理器上计算矩阵-矩阵乘法时所需I/O的严格下限。以前的工作通过推理执行C：=AB所需的阶段数获得了较弱的下界，其中每个阶段是涉及S对快存储器的读写的一系列操作，而S是快存储器的大小。然后，通过获得每个阶段执行的标量乘法的数量的上限来确定阶段数量的下限。本文遵循相同的高层方法，但改进了下界，用C：=AB+C代替C：=AB，得到了每相最大标量融合乘加(FMA)数，而不是标量加法。获得新结果的关键是将每个阶段的I/O与快速内存的大小分离。新的下限是2mnk/S-2S，其中S是快记忆的大小。前导项的常数是因子4/2的改进。给出了一个达到下界的理论算法，并讨论了目前最先进的Goto算法在某种意义上也达到了下界。
A tight lower bound for required I/O when computing a matrix-matrix multiplication on a processor with two layers of memory is established. Prior work obtained weaker lower bounds by reasoning about the number of phases needed to perform C:=AB, where each phase is a series of operations involving S reads and writes to and from fast memory, and S is the size of fast memory. A lower bound on the number of phases was then determined by obtaining an upper bound on the number of scalar multiplications performed per phase. This paper follows the same high level approach, but improves the lower bound by considering C:=AB+C instead of C:=AB, and obtains the maximum number of scalar fused multiply-adds (FMAs) per phase instead of scalar additions. Key to obtaining the new result is the decoupling of the per-phase I/O from the size of fast memory. The new lower bound is 2mnk/ S - 2S where S is the size of fast memory. The constant for the leading term is an improvement of a factor 4/ 2. A theoretical algorithm that attains the lower bound is given, and how the state-of-the-art Goto's algorithm also in some sense meets the lower bound is discussed.
矩阵化张量时间 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