L’intelligence artificielle de Google DeepMind optimise les algorithmes de tri

Trier une liste d'éléments est une des fonctions les plus fondamentales dans le traitement d'informations, et le moindre changement dans les algorithmes peut avoir des effets significatifs sur les performances des logiciels. Des chercheurs de chez Google DeepMind ont utilisé l'intelligence artificielle pour optimiser les algorithmes de tri de la bibliothèque libc++ intégrée au compilateur LLVM, qui n'ont pas été modifiés en plus de dix ans, afin de les rendre plus efficaces. Ils ont repris le même principe que pour leurs IA spécialisées dans les jeux comme AlphaGoAlphaGo pour le jeu de Go, AlphaZero pour les échecs et AlphaStar pour StarcraftStarcraft. Ils ont publié leurs résultats dans la revue Nature.

À gauche, une fonction pour trier deux éléments, écrit en C++. À droite, la même fonction une fois compilée en assembleur. © Google DeepMind

Un apprentissage par renforcement profond

Il existe deux approches pour apprendre à une intelligence artificielle à générer du code de programmation. La première est de lui montrer de nombreux exemples écrits par des humains. Toutefois, ceci limite sa créativité car l'IA a tendance à reproduire les approches déjà connues. L'autre est de lancer l'IA sans la moindre connaissance, et de la laisser tâtonner avec toutes les possibilités. C'est cette seconde approche qu'a choisie GoogleGoogle DeepMind.

Les chercheurs ont utilisé l’apprentissage par renforcement profond pour créer leur IA, baptisée AlphaDev. Il existe différentes fonctions de tri dans la bibliothèque libc++, selon le nombre d'éléments à trier (sort2, sort3, sort4, etc.). Ils ont présenté le problème à l'IA sous forme de jeu, et elle devait utiliser l'assembleur, le langage de programmation le plus bas niveau, pour effectuer le tri et recevait des points en fonction de sa réussite et du temps nécessaire pour exécuter la fonction ainsi générée. L'IA est parvenue à réduire le nombre d'instructions pour les opérations de tri comportant deux à huit éléments, sauf pour quatre éléments où l'algorithme de libc++ était déjà optimal.

À gauche, le fonctionnement de l’algorithme pour trier deux, trois ou quatre éléments écrits par des humains. À droite, celui conçu par AlphaDev, qui suit un cheminement inattendu pour trier quatre éléments. © Google DeepMind

Des algorithmes utilisés plusieurs billions de fois par jour

Les chercheurs ont également tenté la même méthode pour des algorithmes avec un nombre d'éléments variables. Par exemple, la fonction pour quatre éléments (VarSort4) peut trier deux, trois ou quatre éléments, en faisant appel à chaque fois à l'algorithme pour le nombre exact. C'est ici qu'ils ont découvert un comportement étonnant. Si la longueur est de deux ou trois éléments, il fait appel aux fonctions sort2 ou sort3 respectivement. Pour quatre éléments, il fait appel à sort3 pour trier les trois premiers éléments, puis à une version simplifiée de sort4 pour insérer le dernier chiffre au bon endroit.

Les chercheurs ont ensuite converti le code des fonctions sort3, sort4 et sort5, écrit en assembleur, en C++. Les algorithmes de libc++ pour les grands nombres d'éléments faisant souvent appel à ceux-ci, les chercheurs les ont donc testés sur différents nombres d'éléments à trier. Une fois fait, ils ont constaté un gain de performances d'environ 70 % pour cinq éléments, ainsi qu'une amélioration de 1,7 % pour les séquences de plus de 250 000 éléments. Les nouveaux algorithmes optimisés par AlphaDev ont été ensuite intégrés dans la bibliothèque libc++, où les chercheurs estiment qu'ils sont appelés plusieurs billions de fois chaque jour.