Vers un solveur tensoriel parallèle rapide à base de tâches pour les problèmes de haute dimension

La décomposition tensor-train (TT) est largement utilisée pour traiter efficacement des données de grande dimension et de faible rang, notamment en analyse de données, en apprentissage automatique et en calcul scientifique ou quantique. Elle fournit des représentations compactes de vecteurs et de matrices dotées d’une structure de rang faible de type produit de Kronecker, permettant d’exécuter des opérations algébriques sous forme compressée. Notre objectif est de construire des solveurs numériques rapides qui opèrent directement sur des matrices et des vecteurs au format TT. À cette fin, cette thèse vise à accélérer deux opérations clés pour des solveurs numériques utilisant de tels vecteurs : le produit scalaire et la recompression de rang. La première est une opération centrale de nombreux algorithmes numériques et revient à une séquence de contractions de tenseurs sur un réseau tensoriel en forme de grille dont l’ordre de contraction influence fortement le coût de calcul. Déterminer un ordre de contraction optimal dans des réseaux tensoriels généraux est un problème NP-difficile ; en conséquence, la plupart des stratégies existantes recourent à des heuristiques, qui se révèlent sous-optimales sur le réseau structuré induit par le produit scalaire TT. Nous présentons donc deux algorithmes efficaces qui calculent des ordres de contraction proches de l’optimal pour de tels réseaux tensoriels issus de produits scalaires de vecteurs au format TT, et nous montrons expérimentalement qu’ils surpassent tous les algorithmes de l’état de l’art pour les réseaux tensoriels généraux tout en restant à quelques pour cent de l’optimum. La meilleure méthode existante entraîne jusqu’à 15% de coût supplémentaire pour les produits scalaires de vecteurs, un coût double pour les produits vecteur-matrice-vecteur, et un coût dix fois supérieur pour les produits vecteur-matrice-matrice-vecteur au format TT. Ensuite, les solveurs numériques requièrent des opérations sur les vecteurs telles que la multiplication matrice-vecteur, l’addition et la mise à l’échelle de vecteurs, ainsi que le produit de Hadamard. Dans le cadre TT, ces opérations induisent, après chaque étape, une croissance artificielle du rang des vecteurs au format TT, augmentant fortement les exigences en calcul et en mémoire. Cet effet peut être maîtrisé en tronquant le rang par recompression, étape critique mais coûteuse d'un solveur fondé sur le format TT. Afin d'accélérer la recompression, nous concevons des algorithmes parallèles à mémoire distribuée à base de tâches, dans lesquels les tenseurs dans le réseau TT sont partitionnés en sous-tenseurs et distribués sur une grille de processeurs. Dans ce modèle, les calculs sont exprimés comme un graphe de tâches interdépendantes, dont les dépendances sont déduites automatiquement des schémas d’accès aux données. Ce paradigme met naturellement en évidence des mécanismes avancés de parallélisme, notamment l’utilisation simultanée de ressources hétérogènes CPU/GPU, une exécution entièrement asynchrone, la priorisation des tâches critiques, ainsi qu’un ordonnancement et un équilibrage de charge sophistiqués fournis par un système d’exécution à base de tâches. Dans nos expériences, nos méthodes passent à l’échelle jusqu’à 2560 cœurs CPU sur un cluster et ces mécanismes fournis par le système d’exécution offrent des gains de performance substantiels qui ne sont pas atteignables avec une parallélisation traditionnelle basée sur MPI, permettant d’atteindre jusqu’à 17,6 fois plus de performances par rapport à l'état de l'art tout en utilisant le même nombre de cœurs CPU. Enfin, nous implémentons des algorithmes de haut niveau parallèles par tâches et des primitives de bas niveau pour matrices et tenseurs dans une bibliothèque C++ de solveurs tensoriels, Celeste, qui s’appuie respectivement sur les bibliothèques StarPU et Chameleon pour l’exécution par tâches et les opérations matricielles, au moyen de couches d’abstraction C++ modernes.