Implementing a Systolic Algorithm for QR Factorization on Multicore Clusters with PaRSEC
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.
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.
Origin : Files produced by the author(s)
Loading...