A Medium-Grained Algorithm for Distributed Sparse Tensor Factorization

Smith, Shaden
Karypis, George
2016-05-02
Thumbnail Image

View/Download File

16-006.pdf (319.61 KB)

Persistent link to this item

https://hdl.handle.net/11299/215991
Statistics
View Statistics

Journal Title

Journal ISSN

Volume Title

Title

A Medium-Grained Algorithm for Distributed Sparse Tensor Factorization

Authors

Published Date

2016-05-02

Publisher

Type

Report

Abstract

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.

Keywords

Description

Related to

Replaces

License

Collections

Computer Science & Engineering (CS&E) Technical Reports

Series/Report Number

Technical Report; 16-006

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Suggested citation

Smith, Shaden; Karypis, George. (2016). A Medium-Grained Algorithm for Distributed Sparse Tensor Factorization. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215991.

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.