Alphadev découvre des algorithmes de tri plus rapides

De nouveaux algorithmes transformeront les fondations de l’informatique

La société numérique stimule une demande croissante de calcul et une consommation d’énergie. Au cours des cinq dernières décennies, nous nous sommes appuyés sur des améliorations du matériel pour suivre le rythme. Mais à mesure que les micropuces abordent leurs limites physiques, il est essentiel d’améliorer le code qui les exécute pour rendre l’informatique plus puissante et durable. Ceci est particulièrement important pour les algorithmes qui composent le code exécutant des milliards de fois par jour.

Dans notre Document publié aujourd’hui dans Naturenous présentons Alphadev, un système d’intelligence artificielle (IA) qui utilise l’apprentissage du renforcement pour découvrir des algorithmes informatiques améliorés – dépasser les personnes perfectionnées par les scientifiques et les ingénieurs au fil des décennies.

Alphadev a découvert un algorithme plus rapide pour le tri, une méthode de commande de données. Des milliards de personnes utilisent ces algorithmes tous les jours sans s’en rendre compte. Ils sous-tendent tout, du classement des résultats de recherche en ligne et des publications sociales à la façon dont les données sont traitées sur les ordinateurs et les téléphones. La génération de meilleurs algorithmes en utilisant l’IA transformera la façon dont nous programmons les ordinateurs et avons un impact sur tous les aspects de notre société de plus en plus numérique.

En ouvrant l’approvisionnement de nos nouveaux algorithmes de tri dans la bibliothèque C ++ principaledes millions de développeurs et d’entreprises du monde entier l’utilisent désormais sur des applications d’IA dans toutes les industries, du cloud computing et des achats en ligne à la gestion de la chaîne d’approvisionnement. Il s’agit du premier changement à cette partie de la bibliothèque de tri en plus d’une décennie et la première fois qu’un algorithme conçu par l’apprentissage par renforcement a été ajouté à cette bibliothèque. Nous voyons cela comme un tremplin important pour utiliser l’IA pour optimiser le code du monde, un algorithme à la fois.

Qu’est-ce que le tri?

Le tri est une méthode pour organiser un certain nombre d’éléments dans un ordre particulier. Les exemples incluent l’alphabétisation de trois lettres, l’organisation de cinq nombres du plus grand au plus petit ou la commande d’une base de données de millions d’enregistrements.

Cette méthode a évolué à travers l’histoire. L’un des premiers exemples remonte au deuxième et troisième siècle lorsque les chercheurs alphabétisés des milliers de livres à la main sur les étagères de la grande bibliothèque d’Alexandrie. Suite à la révolution industrielle, l’invention des machines est venue pour aider à le tri – les machines de tabulation ont stocké des informations sur les cartes de punch qui ont été utilisées pour collecter les résultats du recensement de 1890 aux États-Unis.

Et avec la montée en puissance des ordinateurs commerciaux dans les années 1950, nous avons vu le développement des premiers algorithmes informatiques pour le tri. Aujourd’hui, il existe de nombreuses techniques et algorithmes de tri différents qui sont utilisés dans les bases de code du monde entier pour organiser des quantités massives de données en ligne.

Les algorithmes contemporains ont emmené des informaticiens et des programmeurs de recherches à développer. Ils sont si efficaces que de faire de nouvelles améliorations est un défi majeur, semblable à essayer de trouver une nouvelle façon d’économiser de l’électricité ou une approche mathématique plus efficace. Ces algorithmes sont également une pierre angulaire de l’informatique, enseignée dans des cours d’informatique d’introduction dans les universités.

Recherche de nouveaux algorithmes

Alphadev a découvert des algorithmes plus rapides en partant de zéro plutôt que de raffiner les algorithmes existants, et a commencé à regarder où la plupart des humains ne le font pas: les instructions d’assemblage de l’ordinateur.

Les instructions d’assemblage sont utilisées pour créer du code binaire pour les ordinateurs à mettre en action. Alors que les développeurs écrivent dans des langages de codage comme C ++, connus sous le nom de langages de haut niveau, cela doit être traduit en instructions d’assemblage «de bas niveau» à comprendre.

Nous pensons que de nombreuses améliorations existent à ce niveau inférieur qui peuvent être difficiles à découvrir dans un langage de codage de niveau supérieur. Le stockage et les opérations informatiques sont plus flexibles à ce niveau, ce qui signifie qu’il existe beaucoup plus d’améliorations potentielles qui pourraient avoir un impact plus important sur la vitesse et la consommation d’énergie.

Trouver les meilleurs algorithmes avec un jeu

Alphadev est basé sur Alphazernotre modèle d’apprentissage en renforcement qui a battu les champions du monde dans des jeux comme Go, Chess et Shogi. Avec Alphadev, nous montrons comment ce modèle peut transférer des jeux aux défis scientifiques et des simulations aux applications du monde réel.

Pour former Alphadev à découvrir de nouveaux algorithmes, nous avons transformé le tri en un «jeu d’assemblage» d’un joueur. À chaque tour, Alphadev observe l’algorithme qu’il a généré et les informations contenues dans l’unité centrale de traitement (CPU). Ensuite, il joue un mouvement en choisissant une instruction à ajouter à l’algorithme.

