Solveur linéaire creux exploitant des matrices hierarchiques – SaSHiMi

Aujourd'hui, le nombre de coeurs de calculs dans les supercalculateurs a augmenté considérablement, atteignant plusieurs millions d'unités. Malheureusement, l'évolution de la quantité de mémoire disponible ne suit pas cette tendance, et la quantité de mémoire disponible par unité de calcul décroît. Pour faire face à ce problème, les applications et les bibliothèques de calculs hautes performances doivent non seulement être hautement parallélisables, mais elles doivent également réduire leur consommation mémoire. Dans le domaine de la simulation numérique, la résolution de grands systèmes d'équations linéaires est un problème récurrent, très consommateur de mémoire et qui requiert une grande capacité de calcul. Au cours des dernières années, de nombreux travaux ont étudié l'utilisation de techniques de compression afin de réduire cette consommation mémoire. On peut les classer en trois familles de format: à un niveau (BLR), hiérarchiques avec bases non emboîtées (H et HODLR) et hiérarchiques avec bases emboîtées (H2 et HSS), qui présentent différents niveaux de compressions et sont plus ou moins difficile à mettre en oeuvre. Ces techniques ont été largement étudiées dans le cas dense, mais restent un sujet actif pour les matrices creuses. En particulier, elles ont été étudiées dans le cas de la méthode multifrontale pour réduire le coût des fronts dus à cette méthode ainsi que le temps de résolution. Le projet SaSHiMi souhaite étudier plus particulièrement les méthodes supernodales. Ces méthodes offrent un plus grand parallélisme et sont la seule solution pour réduire efficacement le pic mémoire grâce à l'absence des fronts.

Le projet continuera les travaux préliminaires sur les formats à un niveau (BLR) en passant à des formats hiérarchiques, qui offrent de meilleurs taux de compression et une plus grande réduction des coûts asymptotiques. Les travaux seront réalisés dans la bibliothèque PaStiX qui est implémentée au-dessus de supports d'exécution. Cela permettra une meilleure adaptation à l'irrégularité des noyaux de calcul hiérarchiques. Le solveur sera étudié sur des architectures à mémoire partagée et distribuée et de nouvelles solutions dédiées à la distribution des données et à l'ordonnancement des calculs seront étudiées. Le résultat final sera comparé aux principaux compétiteurs en termes de précision, temps de calcul et consommation mémoire.

La principale difficulté des formats hiérarchiques réside dans la complexité à développer un noyau de mise à jour. Pour faciliter cette opération, et la rendre plus efficace, de nouvelles stratégies de numérotation seront étudiées à l’aide de deux approches. Premièrement, des stratégies seront étudiées pour aligner les séparateurs, calculés lors de la dissection emboîtée, et deuxièmement des stratégies seront étudiées pour regrouper et présélectionner les inconnues de chaque séparateur afin de réduire le nombre de mises à jour et de tentatives de compression.

Les retombées de ce projet seront d'un grand intérêt pour la communauté du calcul scientifique, mais également pour de nombreux autres domaines. Dans ce but, tous les résultats seront diffusés dans des logiciels libres: PaStiX pour la partie solveur et Scotch pour les techniques de numérotation.

Enfin, les résultats de ce projet seront intégrés dans deux classes d'applications pour valider les choix et ouvrir de nouvelles opportunités de recherche. La première classe étudiée sera celle des solveurs hybrides et la seconde sera celle des applications du programme de fusion des plasmas du projet ITER.