Impact
De nouveaux algorithmes transformeront les fondements de l’informatique
La société numérique entraîne une demande croissante en matière de calcul et de consommation d’énergie. Au cours des cinq dernières décennies, nous avons compté sur les améliorations matérielles pour suivre le rythme. Mais à mesure que les micropuces approchent de leurs limites physiques, il est essentiel d’améliorer le code qui s’exécute dessus pour rendre l’informatique plus puissante et plus durable. Ceci est particulièrement important pour les algorithmes qui composent le code qui s’exécute des milliards de fois par jour.
Dans notre article publié aujourd'hui dans Naturenous présentons AlphaDev, un système d'intelligence artificielle (IA) qui utilise l'apprentissage par renforcement pour découvrir des algorithmes informatiques améliorés – surpassant ceux perfectionnés par les scientifiques et les ingénieurs au fil des décennies.
AlphaDev a découvert un algorithme de tri plus rapide, une méthode de classement des données. Des milliards de personnes utilisent ces algorithmes quotidiennement sans s’en rendre compte. Ils sous-tendent tout, du classement des résultats de recherche en ligne et des publications sur les réseaux sociaux à la manière dont les données sont traitées sur les ordinateurs et les téléphones. Générer de meilleurs algorithmes à l’aide de 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 open sourceant nos nouveaux algorithmes de tri en la bibliothèque principale C++, des millions de développeurs et d'entreprises dans le monde l'utilisent désormais sur des applications d'IA dans des secteurs allant du cloud computing 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 un tremplin important pour utiliser l’IA afin d’optimiser le code mondial, un algorithme à la fois.
Qu’est-ce que le tri ?
Le tri est une méthode permettant d'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é au cours de l'histoire. L’un des premiers exemples remonte aux deuxième et troisième siècles, lorsque les érudits classèrent à la main des milliers de livres sur les étagères de la Grande Bibliothèque d’Alexandrie. La révolution industrielle a suivi l’invention de machines qui pourraient faciliter le tri : les machines à tabuler stockaient les informations sur des cartes perforées qui étaient utilisées pour collecter les résultats du recensement de 1890 aux États-Unis.
Et avec l’essor des ordinateurs commerciaux dans les années 1950, nous avons assisté au développement des premiers algorithmes informatiques de 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 d’énormes quantités de données en ligne.
Les algorithmes contemporains ont nécessité des décennies de recherche pour les informaticiens et les programmeurs. Ils sont si efficaces que les améliorer constitue un défi majeur, comparable à la recherche d'une nouvelle façon d'économiser de l'électricité ou d'une approche mathématique plus efficace. Ces algorithmes sont également une pierre angulaire 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 affinant les algorithmes existants, et a commencé à chercher là 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 que les ordinateurs peuvent mettre en œuvre. Alors que les développeurs écrivent dans des langages de codage comme 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 qu'il existe de nombreuses améliorations à 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 AlphaZéro, notre modèle d'apprentissage par renforcement qui a vaincu les champions du monde dans des jeux comme le 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 » pour un seul joueur. A chaque tour, AlphaDev observe l'algorithme qu'il a généré et les informations contenues dans l'unité centrale (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 parmi un nombre énorme de combinaisons possibles d'instructions pour trouver un algorithme capable de trier et 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 coups dans les parties d'échecs (10 120 parties) et de Go (10 700 parties). Et un seul faux mouvement 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 les algorithmes de tri, cela signifie que des nombres non ordonnés entrent et que des nombres correctement triés en sortent. Nous récompensons AlphaDev à la fois pour avoir trié correctement les chiffres et pour la rapidité et l'efficacité avec lesquelles il le fait. AlphaDev remporte la partie 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 de la bibliothèque de tri LLVM libc++ qui étaient jusqu'à 70 % plus rapides pour les séquences plus courtes et environ 1,7 % plus rapides 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 vastes. L’amélioration de ces algorithmes peut conduire à une accélération globale du tri d’un nombre quelconque d’éléments.
Pour rendre le nouvel algorithme de tri plus utilisable par les utilisateurs, nous avons procédé à une rétro-ingénierie des algorithmes et les avons traduits en C++, l'un des langages de codage les plus populaires utilisés 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 à travers le monde.
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 enregistrent une seule instruction à chaque fois qu'elles sont appliquées. Cela peut avoir un impact énorme puisque ces algorithmes sont utilisés des milliards de fois par jour.
Nous appelons cela des « mouvements d'échange et de copie AlphaDev ». Cette approche inédite n'est pas sans rappeler le « coup 37 » d'AlphaGo – un jeu contre-intuitif qui a stupéfié les spectateurs et a conduit à la défaite d'un joueur de Go légendaire. Avec le déplacement d'échange et de copie, AlphaDev saute une étape pour connecter les éléments d'une manière qui ressemble à une erreur mais qui est en réalité un raccourci. Cela montre la capacité d'AlphaDev à découvrir des solutions originales et à remettre en question notre façon de réfléchir à 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 autre algorithme informatique : le hachage.
Le hachage est un algorithme informatique fondamental 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 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 dans lequel 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 des structures de données afin d'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 découvert par AlphaDev était 30 % plus rapide.
Cette année, le nouvel algorithme de hachage d'AlphaDev a été publié en open source Bibliothèque de rappeldisponible pour des millions de développeurs à travers le monde, et nous estimons qu'il est désormais utilisé des milliards de fois par jour.
Optimiser le code mondial, un algorithme à la fois
En optimisant et en lançant des algorithmes améliorés de tri et de hachage utilisés par les 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 à usage général qui pourraient aider à optimiser l’ensemble de l’écosystème informatique et à résoudre d’autres problèmes qui profiteront à la société.
Bien que l'optimisation dans 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++, 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 capables d’optimiser davantage les algorithmes fondamentaux afin de créer un écosystème informatique plus puissant et plus durable.