AlphaDev découvre des algorithmes de tri plus rapides

AlphaDev découvre des algorithmes de tri plus rapides.

De nouveaux algorithmes transformeront les fondements de l’informatique

La société numérique génère une demande croissante en calcul et en énergie. Au cours des cinq dernières décennies, nous nous sommes appuyés sur les améliorations du matériel pour suivre le rythme. Mais alors que les microprocesseurs atteignent leurs limites physiques, il est crucial d’améliorer le code qui s’exécute sur eux pour rendre l’informatique plus puissante et durable. Cela est particulièrement important pour les algorithmes qui composent le code s’exécutant des milliards de fois par jour.

Dans notre article publié aujourd’hui dans Nature, nous présentons AlphaDev, un système d’intelligence artificielle (IA) qui utilise l’apprentissage par renforcement pour découvrir des algorithmes de science informatique améliorés, surpassant ceux perfectionnés par les scientifiques et ingénieurs au fil des décennies.

AlphaDev a découvert un algorithme de tri plus rapide, une méthode pour ordonner les données. Des milliards de personnes utilisent ces algorithmes tous les jours sans le réaliser. Ils sont à la base de tout, depuis le classement des résultats de recherche en ligne et des publications sur les réseaux sociaux jusqu’au traitement des données sur les ordinateurs et les téléphones. La génération de meilleurs algorithmes grâce à l’IA transformera la façon dont nous programmons les ordinateurs et aura un impact sur tous les aspects de notre société de plus en plus numérique.

En mettant en open source nos nouveaux algorithmes de tri dans la principale bibliothèque C++, des millions de développeurs et d’entreprises du monde entier l’utilisent maintenant sur des applications d’IA dans des secteurs allant de l’informatique en nuage et des achats en ligne à la gestion de la chaîne d’approvisionnement. Il s’agit du premier changement apporté à cette partie de la bibliothèque de tri depuis plus d’une décennie et la première fois qu’un algorithme conçu par apprentissage par renforcement est ajouté à cette bibliothèque. Nous considérons cela comme une étape importante pour utiliser l’IA afin d’optimiser le code du monde, un algorithme à la fois.

• Optimisation des systèmes informatiques avec des outils d’IA plus généralisés
• RoboChat Un agent robotique auto-améliorant.
• Rencontrez DragonDiffusion une méthode d’édition d’images de haute précision permettant une manipulation de type drag and drop sur des modèles de diffusion.

Qu’est-ce que le tri ?

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

Cette méthode a évolué tout au long de l’histoire. L’un des premiers exemples remonte aux IIe et IIIe siècles, lorsque les érudits ont classé par ordre alphabétique des milliers de livres à la main sur les étagères de la Grande Bibliothèque d’Alexandrie. À la suite de la révolution industrielle, sont apparues les machines capables d’aider au tri – les machines à tabuler stockaient des informations sur des cartes perforées qui ont été utilisées pour collecter les résultats du recensement de 1890 aux États-Unis.

Et avec l’avènement des ordinateurs commerciaux dans les années 1950, nous avons vu le développement des premiers algorithmes de science informatique pour le tri. Aujourd’hui, il existe de nombreuses techniques et algorithmes de tri différents qui sont utilisés dans des bases de code du monde entier pour organiser d’énormes quantités de données en ligne.

Les algorithmes contemporains ont demandé des décennies de recherche aux informaticiens et programmeurs pour être développés. Ils sont si efficaces que leur amélioration ultérieure représente un défi majeur, semblable à celui de trouver un nouveau moyen d’économiser de l’électricité ou une approche mathématique plus efficace. Ces algorithmes sont également un pilier de l’informatique, enseignés dans les cours d’introduction à l’informatique dans les universités.

Recherche de nouveaux algorithmes

AlphaDev a découvert des algorithmes plus rapides en partant de zéro plutôt qu’en perfectionnant des algorithmes existants, et a commencé à chercher là où la plupart des humains ne cherchent pas : les instructions d’assemblage de l’ordinateur.

Les instructions d’assemblage sont utilisées pour créer du code binaire afin que les ordinateurs puissent le mettre en action. Alors que les développeurs écrivent dans des langages de programmation tels que C++, appelés langages de haut niveau, cela doit être traduit en instructions d’assemblage de « bas niveau » pour que les ordinateurs puissent les comprendre.

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

