Des algorithmes de tri qui pourraient révolutionner les fondements de l'informatique sont découverts,

Par les chercheurs de Deepmind et Google

Des algorithmes de tri qui pourraient révolutionner les fondements de l'informatique sont découverts,
par les chercheurs de Deepmind et Google

Des algorithmes de tri qui pourraient révolutionner les fondements de l'informatique sont découverts par les chercheurs de Deepmind et Google, les performances des algorithmes découverts ont été comparées avec des algorithmes de tri par insertion, de tri rapide ou de tri introspectif. Les chercheurs montrent comment l’intelligence artificielle peut aller au-delà de l’état de l’art actuel en découvrant des routines inconnues jusqu’à présent. Pour ce faire, ils ont formulé la tâche de trouver une meilleure routine de tri comme un jeu à un seul joueur. Ils ont ensuite entraîné un nouvel agent d’apprentissage par renforcement profond (DRL), AlphaDev, à jouer à ce jeu.

Les chercheurs ont formulé la tâche de trouver un meilleur algorithme de tri comme un jeu à un seul joueur, et ont entraîné un nouvel agent DRL, AlphaDev, à jouer à ce jeu. AlphaDev a découvert à partir de zéro de petits algorithmes de tri qui ont surpassé les références humaines connues. Ces algorithmes ont été intégrés dans la bibliothèque standard C++ LLVM 3. Les auteurs présentent également des résultats dans des domaines supplémentaires, montrant la généralité de l’approche.

Des algorithmes fondamentaux tels que le tri ou le hachage sont utilisés des milliards de fois chaque jour. La demande de calcul augmentant, il est devenu essentiel que ces algorithmes soient aussi performants que possible. Bien que des progrès remarquables aient été réalisés dans le passé, l'amélioration de l'efficacité de ces routines s'est avérée difficile, tant pour les scientifiques que pour les approches informatiques. Les chercheurs montrent comment l'intelligence artificielle peut aller au-delà de l'état actuel de la technique en découvrant des routines jusqu'alors inconnues.


Pour ce faire, ils ont formulé la tâche consistant à trouver une meilleure routine de tri sous la forme d'un jeu à un seul joueur. Ils ont ensuite entraîné un nouvel agent d'apprentissage par renforcement profond, AlphaDev, à jouer ce jeu. AlphaDev a découvert de petits algorithmes de tri à partir de zéro qui ont surpassé les références humaines précédemment connues.

Ces algorithmes ont été intégrés dans la bibliothèque de tri standard C++ de LLVM3. Cette modification de cette partie de la bibliothèque de tri représente le remplacement d'un composant par un algorithme qui a été découvert automatiquement à l'aide de l'apprentissage par renforcement.

AlphaDev utilise une architecture d’apprentissage par renforcement profond basée sur l’acteur-critique, qui apprend une politique (acteur) et une fonction de valeur (critique) à partir d’expériences générées par interaction avec l’environnement. L’environnement est constitué d’un compilateur LLVM et d’un processeur x86-64. L’agent reçoit en entrée une séquence d’entiers à trier et produit en sortie un programme C++ qui implémente un algorithme de tri.

Le programme est compilé et exécuté sur le processeur, et le temps d’exécution est mesuré comme la latence du programme. La récompense est une fonction inversement proportionnelle à la latence, qui encourage l’agent à trouver des programmes plus rapides. L’agent utilise également un mécanisme d’exploration basé sur l’entropie pour encourager la diversité des programmes générés.

Les auteurs ont évalué AlphaDev sur plusieurs tailles de séquences à trier, allant de 4 à 16 éléments. Ils ont comparé les performances des algorithmes découverts par AlphaDev avec celles des algorithmes humains connus, tels que le tri par insertion, le tri rapide ou le tri introspectif. Ils ont constaté qu’AlphaDev était capable de trouver des algorithmes plus rapides que les références humaines pour toutes les tailles de séquences testées.

Par exemple, pour une séquence de 16 éléments, AlphaDev a trouvé un algorithme qui était 11% plus rapide que le tri introspectif, qui est considéré comme l’un des algorithmes de tri les plus efficaces en pratique. Les auteurs ont également testé AlphaDev sur d’autres domaines que le tri, tels que le hachage ou la recherche binaire. Ils ont montré qu’AlphaDev pouvait également trouver des algorithmes plus performants que les références humaines pour ces domaines.

Les chercheurs démontrent que l’intelligence artificielle peut découvrir des algorithmes fondamentaux qui surpassent les connaissances humaines actuelles. Ils soulignent que leur méthode est générale et peut être appliquée à d’autres domaines que le tri ou le hachage. Ils suggèrent également que leur approche pourrait être combinée avec des techniques de synthèse de programmes classiques ou basées sur l’apprentissage profond pour générer des programmes corrects et performants.

L'intuition et le savoir-faire humains ont joué un rôle crucial dans l'amélioration des algorithmes. Cependant, de nombreux algorithmes ont atteint un stade où les experts humains n'ont pas été en mesure de les optimiser davantage, ce qui a conduit à un goulot d'étranglement informatique de plus en plus important. Les travaux de la littérature classique sur la synthèse de programmes, qui s'étendent sur plusieurs décennies, visent à générer des programmes corrects et/ou à optimiser les programmes à l'aide d'indicateurs de latence.

