General Memory-Independent Lower Bound for MTTKRP
General Memory-Independent Lower Bound for MTTKRP
复制标题
DOI：
10.1137/1.9781611976137
复制
发表时间：
2020-01
影响因子：
3.7
通讯作者：
Grey Ballard;Kathryn Rouse
中科院分区：
文献类型：
--
作者：
Grey Ballard;Kathryn Rouse
我们的目标是建立一个分布式内存并行机上执行矩阵化张量时间Khatri-Rao产品（MTTKRP）计算所需的通信的下限。MTTKRP是计算CP张量分解的算法中的瓶颈计算，CP张量分解是秩1张量之和的近似，经常用于多维数据分析。本文的主要结果是一个通信下界，概括了以前的结果，收紧的界限，使它是可以实现的，即使当张量尺寸变化（张量不是立方），当处理器的数量是小的相对于张量尺寸。该界的可达性证明了基于张量块分布且只传递因子矩阵的算法是最优的。证明技术利用了一个既定的不等式，涉及到数据访问的计算，以及一种新的方法，基于凸优化。
Our goal is to establish lower bounds on the communication required to perform the Matricized-Tensor Times Khatri-Rao Product (MTTKRP) computation on a distributed-memory parallel machine. MTTKRP is the bottleneck computation within algorithms for computing the CP tensor decomposition, which is an approximation by a sum of rank-one tensors and frequently used in multidimensional data analysis. The main result of this paper is a communication lower bound that generalizes previous results, tightening the bound so that it is attainable even when the tensor dimensions vary (the tensor is not cubical) and when the number of processors is small relative to the tensor dimensions. The attainability of the bound proves that the algorithm that at-tains it, which is based on a block distribution of the tensor and communicating only factor matrices, is communication optimal. The proof technique utilizes an established inequality that relates computations to data access as well as a novel approach based on convex optimization.