A Medium-Grained Algorithm for Sparse Tensor Factorization
A Medium-Grained Algorithm for Sparse Tensor Factorization
复制标题
稀疏张量分解的中粒度算法
DOI：
10.1109/ipdps.2016.113
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
G. Karypis
中科院分区：
文献类型：
--
作者：
Shaden Smith;G. Karypis
多路数据建模可以使用张量来完成，张量是沿三个或更多维度索引的数据结构。张量越来越多地用于分析生命科学、工程和商业中极其庞大且稀疏的多路数据集。正则多元分解 (CPD) 是一种用于发现潜在特征的流行张量分解，最常见的是通过交替最小二乘法 (CPD-ALS) 发现的。计算 CPD 所需的计算时间和内存限制了典型工作站上可以求解的张量的大小和维数，这使得分布式解决方案成为唯一可行的选择。分布式内存系统的大多数方法都集中在以粗粒度的一维方式分布张量，这过高地要求在每个节点上完全复制密集矩阵因子。最近的工作通过使用张量非零值的细粒度分解克服了这一限制，但代价是计算成本高昂的超图划分。为此，我们提出了一种中粒度的分解，避免了完整的因子复制和通信，同时消除了昂贵的预处理步骤的需要。我们使用混合 MPI+OpenMP 实现，利用低内存占用的多核架构。我们从理论上分析了粗粒度、中粒度和细粒度分解的可扩展性，并通过实验在各种数据集上对它们进行了比较。实验表明，中粒度分解比粗粒度分解减少了36-90%的通信量，比最先进的MPI代码快41-76倍，比1024核细粒度分解快1.5-5.0倍。
Modeling multi-way data can be accomplished using tensors, which are data structures indexed along three or more dimensions. Tensors are increasingly used to analyze extremely large and sparse multi-way datasets in life sciences, engineering, and business. The canonical polyadic decomposition (CPD) is a popular tensor factorization for discovering latent features and is most commonly found via the method of alternating least squares (CPD-ALS). The computational time and memory required to compute CPD limits the size and dimensionality of the tensors that can be solved on a typical workstation, making distributed solution approaches the only viable option. Most methods for distributed-memory systems have focused on distributing the tensor in a coarse-grained, one-dimensional fashion that prohibitively requires the dense matrix factors to be fully replicated on each node. Recent work overcomes this limitation by using a fine-grained decomposition of the tensor nonzeros, at the cost of computationally expensive hypergraph partitioning. To that effect, we present a medium-grained decomposition that avoids complete factor replication and communication, while eliminating the need for expensive pre-processing steps. We use a hybrid MPI+OpenMP implementation that exploits multi-core architectures with a low memory footprint. We theoretically analyze the scalability of the coarse-, medium-, and fine-grained decompositions and experimentally compare them across a variety of datasets. Experiments show that the medium-grained decomposition reduces communication volume by 36-90% compared to the coarse-grained decomposition, is 41-76x faster than a state-of-the-art MPI code, and is 1.5-5.0x faster than the fine-grained decomposition with 1024 cores.