AlphaDev découvre des algorithmes de tri plus rapides

Dans un monde où la demande en calcul et en énergie ne cesse de croître, il est essentiel d'améliorer le code qui fait fonctionner nos microprocesseurs pour rendre l'informatique plus puissante et durable. C'est dans ce contexte que DeepMind présente AlphaDev, un système d'intelligence artificielle (IA) qui utilise l'apprentissage par renforcement pour découvrir des algorithmes informatiques améliorés, surpassant ceux affinés par les scientifiques et les ingénieurs au fil des décennies.

Illustration du fonctionnement d'un algorithme de tri. Une série de nombres non triés est introduite dans l'algorithme et des nombres triés en sortent.

AlphaDev : une IA pour optimiser les algorithmes

AlphaDev est un système d'IA basé sur AlphaZero, le modèle d'apprentissage par renforcement de DeepMind qui a battu les champions du monde dans des jeux comme le Go, les échecs et le shogi. Avec AlphaDev, DeepMind montre comment ce modèle peut passer des jeux aux défis scientifiques, et des simulations aux applications réelles.

Pour entraîner AlphaDev à découvrir de nouveaux algorithmes, DeepMind a transformé le tri en un "jeu d'assemblage" à un seul joueur. À chaque tour, AlphaDev observe l'algorithme qu'il a généré et les informations contenues dans l'unité centrale de traitement (CPU). Il joue ensuite un coup en choisissant une instruction à ajouter à l'algorithme.

Découverte de nouveaux algorithmes de tri

AlphaDev a découvert de nouveaux algorithmes de tri qui ont conduit à des améliorations dans la bibliothèque de tri libc++ de LLVM, jusqu'à 70% plus rapide pour les séquences plus courtes et environ 1,7% plus rapide pour les séquences dépassant 250 000 éléments.

DeepMind s'est concentré sur l'amélioration des algorithmes de tri pour des séquences plus courtes de trois à cinq éléments. Ces algorithmes sont parmi les plus utilisés car ils sont souvent appelés de nombreuses fois dans le cadre de fonctions de tri plus grandes. L'amélioration de ces algorithmes peut conduire à une accélération globale pour le tri de n'importe quel nombre d'éléments.

Le code est généralement écrit dans un langage de programmation de haut niveau tel que le C++. Il est ensuite traduit en instructions de bas niveau pour l'unité centrale, appelées instructions d'assemblage, à l'aide d'un compilateur. Un assembleur convertit ensuite les instructions d'assemblage en code machine exécutable que l'ordinateur peut exécuter.

Figure A : Un exemple d'algorithme C++ qui trie jusqu'à deux éléments. Figure B : Représentation en assembleur du code correspondant.

Des approches novatrices

AlphaDev n'a pas seulement trouvé des algorithmes plus rapides, mais a également découvert des approches novatrices. Ses algorithmes de tri contiennent de nouvelles séquences d'instructions qui économisent une seule instruction chaque fois qu'elles sont appliquées. Cela peut avoir un impact énorme car ces algorithmes sont utilisés des billions de fois par jour.

DeepMind appelle ces "mouvements de copie et d'échange AlphaDev". Cette approche novatrice rappelle le "coup 37" d'AlphaGo - un jeu contre-intuitif qui a stupéfié les spectateurs et conduit à la défaite d'un joueur légendaire de Go. Avec le mouvement de copie et d'échange, AlphaDev saute une étape pour connecter les éléments d'une manière qui ressemble à une erreur mais qui est en fait un raccourci. Cela démontre la capacité d'AlphaDev à découvrir des solutions originales et remet en question notre façon de penser l'amélioration des algorithmes informatiques.

Figure A : Le jeu d'assemblage. Le joueur, AlphaDev, reçoit l'état du système st en entrée et joue un coup en sélectionnant une instruction d'assemblage à ajouter à l'algorithme qui a été généré jusqu'à présent. Figure B : Le calcul de la récompense. Après chaque coup, l'algorithme généré est alimenté en séquences d'entrée de test - pour sort3, cela correspond à toutes les combinaisons de séquences de trois éléments. L'algorithme génère ensuite une sortie, qui est comparée à la sortie attendue des séquences triées dans le cas du tri. L'agent est récompensé en fonction de la correction et de la latence de l'algorithme.Translated with DeepL

Du tri au hachage dans les structures de données

Après avoir découvert des algorithmes de tri plus rapides, DeepMind a décidé d'appliquer AlphaDev à d'autres problèmes d'algorithmique. L'un des domaines qu'ils ont explorés est le hachage dans les structures de données. Le hachage est une technique utilisée pour accélérer l'accès aux données dans les structures de données, comme les tableaux de hachage.

En utilisant AlphaDev, DeepMind a pu découvrir de nouvelles fonctions de hachage qui améliorent les performances de ces structures de données. Ces nouvelles fonctions de hachage ont permis d'accélérer l'accès aux données, ce qui a un impact direct sur la vitesse d'exécution des programmes qui utilisent ces structures de données.

Gauche : L'implémentation originale de sort3 avec min(A,B,C). Droite : AlphaDev Swap Move - AlphaDev découvre que vous n'avez besoin que de min(A,B).

Conclusion

La découverte par AlphaDev de nouveaux algorithmes de tri et de nouvelles fonctions de hachage montre le potentiel de l'IA pour améliorer l'efficacité de nos systèmes informatiques. En utilisant l'apprentissage par renforcement, AlphaDev a pu découvrir des solutions qui surpassent celles développées par des humains au fil des décennies. Cela ouvre la voie à de nouvelles avancées dans le domaine de l'optimisation des algorithmes, avec des implications potentielles pour une large gamme d'applications, de l'informatique haute performance à l'informatique de bureau.

Source : Nature

Faster sorting algorithms discovered using deep reinforcement learning - Nature

 Artificial intelligence goes beyond the current state of the art by discovering unknown, faster sorting algorithms as a single-player game using a deep reinforcement learning agent. These algorithms are now used in the standard C++ sort library.

NatureDaniel J. Mankowitz