Algorithmes de tri plus rapides découverts à l'aide de l'apprentissage par renforcement profond

Nature volume 618, pages 257–263 (2023)Citer cet article

88 000 accès

794 Altmétrique

Détails des métriques

Les algorithmes fondamentaux tels que le tri ou le hachage sont utilisés des milliards de fois chaque jour1. À mesure que la demande de calcul augmente, il est devenu essentiel que ces algorithmes soient aussi performants que possible. Alors que des progrès remarquables ont été réalisés dans le passé2, l'amélioration de l'efficacité de ces routines s'est avérée difficile tant pour les scientifiques humains que pour les approches informatiques. Nous montrons ici comment l'intelligence artificielle peut aller au-delà de l'état actuel de l'art en découvrant des routines jusqu'alors inconnues. Pour réaliser cela, nous avons formulé la tâche de trouver une meilleure routine de tri en tant que jeu solo. Nous avons ensuite formé un nouvel agent d'apprentissage par renforcement profond, AlphaDev, pour jouer à ce jeu. AlphaDev a découvert de toutes pièces de petits algorithmes de tri qui surpassaient les benchmarks humains connus auparavant. Ces algorithmes ont été intégrés dans la bibliothèque de tri C++ standard LLVM3. Cette modification apportée à cette partie de la bibliothèque de tri représente le remplacement d'un composant par un algorithme qui a été automatiquement découvert à l'aide de l'apprentissage par renforcement. Nous présentons également des résultats dans des domaines supplémentaires, mettant en évidence la généralité de l'approche.

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 entraîne un goulot d'étranglement informatique de plus en plus important. Le travail dans la littérature de synthèse de programme classique, s'étendant sur plusieurs décennies, vise à générer des programmes corrects et/ou à optimiser des programmes en utilisant des proxies pour la latence. Celles-ci incluent les techniques de recherche énumérative4,5,6,7 et la recherche stochastique5,6,8,9,10 ainsi que la tendance plus récente à utiliser l'apprentissage en profondeur dans la synthèse de programmes pour générer des programmes corrects11,12,13,14,15,16 . 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 précédents. .

L'une des questions fondamentales en informatique est de savoir comment trier une séquence17,18,19,20. Ceci est enseigné dans les cours élémentaires d'informatique du monde entier21,22 et est utilisé de manière omniprésente par une vaste gamme d'applications23,24,25. Des décennies de recherche en informatique se sont concentrées sur la découverte et l'optimisation des algorithmes de tri26,27,28. Un élément clé des solutions pratiques est un petit tri sur une courte séquence d'éléments; cet algorithme est appelé à plusieurs reprises lors du tri de grands tableaux qui utilisent des approches diviser pour régner29. Dans ce travail, nous nous concentrons sur deux types d'algorithmes de petit tri : (1) le tri fixe et (2) le tri variable. Les algorithmes de tri fixe trient des séquences de longueur fixe (par exemple, le tri 3 ne peut trier que des séquences de longueur 3), tandis que les algorithmes de tri variable peuvent trier une séquence de taille variable (par exemple, le tri variable 5 peut trier des séquences allant de un à cinq éléments).

Nous formulons le problème de la découverte de nouveaux algorithmes de tri efficaces sous la forme d'un jeu à un joueur que nous appelons AssemblyGame. Dans ce jeu, le joueur sélectionne une série d'instructions CPU de bas niveau, que nous appelons instructions d'assemblage30, à combiner pour produire un nouvel algorithme de tri efficace. C'est un défi car le joueur doit prendre en compte l'espace combinatoire des instructions d'assemblage pour produire un algorithme à la fois correct et rapide. La dureté de l'AssemblyGame provient non seulement de la taille de l'espace de recherche, qui est similaire à des jeux extrêmement difficiles tels que les échecs (10120 parties)31 et Go (10700 parties)32, mais aussi de la nature de la fonction de récompense. Une seule instruction incorrecte dans AssemblyGame peut potentiellement invalider l'ensemble de l'algorithme, rendant l'exploration dans cet espace de jeux incroyablement difficile.

Pour jouer au jeu, nous introduisons AlphaDev, un agent d'apprentissage qui est formé pour rechercher des algorithmes corrects et efficaces. Cet agent est composé de deux composants principaux, à savoir (1) un algorithme d'apprentissage et (2) une fonction de représentation. L'algorithme d'apprentissage AlphaDev peut incorporer à la fois des algorithmes DRL et d'optimisation de recherche stochastique pour jouer à AssemblyGame. L'algorithme d'apprentissage principal d'AlphaDev est une extension d'AlphaZero33, un algorithme DRL bien connu, dans lequel un réseau de neurones est formé pour guider une recherche pour résoudre AssemblyGame. La fonction de représentation est interchangeable et capture la structure sous-jacente des programmes d'assemblage. La représentation primaire d'AlphaDev est basée sur Transformers34.

En utilisant AlphaDev, nous avons découvert de toutes pièces des algorithmes de tri fixes et variables qui sont à la fois nouveaux et plus efficaces que les benchmarks humains de pointe. Les solutions de tri fixes pour le tri 3, le tri 4 et le tri 5 découvertes par AlphaDev ont été intégrées dans la fonction de tri standard de la bibliothèque C++ standard LLVM3. Cette bibliothèque est utilisée par plusieurs millions d'utilisateurs dont des universités et de nombreuses entreprises internationales35. De plus, nous analysons les découvertes de nouveaux algorithmes, comparons AlphaDev aux approches d'optimisation de recherche stochastique et appliquons AlphaDev à d'autres domaines pour montrer la généralité de l'approche.

