KI-System sorgt seit über einem Jahrzehnt für erste Verbesserungen bei der Codesortierung – Ars Technica

Zweifellos hat jeder, der grundlegende Informatik studiert hat, Zeit damit verbracht, einen Sortieralgorithmus zu entwickeln – einen Code, der eine ungeordnete Liste von Elementen nimmt und sie in aufsteigender oder absteigender Reihenfolge anordnet. Es ist eine interessante Herausforderung, weil es so viele Möglichkeiten gibt, dies zu tun, und weil die Leute viel Zeit damit verbracht haben, herauszufinden, wie diese Sortierung so effizient wie möglich durchgeführt werden kann.

Sortieren ist so einfach, dass die Algorithmen in die meisten Standardbibliotheken von Programmiersprachen integriert sind. Und im Fall der C++-Bibliothek, die mit dem LLVM-Compiler verwendet wird, wurde der Code seit über einem Jahrzehnt nicht berührt.

Aber Googles DeepMind AI-Gruppe hat jetzt ein Reinforcement-Learning-Tool entwickelt, das hochoptimierte Algorithmen entwickeln kann, ohne zuvor an menschlichen Codebeispielen trainiert zu werden. Der Trick bestand darin, ihn darauf vorzubereiten, Programmieren als Spiel zu betrachten.

Es ist alles ein Spiel

DeepMind ist unter anderem dafür bekannt, Software zu entwickeln, die sich das Spielen von Spielen selbst beibringt. Dieser Ansatz hat sich als äußerst effektiv erwiesen und so unterschiedliche Spiele wie Schach, GehenUnd Sternen Schiff. Während die Details je nach Spiel variieren, lernt das Programm durch das Spielen selbst und entdeckt Optionen, die es ihm ermöglichen, die Punktzahl zu maximieren.

Da das DeepMind-System nicht auf von Menschen gespielte Spiele trainiert wurde, kann es Wege finden, Spiele zu spielen, an die Menschen nicht gedacht haben. Da es immer gegen sich selbst spielt, gibt es natürlich Fälle, in denen es blinde Flecken entwickelt hat, die der Mensch ausnutzen kann.

Dieser Ansatz ist für die Programmierung sehr relevant. Große Sprachparadigmen schreiben effizienten Code, weil sie viele menschliche Beispiele gesehen haben. Aus diesem Grund ist es jedoch sehr unwahrscheinlich, dass sie etwas entwickeln, was Menschen zuvor nicht getan haben. Wenn wir gut verstandene Algorithmen wie Sortierfunktionen verbessern möchten, erhalten wir im besten Fall eine gleichwertige Leistung, wenn wir etwas auf vorhandenen menschlichen Code basieren. Doch wie bringt man eine KI dazu, wirklich einen neuen Ansatz zu wählen?

Die Leute bei DeepMind haben den gleichen Ansatz gewählt wie beim Schach und Gehen: Sie haben die Codeoptimierung in ein Spiel verwandelt. Das AlphaDev-System entwickelte x86-Kompilierungsalgorithmen, die die Codelatenz als Treffer behandelten und versuchten, diesen Treffer zu minimieren und gleichzeitig sicherzustellen, dass der Code fehlerfrei ausgeführt wurde. Durch verstärkendes Lernen entwickelt AlphaDev nach und nach die Fähigkeit, hocheffizienten und robusten Code zu schreiben.

In AlphaDev

Zu sagen, dass das System die Latenz verbessert, ist etwas ganz anderes als zu erklären, wie es funktioniert. Wie die meisten anderen komplexen KI-Systeme besteht AlphaDev aus mehreren unterschiedlichen Komponenten. Eine davon ist die Darstellungsfunktion, die die Gesamtleistung des Codes während seiner Entwicklung verfolgt. Dazu gehört die Gesamtstruktur des Algorithmus sowie die Verwendung von x86-Registern und Speicher.

Das System fügt Montageanleitungen individuell hinzu, ausgewählt von a Finden Sie den Monte-Carlo-Baum– wiederum ein Ansatz, der von Gaming-Systemen übernommen wurde. Der „Baum“-Aspekt dieses Ansatzes ermöglicht es dem System, aus einer großen Auswahl möglicher Anweisungen schnell einen begrenzten Bereich einzugrenzen, während Monte Carlo den genauen Anweisungen, die aus diesem Zweig ausgewählt werden, ein gewisses Maß an Zufälligkeit hinzufügt. (Beachten Sie, dass „Hilfe“ in diesem Zusammenhang Dinge wie die spezifischen Datensätze umfasst, die zum Erstellen einer gültigen, vollständigen Baugruppe ausgewählt wurden.)

