Schnellere Sortieralgorithmen mithilfe von Deep Reinforcement Learning entdeckt

Nature Band 618, Seiten 257–263 (2023)Diesen Artikel zitieren

88.000 Zugriffe

952 Altmetrisch

Details zu den Metriken

Grundlegende Algorithmen wie Sortieren oder Hashing werden an jedem Tag Billionen Mal verwendet1. Da die Nachfrage nach Berechnungen wächst, ist es immer wichtiger geworden, dass diese Algorithmen so leistungsfähig wie möglich sind. Während in der Vergangenheit bemerkenswerte Fortschritte erzielt wurden2, erwies sich die weitere Verbesserung der Effizienz dieser Routinen sowohl für Humanwissenschaftler als auch für rechnerische Ansätze als Herausforderung. Hier zeigen wir, wie künstliche Intelligenz über den aktuellen Stand der Technik hinausgehen kann, indem sie bisher unbekannte Routinen entdeckt. Um dies zu realisieren, haben wir die Aufgabe formuliert, eine bessere Sortierroutine als Einzelspielerspiel zu finden. Anschließend haben wir einen neuen Deep-Reinforcement-Learning-Agenten, AlphaDev, geschult, um dieses Spiel zu spielen. AlphaDev hat von Grund auf kleine Sortieralgorithmen entdeckt, die bisher bekannte menschliche Benchmarks übertrafen. Diese Algorithmen wurden in die LLVM-Standard-C++-Sortierbibliothek3 integriert. Diese Änderung an diesem Teil der Sortierbibliothek stellt den Ersatz einer Komponente durch einen Algorithmus dar, der mithilfe von Reinforcement Learning automatisch erkannt wurde. Wir präsentieren auch Ergebnisse in zusätzlichen Bereichen und veranschaulichen so die Allgemeingültigkeit des Ansatzes.

Menschliche Intuition und Know-how waren entscheidend für die Verbesserung von Algorithmen. Allerdings haben viele Algorithmen ein Stadium erreicht, in dem menschliche Experten sie nicht mehr weiter optimieren konnten, was zu einem immer größer werdenden Rechenengpass führt. Die jahrzehntelange Arbeit in der klassischen Programmsyntheseliteratur zielt darauf ab, korrekte Programme zu generieren und/oder Programme mithilfe von Proxys für die Latenz zu optimieren. Dazu gehören enumerative Suchtechniken4,5,6,7 und stochastische Suche5,6,8,9,10 sowie der neuere Trend, Deep Learning in der Programmsynthese zur Generierung korrekter Programme zu nutzen11,12,13,14,15,16 . Mithilfe von Deep Reinforcement Learning (DRL) können wir noch einen Schritt weiter gehen, indem wir korrekte und leistungsfähige Algorithmen generieren, indem wir die tatsächlich gemessene Latenz auf CPU-Befehlsebene optimieren und den Speicherplatz korrekter und schneller Programme im Vergleich zu früheren Arbeiten effizienter durchsuchen und berücksichtigen .

Eine der grundlegenden Fragen in der Informatik ist die Sortierung einer Sequenz17,18,19,20. Dies wird in Informatik-Grundkursen auf der ganzen Welt gelehrt21,22 und wird allgegenwärtig in einer Vielzahl von Anwendungen genutzt23,24,25. Jahrzehntelange Informatikforschung konzentrierte sich auf die Entdeckung und Optimierung von Sortieralgorithmen26,27,28. Eine Schlüsselkomponente praktischer Lösungen ist eine kleine Sortierung über eine kurze Folge von Elementen; Dieser Algorithmus wird wiederholt aufgerufen, wenn große Arrays sortiert werden, die Divide-and-Conquer-Ansätze verwenden29. In dieser Arbeit konzentrieren wir uns auf zwei Arten kleiner Sortieralgorithmen: (1) die feste Sortierung und (2) die variable Sortierung. Feste Sortieralgorithmen sortieren Sequenzen einer festen Länge (z. B. kann Sortierung 3 nur Sequenzen der Länge 3 sortieren), wohingegen variable Sortieralgorithmen eine Sequenz unterschiedlicher Größe sortieren können (z. B. variable Sortierung 5 kann Sequenzen im Bereich von eins bis fünf sortieren). Elemente).

Das Problem der Entdeckung neuer, effizienter Sortieralgorithmen formulieren wir als Einzelspielerspiel, das wir als AssemblyGame bezeichnen. In diesem Spiel wählt der Spieler eine Reihe von Low-Level-CPU-Anweisungen aus, die wir als Montageanweisungen30 bezeichnen, um sie zu einem neuen und effizienten Sortieralgorithmus zu kombinieren. Dies ist eine Herausforderung, da der Spieler den kombinatorischen Raum von Montageanweisungen berücksichtigen muss, um einen Algorithmus zu erhalten, der sowohl nachweislich korrekt als auch schnell ist. Die Härte des AssemblyGame ergibt sich nicht nur aus der Größe des Suchraums, der extrem anspruchsvollen Spielen wie Schach (10120 Spiele)31 und Go (10700 Spiele)32 ähnelt, sondern auch aus der Art der Belohnungsfunktion. Eine einzige falsche Anweisung im AssemblyGame kann möglicherweise den gesamten Algorithmus ungültig machen, was die Erkundung dieses Spielbereichs zu einer unglaublichen Herausforderung macht.

Um das Spiel zu spielen, stellen wir AlphaDev vor, einen Lernagenten, der darauf trainiert ist, nach korrekten und effizienten Algorithmen zu suchen. Dieser Agent besteht aus zwei Kernkomponenten, nämlich (1) einem Lernalgorithmus und (2) einer Darstellungsfunktion. Der AlphaDev-Lernalgorithmus kann sowohl DRL- als auch stochastische Suchoptimierungsalgorithmen integrieren, um AssemblyGame zu spielen. Der primäre Lernalgorithmus in AlphaDev ist eine Erweiterung von AlphaZero33, einem bekannten DRL-Algorithmus, bei dem ein neuronales Netzwerk darauf trainiert wird, eine Suche zur Lösung von AssemblyGame zu steuern. Die Darstellungsfunktion ist austauschbar und erfasst die zugrunde liegende Struktur von Assemblerprogrammen. Die primäre AlphaDev-Darstellung basiert auf Transformers34.

Mit AlphaDev haben wir von Grund auf feste und variable Sortieralgorithmen entdeckt, die sowohl neu als auch effizienter sind als die modernen menschlichen Benchmarks. Die von AlphaDev entdeckten festen Sortierlösungen für Sortierung 3, Sortierung 4 und Sortierung 5 wurden in die Standardsortierungsfunktion der LLVM-Standard-C++-Bibliothek3 integriert. Diese Bibliothek wird von mehreren Millionen Nutzern genutzt, darunter Universitäten und zahlreiche internationale Unternehmen35. Darüber hinaus analysieren wir die neuen Algorithmusentdeckungen, vergleichen AlphaDev mit stochastischen Suchoptimierungsansätzen und wenden AlphaDev auf weitere Domänen an, um die Allgemeingültigkeit des Ansatzes zu demonstrieren.

Beim Kompilieren von Algorithmen in Maschinencode aus einer Hochsprache wie C++ (z. B. die Sortierfunktion in Abb. 1a) wird der Algorithmus zunächst in Assembler kompiliert (Abb. 1b). Anschließend wandelt der Assembler das Assemblerprogramm in ausführbaren Maschinencode um. In dieser Arbeit optimieren wir Algorithmen auf Baugruppenebene30. In einem typischen Assemblerprogramm werden die Werte aus dem Speicher in Register kopiert, zwischen Registern manipuliert und dann in den Speicher zurückgeschrieben. Der Satz unterstützter Assembleranweisungen hängt von der Prozessorarchitektur ab. Für die Zwecke dieser Arbeit konzentrieren wir uns auf eine Teilmenge von Assembleranweisungen, die von der x86-Prozessorarchitektur unter Verwendung der AT&T-Syntax36 unterstützt werden. Jede Anweisung hat das Format Opcode⟨OperandA, OperandB⟩. Eine Beispielanweisung ist mov, die als Verschieben eines Werts von der Quelle (A) zum Ziel (B) definiert ist. Weitere Befehlsdefinitionen wie Compare (cmp), Conditional Move (cmovX) und Jump (jX) finden Sie in der Extended Data Table 1. Im Beispiel in Abb. 1b entsprechen %eax, %ecx, %edx, %edi vier verschiedene Registerplätze und (%rsi), 4(%rsi) entsprechen zwei verschiedenen Speicherplätzen. Das Symbol $2 ist ein Platzhalter für einen konstanten Wert, der in diesem Beispiel der Länge des Vektors entspricht. In dieser Arbeit verwenden wir die Begriffe Assemblerprogramm und Assembleralgorithmus synonym. Dies liegt daran, dass AlphaDev jedes Mal, wenn es AssemblyGame spielt, ein Assemblerprogramm von Grund auf aus einem zunächst ungeordneten Satz von Anweisungen erstellt und dabei einen neuen und effizienten Algorithmus definiert.

a: Eine C++-Implementierung einer variablen Sortierfunktion 2, die jede Eingabesequenz mit bis zu zwei Elementen sortiert. b: Die C++-Implementierung in a wird zu dieser äquivalenten Assembly-Darstellung auf niedriger Ebene kompiliert.

In diesem Abschnitt formulieren wir Optimierungsalgorithmen auf der CPU-Anweisungsebene als Reinforcement Learning (RL)-Problem37, bei dem die Umgebung als Einzelspieler-Spiel modelliert wird, das wir als AssemblyGame bezeichnen. Jeder Zustand in diesem Spiel ist als Vektor St = ⟨Pt, Zt⟩ definiert, wobei Pt eine Darstellung des bisher im Spiel generierten Algorithmus ist und Zt den Zustand des Speichers und der Register nach der Ausführung des aktuellen Algorithmus auf einem Satz vordefinierter Elemente darstellt Eingänge. Wie in Abb. 2a zu sehen ist, erhält der Spieler zum Zeitpunkt t den aktuellen Status St und führt eine Aktion aus. Dazu gehört das Anhängen einer gültigen Assembleranweisung (z. B. mov) an den bisher generierten aktuellen Algorithmus. Es wird eine Belohnung erhalten, die sowohl ein Maß für die Korrektheit des Algorithmus als auch die Latenz umfasst. Die Korrektheit des Algorithmus (Abb. 2b) beinhaltet die Eingabe eines Satzes von N Testsequenzen in den aktuellen Algorithmus Pt, um N Ausgaben zu generieren. Diese Ausgaben werden dann mit den erwarteten Ausgaben verglichen und eine Korrektheitsbelohnung rt berechnet. Latenzbelohnungen können generiert werden, indem entweder (1) der Agent dafür bestraft wird, dass er die Länge des Algorithmus erhöht (wenn Länge und Latenz stark korrelieren), was wir als Algorithmuslängenbelohnung bezeichnen, oder (2) die tatsächliche Latenz des Algorithmus misst . Das Spiel wird für eine begrenzte Anzahl von Schritten ausgeführt, danach wird das Spiel beendet. Um das Spiel zu gewinnen, muss mithilfe von Montageanweisungen ein korrekter Algorithmus mit geringer Latenz generiert werden. Das Verlieren des Spiels entspricht der Generierung eines falschen Algorithmus oder eines korrekten, aber ineffizienten Algorithmus.