Le jeu d’assemblage est incroyablement difficile car Alphadev doit rechercher efficacement un nombre énorme de combinaisons possibles d’instructions pour trouver un algorithme qui peut trier et est plus rapide que le meilleur actuel. Le nombre de combinaisons possibles d’instructions est similaire au nombre de particules dans l’univers ou au nombre de combinaisons possibles de mouvements dans les jeux d’échecs (10120 jeux) et GO (10700 jeux). Et un seul coup de mal peut invalider l’ensemble de l’algorithme.

Au fur et à mesure que l’algorithme est construit, une instruction à la fois, Alphadev vérifie qu’il est correct en comparant la sortie de l’algorithme avec les résultats attendus. Pour le tri des algorithmes, cela signifie que les nombres non ordonnés entrent et que les numéros correctement triés sortent. Nous récompensons Alphadev pour le tri correctement des nombres et pour la rapidité et l’efficacité, il le fait. Alphadev remporte le jeu en découvrant un programme correct et plus rapide.

Découvrir des algorithmes de tri plus rapides

Alphadev a découvert de nouveaux algorithmes de tri qui ont conduit à des améliorations dans la bibliothèque de tri LLVM LIBC ++ qui était 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.

Nous nous sommes concentrés 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 plusieurs fois dans le cadre de fonctions de tri plus grandes. L’amélioration de ces algorithmes peut entraîner une accélération globale pour trier n’importe quel nombre d’articles.

Pour rendre le nouvel algorithme de tri plus utilisable pour les personnes, nous avons rétro-ingéré les algorithmes et les avons traduits en C ++, l’une des langues codantes les plus populaires utilisées par les développeurs. Ces algorithmes sont désormais disponibles dans le Bibliothèque de tri standard LLVM LIBC ++utilisé par des millions de développeurs et d’entreprises du monde entier.

Trouver de nouvelles approches

Alphadev a non seulement trouvé des algorithmes plus rapides, mais a également découvert de nouvelles approches. Ses algorithmes de tri contiennent de nouvelles séquences d’instructions qui sauvent une seule instruction à chaque fois qu’elles sont appliquées. Cela peut avoir un impact énorme car ces algorithmes sont utilisés des milliards de fois par jour.

Nous appelons ces «alphades swap et copier des mouvements». Cette nouvelle approche rappelle le «Move 37» d’Alphago – une pièce contre-intuitive qui a stupéfait les spectateurs et a conduit à la défaite d’un légendaire joueur de Go. Avec l’échange et la copie, 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 montre la capacité d’Alphadev à découvrir des solutions originales et remet en question la façon dont nous pensons à l’amélioration des algorithmes informatiques.

Du tri au hachage dans les structures de données

Après avoir découvert des algorithmes de tri plus rapides, nous avons testé si Alphadev pouvait généraliser et améliorer un algorithme d’informatique différent: hachage.

Le hachage est un algorithme fondamental de l’informatique utilisé pour récupérer, stocker et compresser les données. Comme un bibliothécaire qui utilise un système de classification pour localiser un certain livre, les algorithmes de hachage aident les utilisateurs à savoir ce qu’ils recherchent et exactement où le trouver. Ces algorithmes prennent des données pour une clé spécifique (par exemple, le nom d’utilisateur «Jane Doe») et les hachent – un processus où les données brutes sont transformées en une chaîne unique de caractères (par exemple 1234GHfty). Ce hachage est utilisé par l’ordinateur pour récupérer rapidement les données liées à la clé plutôt que de rechercher toutes les données.

Nous avons appliqué Alphadev à l’un des algorithmes les plus couramment utilisés pour le hachage dans les structures de données pour essayer de découvrir un algorithme plus rapide. Et lorsque nous l’avons appliqué à la plage de 9-16 octets de la fonction de hachage, l’algorithme qu’Alphadev a découvert était 30% plus rapide.

Cette année, le nouvel algorithme de hachage d’Alphadev a été libéré dans l’Open d’Open Bibliothèque d’Abseildisponible pour des millions de développeurs dans le monde, et nous estimons qu’il est maintenant utilisé des milliards de fois par jour.

Optimisation du code du monde, un algorithme à la fois

En optimisant et en lançant des algorithmes de tri et de hachage améliorés utilisés par les développeurs du monde entier, Alphadev a démontré sa capacité à généraliser et à découvrir de nouveaux algorithmes avec un impact réel. Nous considérons Alphadev comme une étape vers le développement d’outils d’IA à usage général qui pourraient aider à optimiser l’ensemble de l’écosystème informatique et à résoudre d’autres problèmes qui bénéficieront à la société.

Bien que l’optimisation de l’espace des instructions d’assemblage de bas niveau soit très puissante, il existe des limites à mesure que l’algorithme se développe, et nous explorons actuellement la capacité d’Alphadev à optimiser les algorithmes directement dans des langages de haut niveau tels que C ++ qui seraient plus utiles pour les développeurs.

Les découvertes d’Alphadev, telles que les mouvements d’échange et de copie, montrent non seulement qu’elle peut améliorer les algorithmes mais aussi trouver de nouvelles solutions. Nous espérons que ces découvertes inspireront les chercheurs et les développeurs pour créer des techniques et des approches qui peuvent optimiser davantage des algorithmes fondamentaux pour créer un écosystème informatique plus puissant et durable.