Das System bewertet dann den Status des Assemblercodes auf Latenz und Gültigkeit, weist ihm eine Bewertung zu und vergleicht diese mit der Bewertung der vorherigen Bewertung. Und durch verstärkendes Lernen werden Informationen darüber verknüpft, wie die verschiedenen Zweige des Baums angesichts des Status des Programms funktionieren. Mit der Zeit „lernen“ Sie, wie Sie mit maximaler Punktzahl, also minimaler Latenz, einen erfolgreichen Spielzustand (Sortierung abgeschlossen) erreichen.

Der Hauptvorteil dieses Systems besteht darin, dass für die Schulung keine Codebeispiele erforderlich sind. Stattdessen generiert das System eigene Codebeispiele und wertet diese anschließend aus. Dabei werden Informationen darüber aufgehängt, welche Befehlssätze bei der Sortierung wirksam sind.

Nützlicher Code

Durch die Sortierung in komplexen Programmen können große, beliebige Gruppen von Elementen verarbeitet werden. Auf der Ebene der Standardbibliotheken bestehen sie jedoch aus einer großen Menge sehr spezifischer Funktionen, die nur eine Situation oder wenige Fälle behandeln. Beispielsweise gibt es separate Algorithmen zum Sortieren von drei Artikeln, vier Artikeln und fünf Artikeln. Und es gibt einen weiteren Satz von Funktionen, die eine beliebige Anzahl von Elementen bis zu einem Maximum verarbeiten können – das heißt, Sie können eine Funktion aufrufen, die bis zu vier Elemente sortiert, aber nicht mehr.

DeepMind hat AlphaDev auf jede dieser Funktionen festgelegt, sie funktionieren jedoch sehr unterschiedlich. Für Funktionen, die eine bestimmte Anzahl von Elementen verarbeiten, ist es möglich, Code ohne Verzweigungen zu schreiben, wobei je nach Status der Variablen unterschiedlicher Code ausgeführt wird. Daher ist die Leistung dieses Codes im Allgemeinen proportional zur Anzahl der erforderlichen Anweisungen. AlphaDev war in der Lage, alle Sort-3-, Sort-5- und Sort-8-Anweisungen sowie noch mehr Sort-6- und Sort-7-Anweisungen zu kürzen. Es gab nur einen (Rang 4), bei dem er keine Möglichkeit fand, den menschlichen Code zu verbessern. Die wiederholte Ausführung des Codes auf tatsächlichen Systemen zeigte, dass weniger Anweisungen zu einer besseren Leistung führten.

Das Sortieren einer variablen Anzahl von Einträgen erfordert Verzweigungen im Code, und verschiedene Prozessoren verfügen über unterschiedlich viel Hardware für die Verarbeitung dieser Verzweigungen. Daher wurde der Code anhand seiner Leistung auf 100 verschiedenen Geräten bewertet. Auch hier hat AlphaDev Möglichkeiten gefunden, zusätzliche Leistung zu erzielen, und wir werfen einen Blick darauf, wie das in einer Situation geht: einer Funktion, die bis zu vier Elemente sortiert.

In der aktuellen Implementierung in der C++-Bibliothek führt der Code eine Reihe von Tests durch, um zu sehen, wie viele Elemente sortiert werden müssen, und ruft die benutzerdefinierte Sortierfunktion für diese Anzahl von Elementen auf. Der überarbeitete Code macht etwas noch Seltsameres. Testet, ob zwei Elemente vorhanden sind, und ruft bei Bedarf eine separate Funktion auf, um sie zu sortieren. Wenn die Anzahl größer als zwei ist, ruft der Code auf, die ersten drei zu sortieren. Wenn drei Elemente vorhanden sind, werden die Ergebnisse dieser Sortierung zurückgegeben.

Wenn jedoch vier Elemente sortiert werden müssen, wird spezieller Code ausgeführt, der sehr effizient ein viertes Element an der entsprechenden Stelle innerhalb eines Arrays aus drei sortierten Elementen einfügt. Dies scheint ein seltsamer Ansatz zu sein, aber er hat meinen vorhandenen Code durchweg übertroffen.

in Produktion

Da AlphaDev effizienteren Code produzierte, wollte das Team ihn wieder in die LLVM-Standard-C++-Bibliothek integrieren. Das Problem hierbei ist, dass der Code in Assembler und nicht in C++ war. Sie mussten also rückwärts arbeiten und herausfinden, welcher C++-Code dieselbe Assembly erzeugen würde. Sobald dies erledigt war, wurde der Code in die LLVM-Toolchain integriert – das erste Mal seit über einem Jahrzehnt, dass ein Teil des Codes geändert wurde.

Infolgedessen haben Forscher geschätzt, dass AlphaDev-Code mittlerweile Billionen Mal am Tag ausgeführt wird.

Natur, 2023. DOI: 10.1038 / s41586-023-06004-9 (über DOIs).