a: Das AssemblyGame wird von AlphaDev gespielt, das als Eingabe den aktuellen, bisher generierten Assembly-Algorithmus St erhält und das Spiel spielt, indem es eine auszuführende Aktion auswählt. In diesem Beispiel handelt es sich bei der Aktion um eine mov-Assembly-Anweisung, die an den aktuellen Algorithmus angehängt wird. Der Agent erhält eine Belohnung, die von der Korrektheit des Algorithmus (siehe b) sowie von der Latenz des Algorithmus abhängt. Das Spiel wird gewonnen, wenn der Spieler einen korrekten Algorithmus mit geringer Latenz entdeckt. b: Die Programmkorrektheits- und Latenzberechnungen werden zur Berechnung der Belohnung rt verwendet. In diesem Beispiel werden Testsequenzen in den Algorithmus eingegeben; Im Fall der Sortierung von drei Elementen umfassen die Testeingaben beispielsweise alle Sequenzen unsortierter Elemente der Länge 3. Für jede Sequenz wird die Ausgabe des Algorithmus mit der erwarteten Ausgabe verglichen (im Fall der Sortierung sind die sortierten Elemente die erwartete Ausgabe). ). In diesem Beispiel entspricht die Ausgabe ${\bf{D}}{\boldsymbol{{\prime} }}$ nicht der erwarteten Ausgabe ${\bf{B}}{\boldsymbol{{\prime} }}$ und der Algorithmus ist daher falsch.

Wir bezeichnen den Agenten, der dieses Einzelspielerspiel spielt, als AlphaDev. Der primäre Lernalgorithmus des Agenten ist eine Erweiterung des AlphaZero-Agenten32 und leitet ein Planungsverfahren für die Monte-Carlo-Baumsuche (MCTS) mithilfe eines tiefen neuronalen Netzwerks33,38. Die Eingabe in das neuronale Netzwerk ist der Zustand St und die Ausgabe ist eine Richtlinien- und Wertvorhersage. Die Richtlinienvorhersage ist eine Verteilung über Aktionen und die Wertfunktion ist eine Vorhersage der kumulativen Renditen R, die der Agent vom aktuellen Status St erwarten sollte. Während eines Spiels erhält der Agent als Eingabe den aktuellen Status St. Der Agent dann führt eine MCTS-Prozedur aus und wählt anhand dieser die nächste auszuführende Aktion aus. Die generierten Spiele werden dann verwendet, um die Parameter des Netzwerks zu aktualisieren und dem Agenten das Lernen zu ermöglichen.

Es ist von entscheidender Bedeutung, dass AlphaDev über eine Darstellung39,40 verfügt, die in der Lage ist, komplexe algorithmische Strukturen darzustellen, um den Befehlsraum effizient zu erkunden. Um dies zu erreichen, führen wir das AlphaDev-Repräsentationsnetzwerk ein (Extended Data Abb. 1a). Dieses Netzwerk besteht aus zwei Komponenten, nämlich (1) einem Transformator-Encoder-Netzwerk, das dem Agenten eine Darstellung der Algorithmusstruktur liefert, und (2) dem CPU-Status-Encoder-Netzwerk, das dem Agenten hilft, vorherzusagen, wie sich der Algorithmus auf die Dynamik von Speicher und Registern auswirkt . Das CPU-Zustandscodierernetzwerk umfasst ein mehrschichtiges Perzeptron, das als Eingabe den Zustand jedes Registers und Speicherorts für einen bestimmten Satz von Eingaben empfängt. Diese Netzwerke geben jeweils Einbettungen aus, die kombiniert werden, um die AlphaDev-Zustandsdarstellung zu ergeben.

Transformer sind Encoder für natürliche Texte und haben in letzter Zeit große Erfolge bei Sprachmodellen erzielt14,34,41. Dies motivierte uns, den Standardtransformator an die Montageanleitung des Modells anzupassen. Wir haben einen Transformator-Encoder, unsere Adaption des MultiQuery-Transformator-Encoders42, entwickelt und in das AlphaDev-Repräsentationsnetzwerk integriert, um die Montageanleitungen darzustellen. Der Opcode und die entsprechenden Operanden jeder Assembleranweisung werden in One-Hot-Codierungen konvertiert und verkettet, um die Roheingabesequenz zu bilden. Dies wird durch einen Multilayer-Transformator-Encoder geleitet, der es den entsprechenden Einbettungsvektoren zuordnet (eine Illustration finden Sie in den erweiterten Daten in Abb. 1b).

Latenz ist ein wichtiges Belohnungssignal, das dem Agenten dabei hilft, leistungsfähige Algorithmen zu entdecken. Um die Latenz besser abschätzen zu können, haben wir ein Dual-Value-Funktionssetup implementiert, wobei AlphaDev über zwei Value-Funktionsköpfe verfügt: einen, der die Korrektheit des Algorithmus vorhersagt, und einen zweiten, der die Latenz des Algorithmus vorhersagt. Der Latenzkopf wird verwendet, um die Latenz eines bestimmten Programms direkt vorherzusagen, indem die tatsächlich berechnete Latenz des Programms als Monte-Carlo-Ziel für AlphaDev während des Trainings verwendet wird. Dieser Dual-Head-Ansatz erzielte bei der Optimierung für echte Latenz wesentlich bessere Ergebnisse als das Vanilla-Einzelkopf-Wert-Funktionssetup.

Wir haben den AlphaDev-Agenten von Grund auf trainiert, um eine Reihe fester Sortier- und variabler Sortieralgorithmen zu generieren, die sowohl korrekt sind als auch eine geringere Latenz als die modernen menschlichen Benchmarks erreichen.

Wir haben drei grundlegende Algorithmen betrachtet: Sortierung 3, Sortierung 4 und Sortierung 5. Die modernen menschlichen Benchmarks für diese Algorithmen sind Sortiernetzwerke43, da sie effizienten, bedingten verzweigungslosen Assemblercode generieren. Dies bedeutet, dass alle Anweisungen nacheinander ausgeführt werden und keine Verzweigungen erforderlich sind. Die Verbesserung dieser Algorithmen ist eine Herausforderung, da sie bereits hoch optimiert sind. Wie in Tabelle 1a zu sehen ist, ist AlphaDev in der Lage, Algorithmen mit weniger Anweisungen als die menschlichen Benchmarks für Sortierung 3 und Sortierung 5 zu finden und erreicht die Leistung auf dem neuesten Stand der Technik bei Sortierung 4. Diese kürzeren Algorithmen führen tatsächlich zu einer geringeren Latenz als Die Länge und Latenz des Algorithmus korrelieren für den Fall ohne bedingte Verzweigung. Weitere Einzelheiten finden Sie in Anhang B in den Zusatzinformationen. Wir haben auch die Skalierung auf etwas größere Sortierungen mithilfe einer Variante von AlphaDev untersucht. Es ist uns gelungen, drei Anweisungen für Sortierung 6, zwei Anweisungen für Sortierung 7 und eine Anweisung für Sortierung 8 zu speichern, was eine vielversprechende Grundlage für zukünftige Arbeiten darstellt. Einen Überblick über den Ansatz finden Sie in Anhang C in den Zusatzinformationen.

Wir haben drei variable Sortieralgorithmen betrachtet: VarSort3, VarSort4 und VarSort5. Als menschliche Benchmark wird jeweils ein Algorithmus definiert, der bei gegebener Eingabelänge das entsprechende Sortiernetzwerk aufruft. In diesem Fall ist eine Verzweigung erforderlich, was die Komplexität des Problems erheblich erhöht, da der Agent (1) bestimmen muss, wie viele Unteralgorithmen er erstellen muss, und (2) den Hauptalgorithmus parallel erstellen muss. Der Agent muss möglicherweise auch Unteralgorithmen von anderen Unteralgorithmen aufrufen. In diesem Fall führt die Optimierung der Länge zu deutlich kürzeren Algorithmen im Vergleich zu den menschlichen Benchmarks, wie in Tabelle 1a dargestellt. Aufgrund der Komplexität, die durch die Verzweigung entsteht, korrelieren Latenz und Länge jedoch nicht immer; Weitere Einzelheiten finden Sie in den Zusatzinformationen. Daher haben wir ein Verfahren implementiert, das die tatsächliche Latenz der Programme misst, indem wir das fünfte Perzentil der Latenzmessungen auf 100 verschiedenen Maschinen mit berechneten Konfidenzintervallen44 durchführen und diese Metrik optimieren. Das vollständige Benchmarking-Setup finden Sie unter Methoden. Bei der Latenzoptimierung verbessert sich der Agent in jedem Fall erheblich gegenüber den menschlichen Benchmarks, wie in Tabelle 1b dargestellt.

Die von AlphaDev entdeckten Lösungen umfassen neue und aufregende algorithmische Entdeckungen, die zu einer effizienteren Leistung führen. In der festen Sortiereinstellung haben wir festgestellt, dass AlphaDev zwei interessante Befehlssequenzen entdeckt hat, die bei Anwendung auf einen Sortiernetzwerkalgorithmus den Algorithmus jedes Mal um eine Assembleranweisung reduzieren. Wir bezeichnen jede Befehlsfolge als (1) den AlphaDev-Swap-Move und (2) den AlphaDev-Copy-Move.

Abbildung 3a zeigt ein optimales Sortiernetzwerk für drei Elemente (eine Übersicht über Sortiernetzwerke finden Sie unter Methoden). Wir erklären, wie AlphaDev das eingekreiste Netzwerksegment verbessert hat. Es gibt viele Varianten dieser Struktur, die in Sortiernetzwerken unterschiedlicher Größe vorkommen, und in jedem Fall gilt das gleiche Argument. Der eingekreiste Teil des Netzwerks (die letzten beiden Komparatoren) kann als eine Folge von Anweisungen betrachtet werden, die eine Eingabesequenz ⟨A, B, C⟩ annimmt und jede Eingabe transformiert, wie in Tabelle 2a (links) gezeigt. Allerdings geht diesem Operator ein Komparator auf den Leitungen B und C voraus, sodass Eingabesequenzen mit B ≤ C garantiert sind. Dies bedeutet, dass es ausreicht, als erste Ausgabe min(A, B) anstelle von min(A, B, C) zu berechnen, wie in Tabelle 2a (rechts) gezeigt. Der Pseudocode-Unterschied zwischen Abb. 3b und c zeigt, wie die AlphaDev-Swap-Bewegung bei jeder Anwendung eine Anweisung spart.

