Scalable unsupervised ML: Latency hiding in distributed sparse tensor decomposition
| Autor: | Nabil Abubaker, M. Ozan Karsavuran, Cevdet Aykanat |
|---|---|
| Přispěvatelé: | Abubaker, Nabil, Karsavuran, M. Ozan, Aykanat, Cevdet |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Embedded communication
Computer science Recursive bipartitioning Hypergraph partitioning Parallel computing Concurrent communication Sparse tensor Computational Theory and Mathematics Hardware and Architecture CANDECOMP/PARAFAC Tensor decomposition Signal Processing Scalability Bandwidth (computing) Embedding Overhead (computing) Latency hiding Hypercube Routing (electronic design automation) Latency (engineering) Communication cost Row Canonical polyadic decomposition |
| Zdroj: | IEEE Transactions on Parallel and Distributed Systems (TPDS) |
| Popis: | 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 2KÞ 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|