Lors de la compilation d'algorithmes en code machine à partir d'un langage de haut niveau tel que C++ (par exemple, la fonction de tri de la Fig. 1a), l'algorithme est d'abord compilé en assembleur (Fig. 1b). L'assembleur convertit ensuite le programme d'assemblage en code machine exécutable. Dans ce travail, nous optimisons les algorithmes au niveau de l'assemblage30. Dans un programme d'assemblage typique, les valeurs sont copiées de la mémoire dans des registres, manipulées entre les registres puis réécrites dans la mémoire. Le jeu d'instructions d'assemblage pris en charge dépend de l'architecture du processeur. Pour les besoins de ce travail, nous nous concentrons sur un sous-ensemble d'instructions d'assemblage prises en charge par l'architecture de processeur x86 utilisant la syntaxe AT&T36. Chaque instruction est au format Opcode⟨OpérandeA, OpérandeB⟩. Un exemple d'instruction est mov, qui est défini comme déplacer une valeur de la source (A) à la destination (B). D'autres définitions d'instructions telles que la comparaison (cmp), le déplacement conditionnel (cmovX) et le saut (jX) peuvent être trouvées dans le tableau de données étendu 1. Dans l'exemple de la Fig. 1b, %eax, %ecx, %edx, %edi correspondent à quatre emplacements de registre différents et (%rsi), 4(%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. Nous utilisons indifféremment les termes programme d'assemblage et algorithme d'assemblage dans ce travail. En effet, 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, définissant un nouvel algorithme efficace.

a, Une implémentation C++ d'une fonction de tri variable 2 qui trie toute séquence d'entrée de deux éléments maximum. b, L'implémentation C++ dans a est compilée dans cette représentation d'assemblage de bas niveau équivalente.

Dans cette section, nous formulons des algorithmes d'optimisation au niveau des instructions CPU comme un problème d'apprentissage par renforcement (RL)37, dans lequel l'environnement est modélisé comme un jeu à un joueur que nous appelons AssemblyGame. Chaque état de 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 de paramètres prédéfinis. contributions. Comme le montre la figure 2a, au pas de temps t, le joueur reçoit l'état actuel St et exécute une action à. Cela implique d'ajouter une instruction d'assemblage légale (par exemple, mov) à l'algorithme actuel généré jusqu'à présent. Une récompense reçue comprend à la fois une mesure de l'exactitude et de la latence de l'algorithme. L'exactitude de l'algorithme (Fig. 2b) 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 sorties sont ensuite comparées aux sorties attendues et une récompense d'exactitude rt est calculée. Les récompenses de latence peuvent être générées soit (1) en pénalisant l'agent pour avoir augmenté la longueur de l'algorithme (lorsque la longueur et la latence sont fortement corrélées) que nous appelons la récompense de longueur de l'algorithme, soit (2) en mesurant la latence réelle de l'algorithme . Le jeu est exécuté pendant un nombre limité d'étapes, après quoi le jeu est terminé. Gagner le jeu correspond à générer un algorithme correct et à faible latence à l'aide d'instructions d'assemblage. Perdre la partie correspond à générer un algorithme incorrect ou un algorithme correct mais inefficace.

a, The AssemblyGame est joué par AlphaDev, qui reçoit en entrée l'algorithme d'assemblage actuel généré jusqu'ici St et joue le jeu en sélectionnant une action à exécuter. Dans cet exemple, l'action est une instruction d'assemblage mov, qui est ajoutée à l'algorithme actuel. L'agent reçoit une récompense qui est fonction de l'exactitude de l'algorithme, discutée en b, ainsi que de la latence de l'algorithme. La partie est gagnée si le joueur découvre un algorithme correct à faible latence. b, Les calculs d'exactitude et de latence du programme sont utilisés pour calculer la récompense rt. Dans cet exemple, des séquences de test sont entrées 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 les éléments triés ). Dans cet exemple, la sortie ${\bf{D}}{\boldsymbol{{\prime} }}$ ne correspond pas à la sortie attendue ${\bf{B}}{\boldsymbol{{\prime} }}$ et l'algorithme est donc incorrect.

Nous appelons AlphaDev l'agent qui joue à ce jeu solo. L'algorithme d'apprentissage principal de l'agent est une extension de l'agent AlphaZero32 et guide une procédure de planification de recherche arborescente Monte Carlo (MCTS) à l'aide d'un réseau neuronal profond33,38. L'entrée du réseau neuronal est l'état St et la sortie est une prédiction de politique et de valeur. La prédiction de la politique est une distribution sur les actions et la fonction de valeur est une prédiction des rendements cumulés R que l'agent devrait s'attendre à recevoir de l'état actuel St. Au cours d'un jeu, l'agent reçoit en entrée l'état actuel St. L'agent alors exécute une procédure MCTS et l'utilise pour sélectionner la prochaine action à entreprendre. Les jeux générés sont ensuite utilisés pour mettre à jour les paramètres du réseau, permettant à l'agent d'apprendre.

Il est essentiel qu'AlphaDev dispose d'une représentation39,40 capable de représenter des structures algorithmiques complexes pour explorer efficacement l'espace des instructions. Pour ce faire, nous introduisons le réseau de représentation AlphaDev (Extended Data Fig. 1a). Ce réseau comprend deux composants, à savoir (1) un réseau d'encodeur de transformateur qui fournit à l'agent une représentation de la structure de l'algorithme, et (2) le réseau d'encodeur d'état du CPU qui aide l'agent à prédire comment l'algorithme affecte la dynamique de la mémoire et des registres. . Le réseau de codeur d'état CPU comprend un perceptron multicouche qui reçoit en entrée l'état de chaque registre et emplacement mémoire pour un ensemble d'entrées donné. Ces réseaux produisent chacun des plongements qui sont combinés pour donner la représentation d'état AlphaDev.

Les transformateurs sont des encodeurs de texte naturels et ont récemment eu beaucoup de succès avec les modèles de langage14,34,41. Cela nous a donc motivés à adapter le transformateur standard aux instructions de montage du modèle. Nous avons développé et incorporé un encodeur de transformateur, notre adaptation de l'encodeur de transformateur MultiQuery42, dans le réseau de représentation AlphaDev pour représenter les instructions d'assemblage. L'opcode de chaque instruction d'assemblage et les opérandes correspondants sont convertis en encodages à chaud et concaténés pour former la séquence d'entrée brute. Celui-ci est alimenté par un encodeur de transformateur multicouche, qui le mappe aux vecteurs d'intégration correspondants (voir Données étendues Fig. 1b pour une illustration).

La latence est un signal de récompense important qui est utilisé pour guider l'agent dans la découverte d'algorithmes performants. Pour mieux estimer la latence, nous avons implémenté une configuration de fonction à double valeur, dans laquelle AlphaDev a deux têtes de fonction de valeur : l'une prédisant l'exactitude de l'algorithme et la seconde prédisant la latence de l'algorithme. La tête de latence est utilisée pour prédire directement la latence d'un programme donné en utilisant la latence calculée réelle du programme comme cible de Monte Carlo pour AlphaDev pendant la formation. Cette approche à deux têtes a obtenu des résultats nettement meilleurs que la configuration de la fonction vanille à une seule tête lors de l'optimisation pour une latence réelle.

Nous avons formé l'agent AlphaDev à partir de zéro pour générer une gamme d'algorithmes de tri fixe et de tri variable qui sont à la fois corrects et atteignent une latence inférieure à celle des références humaines de pointe.

Nous avons considéré trois algorithmes fondamentaux : tri 3, tri 4 et tri 5. Les références humaines de pointe pour ces algorithmes sont les réseaux de tri43 car ils génèrent un code d'assemblage conditionnel sans branche efficace. Cela signifie que toutes les instructions sont exécutées séquentiellement et qu'il n'y a pas de branchement impliqué. L'amélioration de ces algorithmes est un défi car ils sont déjà hautement optimisés. Comme on le voit dans le tableau 1a, AlphaDev est capable de trouver des algorithmes avec moins d'instructions que les benchmarks humains pour le tri 3 et le tri 5 et correspond aux performances de pointe sur le tri 4. Ces algorithmes plus courts conduisent en effet à une latence plus faible car la longueur et la latence de l'algorithme sont corrélées pour le cas conditionnel sans branche ; voir l'annexe B dans les informations supplémentaires pour plus de détails. Nous avons également exploré la mise à l'échelle vers des types légèrement plus grands en utilisant une variante d'AlphaDev. Nous avons réussi à enregistrer trois instructions sur le tri 6, deux instructions sur le tri 7 et une instruction sur le tri 8, ce qui fournit une base prometteuse pour les travaux futurs. Voir l'annexe C dans les informations supplémentaires pour un aperçu de l'approche.

Nous avons considéré trois algorithmes de tri de variables : VarSort3, VarSort4 et VarSort5. La référence humaine dans chaque cas est définie comme un algorithme qui, pour une longueur d'entrée donnée, appelle le réseau de tri correspondant. Dans ce cas, un branchement est nécessaire, ce qui augmente considérablement la complexité du problème car l'agent doit (1) déterminer le nombre de sous-algorithmes dont il a besoin pour construire et (2) construire le corps de l'algorithme principal en parallèle. L'agent peut également avoir besoin d'appeler des sous-algorithmes à partir d'autres sous-algorithmes. Dans ce cas, l'optimisation de la longueur conduit à des algorithmes nettement plus courts par rapport aux repères humains, comme le montre le tableau 1a. Cependant, en raison des complexités introduites par le branchement, la latence et la longueur ne sont pas toujours corrélées ; voir Informations supplémentaires pour plus de détails. En tant que tel, nous avons mis en œuvre une procédure qui mesure la latence réelle des programmes en prenant le cinquième centile des mesures de latence sur 100 machines différentes, avec des intervalles de confiance calculés44, et optimisons cette métrique. Voir Méthodes pour la configuration complète de l'analyse comparative. Lors de l'optimisation de la latence, l'agent améliore considérablement les repères humains dans chaque cas, comme le montre le tableau 1b.

Les solutions découvertes par AlphaDev incluent de nouvelles découvertes algorithmiques passionnantes qui conduisent à des performances plus efficaces. Dans le cadre du tri fixe, nous avons constaté qu'AlphaDev a découvert deux séquences d'instructions intéressantes qui, lorsqu'elles sont appliquées à un algorithme de réseau de tri, réduisent l'algorithme d'une instruction d'assemblage à chaque fois. Nous appelons chaque séquence d'instructions (1) le mouvement d'échange AlphaDev et (2) le mouvement de copie AlphaDev respectivement.

La figure 3a présente un réseau de tri optimal pour trois éléments (voir Méthodes pour un aperçu des réseaux de tri). Nous expliquerons comment AlphaDev a amélioré le segment de réseau encerclé. Il existe de nombreuses variantes de cette structure que l'on retrouve dans les réseaux de tri de différentes tailles, et le même argument s'applique dans chaque cas. La partie encerclée du réseau (deux derniers comparateurs) peut être vue comme une séquence d'instructions qui prend une séquence d'entrée ⟨A, B, C⟩ et transforme chaque entrée comme indiqué dans le tableau 2a (à gauche). Cependant, un comparateur sur les fils B et C précède cet opérateur et donc des séquences d'entrée où B ≤ C sont garanties. Cela signifie qu'il suffit de calculer min(A, B) comme première sortie au lieu de min(A, B, C) comme indiqué dans le tableau 2a (à droite). La différence de pseudocode entre les Fig. 3b,c montre comment le mouvement d'échange AlphaDev enregistre une instruction à chaque fois qu'il est appliqué.

a, Un réseau de tri classique optimal pour trois entrées. Les comparateurs cerclés ont été améliorés par AlphaDev. Voir le mouvement d'échange d'AlphaDev pour plus de détails. b,c, Le pseudocode d'assemblage avant l'application du mouvement d'échange AlphaDev (b) et après l'application du mouvement d'échange AlphaDev (c), entraînant la suppression d'une seule instruction. d, Une configuration optimale de comparateur de réseau de tri classique qui a été améliorée par AlphaDev. Voir le mouvement de copie AlphaDev pour plus de détails. e,f, Le pseudocode d'assemblage avant l'application du mouvement de copie AlphaDev (e) et après l'application du mouvement de copie AlphaDev (f), entraînant la suppression d'une seule instruction.

La figure 3d présente une configuration de réseau de tri, composée de trois comparateurs, qui est appliquée sur quatre fils. Cette configuration se retrouve dans un réseau de tri de type 8 et correspond à un opérateur prenant quatre entrées ⟨A, B, C, D⟩ et les transformant en quatre sorties comme on le voit dans le tableau 2b (à gauche). On peut montrer que dans le cadre de la sorte 8, l'entrée qui passe dans l'opérateur satisfait l'inégalité suivante : ${\rm{D}}\ge \min ({\rm{A}},{\rm{C} })$. Cela signifie que l'opérateur peut être amélioré en appliquant le mouvement de copie AlphaDev défini dans le tableau 2b (à droite), ce qui donne une instruction de moins que l'opérateur d'origine. La différence de code entre l'opérateur d'origine et le code après l'application du mouvement de copie AlphaDev est visualisée sur les Fig. 3e, f, respectivement.

L'algorithme VarSort4 découvert par AlphaDev est particulièrement intéressant. L'organigramme de l'algorithme de référence humain et d'AlphaDev peut être vu sur les Fig. 4a, b, respectivement. L'algorithme de référence humain détermine la longueur du vecteur d'entrée, puis appelle le réseau de tri correspondant pour trier les éléments. La solution AlphaDev a une approche complètement différente comme le montre la figure 4b. Si la longueur du vecteur d'entrée est strictement supérieure à 2, la sorte 3 est immédiatement appelée, ce qui entraîne le tri des trois premiers éléments. Si le vecteur est supérieur à trois éléments, un algorithme simplifié de tri 4 est appelé qui trie les éléments non triés restants dans le vecteur d'entrée. C'est cette partie simplifiée de la routine qui donne des gains significatifs en termes de longueur algorithmique et de latence.

a, Un organigramme de l'algorithme de référence humain de tri variable 4 (VarSort4). Dans cet algorithme, une séquence de nombres non triés est entrée dans l'algorithme. Si la longueur de la séquence est de quatre, trois ou deux nombres, alors le réseau de tri de tri 4, tri 3 ou tri 2 correspondant est appelé et trie la séquence résultante. Le résultat est ensuite renvoyé et sorti par la fonction. b, L'algorithme VarSort4 découvert par AlphaDev. Cet algorithme reçoit également des séquences de longueur quatre, trois ou deux nombres en entrée. Dans ce cas, si la longueur est de deux, alors il appelle le réseau de tri sort 2 et revient. Si la longueur est de trois, il appelle sort 3 pour trier les trois premiers nombres et renvoie. Si, toutefois, la longueur est supérieure à trois, il appelle le tri 3, suivi d'une routine de tri simplifiée 4 qui trie le nombre non trié restant. C'est cette partie de la routine qui se traduit par des économies de latence significatives.

Il est important de comprendre les avantages et les limites de RL par rapport à d'autres approches d'optimisation de programme. En tant que tel, nous avons mis en œuvre une approche de superoptimisation stochastique de pointe8, l'avons adaptée au paramètre de tri et l'avons utilisée comme algorithme d'apprentissage dans AlphaDev. Nous appelons cette variante AlphaDev-S (voir Méthodes pour plus de détails). Nous exécutons cet algorithme avec au moins la même quantité de ressources et de temps qu'AlphaDev. AlphaDev-S nécessite un temps prohibitif pour optimiser directement la latence, car la latence doit être calculée après chaque mutation. En tant que tel, AlphaDev-S optimise pour un proxy de latence, à savoir la longueur de l'algorithme, puis, à la fin de la formation, nous recherchons tous les programmes corrects générés par AlphaDev-S et comparons chacun d'eux pour trouver la solution de latence la plus faible. En général, nous constatons qu'AlphaDev surpasse systématiquement AlphaDev-S lors de l'apprentissage à partir de zéro sans connaissances préalables. De plus, à mesure que la taille du programme augmente, AlphaDev explore des ordres de grandeur de moins de programmes (12 millions de programmes dans le pire des cas) par rapport à AlphaDev-S (31 000 milliards de programmes dans le pire des cas). Cela peut être dû au fait qu'AlphaDev est capable de mieux explorer l'espace des algorithmes par rapport à la procédure de recherche stochastique en largeur d'abord qui se coince plus facilement dans les optima locaux ; voir Méthodes pour un aperçu de cette hypothèse d'exploration. De plus, AlphaDev n'évalue jamais la latence pendant la recherche car il utilise les prédictions de la fonction de valeur de latence et, de ce fait, n'a besoin de calculer la latence réelle mesurée que sur moins de 0,002 % des programmes générés. Lors de l'incorporation de connaissances antérieures dans AlphaDev-S, telles que le démarrage à chaud de l'algorithme d'apprentissage avec une solution quasi optimale, AlphaDev-S est plus efficace en termes de calcul pour les tris 3, tri 4 et tri 5 (algorithmes d'assemblage sans branche) et génère également des performances faibles compétitives. algorithmes de latence à celui d'AlphaDev dans chaque cas. Cependant, pour les algorithmes qui nécessitent des branchements (instructions if-else), dans lesquels la longueur et la latence de l'algorithme ne sont pas bien corrélées, AlphaDev découvre des solutions à latence plus faible qu'AlphaDev-S, même lors du démarrage à chaud de cet algorithme avec une solution quasi optimale. Voir Méthodes pour une analyse approfondie de ces algorithmes.