a, Ein optimales klassisches Sortiernetzwerk für drei Eingaben. Die eingekreisten Komparatoren wurden von AlphaDev verbessert. Weitere Informationen finden Sie im AlphaDev-Swap-Umzug. b,c, Der Assembly-Pseudocode vor der Anwendung der AlphaDev-Swap-Bewegung (b) und nach der Anwendung der AlphaDev-Swap-Bewegung (c), was zur Entfernung einer einzelnen Anweisung führt. d, Eine optimale klassische Sortiernetzwerk-Komparatorkonfiguration, die von AlphaDev verbessert wurde. Weitere Einzelheiten finden Sie im Abschnitt zum Kopieren von AlphaDev. e,f, Der Assembly-Pseudocode vor der Anwendung der AlphaDev-Kopierbewegung (e) und nach der Anwendung der AlphaDev-Kopierbewegung (f), was zur Entfernung einer einzelnen Anweisung führt.

Abbildung 3d zeigt eine Sortiernetzwerkkonfiguration, bestehend aus drei Komparatoren, die über vier Drähte angewendet werden. Diese Konfiguration findet sich in einem Sortiernetzwerk der Sorte 8 und entspricht einem Operator, der vier Eingaben ⟨A, B, C, D⟩ nimmt und sie in vier Ausgaben umwandelt, wie in Tabelle 2b (links) dargestellt. Man kann zeigen, dass als Teil von Sortierung 8 die Eingabe, die in den Operator fließt, die folgende Ungleichung erfüllt: ${\rm{D}}\ge \min ({\rm{A}},{\rm{C} })$. Dies bedeutet, dass der Operator durch Anwenden der in Tabelle 2b (rechts) definierten AlphaDev-Kopierbewegung verbessert werden kann, was zu einer Anweisung weniger als beim ursprünglichen Operator führt. Der Codeunterschied zwischen dem ursprünglichen Operator und dem Code nach Anwendung der AlphaDev-Kopierbewegung ist in Abb. 3e bzw. f dargestellt.

Besonders interessant ist der von AlphaDev entdeckte VarSort4-Algorithmus. Das Flussdiagramm für den menschlichen Benchmark-Algorithmus und AlphaDev ist in Abb. 4a bzw. b zu sehen. Der menschliche Benchmark-Algorithmus bestimmt die Länge des Eingabevektors und ruft dann das entsprechende Sortiernetzwerk auf, um die Elemente zu sortieren. Die AlphaDev-Lösung verfolgt einen völlig anderen Ansatz, wie in Abb. 4b zu sehen ist. Wenn die Länge des Eingabevektors unbedingt größer als 2 ist, wird sofort sort 3 aufgerufen, was dazu führt, dass die ersten drei Elemente sortiert werden. Wenn der Vektor mehr als drei Elemente umfasst, wird ein vereinfachter Sortier-4-Algorithmus aufgerufen, der die verbleibenden unsortierten Elemente im Eingabevektor sortiert. Es ist dieser vereinfachte Teil der Routine, der erhebliche Vorteile hinsichtlich der algorithmischen Länge und Latenz bringt.

a, Ein Flussdiagramm des menschlichen Benchmark-Algorithmus Variable Sort 4 (VarSort4). Bei diesem Algorithmus wird eine Folge unsortierter Zahlen in den Algorithmus eingegeben. Wenn die Sequenzlänge vier, drei oder zwei Zahlen beträgt, wird das entsprechende Sortiernetzwerk „Sort 4“, „Sort 3“ oder „Sort 2“ aufgerufen, das die resultierende Sequenz sortiert. Das Ergebnis wird dann von der Funktion zurückgegeben und ausgegeben. b, Der von AlphaDev entdeckte VarSort4-Algorithmus. Dieser Algorithmus erhält als Eingabe auch Folgen der Länge vier, drei oder zwei Zahlen. Wenn in diesem Fall die Länge zwei beträgt, wird das Sortiernetzwerk „Sort 2“ aufgerufen und zurückgegeben. Wenn die Länge drei beträgt, ruft es sort 3 auf, um die ersten drei Zahlen zu sortieren, und gibt zurück. Wenn die Länge jedoch größer als drei ist, wird Sortierung 3 aufgerufen, gefolgt von einer vereinfachten Sortierung4-Routine, die die verbleibende unsortierte Zahl sortiert. Es ist dieser Teil der Routine, der zu erheblichen Latenzeinsparungen führt.

Es ist wichtig, die Vorteile und Grenzen von RL im Vergleich zu anderen Ansätzen zur Programmoptimierung zu verstehen. Daher haben wir einen hochmodernen stochastischen Superoptimierungsansatz8 implementiert, ihn an die Sortiereinstellung angepasst und ihn als Lernalgorithmus in AlphaDev verwendet. Wir bezeichnen diese Variante als AlphaDev-S (weitere Einzelheiten finden Sie unter Methoden). Wir führen diesen Algorithmus mit mindestens der gleichen Menge an Ressourcen und der gleichen Arbeitszeit wie AlphaDev aus. AlphaDev-S erfordert eine unerschwingliche Zeit, um die Latenz direkt zu optimieren, da die Latenz nach jeder Mutation berechnet werden muss. Als solches optimiert AlphaDev-S für einen Latenz-Proxy, nämlich die Algorithmuslänge, und dann, am Ende des Trainings, durchsuchen wir alle korrekten von AlphaDev-S generierten Programme und vergleichen jedes einzelne, um die Lösung mit der niedrigsten Latenz zu finden. Im Allgemeinen stellen wir fest, dass AlphaDev AlphaDev-S durchweg übertrifft, wenn es ohne Vorkenntnisse von Grund auf lernt. Darüber hinaus erforscht AlphaDev mit zunehmender Programmgröße um Größenordnungen weniger Programme (12 Millionen Programme im schlimmsten Fall) als AlphaDev-S (31 Billionen Programme im schlimmsten Fall). Dies kann daran liegen, dass AlphaDev den Raum von Algorithmen besser erkunden kann als das stochastische Suchverfahren mit der Breitenorientierung, das leichter in lokalen Optima hängenbleibt; Einen Überblick über diese Explorationshypothese finden Sie unter Methoden. Darüber hinaus bewertet AlphaDev niemals die Latenz während der Suche, da es die Vorhersagen der Latenzwertfunktion verwendet und aus diesem Grund nur die tatsächlich gemessene Latenz bei weniger als 0,002 % der generierten Programme berechnen muss. Bei der Einbeziehung von Vorkenntnissen in AlphaDev-S, wie z. B. dem Warmstart des Lernalgorithmus mit einer nahezu optimalen Lösung, ist AlphaDev-S recheneffizienter für Sortierung 3, Sortierung 4 und Sortierung 5 (Branchless-Assembly-Algorithmen) und generiert außerdem wettbewerbsfähige Low- Latenzalgorithmen entsprechen jeweils denen von AlphaDev. Für Algorithmen, die eine Verzweigung erfordern (if–else-Anweisungen), bei denen Algorithmuslänge und Latenz nicht gut korrelieren, entdeckt AlphaDev jedoch Lösungen mit geringerer Latenz als AlphaDev-S, selbst wenn dieser Algorithmus mit einer nahezu optimalen Lösung warm gestartet wird. Eine ausführliche Analyse dieser Algorithmen finden Sie unter Methoden.

Um die Allgemeingültigkeit von AlphaDev zu testen, trainieren wir den Agenten auf einer Reihe zusätzlicher Domänen. Dazu gehören eine Unterroutine zur Protokollpuffer-Deserialisierung namens VarInt, die unten vorgestellt wird, und ein konkurrierendes Codierungsproblem (weitere Einzelheiten finden Sie in Anhang D in den Zusatzinformationen). Die Latenzleistung der wettbewerbsfähigen Codierungsdomäne ist in Tabelle 1b aufgeführt.

Protocol Buffer ist das Open-Source-Datenformat von Google, das zur Serialisierung strukturierter Daten45 verwendet wird. Dieses Format wird häufig in Fällen verwendet, in denen Leistung oder Netzwerklast im Vordergrund stehen. Der VarInt-Algorithmus46 ist eine Schlüsselkomponente sowohl im Serialisierungs- als auch im Deserialisierungsprozess. Wir haben den AlphaDev-Agenten in der Variablensortierung trainiert, um die VarInt-Deserialisierungsfunktion im Hinblick auf Korrektheit und gemessene Latenz zu optimieren. Für die Korrektheit belohnen wir den Agenten für die korrekte Deserialisierung jeder Eingabe. Wir verwenden einen Satz von 80 Eingaben und entsprechenden Ausgaben, die gängige Protobuf-Anwendungsfälle abdecken. AlphaDev lernt eine optimierte VarInt-Deserialisierungsfunktion und schafft es, den menschlichen Benchmark für einwertige Eingaben deutlich zu übertreffen. Unser Agent entdeckt eine verzweigungslose Lösung, die sowohl kürzer (Tabelle 1a) als auch etwa dreimal schneller ist als der menschliche Benchmark (Tabelle 1b). Dabei entdeckte der Agent auch eine neue VarInt-Zuweisungsmethode, bei der AlphaDev lernt, zwei Operationen in einer einzigen Anweisung zu kombinieren, was zu Latenzeinsparungen führt. Einen vollständigen Überblick über diesen Schritt finden Sie in Anhang D.1 in den Zusatzinformationen. Dies ist ein starker Hinweis darauf, dass AlphaDev in der Lage ist, nicht-triviale, reale Algorithmen zu verallgemeinern und zu optimieren.

Die Algorithmen sort 3, sort 4 und sort 5 in der Standardsortierbibliothek LLVM libc++ werden von größeren Sortieralgorithmen oft aufgerufen und sind daher grundlegende Bestandteile der Bibliothek. Wir haben die von AlphaDev für Sortierung 3, Sortierung 4 und Sortierung 5 entdeckten Low-Level-Assembly-Sortieralgorithmen in C++ zurückentwickelt und festgestellt, dass unsere Sortierimplementierungen zu Verbesserungen von bis zu 70 % für Sequenzen mit einer Länge von fünf und etwa 1,7 % für führten Sequenzen mit mehr als 250.000 Elementen. Diese Verbesserungen gelten für die Datentypen uint32, uint64 und float für ARMv8-, Intel Skylake- und AMD Zen 2-CPU-Architekturen; Die vollständigen Leistungstabellen finden Sie in Anhang E in den Zusatzinformationen. Die Leistungsverbesserungen sind sowohl auf die von AlphaDev generierte verzweigte bedingte Assembly als auch auf die neue AlphaDev-Swap-Bewegung zurückzuführen. Für Sortierung 5 verwendeten wir einen von AlphaDev entdeckten Algorithmus mit 43 Längen, da er zu einer effizienteren C++-Implementierung führte. Diese Algorithmen wurden zur Überprüfung eingesandt und offiziell in die Standardsortierbibliothek libc++3 aufgenommen. Es ist die erste Änderung dieser Unterroutinen seit über einem Jahrzehnt. Dies ist auch das erste Mal, dass eine Komponente in dieser Sortierbibliothek durch einen Algorithmus ersetzt wurde, der mithilfe von Reinforcement Learning automatisch erkannt wurde. Wir schätzen, dass diese Routinen jeden Tag Billionen Mal aufgerufen werden1,35,47.

