Exemple SpMM (C <sub>m,n</sub> = A <sub>m,k </sub> ∗ B <sub>k,n</sub> ) et différents formats creux pour la matrice A : COO, ELL et CSR. Crédit : arXiv (2025). DOI : 10.48550/arxiv.2510.17505
La multiplication de matrices et de tableaux de dimension supérieure appelés tenseurs est au cœur de l’informatique moderne. La multiplication de matrices ou de tenseurs est en effet l’opération la plus courante dans les applications d’intelligence artificielle, ainsi que dans les simulations scientifiques et l’infographie. Les ordinateurs à hautes performances, notamment ceux équipés d’unités de traitement graphique (GPU), sont conçus pour traiter des matrices ou des tenseurs dits denses, c’est-à-dire ceux qui contiennent relativement peu d’éléments nuls.
Le fait que des machines de pointe soient conçues pour fonctionner de cette manière a engendré un problème inattendu, selon Saman Amarasinghe, professeur Thomas et Gerd Perkins de génie électrique et d’informatique (EECS) au MIT et chercheur principal au Laboratoire d’informatique et d’intelligence artificielle (CSAIL). « Le problème, c’est que le monde est caractérisé par une grande rareté des données. »
Cela se traduit par des tableaux contenant une grande quantité de zéros, comparables, par exemple, aux images de la lune sur un ciel uniformément sombre. Parmi le million de pixels environ qui composent une photo haute résolution de ce type, la majorité peut se voir attribuer la valeur zéro, ce qui signifie qu’ils ne transmettent aucune information visuelle utile.
En stockant tous ces zéros, les tableaux creux peuvent gaspiller beaucoup de mémoire. Et pour des opérations comme la multiplication, « on finit par effectuer de nombreux calculs inutiles car, comme presque tous les écoliers le savent, zéro multiplié par n’importe quel nombre donne zéro », explique Joel Emer, professeur au MIT, chercheur principal au CSAIL et chercheur émérite chez NVIDIA.
Combler une lacune dans le calcul clairsemé
Un article présenté en mars dernier à la conférence APLOS ’26 à Princeton, co-écrit par Jaeyeon Won, doctorante au CSAIL, et Willow Ahrens, professeure adjointe au Georgia Institute of Technology, en collaboration avec Emer et Amarasinghe, introduit de nouvelles techniques pour améliorer l’efficacité des calculs impliquant des tableaux clairsemés. Cette étude est disponible sur le serveur de prépublications arXiv .
En 2017, Amarasinghe et quatre collègues ont créé TACO (Tensor Algebra Compiler), un compilateur informatique qui convertit du code en un format exécutable. Neuf ans plus tard, TACO reste le meilleur compilateur disponible pour les opérations entre deux tableaux creux. « Mais lorsqu’il s’agit de multiplier un tableau creux par un tableau dense, TACO est beaucoup moins performant », explique Won. Leurs nouveaux travaux, présentés à APLOS ’26, « visent à combler cette lacune », ajoute-t-il. « Nous nous concentrons spécifiquement sur les calculs impliquant des tenseurs ou des matrices creux et denses. »
Du code concis au travail gaspillé
Pour comprendre leur démarche, un bon point de départ consiste à examiner le code informatique de multiplication de matrices et de tenseurs appelé Einsum, qui emprunte à la notation mathématique des opérations tensorielles utilisée par Albert Einstein il y a plus d’un siècle pour formuler sa théorie de la gravitation. Selon Won, l’un des avantages des Einsums est leur clarté et leur concision. Le programme nécessite moins de lignes de code.
« Les sommes d’Einstein ne sont pas seulement une manière concise de décrire les calculs d’algèbre linéaire », explique Emer, « elles sont également précises, fournissant des spécifications complètes sur ce que vous devez faire. » Par analogie, imaginez que vous prépariez un gâteau où l’ordre dans lequel vous mélangez les ingrédients n’a pas d’importance.
Une recette complète pourrait indiquer : « Ajoutez 1 œuf, puis 240 ml d’eau et 57 g de beurre. Incorporez ensuite 470 ml de farine et 120 ml de sucre. Préchauffez le four à 177 °C et faites cuire pendant 30 minutes. »
Tandis que la recette Einsum serait plus concise : 1 œuf, 240 ml d’eau, 57 g de beurre, 470 ml de farine, 120 ml de sucre. Cuire 30 minutes à 177 °C. « Comme une recette Einsum », dit Emer, « qui vous dit tout ce qu’il faut savoir. »
Malgré les avantages des Einsums, un inconvénient potentiel subsiste : elles ne permettent pas de suivre l’emplacement des zéros dans le tableau, ce qui peut engendrer des calculs inutiles et superflus. C’est là que l’équipe du MIT a réalisé une innovation majeure : elle a conçu une méthode pour réécrire l’Einsum sous une forme différente, qu’elle appelle Einsum indirecte ou Insum.
Le terme « indirecte » indique qu’il ne s’agit pas d’utiliser l’Einsum directement ; une étape supplémentaire est ajoutée au protocole par sa conversion. L’Insum résultant de cette transformation, contrairement à une Einsum classique, connaît l’emplacement de tous les zéros et peut ainsi éviter les calculs inutiles.
En réalité, il se peut qu’il n’y ait aucun zéro à gérer, car le tableau lui-même a pu être « compressé » dans un format différent : reconfiguré en un tableau plus petit, débarrassé de tous les zéros. Toutefois, les informations relatives aux positions, ou coordonnées, d’origine des éléments non nuls doivent être conservées. La fonction Insum comprend ce nouveau format, c’est-à-dire la manière modifiée dont les données sont stockées. Et cela aussi peut faciliter des opérations plus efficaces.
Éviter les sièges vides
Pour illustrer ce point, Won propose un exemple simple : imaginez que vous donniez un cours magistral à 100 étudiants, chacun assis à une place numérotée de 1 à 100. Vous devez faire l’appel chaque jour, en appelant un par un les étudiants de chaque place et en attendant leur réponse « présent ». Si vous savez à l’avance que 55 étudiants sont en sortie scolaire, vous gagnerez un temps précieux en n’appelant que les noms des étudiants absents.
Insums exploite ce type d’informations, ce qui peut considérablement simplifier les calculs. En effet, l’équipe a démontré expérimentalement que le compilateur Insums leur permettait d’accélérer les applications GPU éparses, parfois d’un facteur proche de 4. Ils ont également réduit le nombre de lignes de code nécessaires à l’implémentation de ces opérations d’un facteur allant de 200 à 4 500.
Des cas plus difficiles nous attendent.
« Étant donné que les ordinateurs actuels sont très performants pour les calculs complexes, une forte proportion de zéros est nécessaire pour que cette conversion [d’une somme d’Einsum standard vers une somme d’Einsum indirecte] soit pertinente », explique Emer. Ce processus est complexe et, pour l’instant, il doit être réalisé manuellement, chaque étape étant consignée par écrit. « L’automatisation de ce processus fait partie des travaux en cours », ajoute Emer.
La conversion en Insums devient une procédure beaucoup plus complexe lorsqu’on multiplie deux tableaux creux. Emer et Amarasinghe collaborent actuellement avec Ahrens et un étudiant de Georgia Tech afin d’améliorer la gestion des opérations entre tableaux creux par tableaux creux par Insums.
Alors même que le groupe poursuit ces améliorations et d’autres encore, Jason Ansel, informaticien chez Meta, est déjà impressionné par les résultats obtenus. « Les calculs épars dans les réseaux neuronaux graphiques et les simulations scientifiques sont notoirement difficiles à exécuter efficacement sur les GPU modernes », commente Ansel. « Insum résout ce problème en permettant une exécution plus rapide avec beaucoup moins de code. Cela représente une avancée importante vers l’obtention de hautes performances GPU pour un plus large éventail de charges de travail éparses. »
https://www.csail.mit.edu/news/new-way-speed-sparse-computations
