Accélérer les calculs : le défi de la vectorisation

À l’ère où un nombre croissant de domaines d’activité génère des quantités toujours plus grandes de données, il est crucial de disposer de logiciels capables de les traiter efficacement et de manière moins énergivore. Les processeurs jouent un rôle clé dans cette course au rendement. En effet, ils constituent les unités de calcul au cœur de tous nos ordinateurs et smartphones. Afin d’augmenter leur puissance, on peut par exemple accroître la fréquence de fonctionnement. Le processeur effectue alors plus d’opérations en un temps donné. 

Cependant, depuis 2005, les fabricants rencontrent un "mur de fréquence" (limite physique et technique à l’augmentation de la fréquence d’horloge des processeurs). Une des réponses a consisté à placer plusieurs processeurs fonctionnant en parallèle. « Mais un des grands enjeux industriels est de continuer d’augmenter la densité de calculs des processeurs par la vectorisation », explique Charles Paperman, membre de l’équipe-projet Inria Links (Centre Inria de l'Université de Lille), maître de conférence à l’Université de Lille et porteur du projet Shannon meets Cray (SxC). La vectorisation est justement l’objet de ce projet financé par l’Agence nationale de la recherche (ANR), auquel participent plusieurs équipes Inria.

La vectorisation, une technique mathématique imparable

Pour comprendre de quoi il s’agit, imaginez un processeur qui doit effectuer cinq additions de deux nombres. Une possibilité est de faire ces cinq additions les unes à la suite des autres. Cinq cycles du processeur (les spécialistes parlent d’"instructions") sont nécessaires.

Une autre possibilité est de regrouper les chiffres à additionner en deux colonnes (des vecteurs en langage mathématique), puis d’additionner ces colonnes ensemble en une seule instruction. C’est le principe de la vectorisation. Les calculs sont ainsi densifiés et nécessitent moins d’instructions pour le processeur. « Dans les cas idéaux, les accélérations obtenues sont d’un facteur huit », précise Gabriel Radanne, chercheur au sein de l’équipe-projet Cash (centre Inria de Lyon) et engagé dans le projet SxC.

Une méthode héritée des supercalculateurs Cray

Cette technique n’est pas nouvelle, puisqu’elle a été introduite dans les ordinateurs pour la première fois dans les supercalculateurs Cray (du nom de l’ingénieur Seymour Cray) dans les années 1970. « Ces ordinateurs étaient essentiellement destinés au calcul scientifique et ils ont gagné la course au FLOPS, c’est-à-dire à la rapidité de calcul », souligne Charles Paperman. 

Depuis une dizaine d’années, ces architectures vectorielles se sont démocratisées. Elles sont désormais incluses dans les processeurs que nous utilisons, notamment pour le décodage des vidéos. Cependant, certains domaines résistent encore à la vectorisation.

Afin de bénéficier de cette accélération, il faut d’une part que le processeur bénéficie d’une unité consacrée au calcul vectoriel (telles les architectures x86 couramment utilisées). De pair avec cette unité vectorielle, un jeu d’instructions est nécessaire pour donner les consignes au processeur dans un langage qu’il comprend (le langage assembleur, dit de "bas niveau"). 

Enfin, l’algorithme à accélérer, qui est rédigé dans un langage "haut niveau" que les programmeurs manient plus aisément, doit être transformé de façon à utiliser à bon escient les instructions vectorielles.

Mais lorsque l'on s’éloigne de cette structure, cette technique fonctionne moins, voire pas du tout.

Des applications possibles en bio-informatique ou dans le traitement de données

Le projet SxC s’attaque précisément à ce problème:

Un des objectifs du projet est donc de créer un langage de programmation qui donnera des garanties de produire du code vectorisé. Et les applications possibles ne manquent pas... Premières pistes envisagées : la bio-informatique pour l’analyse de séquences ADN, ou encore le traitement de données. Autres domaines potentiellement concernés : la cybersécurité ou l’intelligence artificielle.

Un travail collaboratif d’ampleur entre différents domaines

À cette fin, des chercheurs et chercheuses d’Inria, de l’université de Lille, de l’ENS de Lyon, de Grenoble INP - UGA ou encore de l’université de Bordeaux vont travailler main dans la main. Certains sont spécialistes d’informatique théorique, d’autres des langages de programmation, de synthèse matérielle, ou des applications considérées. 

« Ce sont des communautés de l'informatique très disjointes, qui ont rarement l’habitude de travailler ensemble. C’est un des intérêts du projet », souligne Gabriel Radanne, expert pour sa part des langages de programmation, tandis que Charles Paperman, lui, est familier de la théorie de la complexité de circuits. 

Shannon en renfort

C’est justement de cette théorie de la complexité des circuits, développée par Claude Shannon dans les années 1940, que seront tirés les outils pour surmonter les obstacles à la vectorisation. En amont du projet SxC, Charles Paperman a ainsi participé à l’élaboration d’un algorithme vectorisé "à la main" d’un moteur de requête pour explorer les documents JSON, un format massivement utilisé sur le Web. En tirant parti des outils théoriques de la théorie de la complexité des circuits, cet algorithme permet de gagner de un à deux ordres de grandeur dans l’efficacité d’extraction d’informations.

Sur cette base, le projet vise désormais à construire une "représentation intermédiaire" dont la tâche sera d’effectuer les transformations d’algorithmes nécessaires, mais aussi de répondre à des questions formelles. « Au-delà des applications, plusieurs questions ouvertes fondamentales motivent ce projet. Y a-t-il des programmes qu’on ne peut pas vectoriser ? Quelle est la classe de problèmes qui peuvent l’être ? », illustre Charles Paperman. Un langage de programmation sera aussi conçu pour permettre aux utilisateurs et utilisatrices de s’adresser à cette représentation intermédiaire dans l’écosystème Rust (un langage de programmation largement utilisé). 

Des développements logiciels en open source

Le tout devra aussi s’adapter aux différents jeux d’instructions vectorisés, soit les "chefs d’orchestre" des microprocesseurs. En particulier, un volet du projet est consacré au jeu d’instructions RISC-V.  Contrairement aux jeux d’instructions des constructeurs comme Intel, celui-ci est libre d’utilisation.  Développer et tester des instructions vectorisées pour RISC-V est donc un enjeu de souveraineté numérique à l’échelle nationale et européenne. Par ailleurs, l’intégralité des développements logiciels du projet sera effectuée en open source.

Si le coup d’envoi de Shannon meets Cray a eu lieu en mars dernier, le projet prendra réellement toute son ampleur en septembre prochain, avec le recrutement de plusieurs doctorants. « Tout le monde est dans les starting blocks ! » confie Charles Paperman. Au total, ce projet est prévu pour durer cinq ans. Affaire à suivre…