AlphaDev entdeckt von Grund auf neue, hochmoderne Sortieralgorithmen, die in die LLVM C++-Bibliothek integriert wurden und von Millionen von Entwicklern und Anwendungen auf der ganzen Welt verwendet werden23,24,25. Sowohl AlphaDev als auch die stochastische Suche sind leistungsstarke Algorithmen. Eine interessante Richtung für zukünftige Forschung besteht darin, die Kombination dieser Algorithmen zu untersuchen, um die komplementären Vorteile beider Ansätze zu nutzen.

Es ist wichtig zu beachten, dass AlphaDev theoretisch auf Funktionen verallgemeinern kann, die keine umfassende Überprüfung von Testfällen erfordern. Beispielsweise definieren Hashing-Funktionen48 sowie kryptografische Hashing-Funktionen49 die Funktionskorrektheit durch die Anzahl der Hashing-Kollisionen. Daher kann AlphaDev in diesem Fall eine Optimierung zur Minimierung von Kollisionen und Latenz durchführen. AlphaDev kann theoretisch auch komplizierte Logikkomponenten innerhalb großer, beeindruckender Funktionen optimieren. Wir hoffen, dass AlphaDev interessante Einblicke liefern und neue Ansätze sowohl in der Künstliche-Intelligenz- als auch in der Programmsynthese-Community inspirieren kann.

AlphaZero33 ist ein RL-Algorithmus, der MCTS als Operator zur Richtlinienverbesserung nutzt. Es besteht aus (1) einem Darstellungsnetzwerk frep, das eine latente Darstellung ht des Zustands St ausgibt; und (2) ein Vorhersagenetzwerk fpred, das die erwartete Rendite (den Wert) ${\hat{v}}_{t}$ und eine Richtlinie (d. h. die Verteilung über den Aktionsraum) ${\hat {\pi }}_{t}$ aus einem gegebenen latenten Zustand. Der Algorithmus nutzt bei der Planung die wahre Dynamik und Belohnung. MuZero38 ist eine modellbasierte Variante von AlphaZero, die über dieselben Darstellungs- und Vorhersagenetzwerke verfügt, aber auch ein Modell der Dynamik lernt und Belohnungen vorhersagt, die es für die Planung verwendet. Insbesondere lernt es ein dynamisches Netzwerk fdyn, das den nächsten latenten Zustand ${{\bf{\text{h}}}}_{t}^{k+1}$ und die Belohnung ${\hat{r }}_{t}^{k+1}$ resultierend aus einem Übergang. Beachten Sie, dass der tiefgestellte Index t Zeitschritte in der realen Umgebung bezeichnet und der hochgestellte Index k Zeitschritte im Modell darstellt.

Beim Erreichen eines neuen Zustands kodiert AlphaZero zunächst den Zustand in eine latente Darstellung mit dem Darstellungsnetzwerk. Anschließend werden die wahre Dynamik oder das Dynamiknetzwerk (für MuZero) sowie das Vorhersagenetzwerk fpred(ht) verwendet, um mehrere Trajektorien zu simulieren, die einen Suchbaum ausfüllen, indem Zustandsübergänge abgetastet werden. An jedem Knoten werden die Aktionen mithilfe einer optimistischen Strategie namens „Predictor Upper Confidence Tree Bound32“ ausgewählt, die darauf abzielt, die Erforschung (Ausprobieren neuer Aktionen) und die Ausnutzung (weiter unten im Teilbaum der aktuellen Schätzung der besten Aktion voranschreiten) auszubalancieren. Diese Strategie beginnt mit der genauen Einhaltung der vorhergesagten Richtlinie ${\hat{\pi }}_{t}$ und geht dann schrittweise in Richtung Maximierung der vorhergesagten Wertfunktion über. Letztendlich wird eine Aktion durch Stichprobenentnahme vom Wurzelknoten mit einer Wahrscheinlichkeit proportional zu seiner Besuchszahl während MCTS empfohlen. Die vorhergesagte Richtlinie wird dann so trainiert, dass sie mit den Besuchszahlen der MCTS-Richtlinie übereinstimmt, um zu versuchen, das Suchverfahren in eine Richtlinie zu destillieren, sodass nachfolgende Iterationen von MCTS Knoten ignorieren, die nicht vielversprechend sind.

Sortiernetzwerke sind sehr effizient, da ihre Strukturen auf modernen CPU-Architekturen parallelisiert werden können. Daher erzielen sie tendenziell eine schnellere Laufzeitleistung, insbesondere bei kleinen Sortierungen, im Vergleich zu beliebten und effizienten Basisfallalgorithmen wie der Einfügungssortierung17,43,50. Ein Sortiernetzwerk43 besteht aus zwei Arten von Elementen, die als Komparatoren (vertikale Linien) und Drähte (horizontale Linien) bezeichnet werden (Extended Data Abb. 2a). Jeder Draht trägt einen Wert von links nach rechts. Wenn sich zwei Drähte an einem Komparator kreuzen, werden die Werte auf den beiden Drähten verglichen. Wenn der Wert des unteren Drahtes kleiner als der Wert des oberen Drahtes ist, werden die Werte zwischen den Drähten vertauscht, wie in Abb. 2b „Erweiterte Daten“ dargestellt. Eine programmatische Implementierung eines Sortiernetzwerks besteht darin, diese Austauschvorgänge für bestimmte Elementpaare aus der Eingabesequenz in einer bestimmten Reihenfolge auszuführen.

Wir haben den Aktionsraum beschnitten, indem wir einige Programminvarianzen (z. B. die Reihenfolge der Registerzuweisung) und illegale Anweisungen (z. B. den Vergleich zweier Speicherorte) entfernt haben. Dies trägt dazu bei, die Größe des Aktionsraums zu reduzieren und die Konvergenzrate zu erhöhen. Für unsere Experimente haben wir die folgenden Regeln verwendet:

Speicherorte werden immer in inkrementeller Reihenfolge gelesen.

Wir können keinen Speicherort vergleichen oder bedingt verschieben (illegal).

Wir können jeden Speicherort nur einmal lesen und beschreiben.

Wir können keine nicht initialisierten Register verwenden (illegal).

Führen Sie keine aufeinanderfolgenden Vergleichsanweisungen aus.

Wir trainieren AlphaDev auf einer Tensor Processing Unit (TPU) v.3 mit einer Gesamtstapelgröße von 1.024 pro TPU-Kern. Wir verwenden bis zu 16 TPU-Kerne und trainieren für 1 Million Iterationen. Auf der Schauspielerseite werden die Spiele auf Standalone-TPU v.4 gespielt und wir verwenden bis zu 512 Schauspieler. In der Praxis dauert das Training über alle Aufgaben hinweg im schlimmsten Fall 2 Tage, um sich anzunähern.

Es ist wichtig, die Vorteile und Grenzen von RL im Vergleich zu anderen möglichen Ansätzen zur Programmoptimierung zu verstehen. Daher haben wir einen hochmodernen stochastischen Superoptimierungsansatz8 implementiert und ihn als Lernalgorithmus zur Optimierung von Sortierfunktionen in AlphaDev integriert. Wir bezeichnen diese angepasste Version als AlphaDev-S. Unsere Neuimplementierung wurde speziell für die Sortierdomäne optimiert. Dazu gehört die Implementierung des Algorithmus zur Ausführung in unserer Assembly-Umgebung, die Definition einer Korrektheits- und Leistungsverlustfunktion speziell für die Sortierung und die Durchführung umfangreicher Hyperparameter-Sweeps, um die beste Variante zu ermitteln. Die für AlphaDev-S verwendete Kostenfunktion ist c = Korrektheit + α × Leistung, wobei Korrektheit der Berechnung der Anzahl falscher Eingabesequenzelemente entspricht, die noch unsortiert sind, Leistung der Belohnung für die Algorithmuslänge entspricht und α ein Gewicht ist, das die beiden Kosten abwägt Funktionen. Wir können die Latenz nicht direkt optimieren, da dies den Lernalgorithmus erheblich verlangsamt und das Lernen unmöglich macht. Es ist zu beachten, dass diese Funktion angepasst wurde, um denselben Satz von Assembleranweisungen zu unterstützen, der von AlphaDev verwendet wird, und um denselben Satz falscher oder illegaler Aktionen zu bereinigen. Es verwendet auch dasselbe Modul zur Berechnung der Programmkorrektheit (Abb. 2b), um den Korrektheitsterm zu berechnen.

AlphaDev-S wird dann ausgeführt, indem zunächst eine Transformation für das im Puffer gespeicherte Programm vorgeschlagen wird (der leer sein oder mit einem bereits sortierten Programm initialisiert werden kann). Die Korrektheits- und Leistungsterme werden dann mithilfe des Programmkorrektheitsmoduls bzw. der Algorithmuslänge berechnet. Wenn die Kosten niedriger sind als die aktuell besten Kosten, wird das neue Programm mit hoher Wahrscheinlichkeit akzeptiert, andernfalls wird es abgelehnt. Wir werden nun die Korrektheitskostenfunktion und die Transformationsgewichte detaillierter diskutieren.

Für die Korrektheitskostenfunktion haben wir drei Arten von Kostenfunktionen implementiert. Der erste ist als Prozentsatz der falsch platzierten Elemente definiert: $\frac{PP{C}_{t}}{P}$, wobei P die Gesamtzahl der zu platzierenden Elemente und PCt die Anzahl der richtig platzierten Elemente ist zum Zeitpunkt t. Die zweite Variante ist die Quadratwurzel dieser Gleichung. Die endgültige Kostenfunktion zieht die Quadratwurzel der Differenz $\sqrt{-{PC}_{t}}$ und liefert so die beste Leistung.

Wir haben mehrere Programmtransformationen ermöglicht, wie das Hinzufügen einer Anweisung zur Vergrößerung des Programms (Add Transform), das Austauschen zweier Anweisungen (Swap Transform), das zufällige Ändern eines Opcodes für eine Anweisung (Opcode Transform) und das zufällige Abtasten eines Operanden für eine ausgewählte Anweisung (Operandentransformation) und stichprobenartig einen Opcode und seine entsprechenden Operanden ab (Befehlstransformation). Es ist möglich, die Abtastung dieser Transformationen zu beeinflussen, um zu erreichen, dass einige davon mehr oder weniger häufig abgetastet werden. Wir haben die Gewichte für Sampling-Transformationen optimiert, indem wir einen umfangreichen Hyperparameter-Sweep durchgeführt haben.

