Advanced task-based programming models for scalable linear algebra operations
Modèles de programmation avancés à base de tâches pour les algorithmes d'algèbre linéaire qui passent à l'échelle
Résumé
Writing high-performance computing packages is not an easy task given the ever-burgeoning supercomputing ecosystems. In the last decade the landscape of supercomputers has become more complex to maintain low energy consumption and high computing power throughput. To achieve this feat groundbreaking computing chips are used such as GPUs. This hardware comes with specific low-level tools to program it and, as such, requires much expertise when building computing-intensive applications. This thesis is focused on task-based programming models that make the adaptation of the software stack more productive and more resilient to hardware breakthroughs. The sequential task flow (STF) model is given special care as it proposes polished interfaces that has been widely adopted in scientific computing packages executed on shared memory parallel machines. The adoption of this model is more disputable on distributed memory machines; the mechanisms put in place by state-of-the-art scalable algorithms are well-established in low-level programming models such as the message passing interface however they are not transparently supported by the STF model. By reviewing linear algebra scalable algorithms we have identified missing features in STF that are pivotal to obtain scalability by avoiding communications. We have implemented and validated them in the StarPU runtime system that support the STF model. The resulting extended programming model makes it possible to express state-of-the-art scalable algorithms in a portable and compact way. The first one is distributed memory matrixmatrix multiplication for which we deliver a single elegant code that can span multiple algorithmic variants. The second one is matrix decomposition for which our implementation compactly exhibits state-of-the-art designs. These algorithms have been added to the dense routines of the qr_mumps package. A large experimental campaign has been carried out to validate the performance of our implementations. Performance measurements indicate compelling results with regard to other dense linear algebra packages especially on smaller problems typically harder to parallelize or when input matrices dimensions are unbalanced. The flexibility of our implementations was instrumental to enable the use of layouts tailored for symmetric matrix multiplication when the symmetric matrix is the largest one. The resulting operation now performs comparably well to general matrix multiplication while using half the memory.
L'écriture de bibliothèques de calcul haute performance n'est pas une tâche aisée surtout dans des environnements de calcul en perpétuelle évolution. La dernière décennie a vu le paysage des supercalculateurs se complexifier pour maintenir une consommation d'énergie faible et une puissance de calcul élevée. Pour y parvenir des technologies avancées comme les GPU sont mises en oeuvre. Ce matériel peut être programmé à l'aide d'outils bas-niveau et à ce titre une expertise est requise pour développer des applications de calcul intensif. Cette thèse étudie les modèles de programmation à base de tâches rendant l'adaptation logicielle productive et flexible aux innovations matérielles. On s'intéresse en particulier au modèle de programmation séquentiel en flots de tâches (STF) qui propose une interface largement adoptée par la communauté du calcul scientifique dans l'utilisation des machines en mémoire partagée. Cette adoption est cependant moins univoque dans le cadre des machines à mémoire distribuée; les méchanismes mis en place par les algorithmes de l'état de l'art qui passent à l'échelle s'appuyant plus souvent sur des interfaces bas-niveau comme celle proposée par MPI, ils ne sont pas disponibles de manière transparente dans le STF. En passant en revue les algorithmes d'algèbre linéaire qui passent à l'échelle on a pu identifié des fonctionnalités manquantes au modèle qui permettent l'évitement des communications. On a implémenté et validé ces fonctionnalités dans le moteur d'exécution StarPU qui prend en charge le modèle STF. Le modèle étendu qui en résulte rend possible l'expression portable et compacte d'algorithmes de l'état de l'art qui passent à l'échelle. Le premier algorithme d'intérêt est la multiplication de matrices pour laquelle on fournit un unique code élégant qui balaie différentes variantes. Le second est la factorisation de matrice dont notre implémentation expose compactement des choix de conception de l'état de l'art. Ces algorithmes ont été intégrés à la suite de routines denses de qr_mumps. Une campagne expérimentale importante a été mise en place pour valider les gains de performance réalisés. Les résultats indiquent que notre approche est compétitive face à celle mise en place par des bibliothèques de l'état de l'art, en particullier sur des problèmes de petites tailles difficiles à paralléliser ou bien des problèmes pour lesquels les dimensions sont déséquilibrées. La flexibilité de nos implémentations a été déterminante pour permettre l'utilisation de distrbutions de données avancées quand la matrice symmétrique est la plus grande. L'opération qui en résulte est aussi performante que la multiplication de générale tout en utilisant moitié moins de mémoire.
Origine : Version validée par le jury (STAR)