Pour tester la généralité d'AlphaDev, nous entraînons l'agent sur un ensemble de domaines supplémentaires. Celles-ci incluent une sous-routine de désérialisation de tampon de protocole appelée VarInt, présentée ci-dessous, et un problème de codage concurrentiel (voir l'annexe D dans les informations supplémentaires pour plus de détails). Les performances de latence du domaine de codage concurrentiel sont indiquées dans le tableau 1b.

Protocol Buffer est le format de données open source de Google utilisé pour sérialiser les données structurées45. Ce format est couramment utilisé dans les cas où les performances ou la charge du réseau sont primordiales. L'algorithme VarInt46 est un élément clé dans les processus de sérialisation et de désérialisation. Nous avons formé l'agent AlphaDev comme dans le tri variable pour optimiser la fonction de désérialisation VarInt en ce qui concerne l'exactitude et la latence mesurée. Par souci d'exactitude, nous récompensons l'agent pour la désérialisation correcte de chaque entrée. Nous utilisons un ensemble de 80 entrées et sorties correspondantes qui couvrent les cas d'utilisation courants de protobuf. AlphaDev apprend une fonction de désérialisation VarInt optimisée et parvient à surpasser de manière significative la référence humaine pour les entrées à valeur unique. Notre agent découvre une solution sans branche qui est à la fois plus courte (tableau 1a) et environ trois fois plus rapide que la référence humaine (tableau 1b). Ce faisant, l'agent a également découvert un nouveau mouvement d'affectation VarInt dans lequel AlphaDev apprend à combiner deux opérations en une seule instruction, ce qui permet de réduire la latence. Voir l'annexe D.1 dans les informations supplémentaires pour un aperçu complet de ce déménagement. C'est une indication forte qu'AlphaDev est capable de généraliser pour optimiser des algorithmes non triviaux du monde réel.

Les algorithmes de tri 3, tri 4 et tri 5 de la bibliothèque de tri standard LLVM libc++ sont appelés plusieurs fois par des algorithmes de tri plus grands et sont donc des composants fondamentaux de la bibliothèque. Nous avons procédé à l'ingénierie inverse des algorithmes de tri d'assemblage de bas niveau découverts par AlphaDev pour le tri 3, le tri 4 et le tri 5 en C++ et découvert que nos implémentations de tri conduisaient à des améliorations allant jusqu'à 70 % pour les séquences d'une longueur de cinq et d'environ 1,7 % pour séquences dépassant 250 000 éléments. Ces améliorations concernent les types de données uint32, uint64 et float pour les architectures CPU ARMv8, Intel Skylake et AMD Zen 2 ; voir l'annexe E dans les informations supplémentaires pour les tableaux de performances complets. Les améliorations de performances sont dues à la fois à l'assemblage conditionnel sans branche généré par AlphaDev ainsi qu'au nouveau mouvement d'échange d'AlphaDev. Pour le tri 5, nous avons utilisé un algorithme de longueur 43 découvert par AlphaDev, car il a conduit à une implémentation C++ plus efficace. Ces algorithmes ont été envoyés pour révision et ont été officiellement inclus dans la bibliothèque de tri standard libc++3. Il s'agit du premier changement apporté à ces sous-routines depuis plus d'une décennie. C'est également la première fois qu'un composant de cette bibliothèque de tri est remplacé par un algorithme qui a été automatiquement découvert à l'aide de l'apprentissage par renforcement. Nous estimons que ces routines sont appelées des billions de fois chaque jour1,35,47.

AlphaDev découvre de toutes pièces de nouveaux algorithmes de tri à la pointe de la technologie qui ont été intégrés à la bibliothèque LLVM C++, utilisée par des millions de développeurs et d'applications dans le monde23,24,25. AlphaDev et la recherche stochastique sont des algorithmes puissants. Une direction intéressante pour les recherches futures consiste à étudier la combinaison de ces algorithmes pour réaliser les avantages complémentaires des deux approches.

Il est important de noter qu'AlphaDev peut, en théorie, généraliser à des fonctions qui ne nécessitent pas une vérification exhaustive des cas de test. Par exemple, les fonctions de hachage48 ainsi que les fonctions de hachage cryptographique49 définissent l'exactitude de la fonction par le nombre de collisions de hachage. Par conséquent, dans ce cas, AlphaDev peut optimiser pour minimiser les collisions ainsi que la latence. AlphaDev peut aussi, en théorie, optimiser des composants logiques complexes dans le corps de grandes fonctions impressionnantes. Nous espérons qu'AlphaDev pourra fournir des informations intéressantes et inspirer de nouvelles approches dans les communautés de l'intelligence artificielle et de la synthèse de programmes.

AlphaZero33 est un algorithme RL qui exploite MCTS en tant qu'opérateur d'amélioration des politiques. Il consiste en (1) un réseau de représentation frep qui délivre une représentation latente ht de l'état St ; et (2) un réseau de prédiction fpred qui prédit le retour attendu (la valeur) ${\hat{v}}_{t}$ et une politique (c'est-à-dire la distribution sur l'espace d'action) ${\hat {\pi }}_{t}$ à partir d'un état latent donné. L'algorithme utilise la véritable dynamique et la récompense lors de la planification. MuZero38 est une variante basée sur un modèle d'AlphaZero qui a les mêmes réseaux de représentation et de prédiction, mais apprend également un modèle de la dynamique et prédit les récompenses, qu'il utilise pour la planification. Plus précisément, il apprend un réseau dynamique fdyn qui prédit le prochain état latent ${{\bf{\text{h}}}}_{t}^{k+1}$ et récompense ${\hat{r }}_{t}^{k+1}$ résultant d'une transition. Notez que l'indice t désigne les pas de temps dans l'environnement réel et l'exposant k représente les pas de temps dans le modèle.