Trouver les meilleurs algorithmes avec un jeu

AlphaDev est basé sur AlphaZero, notre modèle d’apprentissage par renforcement qui a vaincu des champions du monde dans des jeux tels que Go, les échecs et le shogi. Avec AlphaDev, nous montrons comment ce modèle peut passer des jeux aux défis scientifiques, et des simulations aux applications du monde réel.

Pour entraîner AlphaDev à découvrir de nouveaux algorithmes, nous avons 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). Ensuite, il joue un coup en choisissant une instruction à ajouter à l’algorithme.

Le jeu d’assemblage est incroyablement difficile car AlphaDev doit rechercher efficacement à travers un nombre énorme de combinaisons possibles d’instructions pour trouver un algorithme qui peut trier et est plus rapide que le meilleur algorithme 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 (10^120 parties) et de Go (10^700 parties). Et un seul mauvais coup peut invalider tout l’algorithme.

À 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 les algorithmes de tri, cela signifie que les nombres non triés entrent et que les nombres triés correctement sortent. Nous récompensons AlphaDev à la fois pour le tri correct des nombres et pour sa rapidité et son efficacité. AlphaDev remporte le jeu en découvrant un programme correct et plus rapide.

Découverte d’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++, jusqu’à 70% plus rapides pour les séquences plus courtes et environ 1,7% plus rapides pour les séquences de plus de 250 000 éléments.

Nous nous sommes concentrés sur l’amélioration des algorithmes de tri pour les 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 importantes. L’amélioration de ces algorithmes peut entraîner une accélération globale pour le tri de n’importe quel nombre d’éléments.

Pour rendre le nouvel algorithme de tri plus utilisable pour les personnes, nous avons rétro-ingénieré les algorithmes et les avons traduits en C++, l’un des langages de programmation les plus populaires utilisés par les développeurs. Ces algorithmes sont maintenant disponibles dans la bibliothèque de tri standard LLVM libc++, utilisée par des millions de développeurs et d’entreprises dans le monde entier.

Découverte 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 permettent d’économiser une instruction à chaque fois qu’elles sont appliquées. Cela peut avoir un impact énorme étant donné que ces algorithmes sont utilisés des milliards de fois par jour.

Nous appelons ces mouvements “AlphaDev d’échange et de copie”. Cette approche novatrice rappelle le “mouvement 37” d’AlphaGo – un coup contre-intuitif qui a stupéfié les spectateurs et a conduit à la défaite d’un joueur légendaire de Go. Avec le mouvement d’échange et de copie, AlphaDev saute une étape pour connecter des éléments d’une manière qui semble être une erreur, mais qui est en réalité 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 en informatique.

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 pourrait généraliser et améliorer un autre algorithme informatique : le hachage.

Le hachage est un algorithme fondamental en informatique utilisé pour récupérer, stocker et compresser des 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 cherchent et où le trouver exactement. 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 de caractères unique (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 afin de tenter 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 découvert par AlphaDev était 30% plus rapide.

Cette année, le nouvel algorithme de hachage d’AlphaDev a été publié dans la bibliothèque open-source Abseil, disponible pour des millions de développeurs du monde entier, et nous estimons qu’il est maintenant utilisé des milliards de fois par jour.

Optimiser le 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 des développeurs du monde entier, AlphaDev a démontré sa capacité à généraliser et à découvrir de nouveaux algorithmes ayant un impact réel. Nous considérons AlphaDev comme une étape vers le développement d’outils d’IA polyvalents qui pourraient aider à optimiser l’ensemble de l’écosystème informatique et à résoudre d’autres problèmes bénéfiques à la société.

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

Les découvertes d’AlphaDev, telles que les mouvements d’échange et de copie, montrent non seulement qu’il 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 à créer des techniques et des approches qui pourront optimiser davantage les algorithmes fondamentaux pour créer un écosystème informatique plus puissant et durable.

En savoir plus sur l’optimisation de l’écosystème informatique :

Lisez notre étude de cas : https://www.deepmind.com/blog/optimising-computer-systems-with-more-generalised-ai-tools

We will continue to update IPGirl; if you have any questions or suggestions, please contact us!