Wir präsentieren nun eine Reihe von Untersuchungsstudien, die dabei helfen, die Vorteile und Grenzen des DRL und der in AlphaDev verwendeten stochastischen Suchlernalgorithmen besser zu verstehen. Wir vergleichen AlphaDev mit AlphaDev-S. Wir haben zwei Varianten von AlphaDev-S implementiert: (1) Kaltstart (AlphaDev-S-CS) und (2) Warmstart (AlphaDev-S-WS). AlphaDev-S-CS verwendet keine vorherigen Informationen und muss ein Programm aus einem leeren Programmpuffer generieren. Der Puffer von AlphaDev-S-WS wird mit einem korrekten Sortierprogramm (z. B. einem optimalen Sortiernetzwerk-Assembly-Programm) warmgestartet und bearbeitet das Programm, um es weiter zu optimieren. Wir haben die Varianten mit AlphaDev sowohl im individuellen als auch im variablen Sortieralgorithmus-Setup verglichen.

Da AlphaDev ohne Vorkenntnisse immer von Grund auf lernt, wäre der direkte Vergleich die Kaltstartversion der stochastischen Suche: AlphaDev-S-CS. Da jedoch manchmal erste nahezu optimale Programme verfügbar sind, vergleichen wir AlphaDev auch mit der stochastischen Warmstart-Suchversion: AlphaDev-S-WS.

Es ist zu beachten, dass die stochastischen Suchvarianten nicht in der Lage sind, die Latenz direkt zu optimieren, da dies das Lernen aufgrund der Recheneffizienz unmöglich machen würde. Daher optimieren unsere AlphaDev-S-Varianten die Algorithmuslänge. Dann, am Ende des Trainings, durchlaufen wir die Menge der generierten Programme für AlphaDev-S über verschiedene Längen und identifizieren das Programm mit der niedrigsten Latenz.

In jedem Fall werden die stochastischen Suchalgorithmen (AlphaDev-S) mit mindestens denselben Rechenressourcen und derselben Rechenzeit wie AlphaDev ausgeführt.

Wir untersuchen zunächst die Leistung der verschiedenen Ansätze für die festen Sortieralgorithmen. In diesem Fall optimieren alle Algorithmusvarianten die Algorithmuslänge, da Algorithmuslänge und Latenz in der bedingten verzweigungslosen Einstellung stark korrelieren (weitere Einzelheiten finden Sie in den Zusatzinformationen).

In der Kaltstarteinstellung ist AlphaDev-S-CS nicht in der Lage, die jeweils optimalen Programme zu finden, wie in der erweiterten Datentabelle 2a zu sehen ist. Darüber hinaus untersucht AlphaDev-S-CS um Größenordnungen mehr Programme als AlphaDev, wie in der erweiterten Datentabelle 2b gezeigt. In der Warmstarteinstellung wird AlphaDev-S mit einem nahezu optimal sortierten Programm warmgestartet und kann in jedem Fall mit der Leistung von AlphaDev mithalten, wie in der erweiterten Datentabelle 2a gezeigt. Es ist recheneffizienter als AlphaDev, wie in der erweiterten Datentabelle 2c gezeigt, untersucht aber um Größenordnungen mehr Programme für Sortierung 3 und Sortierung 5, wie in der erweiterten Datentabelle 2b gezeigt. Es kann argumentiert werden, dass AlphaDev-S-WS in diesem Szenario einen erheblichen Vorteil hat, da es mit einem anfänglichen nahezu optimalen Programm ausgestattet ist. Wir werden im Abschnitt „Variablensortierung“ zeigen, dass, wenn die Algorithmen komplizierter werden und Verzweigungen eingeführt werden, ein Warmstart des Lernalgorithmus mit einem nahezu optimalen Programm nicht ausreicht und dazu führen kann, dass er in suboptimalen Lösungen stecken bleibt.

Wir haben auch einen Brute-Force-Ansatz verwendet, um zu beweisen, dass für Sortierung 3 kein Programm existiert, das kürzer als 17 Anweisungen ist. Wir mussten ungefähr 1032 Programme aufzählen und selbst mit Pruning-Heuristiken dauerte es mehr als drei Tage, um diese Hypothese zu beweisen. Für Sortierung 4 und höher ist dieser Ansatz nicht durchführbar.

Die Länge eines Programms ist nur ein Indikator für die Leistung eines Algorithmus. Wenn wir Verzweigungsstrukturen einführen, korrelieren Länge und Latenz eines Programms nicht gut. Deshalb führen wir die Programme auf echten Maschinen aus und messen deren Latenz. Mikrobenchmarking ist angesichts der zahlreichen Rauschquellen, die die Messungen beeinflussen könnten, eine große Herausforderung. Dies gilt insbesondere bei der Ausführung auf gemeinsam genutzten Maschinen, wo es zu Störungen durch andere Prozesse kommen kann. Unser Ansatz besteht darin, über einen separaten Benchmarking-Service zu verfügen, der auf separaten Maschinen repliziert wird, sodass wir viele Messungen schnell in einer kontrollierten Umgebung unter verschiedenen Bedingungen durchführen können. Das System funktioniert wie folgt:

Der RL-Agent verarbeitet mithilfe des replizierten Dienstes 1.000 Messungen auf allen Maschinen.

Für jede Messung führt der Dienst den angegebenen Sortieralgorithmus über 10.000 zufällige Eingaben aus (für Sortierung 3 wären dies beispielsweise 3 × 10.000 = 30.000 zufällige ganze Zahlen).

Wir messen die benötigte Zeit mithilfe eines CPU-Leistungszählers (CPU_CLK_UNHALTED.CORE).

Als endgültige Messung verwenden wir dann das fünfte Perzentil, da wir davon ausgehen, dass die meisten Rauschquellen einseitig sind (z. B. Cache-Fehler, Vorabentscheidungen usw.). Während des Trainings verarbeiten wir die Messungen auf zehn Maschinen, um die Recheneffizienz zu erhöhen. Nach der Schulung vergleichen wir die Lösung von AlphaDev mit den Basislösungen und verarbeiten die Messungen auf 100 Maschinen für mehr Genauigkeit und Rauschreduzierung. Für jeden Benchmark berechnen wir Konfidenzintervalle unter Verwendung des verteilungsfreien zweiseitigen Konfidenzintervalls für eine Quantiltabellenmethode44.

Bei der direkten Optimierung der Latenz übertrifft AlphaDev AlphaDev-S-WS bei VarSort3, VarSort4 und VarSort5, wie in der erweiterten Datentabelle 3a zu sehen ist. AlphaDev-S-CS findet jeweils keine Lösung. Bei VarSort4 und VarSort5 besteht kein Zusammenhang zwischen Programmlänge und Latenz (weitere Einzelheiten finden Sie in den Zusatzinformationen). Dies weist darauf hin, dass AlphaDev im Vergleich zu AlphaDev-S Lösungen mit geringerer Latenz finden kann, wenn die Programmlänge nicht als Indikator für die Leistung verwendet werden kann. Dies gilt selbst dann, wenn die stochastische Suche mit einem nahezu optimalen Programm warm gestartet wird. Darüber hinaus konvergiert AlphaDev zur optimalen Lösung, nachdem maximal 12 Millionen Programme untersucht wurden, wie in der erweiterten Datentabelle 3b dargestellt. Dies ist um Größenordnungen niedriger als bei AlphaDev-S-CS bzw. AlphaDev-S-WS (31 Billionen Programme im schlimmsten Fall).

Wir schlugen vor, dass AlphaDev-S Schwierigkeiten hat, Programme zu entdecken, wenn es von Grund auf lernt, und beim Warmstart aufgrund seiner begrenzten Explorationsfähigkeiten aufgrund des stochastischen Suchverfahrens in lokalen Optima stecken bleibt. Erweiterte Daten Abb. 3 zeigt zweidimensionale t-stochastische Nachbareinbettungsprojektionen (t-SNE)51 der Assemblierungsalgorithmen von AlphaDev und AlphaDev-S, die während ihrer jeweiligen Trainingsverfahren für VarSort5 entdeckt wurden. Zu den in der Projektion verwendeten Merkmalen gehören Korrektheit, Latenz, Algorithmuslänge und eine Histogrammanzahl der pro Algorithmus verwendeten Anweisungen. Extended Data Abb. 3a zeigt die Regionen im Algorithmusraum, die von AlphaDev, AlphaDev-S-CS bzw. AlphaDev-S-WS untersucht werden, während Extended Data Abb. 3b die Algorithmuskorrektheit jedem Punkt in der t-SNE-Projektion überlagert, in dem die Die Farbe zeigt die Richtigkeit jedes entdeckten Algorithmus an und reicht von falschen Algorithmen (lila) bis hin zu korrekten Algorithmen (gelb). Die AlphaDev-S-Varianten decken beide einen dicht gepackten kreisförmigen Bereich um ihren ursprünglichen Startwert ab, was die Breitenorientierung ihres stochastischen Suchverfahrens unterstreicht. Dies zeigt, dass es AlphaDev-S-CS nicht gelingt, in angemessener Zeit durch den Raum falscher Algorithmen zu navigieren und die richtigen Algorithmen zu entdecken, wenn es von Grund auf lernt. Ein ähnliches Argument gilt für AlphaDev-S-WS, bei dem der Algorithmus bei der Optimierung auf der Grundlage einer bereits korrekten, aber suboptimalen Expertendemonstration auf die Erkundung seiner Umgebung ausgerichtet ist und Schwierigkeiten hat, diesen lokalen Maxima zu entgehen. Im Gegensatz dazu verfügt AlphaDev über eine vielfältigere Algorithmusraumabdeckung, da die Langzeitwertfunktion ein Leitsignal für die Entdeckung neuer und interessanter Teile des Algorithmusraums ist. Wie in Extended Data Abb. 3b zu sehen ist, ist es in der Lage, den Raum falscher Algorithmen zu verlassen, um einen neuen Raum korrekter Algorithmen zu entdecken, was die Explorationsvorteile von AlphaDev hervorhebt.

Es gibt zahlreiche Ansätze zur Optimierung von Assemblerprogrammen, die wir in drei Gruppen eingeteilt haben: enumerative Suche, stochastische Suche und symbolische Suche5.

Erstens umfassen enumerative Suchtechniken die Brute-Force-Programmaufzählung4,5,6 sowie die implizite Aufzählung unter Verwendung symbolischer Theorembeweise52,53. Diese Ansätze durchsuchen den Programmraum, um eine Lösung zu finden, die auf einem vordefinierten Satz von Programmen, Heuristiken und/oder Kostenfunktionen basiert. Diese Ansätze haben Schwierigkeiten, große Bereiche des Programmraums abzudecken, insbesondere wenn die Größe und Komplexität des Programms zunimmt.

