Abstract : This article introduces a new systolic algorithm for QR factorization, and its implementation on a supercomputing cluster of multicore nodes. The algorithm targets a virtual 3D-array and requires only local communications. The implementation of the algorithm uses threads at the node level, and MPI for inter-node communications. The complexity of the implementation is addressed with the PaRSEC software, which takes as input a parametrized dependence graph, which is derived from the algorithm, and only requires the user to decide, at the high-level, the allocation of tasks to nodes. We show that the new algorithm exhibits competitive performance with state-of-the-art QR routines on a supercomputer called Kraken, which shows that high-level programming environments, such as PaRSEC, provide a viable alternative to enhance the production of quality software on complex and hierarchical architectures.
Résumé : Cet article présente un nouvel algorithme systolique pour la factorisation QR, ainsi que son implémentation sur un cluster de noeuds multicoeurs. L'algorithme a été conçu pour un tore-3D virtuel et ne demande que des communications locales. L'implémentation de cet algorithme utilise des threads au niveau des noeuds, ainsi que MPI pour les communication inter-noeuds. La complexité de l'implémentation a été maîtrisée grâce à l'utilisation du logiciel PaRSEC, qui prend en entrée un graphe de dépendances paramétrisé, dérivé de l'algorithme, et ne laisse à l'utilisateur que le choix de l'allocation haut-niveau des tâches aux noeuds. Le nouvel algorithme s'avère aussi efficace que des routines QR à la pointe de l'art sur le super-ordinateur Kraken, montrant ainsi que l'environnement PaRSEC est une excellente alternative pour accroître la production de logiciels de qualité sur des architectures complexes et hiérarchiques.
