.png){kind=icon}
返回
Scalable Unsupervised ML: Latency Hiding in Distributed Sparse Tensor Decomposition
.png){kind=icon}
OA
AI
DOI：10.1109/TPDS.2021.3128827.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Latency overhead in distributed-memory parallel CPD-ALS scales with the number of processors, limiting the scalability of computing CPD of large irregularly sparse tensors. This overhead comes in the form of sparse reduce and expand operations performed on factor-matrix rows via point-to-point messages. We propose to hide the latency overhead through embedding all of the point-to-point messages incurred by the sparse reduce and expand into dense collective operations which already exist in the CPD-ALS. The conventional parallel CPD-ALS algorithm is not amenable for embedding so we propose a computation/communication rearrangement to enable the embedding. We embed the sparse expand and reduce into a hypercube-based ALL-REDUCE operation to limit the latency overhead to O( log(2)K) for a K-processor system. The embedding comes with the cost of increased bandwidth overhead due to the multi-hop routing of factor-matrix rows during the embedded-ALL-REDUCE. We propose an embedding scheme that takes advantage of the expand/reduce properties to reduce this overhead. Furthermore, we propose a novel recursive bipartitioning framework that enables simultaneous hypergraph partitioning and subhypergraph-to-subhypercube mapping to achieve subtensor-to-processor assignment with the objective of reducing the bandwidth overhead during the embedded-ALL-REDUCE. We also propose a bin-packing-based algorithm for factor-matrix row to processor assignment aiming at reducing processors' maximum send and receive volumes during the embedded-ALL-REDUCE. Experiments on up to 4096 processors show that the proposed framework scales significantly better than the state-of-the-art point-to-point method.
Keyword:
Sparse tensor
tensor decomposition
CANDECOMP/PARAFAC
canonical polyadic decomposition
latency hiding
embedded communication
communication cost
concurrent communication
recursive bipartitioning
hypergraph partitioning
期刊
IF:
6
论文数:
5.2K
被引数:
1.1W
机构
引用论文
True Load Balancing for Matricized Tensor Times Khatri-Rao ProductMatricized Tensor Times khatri-rao产品的真正负载平衡
.png){kind=icon}
PREAI
分享收藏
分享收藏
查看更多内容