QR Factorization of Tall and Skinny Matrices in a Grid Computing Environment

Emmanuel Agullo 1, 2, 3 Camille Coti 4, 5 Jack Dongarra 1 Thomas Herault 1, 4, 5 Julien Langou 6
2 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
5 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : To exploit the potential of multicore architectures, recent dense linear algebra libraries have used tile algorithms, which consist in scheduling a Directed Acyclic Graph (DAG) of tasks of fine granularity where nodes represent tasks, either panel factorization or update of a block-column, and edges represent dependencies among them. Although past approaches already achieve high performance on moderate and large square matrices, their way of processing a panel in sequence leads to limited performance when factorizing tall and skinny matrices or small square matrices. We present a new fully asynchronous method for computing a QR factorization on shared-memory multicore architectures that overcomes this bottleneck. Our contribution is to adapt an existing algorithm that performs a panel factorization in parallel (named Communication-Avoiding QR and initially designed for distributed-memory machines), to the context of tile algorithms using asynchronous computations. An experimental study shows significant improvement (up to almost 10 times faster) compared to state-of-the-art approaches. We aim to eventually incorporate this work into the Parallel Linear Algebra for Scalable Multi-core Architectures (PLASMA) library.
Type de document :
Communication dans un congrès
24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010), Apr 2010, Atlanta, United States. 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00548900
Contributeur : Emmanuel Agullo <>
Soumis le : mardi 21 décembre 2010 - 09:39:58
Dernière modification le : jeudi 9 février 2017 - 15:54:06
Document(s) archivé(s) le : lundi 5 novembre 2012 - 14:41:56

Fichier

grid-QR-IPDPS-2010.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00548900, version 1

Citation

Emmanuel Agullo, Camille Coti, Jack Dongarra, Thomas Herault, Julien Langou. QR Factorization of Tall and Skinny Matrices in a Grid Computing Environment. 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010), Apr 2010, Atlanta, United States. 2010. 〈inria-00548900〉

Partager

Métriques

Consultations de
la notice

638

Téléchargements du document

270