AlphaDev de Deepmind découvre des algorithmes de tri qui peuvent révolutionner les bases informatiques

Le laboratoire de recherche sur l’intelligence artificielle (IA) de Google, DeepMind, a réalisé un exploit remarquable en informatique grâce à son dernier système d’IA, AlphaDev. Cette version spécialisée d’AlphaZero a fait une percée significative en découvrant des algorithmes de tri et de hachage plus rapides, qui sont des processus essentiels utilisés des milliards de fois par jour par les développeurs du monde entier pour le tri, le stockage et la récupération des données.

Dans un article publié aujourd’hui dans la revue scientifique Nature, DeepMind affirme que l’algorithme nouvellement découvert d’AlphaDev permet d’augmenter de 70 % l’efficacité du tri de courtes séquences d’éléments et d’environ 1,7 % pour les séquences dépassant 250 000 éléments, par rapport aux algorithmes de la bibliothèque C++. . Par conséquent, lorsqu’un utilisateur soumet une requête de recherche, l’algorithme AlphaDevs facilite un tri plus rapide des résultats, entraînant des économies de temps et d’énergie importantes lorsqu’il est utilisé à grande échelle.

De plus, le système a également découvert un algorithme plus rapide pour hacher les informations, ce qui se traduit par une amélioration de 30 % de l’efficacité lorsqu’il est appliqué aux fonctions de hachage dans la plage de 9 à 16 octets dans les centres de données.

Révolutionner l’informatique

Deepmind pense que cette réalisation remarquable révolutionne l’informatique et promet de faire progresser l’efficience et l’efficacité.

AlphaDev a découvert des algorithmes de tri améliorés, y compris de nouvelles innovations telles que les mouvements de copie et d’échange d’AlphaDev, a déclaré Daniel Mankowitz, chercheur à Google DeepMind, à VentureBeat. Semblable au célèbre mouvement 37 d’AlphaGos qui a donné un nouvel ensemble de stratégies pour jouer au jeu séculaire de Go, les découvertes algorithmiques uniques d’AlphaDev peuvent, espérons-le, inspirer de nouvelles perspectives et stratégies pour optimiser les algorithmes informatiques fondamentaux et les rendre plus rapides.

Mankowitz a déclaré qu’il s’agissait d’une étape importante pour l’apprentissage par renforcement, car il fournit davantage de preuves de sa capacité à faire de nouvelles découvertes, en particulier dans le domaine de l’optimisation du code.

La société a également annoncé son intention de rendre les nouveaux algorithmes disponibles via la bibliothèque de tri standard LLVM libc++, dans le but d’autonomiser des millions de développeurs et d’entreprises de divers secteurs. De manière significative, cette mise à jour représente la première révision de cette section de la bibliothèque de tri depuis plus d’une décennie et l’inclusion initiale d’un algorithme développé par apprentissage par renforcement.

Nous estimons que nos algorithmes de tri open source, qui permettent d’améliorer la vitesse de 2 % à ~ 70 %, sont appelés des billions de fois chaque jour dans le monde, a déclaré Mankowitz. Ces algorithmes peuvent fournir des économies de ressources aux développeurs et aux entreprises qui appellent ces fonctions dans leurs systèmes et applications. Nous pensons que ces algorithmes inspireront les chercheurs et les praticiens à développer de nouvelles approches qui mèneront à davantage de découvertes d’algorithmes nouveaux et améliorés.

Utilisation de l’apprentissage par renforcement pour améliorer le développement d’algorithmes traditionnels

Selon DeepMind, la plupart des algorithmes de calcul 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 de calcul croissant.

La société a souligné le fait que l’utilisation de l’apprentissage par renforcement profond améliore les méthodes de développement en générant des algorithmes précis et efficaces. Ceci est réalisé en optimisant la latence réelle mesurée au niveau des instructions du processeur tout en effectuant une recherche plus efficace et en tenant compte de l’espace des programmes précis et rapides.

Les algorithmes de tri, à la base, facilitent l’arrangement systématique des éléments dans un ordre spécifié. Ceux-ci servent de base à l’enseignement de l’informatique.

De même, le hachage trouve une application répandue dans le stockage et la récupération de données, comme dans une base de données client. Les algorithmes de hachage utilisent généralement une clé (nom d’utilisateur Jane Doe) pour générer un hachage unique correspondant aux valeurs de données souhaitées pour la récupération (numéro de commande 164335-87). Semblable à un bibliothécaire utilisant un système de classification pour localiser rapidement un livre particulier, un système de hachage permet à l’ordinateur de posséder une connaissance préalable de l’information souhaitée et de son emplacement précis.

Aperçu détaillé

Bien que les développeurs écrivent principalement du code dans des langages de haut niveau conviviaux tels que C++, la traduction de ces langages en instructions d’assemblage de bas niveau est indispensable pour la compréhension informatique.

Les chercheurs de DeepMinds pensent que de nombreuses améliorations existent au niveau inférieur, ce qui peut poser des défis à dévoiler dans les langages de programmation de niveau supérieur. Le niveau d’assemblage offre une flexibilité dans le stockage et les opérations informatiques, présentant un vaste potentiel d’améliorations qui peuvent considérablement influencer la vitesse et l’efficacité énergétique.