En atteignant un nouvel état, AlphaZero procède en codant d'abord l'état dans une représentation latente avec le réseau de représentation. Ensuite, la vraie dynamique ou réseau dynamique (pour MuZero) ainsi que le réseau de prédiction fpred(ht) sont utilisés pour simuler plusieurs trajectoires qui remplissent un arbre de recherche, en échantillonnant des transitions d'état. À chaque nœud, les actions sont sélectionnées à l'aide d'une stratégie optimiste appelée l'arbre de confiance supérieur du prédicteur32, destinée à équilibrer l'exploration (essayer de nouvelles actions) et l'exploitation (progresser plus bas dans le sous-arbre de l'estimation actuelle de la meilleure action). Cette stratégie commence par suivre de près la politique prédite ${\hat{\pi }}_{t}$ et évolue progressivement vers la maximisation de la fonction de valeur prédite. En fin de compte, une action est recommandée en échantillonnant à partir du nœud racine avec une probabilité proportionnelle à son nombre de visites pendant MCTS. La politique prédite est ensuite formée pour correspondre aux nombres de visites de la politique MCTS dans une tentative de distiller la procédure de recherche dans une politique telle que les itérations ultérieures de MCTS ignoreront les nœuds qui ne sont pas prometteurs.

Les réseaux de tri sont très efficaces car leurs structures peuvent être parallélisées sur les architectures CPU modernes. Ils ont donc tendance à atteindre des performances d'exécution plus rapides, en particulier sur les petits tris, par rapport aux algorithmes de cas de base populaires et efficaces tels que le tri par insertion17,43,50. Un réseau de tri43 est constitué de deux types d'éléments appelés comparateurs (lignes verticales) et fils (lignes horizontales) (Extended Data Fig. 2a). Chaque fil porte une valeur de gauche à droite. Lorsque deux fils se croisent au niveau d'un comparateur, les valeurs sur les deux fils sont comparées. Si la valeur du fil inférieur est inférieure à la valeur du fil supérieur, les valeurs sont permutées entre les fils, comme indiqué dans les données étendues Fig. 2b. Une implémentation programmatique d'un réseau de tri consiste à exécuter ces échanges sur des paires particulières d'éléments de la séquence d'entrée dans un ordre particulier.

Nous avons élagué l'espace d'action en supprimant certaines invariances de programme (par exemple, l'ordre d'allocation des registres) et les instructions illégales (par exemple, la comparaison de deux emplacements mémoire). Cela aide à réduire la taille de l'espace d'action et augmente le taux de convergence. Pour nos expériences, nous avons utilisé les règles suivantes :

Les emplacements de mémoire sont toujours lus dans l'ordre incrémentiel.

Les registres sont attribués par ordre incrémentiel.

Nous ne pouvons pas comparer ou déplacer conditionnellement vers un emplacement de mémoire (illégal).

Nous ne pouvons lire et écrire qu'une seule fois dans chaque emplacement de mémoire.

Nous ne pouvons pas utiliser de registres non initialisés (illégaux).

N'exécutez pas d'instructions de comparaison consécutives.

Nous formons AlphaDev sur une unité de traitement de tenseur (TPU) v.3, avec une taille de lot totale de 1 024 par cœur de TPU. Nous utilisons jusqu'à 16 cœurs TPU et nous nous entraînons pour 1 million d'itérations. Du côté des acteurs, les jeux se jouent sur un TPU v.4 autonome, et nous utilisons jusqu'à 512 acteurs. En pratique, sur toutes les tâches, la formation met, dans le pire des cas, 2 jours pour converger.

Il est important de comprendre les avantages et les limites du RL par rapport aux autres approches possibles pour l'optimisation du programme. En tant que tel, nous avons mis en œuvre une approche de superoptimisation stochastique de pointe8 et l'avons incorporée dans AlphaDev comme algorithme d'apprentissage pour optimiser les fonctions de tri. Nous appelons cette version adaptée AlphaDev-S. Notre réimplémentation a été spécifiquement optimisée pour le domaine du tri. Cela inclut la mise en œuvre de l'algorithme à exécuter avec notre environnement d'assemblage, la définition d'une fonction d'exactitude et de perte de performances spécifique au tri et l'exécution de balayages d'hyperparamètres étendus pour identifier la meilleure variante. La fonction de coût utilisée pour AlphaDev-S est c = exactitude + α × performance où l'exactitude correspond au calcul du nombre d'éléments de séquence d'entrée incorrects qui ne sont toujours pas triés, la performance correspond à la récompense de longueur de l'algorithme et α est un poids échangeant les deux coûts les fonctions. Nous ne sommes pas en mesure d'optimiser directement la latence car cela ralentit considérablement l'algorithme d'apprentissage, ce qui rend l'apprentissage impossible. Il convient de noter que cette fonction a été adaptée pour prendre en charge le même ensemble d'instructions d'assemblage utilisé par AlphaDev ainsi que pour supprimer le même ensemble d'actions incorrectes ou illégales. Il utilise également le même module de calcul d'exactitude du programme (Fig. 2b) pour calculer le terme d'exactitude.

AlphaDev-S est alors exécuté en proposant d'abord une transformation au programme stocké dans le buffer (qui peut être vide ou initialisé avec un programme déjà trié). Les termes d'exactitude et de performance sont ensuite calculés à l'aide du module d'exactitude du programme et de la longueur de l'algorithme, respectivement. Si le coût est inférieur au meilleur coût actuel, le nouveau programme est accepté avec une forte probabilité, sinon il est rejeté. Nous allons maintenant discuter de la fonction de coût d'exactitude et des poids de transformation plus en détail.

Pour la fonction de coût de correction, nous avons implémenté trois types de fonction de coût. Le premier est défini comme le pourcentage d'éléments mal placés : $\frac{PP{C}_{t}}{P}$ où P est le nombre total d'éléments à placer et PCt est le nombre d'éléments correctement placés au pas de temps t. La deuxième variante est la racine carrée de cette équation. La fonction de coût finale prend la racine carrée de la différence $\sqrt{-{PC}_{t}}$ et c'est ce qui a donné les meilleures performances.

Nous avons activé plusieurs transformations de programme telles que l'ajout d'une instruction pour augmenter la taille du programme (Add Transform), l'échange de deux instructions (Swap Transform), le changement aléatoire d'un Opcode pour une instruction (Opcode Transform), l'échantillonnage aléatoire d'un Operand pour une instruction choisie (Transformation d'opérande) et échantillonner au hasard un Opcode et ses opérandes correspondants (Transformation d'instruction). Il est possible d'influencer l'échantillonnage de ces transformées pour inciter certaines à être échantillonnées plus ou moins fréquemment. Nous avons optimisé les pondérations pour les transformations d'échantillonnage en exécutant un vaste balayage d'hyperparamètres.

Nous présentons maintenant un ensemble d'études d'investigation qui aident à mieux comprendre les avantages et les limites du DRL et des algorithmes d'apprentissage de recherche stochastique utilisés dans AlphaDev. Nous comparons AlphaDev à AlphaDev-S. Nous avons implémenté deux variantes d'AlphaDev-S : (1) Cold Start (AlphaDev-S-CS) et (2) Warm Start (AlphaDev-S-WS). AlphaDev-S-CS n'utilise aucune information préalable et doit générer un programme à partir d'un tampon de programme vide. Le tampon d'AlphaDev-S-WS est démarré à chaud avec un programme de tri correct (par exemple, un programme d'assemblage de réseau de tri optimal) et il édite le programme pour l'optimiser davantage. Nous avons comparé les variantes avec AlphaDev dans les configurations d'algorithme de tri individuel et variable.

Étant donné qu'AlphaDev apprend toujours à partir de zéro sans aucune connaissance préalable, la comparaison directe serait avec la version de recherche stochastique à démarrage à froid : AlphaDev-S-CS. Cependant, comme des programmes initiaux quasi optimaux peuvent parfois être disponibles, nous comparons également AlphaDev à la version de recherche stochastique à démarrage à chaud : AlphaDev-S-WS.