Il s'agit notamment de techniques de recherche énumérative et de recherche stochastique ainsi que de la tendance plus récente consistant à utiliser l'apprentissage profond dans la synthèse de programmes pour générer des programmes corrects. En utilisant l'apprentissage par renforcement profond (DRL), nous pouvons aller plus loin en générant des algorithmes corrects et performants en optimisant la latence réelle mesurée au niveau des instructions du processeur, en recherchant et en considérant plus efficacement l'espace des programmes corrects et rapides par rapport aux travaux antérieurs.

Représentation des algorithmes sous forme d'instructions de l'unité centrale de bas niveau


a. Implémentation en C++ d'une fonction de tri variable 2 qui trie toute séquence d'entrée comportant jusqu'à deux éléments. b. L'implémentation en C++ en a est compilée dans cette représentation équivalente en assembleur de bas niveau.

Lors de la compilation d'algorithmes en code machine à partir d'un langage de haut niveau tel que le C++ (par exemple, la fonction de tri de la figure a ci-dessus), l'algorithme est d'abord compilé en langage assembleur (figure b). L'assembleur convertit ensuite le programme d'assemblage en code machine exécutable.

Dans ce travail, les chercheurs optimisent les algorithmes au niveau de l'assemblage. Dans un programme d'assemblage typique, les valeurs sont copiées de la mémoire vers les registres, manipulées entre les registres, puis réinscrites dans la mémoire. L'ensemble des instructions d'assemblage prises en charge dépend de l'architecture du processeur. Dans le cadre de ce travail, nous les chercheurs se concentrent sur un sous-ensemble d'instructions d'assemblage supportées par l'architecture de processeur x86 utilisant la syntaxe AT&T. Chaque instruction se présente sous la forme Opcode⟨OperandA, OperandB⟩.

Un exemple d'instruction est mov, qui se définit comme le déplacement d'une valeur de la source (A) vers la destination (B). D'autres définitions d'instructions telles que la comparaison (cmp), le déplacement conditionnel (cmovX) et le saut (jX) figurent dans le tableau de données étendu. Dans l'exemple de la figure b, %eax, %ecx, %edx, %edi correspondent à quatre emplacements de registre différents et (%rsi), (%rsi) correspondent à deux emplacements de mémoire différents. Le symbole $2 est un espace réservé pour une valeur constante, qui correspond à la longueur du vecteur dans cet exemple.

Les termes programme d'assemblage et algorithme d'assemblage sont utilisés de manière interchangeable dans ce travail. Ceci est dû au fait qu'AlphaDev construit un programme d'assemblage à partir de zéro, à partir d'un ensemble d'instructions initialement non ordonnées, chaque fois qu'il joue à AssemblyGame, en définissant un nouvel algorithme efficace.

Apprentissage par renforcement profond pour découvrir des algorithmes plus rapides


a, AssemblyGame est joué par AlphaDev, qui reçoit en entrée l'algorithme d'assemblage courant généré jusqu'à présent St et joue le jeu en sélectionnant une action à exécuter. Dans cet exemple, l'action est une instruction d'assemblage mov<Register0,Memory1>, qui est ajoutée à l'algorithme actuel. L'agent reçoit une récompense qui est fonction de la correction de l'algorithme, discutée en b, ainsi que de la latence de l'algorithme. Le jeu est remporté par le joueur qui découvre un algorithme correct et à faible latence. b) Les calculs de correction et de latence du programme sont utilisés pour calculer la récompense rt. Dans cet exemple, des séquences de test sont introduites dans l'algorithme ; par exemple, dans le cas du tri de trois éléments, les entrées de test comprennent toutes les séquences d'éléments non triés de longueur 3. Pour chaque séquence, la sortie de l'algorithme est comparée à la sortie attendue (dans le cas du tri, la sortie attendue est constituée par les éléments triés). Dans cet exemple, la sortie D′ ne correspond pas à la sortie attendue B′ et l'algorithme est donc incorrect.

L'optimisation des algorithmes au niveau des instructions du processeur est formulée comme un problème d'apprentissage par renforcement, dans lequel l'environnement est modélisé comme un jeu à un seul joueur que nous appelons AssemblyGame. Chaque état dans ce jeu est défini comme un vecteur St = ⟨Pt, Zt⟩ où Pt est une représentation de l'algorithme généré jusqu'à présent dans le jeu et Zt représente l'état de la mémoire et des registres après l'exécution de l'algorithme actuel sur un ensemble d'entrées prédéfinies. Comme le montre la figure a ci-dessus 2, à l'étape t, le joueur reçoit l'état actuel St et exécute une action at.

Cette action consiste à ajouter une instruction d'assemblage légale (par exemple, mov<A,B>) à l'algorithme actuel généré jusqu'à présent. Le joueur reçoit une récompense r qui comprend à la fois une mesure de l'exactitude de l'algorithme et du temps de latence. L'exactitude de l'algorithme (figure b ci-dessus) implique l'entrée d'un ensemble de N séquences de test dans l'algorithme actuel Pt pour générer N sorties. Ces résultats sont ensuite comparés aux résultats attendus et une récompense de correction rt est calculée.

Les récompenses pour la latence peuvent être générées soit en pénalisant l'agent pour avoir augmenté la longueur de l'algorithme (lorsque la longueur et la latence sont fortement corrélées), ce que nous appelons la récompense pour la longueur de l'algorithme, soit en mesurant la latence réelle de l'algorithme. Le jeu est exécuté pendant un nombre limité d'étapes, après quoi il est terminé. Gagner le jeu correspond à la génération d'un algorithme correct et à faible latence à l'aide d'instructions d'assemblage. Perdre le jeu correspond à la génération d'un algorithme incorrect ou d'un algorithme...