Pour exécuter un algorithme en C++, il est d’abord compilé en instructions CPU de bas niveau appelées instructions d’assemblage, qui manipulent les données entre la mémoire et les registres du CPU.

Cela fournit un aperçu beaucoup plus détaillé du fonctionnement de l’algorithme et facilite donc la recherche d’optimisations pour améliorer l’algorithme, a déclaré Mankowitz. En optimisant en assemblage, nous avons découvert les mouvements de copie et d’échange d’AlphaDev. Ce sont des séquences d’instructions d’assemblage qui réduisent la taille du programme d’une seule instruction lorsqu’elles sont appliquées à un programme d’assemblage.

Approche unique de Deepminds pour découvrir des algorithmes plus rapides

DeepMinds AlphaDev a adopté une approche non conventionnelle pour découvrir des algorithmes plus rapides en s’aventurant dans le domaine des instructions d’assemblage informatique, un domaine rarement exploré par les humains.

Pour débloquer de nouveaux algorithmes, AlphaDev s’est inspiré du célèbre modèle d’apprentissage par renforcement de DeepMinds, AlphaZero, qui a remporté des victoires contre des champions du monde dans des jeux comme le go, les échecs et le shogi (échecs japonais).

Pour former AlphaDev à la découverte de nouveaux algorithmes, l’équipe de recherche a réinventé le tri comme un jeu d’assemblage à un joueur. AlphaDev a utilisé l’apprentissage par renforcement pour observer et générer des algorithmes tout en incorporant des informations provenant du CPU.

Le système d’IA a choisi de manière proactive une instruction à incorporer dans l’algorithme à chaque étape, ce qui a entraîné un processus extrêmement complexe et exigeant compte tenu du grand nombre de combinaisons d’instructions potentielles.

Découvrir un programme plus rapide et correct

Comme AlphaDev a construit l’algorithme de manière incrémentielle, il a également validé l’exactitude de chaque mouvement en comparant la sortie de l’algorithme avec les résultats attendus. Le but ultime de cette approche était de découvrir un programme correct et plus rapide, remportant ainsi la victoire dans le jeu.

Le système DeepMinds AI a mis au jour de nouveaux algorithmes de tri qui ont entraîné des améliorations substantielles au sein de la bibliothèque de tri LLVM libc++.

La recherche s’est principalement concentrée sur l’amélioration des algorithmes de tri pour des séquences plus courtes, généralement composées de trois à cinq éléments. Étant donné que ces algorithmes sont fréquemment intégrés à des fonctions de tri plus importantes, l’amélioration de leur efficacité peut améliorer la vitesse globale lors du tri d’un nombre quelconque d’éléments.

Afin d’améliorer la convivialité, DeepMind a rétro-conçu les algorithmes découverts et les a convertis en C++.

Dépasser le domaine des algorithmes de tri

Les améliorations concernent les routines sort3, sort4 et sort5 qui trient les nombres, en particulier les entiers et les flottants, a expliqué Mankowitz.

Chaque fois qu’un développeur ou une application a besoin de trier ces types de données, nos algorithmes de tri peuvent être appelés, a-t-il déclaré. Avec des améliorations de vitesse allant de 2 % à 70 % en fonction du nombre d’éléments à trier, et ces fonctions étant appelées des billions de fois chaque jour, les développeurs et les utilisateurs pourront exécuter leurs applications/utiliser divers services tout en consommant moins de ressources.

De plus, les capacités d’AlphaDev dépassent le domaine des algorithmes de tri. DeepMind a exploré le potentiel des systèmes pour généraliser son approche et améliorer d’autres algorithmes informatiques essentiels, y compris le hachage. L’application de la méthodologie AlphaDevs à l’algorithme de hachage dans la plage de 9 à 16 octets a permis d’améliorer la vitesse de 30 %.

En tant que tel, nous avons optimisé l’exactitude du hachage (minimisation des collisions) et la vitesse (latence), a expliqué Mankowitz.

L’algorithme de hachage est maintenant disponible dans la bibliothèque open-source Abseil.

Quelle est la prochaine étape pour Deepmind ?

Selon DeepMind, AlphaDev est une étape importante dans la progression vers la création d’outils d’IA polyvalents capables d’optimiser l’ensemble de l’écosystème informatique et de relever divers défis sociétaux.

Alors que l’optimisation des instructions d’assemblage de bas niveau s’est avérée extrêmement puissante, la société a déclaré qu’elle explorait activement le potentiel d’AlphaDev pour optimiser les algorithmes directement dans des langages de haut niveau comme C++, ce qui serait encore plus précieux pour les développeurs.

AlphaDev optimise une partie de la pile informatique, a déclaré Mankowitz. Cela rend les algorithmes sous-jacents qui s’exécutent dans la pile plus efficaces. Nous essayons également d’optimiser d’autres aspects de la pile.

Par exemple, planifier les ressources plus efficacement lors de l’exécution d’applications et de services, optimiser le pipeline de compression vidéo de Youtube et optimiser le matériel sous-jacent sur lequel les systèmes et les applications sont exécutés.

Nous espérons que ces algorithmes donneront aux chercheurs et aux praticiens une perspective différente sur la façon dont les algorithmes peuvent être construits, a déclaré Mankowitz.