Il convient de noter que les variantes de recherche stochastiques ne sont pas en mesure d'optimiser directement la latence, car cela rendrait l'apprentissage impossible en raison de l'efficacité de calcul. Ainsi, nos variantes AlphaDev-S optimisent la longueur de l'algorithme. Ensuite, à la fin de la formation, nous parcourons l'ensemble des programmes générés pour AlphaDev-S sur des longueurs variables et identifions le programme avec la latence la plus faible.

Dans chaque cas, les algorithmes de recherche stochastique (AlphaDev-S) sont exécutés en utilisant au moins les mêmes ressources de calcul et le même temps d'horloge que AlphaDev.

Nous examinons d'abord les performances des différentes approches pour les algorithmes de tri fixe. Dans ce cas, toutes les variantes algorithmiques optimisent la longueur de l'algorithme car la longueur et la latence de l'algorithme sont fortement corrélées dans le paramètre conditionnel sans branche (voir Informations supplémentaires pour plus de détails).

Dans le cadre du démarrage à froid, AlphaDev-S-CS est incapable de trouver les programmes optimaux dans chaque cas, comme indiqué dans le tableau de données étendu 2a. De plus, AlphaDev-S-CS explore des ordres de grandeur plus de programmes qu'AlphaDev, comme indiqué dans le tableau de données étendu 2b. Dans le cadre du démarrage à chaud, AlphaDev-S est démarré à chaud avec un programme trié quasi optimal et est capable de correspondre aux performances d'AlphaDev dans chaque cas, comme indiqué dans le tableau de données étendu 2a. Il est plus efficace en termes de calcul qu'AlphaDev, comme indiqué dans le tableau de données étendu 2c, mais explore des ordres de grandeur de programmes supplémentaires pour les types 3 et 5, comme indiqué dans le tableau de données étendu 2b. On peut affirmer qu'AlphaDev-S-WS a un avantage substantiel dans ce scénario car il est fourni avec un programme initial presque optimal. Nous montrerons dans la section Tri variable que lorsque les algorithmes deviennent plus compliqués et que des branchements sont introduits, le démarrage à chaud de l'algorithme d'apprentissage avec un programme quasi-optimal ne suffit pas et peut le bloquer dans des solutions sous-optimales.

Nous avons également utilisé une approche par force brute pour prouver qu'aucun programme de moins de 17 instructions n'existe pour le tri 3. Nous avons dû énumérer environ 1032 programmes et, même avec l'heuristique d'élagage, il a fallu plus de 3 jours pour prouver cette hypothèse. Pour le tri 4 et au-dessus, cette approche est irréalisable.

La longueur d'un programme n'est qu'une approximation des performances d'un algorithme. Comme nous introduisons des structures de branchement, la longueur et la latence d'un programme ne sont pas bien corrélées. Par conséquent, nous exécutons les programmes sur des machines réelles et mesurons leur latence. Le microbenchmarking est très difficile étant donné les nombreuses sources de bruit qui pourraient affecter les mesures. Cela est particulièrement vrai lors de l'exécution sur des machines partagées où il pourrait y avoir des interférences d'autres processus. Notre approche consiste à disposer d'un service de benchmarking séparé, répliqué sur des machines séparées, afin de pouvoir effectuer rapidement de nombreuses mesures dans un environnement contrôlé dans différentes conditions. Le système fonctionne comme suit :

L'agent RL traite 1 000 mesures sur les machines à l'aide du service répliqué.

Pour chaque mesure, le service exécute l'algorithme de tri donné sur 10 000 entrées aléatoires (par exemple, pour le tri 3, ce serait 3 × 10 000 = 30 000 entiers aléatoires).

Nous mesurons le temps pris à l'aide d'un compteur de performance CPU (CPU_CLK_UNHALTED.CORE).

Nous prenons ensuite le cinquième centile comme mesure finale, car nous supposons que la plupart des sources de bruit sont unilatérales (par exemple, les échecs de cache, les préemptions, etc.). Pendant la formation, nous traitons les mesures sur dix machines pour une efficacité de calcul. Après la formation, nous comparons la solution d'AlphaDev aux solutions de base et traitons les mesures sur 100 machines pour plus de précision et de réduction du bruit. Pour chaque indice de référence, nous calculons des intervalles de confiance à l'aide de l'intervalle de confiance bilatéral sans distribution pour une méthode tabulaire quantile44.

Lors de l'optimisation directe de la latence, AlphaDev surpasse AlphaDev-S-WS sur VarSort3, VarSort4 et VarSort5, comme indiqué dans le tableau de données étendu 3a. AlphaDev-S-CS ne parvient pas à trouver une solution dans chaque cas. Dans les cas de VarSort4 et VarSort5, la durée du programme et la latence ne sont pas corrélées (voir Informations supplémentaires pour plus de détails). Cela indique que lorsque la longueur du programme ne peut pas être utilisée comme indicateur de performance, AlphaDev est capable de trouver des solutions à latence plus faible par rapport à AlphaDev-S. C'est même dans le cas où la recherche stochastique est démarrée à chaud avec un programme quasi-optimal. De plus, AlphaDev converge vers la solution optimale après avoir exploré un maximum de 12 millions de programmes, comme indiqué dans le tableau de données étendu 3b. C'est des ordres de grandeur inférieurs à ceux d'AlphaDev-S-CS et d'AlphaDev-S-WS, respectivement (31 000 milliards de programmes dans le pire des cas).

Nous avons proposé qu'AlphaDev-S ait du mal à découvrir les programmes lors de l'apprentissage à partir de zéro et reste bloqué dans les optima locaux lors du démarrage à chaud en raison de ses capacités d'exploration limitées en raison de la procédure de recherche stochastique. Données étendues La figure 3 montre des projections bidimensionnelles d'intégration de voisins t-stochastiques (t-SNE)51 des algorithmes d'assemblage d'AlphaDev et d'AlphaDev-S découverts au cours de leurs procédures d'apprentissage respectives pour VarSort5. Les caractéristiques utilisées dans la projection comprennent l'exactitude, la latence, la longueur de l'algorithme et un nombre d'histogrammes des instructions utilisées par algorithme. La figure 3a des données étendues indique les régions de l'espace algorithmique explorées par AlphaDev, AlphaDev-S-CS et AlphaDev-S-WS, respectivement, tandis que la figure 3b des données étendues superpose l'exactitude de l'algorithme sur chaque point de la projection t-SNE dans laquelle le la couleur indique l'exactitude de chaque algorithme découvert, allant des algorithmes incorrects (violet) aux algorithmes corrects (jaune). Les variantes AlphaDev-S couvrent toutes deux une région circulaire dense autour de leur graine initiale, ce qui met en évidence la nature étendue de leur procédure de recherche stochastique. Cela montre qu'AlphaDev-S-CS ne parvient pas à naviguer dans l'espace des algorithmes incorrects dans un délai raisonnable et à découvrir les algorithmes corrects lors de l'apprentissage à partir de zéro. Un argument similaire s'applique à AlphaDev-S-WS selon lequel, lors de l'optimisation à partir d'une démonstration d'expert déjà correcte mais sous-optimale, l'algorithme est biaisé pour explorer son voisinage et a du mal à échapper à ces maxima locaux. En revanche, AlphaDev a une couverture plus diversifiée de l'espace algorithmique, car la fonction de valeur à long terme est un signal de guidage pour découvrir de nouvelles parties intéressantes de l'espace algorithmique. Comme le montre la figure 3b Extended Data, il est capable d'échapper à l'espace des algorithmes incorrects pour découvrir un nouvel espace d'algorithmes corrects, mettant en évidence les avantages d'exploration offerts par AlphaDev.

Il existe de nombreuses approches pour optimiser les programmes d'assemblage, que nous avons classées en trois groupes : la recherche énumérative, la recherche stochastique et la recherche symbolique5.

Tout d'abord, les techniques de recherche énumérative incluent l'énumération par programme de force brute4,5,6 ainsi que l'énumération implicite utilisant la preuve de théorème symbolique52,53. Ces approches parcourent l'espace des programmes pour trouver une solution basée sur un ensemble prédéfini de programmes, d'heuristiques et/ou de fonction de coût. Ces approches ont du mal à couvrir de vastes régions de l'espace du programme, d'autant plus que la taille et la complexité du programme augmentent.

Deuxièmement, les techniques de recherche stochastique contournent l'énumération complète en s'appuyant sur des mécanismes d'échantillonnage tels que l'échantillonnage de Monte Carlo par chaînes de Markov5,6,8,9. Rajeev Alur et al.5 définissent une spécification d'exactitude, fournie par une formule logique qui utilise des symboles issus d'une théorie d'arrière-plan. Le but est alors de trouver une expression d'implémentation telle que la formule logique définissant la spécification soit valide. L'idée est d'ajouter de manière itérative des cas de test, puis de rechercher et d'étendre le programme pour résoudre les cas de test donnés. Ils optimisent l'exactitude des problèmes du livre Hacker's delight54. Phitchaya Mangpo Phothilimthana et al.6 présentent l'algorithme LENS qui est basé sur l'exécution de recherches énumératives, stochastiques et symboliques en parallèle, tout en s'appuyant sur des règles d'élagage artisanales. Cette configuration est capable d'optimiser jusqu'à 21 instructions et ne peut pas optimiser la latence ni prendre en charge le branchement. Un autre algorithme8 est basé sur l'échantillonnage de rejet de chaîne de Markov Monte Carlo et applique des transformations aux programmes en assemblage en utilisant une fonction de perte qui est une fonction d'exactitude et de performance. Bon nombre de ces approches ont tendance à rester coincées dans les minima locaux et peuvent également rencontrer des difficultés à mesure que la taille et/ou la complexité du programme augmentent. De plus, l'intégration d'une latence réelle et mesurée dans ces approches est soit irréalisable, soit d'un coût prohibitif.

