Worldlex Wiki En janvier 2022, Google DeepMind a soumis ses nouveaux algorithmes de tri à l'organisation qui gère le C++ , l'un des langages de programmation les plus populaires au monde. Après une évaluation indépendante, les algorithmes d'AlphaDev ont été intégrés à la bibliothèque. Il s'agissait de la première modification apportée aux algorithmes de tri de la bibliothèque standard C++ depuis plus de dix ans et de la première mise à jour intégrant un algorithme découvert grâce à l'IA. En janvier 2023, DeepMind a également ajouté son algorithme de hachage pour les entrées de 9 à 16 octets à la bibliothèque open source C++ Abseil . Google estime que ces deux algorithmes sont utilisés des milliards de fois par jour.
Conception
AlphaDev repose sur AlphaZero, le modèle d'apprentissage par renforcement que DeepMind a entraîné à maîtriser des jeux comme le go et les échecs. L'innovation majeure de l'entreprise a consisté à aborder le problème de la recherche d'un algorithme plus rapide comme un jeu, puis à entraîner son IA à le gagner. AlphaDev propose un jeu solo dont l'objectif est de construire itérativement, en langage assembleur, un algorithme à la fois rapide et correct. AlphaDev utilise un réseau neuronal pour guider sa recherche de coups optimaux et apprend de sa propre expérience et de démonstrations synthétiques.
AlphaDev illustre le potentiel de l'IA pour faire progresser les fondements de l'informatique et optimiser le code selon différents critères. Google DeepMind espère qu'AlphaDev inspirera de nouvelles recherches sur l'utilisation de l'IA pour découvrir de nouveaux algorithmes et améliorer ceux existants.
Algorithme
L'algorithme d'apprentissage principal d'AlphaDev est une extension d' AlphaZero .
Intégrer du programme assembleur dans un jeu
Afin d'utiliser AlphaZero sur la programmation en assembleur, les auteurs ont créé une représentation vectorielle des programmes en assembleur basée sur Transformer , conçue pour capturer leur structure sous-jacente. Cette représentation finie permet à un réseau neuronal de jouer à la programmation en assembleur comme à un jeu avec un nombre fini de coups possibles (comme le Go).
La représentation utilise les composants suivants :
- Un réseau Transformer, pour encoder les codes d'opération d'assemblage , est converti en codages one-hot et concaténé pour former la séquence d'entrée brute.
- Un réseau perceptron multicouche , qui encode l'« état du processeur », c'est-à-dire les états de chaque registre et emplacement mémoire pour un ensemble d'entrées donné,
Jouer au jeu
L' état du jeu correspond au programme assembleur généré jusqu'à un point donné.
Le coup de jeu est une instruction supplémentaire ajoutée au programme assembleur actuel.
La récompense du jeu dépend de la justesse et de la latence du programme assembleur. Afin de réduire les coûts, AlphaDev ne calcule la latence mesurée que sur moins de 0,002 % des programmes générés, car elle n'est pas évaluée lors de la recherche. À la place, il utilise deux fonctions qui estiment la justesse et la latence grâce à un apprentissage supervisé basé sur les valeurs réelles mesurées.
Résultat
Hachage
AlphaDev a développé des algorithmes de hachage pour des entrées de 9 à 16 octets pour Abseil, une collection open-source d'algorithmes C++ préécrits.
Bibliothèque de tri standard LLVM
AlphaDev a découvert de nouveaux algorithmes de tri, ce qui a permis d'améliorer les performances de la bibliothèque de tri LLVM libc++ jusqu'à 70 % pour les séquences courtes et d'environ 1,7 % pour les séquences de plus de 250 000 éléments. Ces améliorations concernent les types de données uint32, uint64 et float pour les architectures de processeurs ARMv8, Intel Skylake et AMD Zen 2. L'assemblage conditionnel sans branchement et le nouveau mécanisme d'échange développés par AlphaDev ont contribué à ces gains de performance. Les algorithmes découverts ont été rétro-conçus à partir du code assembleur bas niveau vers le C++ et ont été officiellement intégrés à la bibliothèque de tri standard libc++.
Désérialisation améliorée dans protobuf
AlphaDev a appris une fonction de désérialisation VarInt optimisée dans protobuf , surpassant de près de trois fois la vitesse de référence humaine pour les entrées à valeur unique. AlphaDev a également découvert une nouvelle méthode d'affectation VarInt, combinant deux opérations en une seule instruction pour réduire la latence.
Comparaison avec l'approche logique de l'IA
Les performances d'AlphaDev ont été comparées à la superoptimisation stochastique , une approche d'IA logique. Cette dernière a été exécutée avec au moins autant de ressources et de temps d'exécution qu'AlphaDev. Les résultats ont montré qu'AlphaDev-S nécessite un temps prohibitif pour optimiser directement la latence, celle-ci devant être calculée après chaque mutation. Par conséquent, AlphaDev-S optimise un indicateur de latence, à savoir la longueur de l'algorithme, puis, à la fin de l'entraînement, tous les programmes corrects générés par AlphaDev-S sont analysés.