Skip to Main content Skip to Navigation
Conference papers

High Performance Parallel Algorithms for the Tucker Decomposition of Sparse Tensors

Oguz Kaya 1, 2, * Bora Uçar 1, 2
* Corresponding author
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : —We investigate an efficient parallelization of a class of algorithms for the well-known Tucker decomposition of general N-dimensional sparse tensors. The targeted algorithms are iterative and use the alternating least squares method. At each iteration, for each dimension of an N-dimensional input tensor, the following operations are performed: (i) the tensor is multiplied with (N − 1) matrices (TTMc step); (ii) the product is then converted to a matrix; and (iii) a few leading left singular vectors of the resulting matrix are computed (TRSVD step) to update one of the matrices for the next TTMc step. We propose an efficient parallelization of these algorithms for the current parallel platforms with multicore nodes. We discuss a set of preprocessing steps which takes all computational decisions out of the main iteration of the algorithm and provides an intuitive shared-memory parallelism for the TTM and TRSVD steps. We propose a coarse and a fine-grain parallel algorithm in a distributed memory environment, investigate data dependencies, and identify efficient communication schemes. We demonstrate how the computation of singular vectors in the TRSVD step can be carried out efficiently following the TTMc step. Finally, we develop a hybrid MPI-OpenMP implementation of the overall algorithm and report scalability results on up to 4096 cores on 256 nodes of an IBM BlueGene/Q supercomputer.
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/hal-01354894
Contributor : Equipe Roma <>
Submitted on : Friday, August 19, 2016 - 9:17:27 PM
Last modification on : Wednesday, November 20, 2019 - 3:18:43 AM
Long-term archiving on: : Sunday, November 20, 2016 - 10:29:05 AM

File

PID4261953.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01354894, version 1

Collections

Citation

Oguz Kaya, Bora Uçar. High Performance Parallel Algorithms for the Tucker Decomposition of Sparse Tensors. International Conference on Parallel Processing (ICPP), Aug 2016, 2016-08-19, United States. ⟨hal-01354894⟩

Share

Metrics

Record views

318

Files downloads

866