Troisièmement, des approches de recherche symbolique peuvent également être mises en œuvre pour optimiser les programmes d'assemblage. Il s'agit notamment des solveurs SAT55, des solveurs SMT5,6 et des programmes mixtes d'entiers (MIP)56,57. Cependant, ces approches souffrent de problèmes de mise à l'échelle. Par exemple, les solveurs classiques exigent qu'un problème soit traduit dans une certaine forme canonique. Cela nécessite généralement un expert desdits solveurs et un temps considérable pour trouver une formulation efficace. De plus, pour toute nouvelle modification du problème, ceci doit être répété. Les solveurs classiques sont également difficiles à paralléliser et, par conséquent, il est difficile de tirer parti de plus de matériel pour accélérer le processus de résolution. Un autre algorithme de recherche symbolique est Cholorphyll10 qui implémente une approche multi-phases. Il nécessite d'abord en entrée un programme source avec des annotations de partition qui spécifient où résident le code et les données. Ensuite, un synthétiseur de mise en page mappe des fragments de programme sur des cœurs physiques pour minimiser les coûts de calcul. Le code est ensuite séparé en fragments de programme par cœur et les fragments de programme sont compilés en code machine. À ce stade, un superoptimiseur optimise chacun de ces fragments.

Diverses approches58,59,60 ont également été appliquées aux fonctions de tri qui s'exécutent dans la configuration à instruction unique, données multiples (SIMD)61. Cette configuration est capable de paralléliser l'exécution des instructions, mais n'est pas prise en charge actuellement dans les bibliothèques populaires telles que la bibliothèque libc++ std :: sort de LLVM. Un exemple est celui de Gilles Barthe et al.7 qui propose une méthodologie d'optimisation des programmes en vectorisant automatiquement les boucles avec des instructions SIMD. Pour ce faire, ils introduisent un cadre permettant de vérifier l'exactitude des transformations d'un programme et d'effectuer une procédure basée sur la recherche à l'aide de ladite transformation. Leur cadre peut découvrir des structures de bouclage SIMD jusqu'à neuf instructions en 0,12 s, ce qui correspond à une accélération minimale de 2 ×.

Il existe également plusieurs études utilisant RL pour l'optimisation du programme. Kevin Ellis et al.62 apprennent une politique et une fonction de valeur pour écrire et évaluer du code, ainsi qu'une stratégie de recherche de type Monte Carlo pendant l'inférence. Ce travail nécessite une étape de pré-apprentissage et vise à générer des programmes corrects répondant à un cahier des charges prédéfini. L'approche est appliquée avec succès aux programmes de conception assistée par ordinateur et d'édition de chaînes. SuperSonic63 utilise un méta-optimiseur RL pour sélectionner entre différentes architectures RL, en utilisant une recherche de politique Bandit multi-armé pour trouver une représentation d'état, une fonction de récompense et un algorithme RL qui sont optimaux pour la tâche en cours. Cela nécessite de suivre de nombreux algorithmes et architectures RL, qui sont utilisés dans le cadre de l'espace d'état. En revanche, notre approche se concentre uniquement sur la formation d'une seule architecture RL, en tirant parti de la recherche MCTS et des puissantes représentations d'état. Shypula et al.64 créent un ensemble de données d'assemblage supervisé et l'utilisent pour former un modèle Transformer pour mapper du code non optimisé à du code optimisé, suivi d'une étape RL pour améliorer la qualité de la solution. Notre méthode ne nécessite pas d'ensemble de données supervisé ou deux étapes de formation et de réglage fin distinctes, et optimise tout de bout en bout en utilisant RL et la recherche à la place. Chen et al.65 définissent leur propre langage spécifique à un domaine et effectuent une synthèse de programme d'entrée-sortie qui utilise mieux la représentation de programme intermédiaire pour guider la routine de synthèse. Ils montrent que cela peut être incorporé avec RL, en utilisant la configuration de Rudy Bunel et al.66 et améliorer l'exactitude des fonctions générées. Cependant, ils n'optimisent pas la durée ou la latence du programme.

Un grand nombre de travaux abordent le problème de l'apprentissage de programmes à partir de paires d'entrées-sorties. Un type d'approche apprend un réseau de neurones pour faire correspondre directement les entrées aux sorties11,13,67,68. Cette approche est difficile à intégrer dans les bibliothèques existantes et peut avoir du mal à se généraliser à des entrées inédites, bien qu'il y ait eu des progrès récents encourageants en utilisant des représentations graphiques69. Un autre type d'approche consiste à effectuer une recherche dans l'espace programme, guidée par un modèle appris12,70,71,72. Par exemple, Chen et al.70 utilisent un modèle qui prédit le prochain jeton de programme sur la base d'un programme partiel et des paires entrée-sortie. Cela présente certaines similitudes avec la façon dont la recherche est guidée dans notre approche : la politique apprise a priori dans AlphaZero est un modèle de prédiction du jeton suivant, appris sur la base d'une combinaison d'un programme partiel et des effets de ce programme sur les entrées. Cependant, nous souhaitons trouver des programmes corrects et efficaces, ce que nous obtenons en apprenant davantage une fonction de valeur pour approximer la latence attendue des programmes partiels, et en utilisant AlphaZero pour incorporer cette fonction de valeur dans le processus de recherche.

Il existe également plusieurs approches d'apprentissage en profondeur qui utilisent de grands modèles de langages pour générer du code. Ces approches varient dans leurs utilisations allant de la transpilation, la refactorisation du code et l'explication du code15 à la génération de code compétitif au niveau humain à l'aide d'une description en langage naturel14. Ce travail particulier vise à générer un code correct, mais ne se concentre pas sur la génération de solutions à faible latence.

Il existe plusieurs études de synthèse de programme qui ont abordé les algorithmes de tri. Par exemple, White et al.26 utilisent RL pour apprendre les fonctions de tri. Leur travail utilise plusieurs heuristiques et un langage spécifique à un domaine pour produire un algorithme de tri appelé tri de programmation par renforcement. Srivastava et al.27 codent la synthèse du programme comme un problème de vérification. Plus précisément, ils représentent une tâche de synthèse sous la forme d'un tuple composé de l'expression fonctionnelle, des domaines et gardes apparaissant dans le programme synthétisé et des contraintes de ressources. L'idée est que, étant donné une contrainte de ressource prédéfinie, leur synthétiseur produit un programme qui répond à la spécification prédéfinie pour garantir l'exactitude. Ils l'appliquent pour découvrir le tri par fusion et le tri rapide. Jason Ansel et al.28 prend en entrée des algorithmes prédéfinis (par exemple, le tri par insertion, le tri par fusion et le tri rapide) puis détermine quand sélectionner ces algorithmes pour exécution à l'aide de sa fonction d'autotuner. Pour ce faire, il définit un langage contenant des règles et des transformations qui dictent la manière dont les algorithmes sont sélectionnés et où ils sont exécutés.

Les données utilisées pour former le système ont été générées synthétiquement selon les procédures expliquées dans l'article. Les algorithmes découverts par AlphaDev pour les opérateurs de copie et d'échange sont présentés dans l'article principal. Nous avons également publié les implémentations d'assemblage AlphaDev découvertes pour les tris 3 à 8 ainsi que VarSort3, 4 et 5 sur Github à l'adresse https://github.com/deepmind/alphadev. Nous avons inclus des tests exhaustifs pour nous assurer que chaque implémentation est correcte. De plus, l'annexe G dans les informations supplémentaires contient une liste d'algorithmes de tri supplémentaires et corrects découverts par AlphaDev pour les tri 3, tri 4 et tri 5. Les performances des algorithmes de tri 3, tri 4 et tri 5 sur la suite officielle d'analyse comparative LLVM pour trois architectures CPU différentes ainsi que les types de données flottants, int32 et int64 sont détaillés dans l'annexe E des informations supplémentaires. De plus, les implémentations AlphaDev sort 3, sort 4 et sort 5 se trouvent dans la bibliothèque de tri standard LLVM libc++3.

Nous avons également publié un pseudocode sur https://github.com/deepmind/alphadev qui inclut l'environnement, l'acteur complet et les boucles d'entraînement ainsi que l'algorithme MCTS de base. En outre, nous incluons notre implémentation JAX réelle de nos réseaux de politique, de valeur et de représentation qui permettent de reproduire les architectures. Enfin, nous avons un fichier de configuration contenant les définitions d'hyperparamètres à utiliser avec l'agent.

Amazone. Amazon S3 : deux billions d'objets, 1,1 million de requêtes/seconde. AWS https://aws.amazon.com/blogs/aws/amazon-s3-two-trillion-objects-11-million-requests-second/ (2013).

Cormen, TH et al. Introduction aux algorithmes (MIT Press, 2022).