Zweitens umgehen stochastische Suchtechniken eine umfassende Aufzählung, indem sie sich auf Stichprobenmechanismen wie Markov-Ketten-Monte-Carlo-Stichproben 5,6,8,9 stützen. Rajeev Alur et al.5 definieren eine Korrektheitsspezifikation, die durch eine logische Formel bereitgestellt wird, die Symbole aus einer Hintergrundtheorie verwendet. Das Ziel besteht dann darin, einen Implementierungsausdruck zu finden, sodass die logische Formel, die die Spezifikation definiert, gültig ist. Die Idee besteht darin, iterativ Testfälle hinzuzufügen und dann das Programm zu durchsuchen und zu erweitern, um die gegebenen Testfälle zu lösen. Sie optimieren die Korrektheit von Problemen aus dem Buch Hacker's Delight54. Phitchaya Mangpo Phothilimthana et al.6 stellen den LENS-Algorithmus vor, der auf der parallelen Ausführung einer enumerativen, stochastischen und symbolischen Suche basiert und sich dabei auf handgefertigte Bereinigungsregeln stützt. Dieses Setup ist in der Lage, bis zu 21 Anweisungen zu optimieren und kann weder die Latenz optimieren noch Verzweigungen unterstützen. Ein weiterer Algorithmus8 basiert auf der Markov-Ketten-Monte-Carlo-Ablehnungsstichprobe und wendet Transformationen auf Programme in Assembler an, indem er eine Verlustfunktion verwendet, die eine Funktion der Korrektheit und Leistung ist. Viele dieser Ansätze neigen dazu, in lokalen Mindestvorgaben steckenzubleiben und können mit zunehmender Größe und/oder Komplexität des Programms auch Probleme bereiten. Darüber hinaus ist die Einbeziehung tatsächlicher, gemessener Latenzzeiten in diese Ansätze entweder undurchführbar oder unerschwinglich teuer.

Drittens können auch symbolische Suchansätze zur Optimierung von Assemblerprogrammen eingesetzt werden. Dazu gehören SAT-Löser55, SMT-Löser5,6 und Mixed Integer Programs (MIPs)56,57. Diese Ansätze leiden jedoch unter Skalierungsproblemen. Klassische Löser erfordern beispielsweise, dass ein Problem in eine bestimmte kanonische Form übersetzt wird. Um eine effiziente Formulierung zu finden, sind in der Regel ein Experte für die genannten Lösungswege und ein erheblicher Zeitaufwand erforderlich. Darüber hinaus muss dies bei jeder neuen Änderung des Problems wiederholt werden. Klassische Löser lassen sich zudem nur schwer parallelisieren, weshalb es schwierig ist, mehr Hardware einzusetzen, um den Lösungsprozess zu beschleunigen. Ein weiterer symbolischer Suchalgorithmus ist Cholorphyll10, der einen mehrstufigen Ansatz implementiert. Als Eingabe ist zunächst ein Quellprogramm mit Partitionsanmerkungen erforderlich, die angeben, wo sich Code und Daten befinden. Anschließend ordnet ein Layout-Synthesizer Programmfragmente physischen Kernen zu, um die Rechenkosten zu minimieren. Der Code wird dann in Programmfragmente pro Kern aufgeteilt und die Programmfragmente werden in Maschinencode kompiliert. An diesem Punkt optimiert ein Superoptimierer jedes dieser Fragmente.

Verschiedene Ansätze58,59,60 wurden auch auf Sortierfunktionen angewendet, die im SIMD-Setup (Single Instruction, Multiple Data)61 ausgeführt werden. Dieses Setup ist in der Lage, die Befehlsausführung zu parallelisieren, wird jedoch derzeit in gängigen Bibliotheken wie der libc++ std::sort-Bibliothek von LLVM nicht unterstützt. Ein Beispiel ist das von Gilles Barthe et al.7, das eine Methodik zur Optimierung von Programmen durch automatische Vektorisierung von Schleifen mit SIMD-Anweisungen vorschlägt. Dies erreichen sie durch die Einführung eines Frameworks zur Überprüfung der Korrektheit von Transformationen in einem Programm und durch die Durchführung einer suchbasierten Prozedur unter Verwendung dieser Transformation. Ihr Framework kann SIMD-Schleifenstrukturen von bis zu neun Befehlen in 0,12 s erkennen, was einer mindestens zweifachen Geschwindigkeitssteigerung entspricht.

Es gibt auch mehrere Studien, in denen RL zur Programmoptimierung eingesetzt wird. Kevin Ellis et al.62 erlernen eine Richtlinien- und Wertefunktion zum Schreiben und Auswerten von Code sowie zum Durchführen einer Suchstrategie im Monte-Carlo-Stil während der Inferenz. Diese Arbeit erfordert einen Vortrainingsschritt und zielt darauf ab, korrekte Programme zu generieren, die eine vordefinierte Spezifikation erfüllen. Der Ansatz wird erfolgreich auf computergestützte Design- und String-Editing-Programme angewendet. SuperSonic63 verwendet einen RL-Meta-Optimierer, um zwischen verschiedenen RL-Architekturen auszuwählen, und verwendet eine Multi-Armed-Bandit-Richtliniensuche, um eine Zustandsdarstellung, Belohnungsfunktion und einen RL-Algorithmus zu finden, die für die aktuelle Aufgabe optimal sind. Dies erfordert die Verfolgung vieler RL-Algorithmen und -Architekturen, die als Teil des Zustandsraums verwendet werden. Im Gegensatz dazu konzentriert sich unser Ansatz nur auf das Training einer einzelnen RL-Architektur und nutzt dabei die MCTS-Suche und leistungsstarke Zustandsdarstellungen. Shypula et al.64 erstellen einen überwachten Assembly-Datensatz und trainieren damit ein Transformer-Modell für die Zuordnung von nicht optimiertem zu optimiertem Code, gefolgt von einer RL-Phase zur Verbesserung der Lösungsqualität. Unsere Methode erfordert keinen überwachten Datensatz oder zwei separate Trainings- und Feinabstimmungsphasen und optimiert stattdessen alles durchgängig mithilfe von RL und Suche. Chen et al.65 definieren ihre eigene domänenspezifische Sprache und führen eine Eingabe-Ausgabe-Programmsynthese durch, die die Zwischenprogrammdarstellung besser zur Steuerung der Syntheseroutine nutzt. Sie zeigen, dass dies mithilfe des Setups von Rudy Bunel et al.66 in RL integriert werden kann und die Korrektheit der generierten Funktionen verbessert. Sie optimieren jedoch nicht die Programmlänge oder Latenz.

Zahlreiche Arbeiten befassen sich mit dem Problem des Lernens von Programmen aus Input-Output-Paaren. Eine Art von Ansatz erlernt ein neuronales Netzwerk, um Eingaben direkt mit Ausgaben abzugleichen11,13,67,68. Dieser Ansatz lässt sich nur schwer in bestehende Bibliotheken integrieren und es kann schwierig sein, ihn auf bisher nicht sichtbare Eingaben zu übertragen, obwohl es in jüngster Zeit einige ermutigende Fortschritte bei der Verwendung von Diagrammdarstellungen gegeben hat69. Ein anderer Ansatz besteht darin, eine Suche im Programmraum durchzuführen, die von einem erlernten Modell12,70,71,72 geleitet wird. Beispielsweise verwenden Chen et al.70 ein Modell, das den nächsten Programm-Token auf der Grundlage eines Teilprogramms und der Eingabe-Ausgabe-Paare vorhersagt. Dies weist einige Ähnlichkeiten mit der Art und Weise auf, wie die Suche in unserem Ansatz gesteuert wird: Die zuvor erlernte Richtlinie in AlphaZero ist ein Modell zur Vorhersage des nächsten Tokens, das auf der Grundlage einer Kombination aus einem Teilprogramm und den Auswirkungen dieses Programms auf die Eingaben gelernt wird. Wir sind jedoch daran interessiert, korrekte und effiziente Programme zu finden, was wir erreichen, indem wir eine Wertfunktion zur Annäherung an die erwartete Latenz von Teilprogrammen weiter erlernen und diese Wertfunktion mithilfe von AlphaZero in den Suchprozess integrieren.

Es gibt auch mehrere Deep-Learning-Ansätze, die große Sprachmodelle zum Generieren von Code verwenden. Die Einsatzmöglichkeiten dieser Ansätze variieren von Transpilation, Code-Refactoring und Code-Erklärung15 bis hin zur Generierung von kompetitivem Code auf menschlicher Ebene mithilfe einer Beschreibung in natürlicher Sprache14. Diese spezielle Arbeit zielt darauf ab, korrekten Code zu generieren, konzentriert sich jedoch nicht auf die Generierung von Lösungen mit geringer Latenz.

Es gibt mehrere Studien zur Programmsynthese, die sich mit Sortieralgorithmen befassen. Beispielsweise verwenden White et al.26 RL zum Erlernen von Sortierfunktionen. Ihre Arbeit nutzt mehrere Heuristiken und eine domänenspezifische Sprache, um einen Sortieralgorithmus namens „Reinforcement Programming Sort“ zu erstellen. Srivastava et al.27 kodieren die Programmsynthese als Verifikationsproblem. Konkret stellen sie eine Syntheseaufgabe als Tupel dar, bestehend aus dem Funktionsausdruck, den im synthetisierten Programm vorkommenden Domänen und Guards und den Ressourcenbeschränkungen. Die Idee besteht darin, dass ihr Synthesizer bei einer vorgegebenen Ressourcenbeschränkung ein Programm erzeugt, das der vordefinierten Spezifikation entspricht, um die Korrektheit sicherzustellen. Sie wenden dies an, um Zusammenführungssortierung und Schnellsortierung zu ermitteln. Jason Ansel et al.28 verwenden als Eingabe vordefinierte Algorithmen (z. B. Einfügungssortierung, Zusammenführungssortierung und Schnellsortierung) und bestimmen dann mithilfe der Autotuner-Funktion, wann diese Algorithmen zur Ausführung ausgewählt werden sollen. Dies geschieht durch die Definition einer Sprache, die Regeln und Transformationen enthält, die vorgeben, wie die Algorithmen ausgewählt werden und wo sie ausgeführt werden.

