Parallel CP decomposition of sparse tensors using dimension trees

Oguz Kaya 1 Bora Uçar 1
1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Tensor factorization has been increasingly used to address various problems in many fields such as signal processing, data compression, computer vision, and computational data analysis. CANDECOMP/PARAFAC~(CP) decomposition of sparse tensors has successfully been applied to many well-known problems in web search, graph analytics, recommender systems, health care data analytics, and many other domains. In these applications, computing the CP decomposition of sparse tensors efficiently is essential in order to be able to process and analyze data of massive scale. For this purpose, we investigate an efficient computation and parallelization of the CP decomposition for sparse tensors. We provide a novel computational scheme for reducing the cost of a core operation in computing the CP decomposition with the traditional alternating least squares (CP-ALS) based algorithm. We then effectively parallelize this computational scheme in the context of CP-ALS in shared and distributed memory environments, and propose data and task distribution models for better scalability. We implement parallel CP-ALS algorithms and compare our implementations with an efficient tensor factorization library, using tensors formed from real-world and synthetic datasets. With our algorithmic contributions and implementations, we report up to 3.95x, 3.47x, and 3.9x speedups in sequential, shared memory parallel, and distributed memory parallel executions over the state of the art, and up to 1466x overall speedup over the sequential execution using 4096 cores on an IBM BlueGene/Q supercomputer.
Type de document :
Rapport
[Research Report] RR-8976, Inria - Research Centre Grenoble – Rhône-Alpes. 2016
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01397464
Contributeur : Equipe Roma <>
Soumis le : mardi 15 novembre 2016 - 21:22:01
Dernière modification le : mardi 16 janvier 2018 - 15:30:16
Document(s) archivé(s) le : jeudi 16 mars 2017 - 13:42:27

Fichier

RR-8976.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01397464, version 1

Collections

Citation

Oguz Kaya, Bora Uçar. Parallel CP decomposition of sparse tensors using dimension trees. [Research Report] RR-8976, Inria - Research Centre Grenoble – Rhône-Alpes. 2016. 〈hal-01397464〉

Partager

Métriques

Consultations de la notice

253

Téléchargements de fichiers

221