Gelmi, M. Introduire des fonctions de tri sans branche pour sort3, sort4 et sort5. LLVM.org https://reviews.llvm.org/D118029 (2022).

Bansal, S. & Aiken, A. Génération automatique de superoptimiseurs de judas. Calcul ACM SIGARCH. Cambre. Nouvelles 34, 394-403 (2006).

Alur, R. et al. Synthèse guidée par la syntaxe (IEEE, 2013).

Phothilimthana, PM et al. Mise à l'échelle de la superoptimisation. Dans Proc. Vingt et unième Conférence internationale sur le support architectural pour les langages de programmation et les systèmes d'exploitation 297–310 (ACM, 2016).

Barthe, G. et al. De la vérification relationnelle à la synthèse de boucles SIMD. Dans Proc. du 18e symposium ACM SIGPLAN sur les principes et la pratique de la programmation parallèle 123–134 (ACM, 2013).

Schkufza, E., Sharma, R. & Aiken, A. Superoptimisation stochastique. Avis ACM SIGPLAN 48, 305–315 (2013).

Bunel, R. et al. Apprendre à suroptimiser les programmes. Dans Proc. Conférence internationale sur les représentations de l'apprentissage (ICLR, 2016).

Phothilimthana, PM et al. Chlorophylle : compilateur assisté par synthèse pour les architectures spatiales de faible puissance. Avis ACM SIGPLAN 49, 396–407 (2014).

Vinyals, O. et al. Grammaire comme langue étrangère. Adv. Information neuronale. Proc. Syst. 28, 2773-2781 (2015).

Chen, X., Liu, C. & Song, D. Vers la synthèse de programmes complexes à partir d'exemples d'entrées-sorties. Dans Proc. Conférence internationale sur les représentations de l'apprentissage (ICLR, 2018).

Devlin, J. et al. Robustfill : apprentissage de programmes neuronaux sous des entrées/sorties bruyantes. Dans Proc. Conférence internationale sur l'apprentissage automatique 990–998 (PMLR, 2017).

Li, Y. et al. Génération de code de niveau compétition avec AlphaCode. Sciences 378, 1092-1097 (2022).

Pearce, H. et al. Le codex et d'autres grands modèles de langage peuvent-ils nous aider à corriger les bogues de sécurité ? Préimpression sur https://arxiv.org/abs/2112.02125 (2021).

Chen, M. et al. Évaluer de grands modèles de langage formés sur du code. Préimpression sur https://arxiv.org/abs/2107.03374 (2021).

Bingmann, T., Marianczuk, J. & Sanders, P. Concevoir des trieurs plus rapides pour de petits ensembles d'articles. Logiciel : Entraînement. Exp. 51, 965-1004 (2021).

Levcopoulos, C. & Petersson, O. Splitsort : un algorithme de tri adaptatif. Informer. Proc. Lett. 39, 205-211 (1991).

Helman, DR, Bader, DA & JáJá, J. Un algorithme de tri parallèle randomisé avec une étude expérimentale. J. Distribution parallèle. Calcul. 52, 1–23 (1998).

Goodrich, MT Randomized shellsort : un simple algorithme de tri inconscient. Dans Proc. du vingt et unième symposium annuel ACM-SIAM sur les algorithmes discrets 1262–1277 (ACM, 2010).

Mehlhorn, K., Sanders, P. & Sanders, P. Algorithmes et structures de données : la boîte à outils de base Vol. 55. (Springer, 2008).

Knebl, H. Algorithmes et structures de données (Springer, 2020).

Karatzoglou, A., Baltrunas, L. & Shi, Y. Apprendre à se classer pour les systèmes de recommandation. Dans Proc. de la 7e conférence ACM sur les systèmes de recommandation 493–494 (ACM, 2013).

Yang, JY, Zhang, B. & Mao, Y. Étude sur l'algorithme de tri de récupération d'informations dans un environnement de fabrication en réseau. Dans Mécanique Appliquée et Matériaux Vol. 484, 183–186 (Trans Tech Publishing, 2014).

Krallmann, J., Schwiegelshohn, U. & Yahyapour, R. Sur la conception et l'évaluation des algorithmes de planification des tâches. Dans Workshop on Job Scheduling Strategies for Parallel Processing 17–42 (Springer, 1999).

White, SK, Martinez, T. & Rudolph, G. Génération d'un nouvel algorithme de tri à l'aide de la programmation par renforcement. Dans Proc. Congrès IEEE sur le calcul évolutif 1–8 (IEEE, 2010).

Srivastava, S., Gulwani, S. & Foster, JS De la vérification de programme à la synthèse de programme. Dans Proc. du 37e symposium annuel ACM SIGPLAN-SIGACT sur les principes des langages de programmation 313–326 (ACM, 2010).

Ansel, J. et al. Petabricks : un langage et un compilateur pour le choix algorithmique. ACM Sigplan Notices 44, 38–49 (2009).

Smith, DR La conception d'algorithmes de division pour mieux régner. Sci. Calcul. Programme. 5, 37–58 (1985).

Irvine, KR et al. Langage d'assemblage pour les ordinateurs basés sur Intel (Prentice Hall, 2003).

Shannon, CE XXII. Programmation d'un ordinateur pour jouer aux échecs. Londres, Edinb. Philosophie de Dublin. Mag. J. Sci. 41.314, 256–275 (1950).

Silver, D. et al. Maîtriser le jeu de Go avec les réseaux de neurones profonds et la recherche arborescente. Nature 529, 484–489 (2016).

Silver, D. et al. Un algorithme général d'apprentissage par renforcement qui maîtrise les échecs, le shogi et le Go grâce à l'auto-jeu. Sciences 362, 1140-1144 (2018).

Vaswani, A. et al. L'attention est tout ce dont vous avez besoin. Adv. Information neuronale. Proc. Syst. 30, 5999–6009 (2017).

LLVM. Utilisateurs LLVM https://llvm.org/Users.html (LLVM, 2022).

Bartlett, J. Apprenez à programmer avec Assembly 271–273 (Apress, 2021).

Sutton, RS & Barto, AG Apprentissage par renforcement : une introduction 2e édition (MIT Press, 2018).

Schrittwieser, J. et al. Maîtriser l'atari, le go, les échecs et le shogi en planifiant avec un modèle savant. Nature 588, 604–609 (2020).

Maillard, O.-A., Ryabko, D. & Munos, R. Sélection de la représentation de l'état dans l'apprentissage par renforcement. Adv. Information neuronale. Proc. Syst. 24, 2627-2635 (2011).

Qian, R. et al. Apprentissage spatio-temporel de la représentation vidéo contrastive. Dans Proc. Conférence IEEE/CVF sur la vision par ordinateur et la reconnaissance de formes 6964–6974 (IEEE, 2021).

Brown, T. et al. Les modèles de langage sont des apprenants peu nombreux. Adv. Information neuronale. Proc. Syst. 33, 1877-1901 (2020).

Shazeer, N. Décodage rapide par transformateur : une seule tête d'écriture suffit. Préimpression sur https://arxiv.org/abs/1911.02150 (2019).

Bundala, D. & Závodny, J. Réseaux de tri optimaux. Dans Proc. Conférence internationale sur la théorie et les applications du langage et des automates 236–247 (Springer, 2014).

Hahn, GJ & Meeker, WQ Intervalles statistiques : Un guide pour les praticiens Vol. 92 (John Wiley & Fils, 2011).

Google. Tampons de protocole, version 0.2.5 ; https://developers.google.com/protocol-buffers (2022).

Google. Sérialisation et désérialisation du tampon de protocole VarInt, version 0.2.5 ; https://developers.google.com/protocol-buffers/docs/encoding (2022).

Protvin, R. & Levenberg, J. Pourquoi Google stocke des milliards de lignes de code dans un référentiel unique. Commun. ACM 59, 78–87 (2016).

Berman, I. et al. Fonctions de hachage résistantes aux collisions multiples et leurs applications. Dans Proc. Conférence internationale annuelle sur la théorie et les applications des techniques cryptographiques 133–161 (Springer, 2018).

Damgård, IB Fonctions de hachage sans collision et schémas de signature de clé publique. Dans Atelier sur la théorie et l'application des techniques cryptographiques 203–216 (Springer, 1987).

Hwang, M. Sort, Bitset (GitHub, 2021).

Van der Maaten, L. & Hinton, G. Visualisation des données à l'aide de t-SNE. J.Mach. Apprendre. Rés. 9.11, 2579–2605 (2008).

Gulwani, S. et al. Synthèse de programmes sans boucle. Avis ACM SIGPLAN 46.6, 62–73 (2011).

Sasnauskas, R. et al. Souper : un superoptimiseur de synthèse. Préimpression sur https://arxiv.org/abs/1711.04422 (2017).

Warren, HS Hacker's Delight (Pearson Education, 2013).

Hamadi, Y., Jabbour, S. & Sais, L. ManySAT : un solveur SAT parallèle. J. Satisfiabilité, modèle booléen. Calcul. 6, 245-262 (2010).

Wolsey, LA Programmation mixte en nombres entiers. Dans Wiley Encyclopedia of Computer Science and Engineering 1–10 (Wiley, 2007).

Nair, V. et al. Résolution de programmes mixtes en nombres entiers à l'aide de réseaux de neurones. Préimpression sur https://arxiv.org/abs/2012.13349 (2020).