Die zum Trainieren des Systems verwendeten Daten wurden gemäß den in der Arbeit erläuterten Verfahren synthetisch generiert. Die von AlphaDev entdeckten Algorithmen für die Kopier- und Swap-Operatoren werden im Hauptpapier vorgestellt. Wir haben auch die entdeckten AlphaDev-Assembly-Implementierungen für Sortierung 3–8 sowie VarSort3, 4 und 5 auf Github unter https://github.com/deepmind/alphadev veröffentlicht. Wir haben umfassende Tests integriert, um sicherzustellen, dass jede Implementierung korrekt ist. Darüber hinaus enthält Anhang G in den Zusatzinformationen eine Liste zusätzlicher, korrekter Sortieralgorithmen, die von AlphaDev für Sortierung 3, Sortierung 4 und Sortierung 5 entdeckt wurden. Die Leistung der Sortierungsalgorithmen Sortierung 3, Sortierung 4 und Sortierung 5 in der offiziellen LLVM-Benchmarking-Suite für Drei verschiedene CPU-Architekturen sowie die Datentypen float, int32 und int64 werden in Anhang E der Zusatzinformationen detailliert beschrieben. Darüber hinaus sind die AlphaDev-Implementierungen sort 3, sort 4 und sort 5 in der LLVM libc++-Standardsortierbibliothek3 zu finden.

Wir haben außerdem Pseudocode unter https://github.com/deepmind/alphadev veröffentlicht, der die Umgebung, die vollständigen Akteur- und Trainingsschleifen sowie den MCTS-Kernalgorithmus enthält. Darüber hinaus beziehen wir unsere tatsächliche JAX-Implementierung unserer Richtlinien-, Werte- und Repräsentationsnetzwerke ein, die die Reproduktion der Architekturen ermöglichen. Schließlich haben wir eine Konfigurationsdatei, die die Hyperparameterdefinitionen enthält, die mit dem Agenten verwendet werden sollen.

Amazonas. Amazon S3 – zwei Billionen Objekte, 1,1 Millionen Anfragen/Sekunde. AWS https://aws.amazon.com/blogs/aws/amazon-s3-two-trillion-objects-11-million-requests-second/ (2013).

Cormen, TH et al. Einführung in Algorithmen (MIT Press, 2022).

Gelmi, M. Einführung verzweigungsloser Sortierfunktionen für sort3, sort4 und sort5. LLVM.org https://reviews.llvm.org/D118029 (2022).

Bansal, S. & Aiken, A. Automatische Generierung von Guckloch-Superoptimierern. ACM SIGARCH Comput. Bogen. Nachrichten 34, 394–403 (2006).

Alur, R. et al. Syntaxgesteuerte Synthese (IEEE, 2013).

Phothilimthana, PM et al. Ausweitung der Superoptimierung. In Proc. Einundzwanzigste internationale Konferenz zur Architekturunterstützung für Programmiersprachen und Betriebssysteme 297–310 (ACM, 2016).

Barthe, G. et al. Von der relationalen Verifizierung bis zur SIMD-Schleifensynthese. In Proc. des 18. ACM SIGPLAN Symposiums zu Prinzipien und Praxis der parallelen Programmierung 123–134 (ACM, 2013).

Schkufza, E., Sharma, R. & Aiken, A. Stochastische Superoptimierung. ACM SIGPLAN Notices 48, 305–315 (2013).

Bunel, R. et al. Lernen, Programme zu superoptimieren. In Proc. Internationale Konferenz über lernende Repräsentationen (ICLR, 2016).

Phothilimthana, PM et al. Chlorophyll: Syntheseunterstützter Compiler für räumliche Architekturen mit geringem Stromverbrauch. ACM SIGPLAN Notices 49, 396–407 (2014).

Vinyals, O. et al. Grammatik als Fremdsprache. Adv. Neuronale Information. Proz. Syst. 28, 2773–2781 (2015).

Chen, X., Liu, C. & Song, D. Auf dem Weg zur Synthese komplexer Programme aus Eingabe-Ausgabe-Beispielen. In Proc. Internationale Konferenz über lernende Repräsentationen (ICLR, 2018).

Devlin, J. et al. Robustfill: Lernen neuronaler Programme unter verrauschter E/A. In Proc. Internationale Konferenz zum maschinellen Lernen 990–998 (PMLR, 2017).

Li, Y. et al. Codegenerierung auf Wettbewerbsniveau mit AlphaCode. Science 378, 1092–1097 (2022).

Pearce, H. et al. Können uns Codex und andere große Sprachmodelle dabei helfen, Sicherheitslücken zu beheben? Vorabdruck unter https://arxiv.org/abs/2112.02125 (2021).

Chen, M. et al. Evaluierung großer Sprachmodelle, die auf Code trainiert wurden. Vorabdruck unter https://arxiv.org/abs/2107.03374 (2021).

Bingmann, T., Marianczuk, J. & Sanders, P. Entwicklung schnellerer Sortierer für kleine Artikelmengen. Software: Praktikum. Experte 51, 965–1004 (2021).

Levcopoulos, C. & Petersson, O. Splitsort: ein adaptiver Sortieralgorithmus. Informieren. Proz. Lette. 39, 205–211 (1991).

Helman, DR, Bader, DA & JáJá, J. Ein randomisierter paralleler Sortieralgorithmus mit einer experimentellen Studie. J. Parallelverteilung Berechnen. 52, 1–23 (1998).

Goodrich, MT Randomized Shellsort: ein einfacher, ahnungsloser Sortieralgorithmus. In Proc. des einundzwanzigsten jährlichen ACM-SIAM-Symposiums zu diskreten Algorithmen 1262–1277 (ACM, 2010).

Mehlhorn, K., Sanders, P. & Sanders, P. Algorithms and Data Structures: The Basic Toolbox Vol. 55. (Springer, 2008).

Knebl, H. Algorithmen und Datenstrukturen (Springer, 2020).

Karatzoglou, A., Baltrunas, L. & Shi, Y. Lernen, für Empfehlungssysteme zu ranken. In Proc. der 7. ACM-Konferenz zu Empfehlungssystemen 493–494 (ACM, 2013).

Yang, JY, Zhang, B. & Mao, Y. Studie zum Sortieralgorithmus zum Informationsabruf in netzwerkbasierten Fertigungsumgebungen. In Applied Mechanics and Materials Vol. 484, 183–186 (Trans Tech Publishing, 2014).

Krallmann, J., Schwiegelshohn, U. & Yahyapour, R. Über den Entwurf und die Bewertung von Job-Scheduling-Algorithmen. Im Workshop zu Job Scheduling-Strategien für die Parallelverarbeitung 17–42 (Springer, 1999).

White, SK, Martinez, T. & Rudolph, G. Generieren eines neuartigen Sortieralgorithmus mithilfe von Reinforcement Programming. In Proc. IEEE Congress on Evolutionary Computation 1–8 (IEEE, 2010).

Srivastava, S., Gulwani, S. & Foster, JS Von der Programmverifizierung zur Programmsynthese. In Proc. des 37. jährlichen ACM SIGPLAN-SIGACT-Symposiums zu Prinzipien von Programmiersprachen 313–326 (ACM, 2010).

Ansel, J. et al. Petabricks: eine Sprache und ein Compiler für algorithmische Auswahl. ACM Sigplan Notices 44, 38–49 (2009).

Smith, DR Das Design von Divide-and-Conquer-Algorithmen. Wissenschaft. Berechnen. Programm. 5, 37–58 (1985).

Irvine, KR et al. Assemblersprache für Intel-basierte Computer (Prentice Hall, 2003).

Shannon, CE XXII. Einen Computer zum Schachspielen programmieren. London, Edinburg. Dublin Philos. Mag. J. Sci. 41.314, 256–275 (1950).

Silver, D. et al. Das Go-Spiel mit tiefen neuronalen Netzen und Baumsuche meistern. Natur 529, 484–489 (2016).

Silver, D. et al. Ein allgemeiner Verstärkungslernalgorithmus, der Schach, Shogi und Go durch Selbstspiel meistert. Wissenschaft 362, 1140–1144 (2018).

Vaswani, A. et al. Aufmerksamkeit ist alles, was Sie brauchen. Adv. Neuronale Information. Proz. Syst. 30, 5999–6009 (2017).

LLVM. LLVM-Benutzer https://llvm.org/Users.html (LLVM, 2022).

Bartlett, J. Lernen Sie, mit Assembly zu programmieren 271–273 (Apress, 2021).

Sutton, RS & Barto, AG Reinforcement Learning: An Introduction 2. Auflage (MIT Press, 2018).

Schrittwieser, J. et al. Beherrschen von Atari, Go, Schach und Shogi durch Planung mit einem erlernten Modell. Natur 588, 604–609 (2020).

Maillard, O.-A., Ryabko, D. & Munos, R. Auswahl der Zustandsdarstellung beim Reinforcement Learning. Adv. Neuronale Information. Proz. Syst. 24, 2627–2635 (2011).

Qian, R. et al. Lernen der räumlich-zeitlichen kontrastiven Videodarstellung. In Proc. IEEE/CVF-Konferenz zu Computer Vision und Mustererkennung 6964–6974 (IEEE, 2021).

Brown, T. et al. Sprachmodelle sind Wenig-Schuss-Lernende. Adv. Neuronale Information. Proz. Syst. 33, 1877–1901 (2020).

Shazeer, N. Schnelle Transformatordekodierung: Ein Schreibkopf ist alles, was Sie brauchen. Vorabdruck unter https://arxiv.org/abs/1911.02150 (2019).

Bundala, D. & Závodny, J. Optimale Sortiernetzwerke. In Proc. Internationale Konferenz über Sprach- und Automatentheorie und -anwendungen 236–247 (Springer, 2014).

Hahn, GJ & Meeker, WQ Statistical Intervals: A Guide for Practitioners Vol. 92 (John Wiley & Sons, 2011).

Google. Protokollpuffer, Version 0.2.5; https://developers.google.com/protocol-buffers (2022).

Google. Serialisierung und Deserialisierung des VarInt-Protokollpuffers, Version 0.2.5; https://developers.google.com/protocol-buffers/docs/encoding (2022).

Protvin, R. & Levenberg, J. Warum Google Milliarden von Codezeilen in einem einzigen Repository speichert. Komm. ACM 59, 78–87 (2016).

Berman, I. et al. Multikollisionsresistente Hash-Funktionen und ihre Anwendungen. In Proc. Jährliche internationale Konferenz über Theorie und Anwendungen kryptografischer Techniken 133–161 (Springer, 2018).

Damgård, IB Kollisionsfreie Hash-Funktionen und Public-Key-Signaturschemata. Im Workshop zur Theorie und Anwendung kryptografischer Techniken 203–216 (Springer, 1987).

Hwang, M. Sort, Bitset (GitHub, 2021).

Van der Maaten, L. & Hinton, G. Visualisieren von Daten mit t-SNE. J. Mach. Lernen. Res. 9.11, 2579–2605 (2008).

Gulwani, S. et al. Synthese schleifenfreier Programme. ACM SIGPLAN-Mitteilungen 46.6, 62–73 (2011).

