DeepMind fait un pas de géant dans la vitesse de tri
Algorithmes fondamentalement différents découverts par AlphaDev. un, 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 4 simplifiée qui trie le nombre non trié restant. C’est cette partie de la routine qui se traduit par des économies de latence significatives. Crédit: Nature (2023). DOI : 10.1038/s41586-023-06004-9
Le tri, ou la structuration des données, est un principe fondamental des opérations informatiques depuis le développement des premiers ordinateurs.
L’ordre et le traitement des nombres ont été démontrés par les Babyloniens vers 2500 av. Les Egyptiens ont emboîté le pas vers 1550 avant JC et le mathématicien grec Euclide vers 300 avant JC a conçu une formule pour trouver rapidement le plus grand diviseur commun de deux entiers.
Au milieu des années 1800, la commande était un objectif principal de la mathématicienne Augusta Ada King, la fille du poète Lord Byron. Elle a créé le premier algorithme, destiné à être utilisé sur ce qui était alors une machine théorique imaginée par son mentor, le mathématicien Charles Babbage (connu comme le père des ordinateurs). Pour cette réalisation, elle a obtenu le titre de « première programmeuse informatique ».
En 1951, une autre femme, Frances Elizabeth Holberton, a conçu le premier système de programmation générative, une procédure de tri/fusion rudimentaire pour l’armée américaine. Elle a également aidé à programmer des trajectoires balistiques pendant la Seconde Guerre mondiale.
En fait, selon l’expert en conception informatique et en cryptologie Frank Rubin, le tri peut être retracé jusqu’aux formes de vie avant même l’évolution des humains, soit quelque 65 millions d’années auparavant. Les dinosaures, a-t-il dit, effectuaient un tri simple. Ils ont classé tous les êtres vivants en deux catégories : « nourriture » et « non alimentaire ».
Le rythme de développement des algorithmes informatiques s’est accéléré du milieu du XXe siècle à nos jours. Nous avons maintenant des ordinateurs capables d’effectuer un quintillion de calculs par seconde.
Les Babyloniens – peut-être même les dinosaures – seraient très impressionnés.
Une percée également impressionnante est annoncée le 7 juin par l’équipe de DeepMind de Google dans un blog en ligne.
L’équipe a mis au point une approche de traitement des chiffres qui est jusqu’à 70 % plus rapide que les méthodes actuelles. Les algorithmes sont utilisés depuis un an car ils ont été ajoutés à la bibliothèque C++. Les algorithmes open source sont désormais utilisés par des millions de développeurs et d’entreprises dans le monde, selon DeepMind.
Le projet d’IA, appelé AlphaDev, est « un système d’intelligence artificielle qui utilise l’apprentissage par renforcement pour découvrir des algorithmes informatiques améliorés, dépassant ceux perfectionnés par les scientifiques et les ingénieurs au fil des décennies », a rapporté DeepMind sur son blog. L’article est également publié dans la revue Nature.
AlphaDev s’appuie sur le succès de son prédécesseur, AlphaZero, qui maîtrisait les stratégies derrière Go et les échecs.
La formation d’AlphaDev au tri a été menée à l’aide de ce que les chercheurs ont appelé un « assemblage d’acteurs [language] jeu. »
Les algorithmes de tri ont été construits une instruction à la fois, alors qu’AlphaDev explorait continuellement les options pour en trouver une qui fonctionnait mieux que la précédente. Le processus consiste à puiser dans les réseaux de neurones pour comparer et déplacer des valeurs, le tout pour obtenir les résultats les plus précis dans les plus brefs délais.
« La loi de Moore touche à sa fin, où les puces approchent de leurs limites physiques fondamentales », a déclaré Daniel Mankowitz, scientifique de DeepMind. « Nous devons trouver des moyens nouveaux et innovants d’optimiser l’informatique. »
La recherche s’est concentrée sur des listes courtes de cinq personnages maximum. Les chercheurs ont déclaré que les algorithmes pour trois à cinq caractères sont les plus fréquemment utilisés par les programmeurs. De tels algorithmes sont utilisés « des milliards de fois par jour », a déclaré le blog DeepMind.
Pour les séquences de tri plus longues, jusqu’à 250 000 éléments, il y a eu une amélioration marginale de la vitesse par rapport aux méthodes actuelles.
La prochaine étape pour AlphaDev consiste à étudier l’optimisation dans des langages de niveau supérieur tels que C++, qui devraient permettre une amélioration plus rapide de la vitesse et être plus utiles aux développeurs.