Inoue, H. et al. AA-sort : un nouvel algorithme de tri parallèle pour les processeurs SIMD multicœurs. Dans Proc. Conférence internationale sur l'architecture parallèle et les techniques de compilation (PACT 2007) 189–198 (IEEE, 2007).

Yin, Z. et al. Tri parallèle efficace sur les architectures multicœurs et multicœurs basées sur avx-512. Dans Proc. IEEE 21st International Conference on High Performance Computing and Communications 168–176 (IEEE, 2019).

Blacher, M. et al. Quicksort vectorisé et performant. Préimpression sur https://arxiv.org/abs/2205.05982 (2022).

Wikipédia. Instruction unique, données multiples https://en.m.wikipedia.org/wiki/SIMD (2022).

Ellis, K. et al. Ecrire, exécuter, évaluer : synthèse de programme avec un REPL. Adv. Information neuronale. Proc. Syst.32, 9137–9146 (2019).

Wang, H. et al. Automatisation de la conception de l'architecture d'apprentissage par renforcement pour l'optimisation du code. Dans Proc. 31e Conférence internationale ACM SIGPLAN sur la construction de compilateurs 129–143 (ACM, 2022).

Shypula, AG et al. Apprendre à superoptimiser les programmes du monde réel. Préimpression sur https://arxiv.org/abs/2109.13498 (2022).

Chen, X., Liu, C. & Song, D. Synthèse de programmes neuronaux guidée par l'exécution. Dans Proc. Conférence internationale sur les représentations de l'apprentissage (ICLR, 2018).

Bunel, R. et al. Tirer parti de la grammaire et de l'apprentissage par renforcement pour la synthèse de programmes neuronaux. Dans Proc. Conférence internationale sur les représentations de l'apprentissage (ICLR, 2018).

Aharoni, R. & Goldberg, Y. Vers une traduction automatique neurale de chaîne en arbre. Dans Proc. 55e réunion annuelle de l'Association for Computational Linguistics132–140 (ACL, 2017).

Dong, L. & Lapata, M. Langage à la forme logique avec attention neurale. Dans Proc. 54e réunion annuelle de l'Association for Computational Linguistics 33–43 (ACL, 2016).

Ibarz, B. et al. Un apprenant algorithmique neuronal généraliste. Dans Proc. Conférence sur l'apprentissage des graphes Vol. 198, 2:1–2:23 (PMLR, 2022).

Chen, X., Song, D. & Tian, Y. Exécution latente pour la synthèse de programmes neuronaux au-delà des langages spécifiques à un domaine. Adv. Information neuronale. Proc. Syst. 34, 22196–22208 (2021).

Parisotto, E. et al. Synthèse de programme neuro-symbolique. Préimpression sur https://arxiv.org/abs/1611.01855 (2016).

Ellis, K., Solar-Lezama, A. & Tenenbaum, J. Échantillonnage pour l'apprentissage du programme bayésien. Adv. Information neuronale. Proc. Syst. 29, 1297-1305 (2016).

Télécharger les références

Nous remercions P. Kurylowicz, N. Anderson et Z. Ahmed pour leur aide à la coordination de la recherche ; L. Dionne et N. Klauser pour avoir patiemment révisé notre code LLVM ; et N. Vaish, D. Gove, D. Kutenin et A. Fawzi pour leurs précieux conseils tout au long du projet. Nous remercions également nos collègues de DeepMind pour leurs encouragements et leur soutien.

Ces auteurs ont contribué à parts égales : Daniel J. Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent

Deepmind, Londres, Royaume-Uni

Daniel J. Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent, Shariq Iqbal, Jean-Baptiste Lespiau, Alex Ahern, Thomas Köppe, Kevin Millikin, Stephen Gaffney, Sophie Elster, Jackson Broshear, Chris Gamble, Kieran Milan, Robert Tung, Taylan Cemgil, Mohammadamin Barekatain, Yujia Li, Amol Mandhane, Thomas Hubert, Julian Steppwieser, Demis Hassabis, Pushmeet Kohli, Martin Riedmiller, Oriol Vinyals et David Silver

Google, Mountain View, Californie, États-Unis

Minjae Hwang

Vous pouvez également rechercher cet auteur dans PubMed Google Scholar

DJM, A.Michi et AZ ont conçu l'idée et mené la recherche. A.Michi, DJM, AZ, MG, MS, CP, EL, SI et A.Mandhane ont développé l'architecture et la formation du réseau neuronal. J.-BL, CP, MG, DJM et EL ont élaboré la ligne de base. MG, AZ, DJM, MH, AA, TK et K.Millikin ont analysé les algorithmes générés et aidé avec le correctif de tri. DJM, A.Michi, AZ, SG, SE, JB, RT, CG et K.Milan, ont géré la recherche. A.Michi, MG et MS ont dirigé la plate-forme technique. A. Mandhane, TH, YL, JS, TC, MB, PK, MR, DS, OV et DH ont apporté des conseils techniques et des idées. DJM et AZ ont conçu le projet. DJM, CP, EL, A.Michi, MG, AZ, PK et MS ont rédigé l'article.

Correspondance à Daniel J. Mankowitz.

DJM, A.Michi, AZ, MG, MS, CP, EL, SI, A.Mandhane, PK, MR, DS et OV envisagent de déposer une demande de brevet relative à l'objet contenu dans cet article au nom de DeepMind Technologies Limité. Les autres auteurs ne déclarent aucun intérêt concurrent.

Nature remercie Zheng Wang et les autres examinateurs anonymes pour leur contribution à l'examen par les pairs de ce travail.

Note de l'éditeur Springer Nature reste neutre en ce qui concerne les revendications juridictionnelles dans les cartes publiées et les affiliations institutionnelles.

(a) Le réseau de représentation AlphaDev comprend un réseau Transformer Encoder qui reçoit en entrée l'algorithme d'assemblage généré jusqu'à présent. Il contient également un réseau CPU State Encoder qui reçoit en entrée l'état actuel de la mémoire et des registres. L'architecture exacte et les hyperparamètres peuvent être trouvés dans les informations supplémentaires, annexe A. (b) Avant d'entrer des instructions dans le réseau Transformer Encoder, l'opcode et les opérandes de chaque instruction de programme sont convertis en codages à chaud et concaténés. Le codage résultant est ensuite introduit dans le réseau Transformer Encoder.

(a) Les lignes horizontales sont appelées fils et les lignes verticales sont appelées comparateurs. (b) Une séquence de valeurs initialement non triée est entrée dans le réseau de tri sur le côté gauche. A différents stades, deux fils rencontrent un comparateur. Si la valeur en haut du comparateur est inférieure à la valeur en bas du comparateur, les chiffres changent de fil. Un réseau de tri optimal place des comparateurs dans des positions spécifiques afin de trier toute séquence de valeurs non triées en utilisant le nombre minimum de comparateurs.

(a) Une projection 2D t-SNE51 indiquant les régions explorées par AlphaDev (bleu) par rapport à AlphaDev-S. ( b ) La même projection 2D t-SNE qu'en ( a ) avec l'exactitude de l'algorithme superposée sur chaque point des programmes incorrects (violet) aux programmes corrects (jaune). Comme on le voit sur la figure, AlphaDev-S a du mal à sortir des optima locaux alors qu'AlphaDev est capable d'explorer de l'espace des programmes incorrects à l'espace des programmes corrects.

Libre accès Cet article est sous licence Creative Commons Attribution 4.0 International, qui permet l'utilisation, le partage, l'adaptation, la distribution et la reproduction sur n'importe quel support ou format, à condition que vous accordiez le crédit approprié à l'auteur ou aux auteurs originaux et à la source, fournir un lien vers la licence Creative Commons et indiquer si des modifications ont été apportées. Les images ou tout autre matériel de tiers dans cet article sont inclus dans la licence Creative Commons de l'article, sauf indication contraire dans une ligne de crédit au matériel. Si le matériel n'est pas inclus dans la licence Creative Commons de l'article et que votre utilisation prévue n'est pas autorisée par la réglementation légale ou dépasse l'utilisation autorisée, vous devrez obtenir l'autorisation directement du détenteur des droits d'auteur. Pour voir une copie de cette licence, visitez http://creativecommons.org/licenses/by/4.0/.

Réimpressions et autorisations

Mankowitz, DJ, Michi, A., Zhernov, A. et al. Algorithmes de tri plus rapides découverts à l'aide de l'apprentissage par renforcement profond. Nature 618, 257-263 (2023). https://doi.org/10.1038/s41586-023-06004-9

Télécharger la citation

Reçu : 25 juillet 2022

Accepté : 23 mars 2023

Publié: 07 juin 2023

Date d'émission : 08 juin 2023

DOI : https://doi.org/10.1038/s41586-023-06004-9

Toute personne avec qui vous partagez le lien suivant pourra lire ce contenu :

Désolé, aucun lien partageable n'est actuellement disponible pour cet article.

Fourni par l'initiative de partage de contenu Springer Nature SharedIt

En soumettant un commentaire, vous acceptez de respecter nos conditions d'utilisation et nos directives communautaires. Si vous trouvez quelque chose d'abusif ou qui ne respecte pas nos conditions ou directives, veuillez le signaler comme inapproprié.