Sasnauskas, R. et al. Souper: ein synthetisierender Superoptimierer. Vorabdruck unter https://arxiv.org/abs/1711.04422 (2017).

Warren, HS Hacker's Delight (Pearson Education, 2013).

Hamadi, Y., Jabbour, S. & Sais, L. ManySAT: ein paralleler SAT-Löser. J. Erfüllbarkeit, Boolesches Modell. Berechnen. 6, 245–262 (2010).

Wolsey, LA Gemischte Ganzzahlprogrammierung. In Wiley Encyclopedia of Computer Science and Engineering 1–10 (Wiley, 2007).

Nair, V. et al. Lösen gemischter ganzzahliger Programme mithilfe neuronaler Netze. Vorabdruck unter https://arxiv.org/abs/2012.13349 (2020).

Inoue, H. et al. AA-sort: ein neuer paralleler Sortieralgorithmus für Multi-Core-SIMD-Prozessoren. In Proc. Internationale Konferenz über parallele Architektur und Kompilierungstechniken (PACT 2007) 189–198 (IEEE, 2007).

Yin, Z. et al. Effiziente parallele Sortierung auf avx-512-basierten Multi-Core- und Many-Core-Architekturen. In Proc. IEEE 21. Internationale Konferenz für Hochleistungsrechnen und Kommunikation 168–176 (IEEE, 2019).

Blacher, M. et al. Vektorisierter und leistungsfähiger Quicksort. Vorabdruck unter https://arxiv.org/abs/2205.05982 (2022).

Wikipedia. Eine Anweisung, mehrere Daten https://en.m.wikipedia.org/wiki/SIMD (2022).

Ellis, K. et al. Schreiben, ausführen, bewerten: Programmsynthese mit einem REPL. Adv. Neuronale Information. Proz. Syst.32, 9137–9146 (2019).

Wang, H. et al. Automatisieren Sie das Design der Reinforcement-Learning-Architektur zur Codeoptimierung. In Proc. 31. ACM SIGPLAN International Conference on Compiler Construction 129–143 (ACM, 2022).

Shypula, AG et al. Lernen, reale Programme zu superoptimieren. Vorabdruck unter https://arxiv.org/abs/2109.13498 (2022).

Chen, X., Liu, C. & Song, D. Ausführungsgesteuerte Synthese neuronaler Programme. In Proc. Internationale Konferenz über lernende Repräsentationen (ICLR, 2018).

Bunel, R. et al. Nutzung von Grammatik und Verstärkungslernen für die Synthese neuronaler Programme. In Proc. Internationale Konferenz über lernende Repräsentationen (ICLR, 2018).

Aharoni, R. & Goldberg, Y. Auf dem Weg zur neuronalen maschinellen String-zu-Baum-Übersetzung. In Proc. 55. Jahrestagung der Association for Computational Linguistics132–140 (ACL, 2017).

Dong, L. & Lapata, M. Sprache mit neuronaler Aufmerksamkeit in logische Form bringen. In Proc. 54. Jahrestagung der Association for Computational Linguistics 33–43 (ACL, 2016).

Ibarz, B. et al. Ein generalistischer neuronaler Algorithmus-Lerner. In Proc. Learning on Graphs Conference Vol. 198, 2:1–2:23 (PMLR, 2022).

Chen, X., Song, D. & Tian, Y. Latente Ausführung für die Synthese neuronaler Programme über domänenspezifische Sprachen hinaus. Adv. Neuronale Information. Proz. Syst. 34, 22196–22208 (2021).

Parisotto, E. et al. Neurosymbolische Programmsynthese. Vorabdruck unter https://arxiv.org/abs/1611.01855 (2016).

Ellis, K., Solar-Lezama, A. & Tenenbaum, J. Sampling für Bayesianisches Programmlernen. Adv. Neuronale Information. Proz. Syst. 29, 1297–1305 (2016).

Referenzen herunterladen

Wir danken P. Kurylowicz, N. Anderson und Z. Ahmed für ihre Unterstützung bei der Koordinierung der Forschung; L. Dionne und N. Klauser für die geduldige Durchsicht unseres LLVM-Codes; und N. Vaish, D. Gove, D. Kutenin und A. Fawzi für ihre hilfreichen Ratschläge im Verlauf des Projekts. Wir danken auch unseren Kollegen bei DeepMind für ihre Ermutigung und Unterstützung.

Diese Autoren haben gleichermaßen beigetragen: Daniel J. Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent

Deepmind, London, Großbritannien

Daniel J. Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent, Shariq Iqbal, Jean-Baptiste Lespiau, Alex Ahern, Thomas Köppe, Kevin Millikin, Stephen Gaffney, Sophie Elster, Jackson Broshear, Chris Gamble, Kieran Milan, Robert Tung, Taylan Cemgil, Mohammadamin Barekatain, Yujia Li, Amol Mandhane, Thomas Hubert, Julian Schrittwieser, Demis Hassabis, Pushmeet Kohli, Martin Riedmiller, Oriol Vinyals & David Silver

Google, Mountain View, CA, USA

Minjae Hwang

Sie können diesen Autor auch in PubMed Google Scholar suchen

DJM, A.Michi und AZ hatten die Idee und leiteten die Forschung. A.Michi, DJM, AZ, MG, MS, CP, EL, SI und A.Mandhane entwickelten die Architektur und das Training des neuronalen Netzwerks. J.-BL, CP, MG, DJM und EL entwickelten die Basislinie. MG, AZ, DJM, MH, AA, TK und K. Millikin analysierten die generierten Algorithmen und halfen beim Sortier-Patch. DJM, A.Michi, AZ, SG, SE, JB, RT, CG und K.Milan leiteten die Forschung. A.Michi, MG und MS leiteten die technische Plattform. A.Mandhane, TH, YL, JS, TC, MB, PK, MR, DS, OV und DH steuerten technische Ratschläge und Ideen bei. DJM und AZ haben das Projekt konzipiert. DJM, CP, EL, A.Michi, MG, AZ, PK und MS haben den Artikel geschrieben.

Korrespondenz mit Daniel J. Mankowitz.

DJM, A.Michi, AZ, MG, MS, CP, EL, SI, A.Mandhane, PK, MR, DS und OV planen, im Namen von DeepMind Technologies eine Patentanmeldung zu den in diesem Dokument enthaltenen Themen einzureichen Begrenzt. Die übrigen Autoren erklären keine konkurrierenden Interessen.

Nature dankt Zheng Wang und den anderen, anonymen Gutachtern für ihren Beitrag zum Peer-Review dieser Arbeit.

Anmerkung des Herausgebers Springer Nature bleibt hinsichtlich der Zuständigkeitsansprüche in veröffentlichten Karten und institutionellen Zugehörigkeiten neutral.

(a) Das AlphaDev-Darstellungsnetzwerk umfasst ein Transformer-Encoder-Netzwerk, das den bisher generierten Assembler-Algorithmus als Eingabe empfängt. Es enthält außerdem ein CPU-State-Encoder-Netzwerk, das als Eingabe den aktuellen Zustand des Speichers und der Register empfängt. Die genaue Architektur und die Hyperparameter finden Sie in den Zusatzinformationen, Anhang A. (b) Vor der Eingabe von Anweisungen in das Transformer Encoder-Netzwerk werden der Opcode und die Operanden jeder Programmanweisung in One-Hot-Codierungen konvertiert und verkettet. Die resultierende Kodierung wird dann in das Transformer Encoder-Netzwerk eingespeist.

(a) Die horizontalen Linien werden Drähte genannt und die vertikalen Linien werden Komparatoren genannt. (b) Eine zunächst unsortierte Folge von Werten wird in das Sortiernetzwerk auf der linken Seite eingegeben. In verschiedenen Phasen treffen zwei Drähte auf einen Komparator. Wenn der Wert oben am Komparator kleiner ist als der Wert unten am Komparator, vertauschen die Zahlen die Leitungen. Ein optimales Sortiernetzwerk platziert Komparatoren an bestimmten Positionen, um jede Folge unsortierter Werte mit der minimalen Anzahl von Komparatoren zu sortieren.

(a) Eine 2D-t-SNE51-Projektion, die die von AlphaDev (blau) erkundeten Regionen im Vergleich zu AlphaDev-S zeigt. (b) Dieselbe 2D-t-SNE-Projektion wie in (a) mit überlagerter Algorithmuskorrektheit für jeden Punkt von falschen Programmen (lila) bis hin zu korrekten Programmen (gelb). Wie in der Abbildung zu sehen ist, hat AlphaDev-S Schwierigkeiten, aus lokalen Optima herauszukommen, wohingegen AlphaDev in der Lage ist, vom Raum falscher Programme zum Raum korrekter Programme zu gelangen.

Open Access Dieser Artikel ist unter einer Creative Commons Attribution 4.0 International License lizenziert, die die Nutzung, Weitergabe, Anpassung, Verbreitung und Reproduktion in jedem Medium oder Format erlaubt, sofern Sie den/die Originalautor(en) und die Quelle angemessen angeben. Geben Sie einen Link zur Creative Commons-Lizenz an und geben Sie an, ob Änderungen vorgenommen wurden. Die Bilder oder anderes Material Dritter in diesem Artikel sind in der Creative Commons-Lizenz des Artikels enthalten, sofern in der Quellenangabe für das Material nichts anderes angegeben ist. Wenn Material nicht in der Creative-Commons-Lizenz des Artikels enthalten ist und Ihre beabsichtigte Nutzung nicht gesetzlich zulässig ist oder über die zulässige Nutzung hinausgeht, müssen Sie die Genehmigung direkt vom Urheberrechtsinhaber einholen. Um eine Kopie dieser Lizenz anzuzeigen, besuchen Sie http://creativecommons.org/licenses/by/4.0/.

Nachdrucke und Genehmigungen

Mankowitz, DJ, Michi, A., Zhernov, A. et al. Schnellere Sortieralgorithmen mithilfe von Deep Reinforcement Learning entdeckt. Natur 618, 257–263 (2023). https://doi.org/10.1038/s41586-023-06004-9

Zitat herunterladen

Eingegangen: 25. Juli 2022

Angenommen: 23. März 2023

Veröffentlicht: 07. Juni 2023

Ausgabedatum: 08. Juni 2023

DOI: https://doi.org/10.1038/s41586-023-06004-9

Jeder, mit dem Sie den folgenden Link teilen, kann diesen Inhalt lesen:

Leider ist für diesen Artikel derzeit kein Link zum Teilen verfügbar.

Bereitgestellt von der Content-Sharing-Initiative Springer Nature SharedIt

Durch das Absenden eines Kommentars erklären Sie sich damit einverstanden, unsere Nutzungsbedingungen und Community-Richtlinien einzuhalten. Wenn Sie etwas als missbräuchlich empfinden oder etwas nicht unseren Bedingungen oder Richtlinien entspricht, kennzeichnen Sie es bitte als unangemessen.