KI schreibt den Sortieralgorithmus neu und ist 70 % schneller: DeepMind AlphaDev erneuert die Computergrundlage und aktualisiert die Bibliothek, die Billionen Mal am Tag aufgerufen wird

„Durch das Vertauschen und Kopieren überspringt AlphaDev einen Schritt und verbindet Elemente auf eine Art und Weise, die falsch erscheint, in Wirklichkeit aber eine Abkürzung ist.“

Vor sieben Jahren besiegte AlphaGo den menschlichen Weltmeister im Go, und jetzt hat uns die KI eine weitere Lektion in Sachen Programmierung erteilt.

Am frühen Morgen brachten zwei Sätze von Hassabis, CEO von Google DeepMind, die Computerwelt zur Explosion: „AlphaDev hat einen neuen und schnelleren Sortieralgorithmus entdeckt, und wir haben ihn als Open-Source-Lösung in die Hauptbibliothek von C++ für Entwickler integriert. Das ist genau das.“ Der Beginn der Fortschritte der KI bei der Verbesserung der Code-Effizienz. Dieses Mal hat das neue Reinforcement-Learning-System AlphaDev einen Hashing-Algorithmus entdeckt, der schneller als je zuvor ist. Die Ergebnisse der KI wurden nun in den LLVM-Standard C++ integriert Bibliothek Abseil und Open Source.

Wie wichtig ist dieses Ergebnis? „Wir schätzen, dass die von ihm entdeckten Sortier- und Hashing-Algorithmen jeden Tag auf der ganzen Welt Billionen Mal aufgerufen werden“, sagte Daniel J. Mankowitz, einer der Hauptautoren von AlphaDev und Forschungswissenschaftler bei Google DeepMind.

KI scheint schneller zu werden die Welt auf algorithmischer Ebene.

Diese Algorithmen verbessern die Sortierbibliothek LLVM libc++, die bei kürzeren Sequenzen 70 % schneller und bei Sequenzen mit mehr als 250.000 Elementen etwa 1,7 % schneller ist. Laut Google DeepMind ist dies die erste Änderung an diesem Teil der Sequenzierungsbibliothek seit mehr als einem Jahrzehnt. Es scheint, dass KI jetzt nicht nur Menschen beim Schreiben von Code helfen kann, sondern auch uns dabei helfen kann, besseren Code zu schreiben.

Im neuesten Blog stellten die Autoren des neuen Systems AlphaDev ausführlich vor.

Neue Algorithmen werden die Grundlagen der Datenverarbeitung verändern.

Die digitale Gesellschaft treibt den wachsenden Bedarf an Datenverarbeitung und Energie voran. In den letzten fünfzig Jahren war das digitale Zeitalter auf Verbesserungen der Hardware angewiesen, um mit der Nachfrage Schritt zu halten. Da Mikrochips jedoch an ihre physikalischen Grenzen stoßen, wird die Verbesserung des darauf ausgeführten Codes von entscheidender Bedeutung. Dies ist besonders wichtig für Algorithmen, die im Code enthalten sind und jeden Tag Billionen Mal ausgeführt werden.

Diese Forschung von Google DeepMind ist daraus entstanden. Das entsprechende Papier wurde in „Nature“ veröffentlicht. AlphaDev ist ein KI-System, das Reinforcement Learning nutzt, um Algorithmen zu entdecken, die sogar das übertreffen, was Wissenschaftler und Ingenieure seit Jahrzehnten verfeinert haben. Ergebnisse.

Papieradresse: https://www.nature.com/articles/s41586-023-06004-9

Im Allgemeinen hat AlphaDev einen schnelleren Sortieralgorithmus gefunden. Obwohl Milliarden von Menschen diese Algorithmen täglich nutzen, erkennt niemand, dass es Raum für Verbesserungen gibt. Sortieralgorithmen werden in einer Vielzahl von Anwendungen eingesetzt, von Online-Suchergebnissen über das Sortieren von Social-Media-Beiträgen bis hin zu verschiedenen Datenverarbeitungsvorgängen auf Computern und Mobiltelefonen, die alle untrennbar mit Sortieralgorithmen verbunden sind. Der Einsatz von KI zur Generierung besserer Algorithmen wird die Art und Weise, wie Menschen Computer programmieren, verändern und erhebliche Auswirkungen auf eine zunehmend digitale Gesellschaft haben.

Durch die Open-Source-Bereitstellung des neuen Sortieralgorithmus in einer großen C++-Bibliothek können Millionen von Entwicklern und Unternehmen auf der ganzen Welt ihn jetzt in KI-Anwendungen in einer Vielzahl von Branchen verwenden, darunter Cloud Computing, Online-Shopping und Lieferkette Management. Dies ist die erste Änderung an der Ranking-Bibliothek seit mehr als einem Jahrzehnt und das erste Mal, dass der Bibliothek Algorithmen hinzugefügt wurden, die mit Reinforcement Learning entwickelt wurden. Betrachten Sie dies als einen wichtigen Meilenstein bei der Nutzung künstlicher Intelligenz zur schrittweisen Optimierung des weltweiten Codes.

Über das Sortieren

Ein Sortieralgorithmus ist eine Methode, um bestimmte Aufgaben in einer bestimmten Reihenfolge anzuordnen. Sortieren Sie beispielsweise drei Buchstaben alphabetisch, ordnen Sie fünf Zahlen vom größten zum kleinsten oder sortieren Sie eine Datenbank mit Millionen von Datensätzen.

Diesen Algorithmus gibt es schon seit langer Zeit und er hat sich gut weiterentwickelt. Eines der frühesten Beispiele für Ordnung geht auf das 2. und 3. Jahrhundert n. Chr. zurück, als Gelehrte in den Regalen der Bibliothek von Alexandria Tausende von Büchern von Hand alphabetisch ordneten. Mit dem Aufkommen der industriellen Revolution kamen Maschinen auf den Markt, die den Menschen beim Sortieren helfen konnten. Tabellierungsmaschinen speicherten Informationen mithilfe von Lochkarten, mit denen die Ergebnisse der US-Volkszählung von 1890 erfasst wurden.

Mit dem Aufkommen kommerzieller Computer in den 1950er Jahren begannen sich die ersten Informatikalgorithmen für Sortieralgorithmen zu entwickeln. Heutzutage werden in Codebasen auf der ganzen Welt viele verschiedene Sortiertechniken und Algorithmen verwendet, um riesige Mengen an Online-Daten zu verarbeiten.

Geben Sie eine Reihe unsortierter Zahlen in den Algorithmus ein und geben Sie sortierte Zahlen aus.

Nach jahrzehntelanger Forschung von Informatikern und Programmierern ist der aktuelle Sortieralgorithmus bereits so effizient, dass es schwierig ist, weitere Verbesserungen zu erzielen. Es ähnelt in gewisser Weise dem Versuch, einen neuen Weg zu finden, um Strom zu sparen oder ihn effizienter zu machen Methoden, und diese Algorithmen sind auch der Grundstein der Informatik.

Erkunden Sie neue Algorithmen: Montageanleitungen

AlphaDev erforscht schnellere Algorithmen von Grund auf, anstatt auf vorhandenen Algorithmen zu basieren. Darüber hinaus kann AlphaDev auch verwendet werden, um Bereiche zu finden, mit denen die meisten Menschen nicht zu tun haben: Montageanleitungen für Computer.

Assembly-Anweisungen können verwendet werden, um Binärcode zu erstellen, den ein Computer ausführt. Entwickler schreiben Code in einer höheren Sprache wie C++, müssen ihn jedoch in Assembleranweisungen auf „niedriger Ebene“ umwandeln, die der Computer versteht.

Google DeepMind glaubt, dass es auf dieser Ebene viel Raum für Verbesserungen gibt, die in höheren Programmiersprachen möglicherweise schwer zu erkennen sind. Auf dieser Ebene sind Computer hinsichtlich Speicher und Betrieb flexibler, was bedeutet, dass es mehr potenzielle Verbesserungsmöglichkeiten gibt, die sich stärker auf Geschwindigkeit und Energieverbrauch auswirken könnten.

Code wird normalerweise in einer höheren Programmiersprache wie C++ geschrieben. Der Compiler wandelt diese dann in Low-Level-CPU-Anweisungen, sogenannte Assembler-Anweisungen, um. Der Assembler wandelt Montageanweisungen in ausführbaren Maschinencode um, damit der Computer ihn ausführen kann.

Abbildung A: Beispiel eines C++-Algorithmus, der bis zu zwei Elemente sortiert; Abbildung B: Entsprechende Assembly-Darstellung.

Mit der Methode von AlphaGo den besten Algorithmus finden

AlphaDev basiert auf einem früheren Ergebnis von Google DeepMind: AlphaZero, einem Reinforcement-Learning-Modell, das den Weltmeister in Spielen wie Go, Schach und Schach besiegte. Und AlphaDev zeigt, wie dieses Modell von Spielen auf wissenschaftliche Herausforderungen und von Simulationen auf reale Anwendungen übertragen werden kann.

Um AlphaDev darin zu trainieren, neue Algorithmen zu entdecken, verwandelte das Team das Sortieren in ein „Assembly-Spiel“ für Einzelspieler. Bei jeder Runde beobachtet AlphaDev den von ihm erzeugten Algorithmus und die in der CPU enthaltenen Informationen und unternimmt dann den nächsten Schritt, indem es eine Anweisung auswählt, die dem Algorithmus hinzugefügt werden soll.

Assembly-Spiele sind sehr schwierig, da AlphaDev eine große Anzahl möglicher Befehlskombinationen effizient durchsuchen muss, um einen Algorithmus zu finden, der sortieren kann und schneller als der derzeit beste Algorithmus ist. Die Anzahl der möglichen Kombinationen von Anweisungen ist ähnlich der Anzahl der Teilchen im Universum oder der Anzahl möglicher Kombinationen von Zügen im Schach (10^120 Spiele) und Go (10^700 Spiele), und ein falscher Zug kann zum Untergang führen der gesamte Algorithmus.

Bild A: Montagespiel. Der Spieler AlphaDev erhält als Eingabe den Status des Systems st und spielt Schach, indem er eine Assembleranweisung auswählt, die er dem aktuell generierten Algorithmus hinzufügen möchte. Abbildung B: Belohnungsberechnung. Nach jeder Bewegung wird dem resultierenden Algorithmus eine Testeingabesequenz zugeführt – für sort3 entspricht dies allen Kombinationen von drei Elementsequenzen. Der Algorithmus erzeugt dann eine Ausgabe, die mit der erwarteten Ausgabe der sortierten Sequenz angesichts der Sortiersituation verglichen wird. Agenten werden basierend auf der Korrektheit und Latenz des Algorithmus belohnt.

Beim Erstellen eines Algorithmus, eine Anweisung nach der anderen, prüft AlphaDev, ob die Ausgabe des Algorithmus korrekt ist, indem sie sie mit dem erwarteten Ergebnis vergleicht. Für einen Sortieralgorithmus bedeutet dies, dass ungeordnete Zahlen hineingehen und korrekt sortierte Zahlen herauskommen. Das Team belohnt AlphaDev für das korrekte Sortieren von Zahlen sowie für die Geschwindigkeit und Effizienz der Sortierung, und AlphaDev gewinnt dann das Spiel, indem es das richtige, schnellere Programm entdeckt.

Es wurden schnellere Sortieralgorithmen entdeckt

AlphaDev hat neue Sortieralgorithmen entdeckt, die zu Verbesserungen der LLVM libc++-Sortierbibliothek führten: Bei kürzeren Sequenzen ist die Sortierbibliothek 70 % schneller, bei Sequenzen mit mehr als 250.000 Elementen die Geschwindigkeit wird um ca. 1,7 % erhöht.

Unter anderem konzentriert sich das Google DeepMind-Team mehr auf die Verbesserung des Kurzsequenz-Sortieralgorithmus von drei bis fünf Elementen. Diese Algorithmen gehören zu den am weitesten verbreiteten, da sie im Rahmen einer größeren Sortierfunktion häufig mehrmals aufgerufen werden. Durch die Verbesserung dieser Algorithmen kann die Gesamtgeschwindigkeit beim Sortieren einer beliebigen Anzahl von Elementen erhöht werden.

Um die neuen Sortieralgorithmen für Menschen nützlicher zu machen, hat das Team die Algorithmen rückentwickelt und in C++ übersetzt, eine der beliebtesten Programmiersprachen, die von Entwicklern verwendet wird.

Derzeit werden diese Algorithmen in der LLVM libc++-Standardsortierbibliothek (https://reviews.llvm.org/D118029) bereitgestellt und von Millionen von Entwicklern und Unternehmen auf der ganzen Welt verwendet.

„Tausch- und Kopieraktionen“, die Hand Gottes erscheint wieder?

Tatsächlich hat AlphaDev nicht nur schnellere Algorithmen entdeckt, sondern auch neue Methoden. Sein Sortieralgorithmus besteht aus einer neuen Folge von Anweisungen, die bei jeder Anwendung eine Anweisung speichert – was offensichtlich enorme Auswirkungen hat, da diese Algorithmen jeden Tag Billionen Mal verwendet werden. Sie nennen diese „AlphaDev-Austausch- und Kopieraktionen“.

Dieser neuartige Ansatz erinnert an „Step 37“ von AlphaGo – ein kontraintuitiver Zug, der die Zuschauer verblüffte und zur Niederlage des legendären Go-Spielers Lee Sedol führte. Durch das Austauschen und Kopieren von Aktionen überspringt AlphaDev einen Schritt und verbindet Elemente auf eine Weise, die wie ein Fehler aussieht, in Wirklichkeit aber eine Abkürzung ist. Dies zeigt die Fähigkeit von AlphaDev, originelle Lösungen zu entdecken und die Art und Weise, wie Menschen über die Verbesserung von Informatikalgorithmen denken, in Frage zu stellen.

Links: min (A,B,C) ursprüngliche sort3-Implementierung; rechts: AlphaDev-Swap-Verschiebung – AlphaDev hat festgestellt, dass Sie nur min (A,B) benötigen.

Links: Ursprüngliche Implementierung mit max(B,min(A,C,D)) in einem größeren Sortieralgorithmus zum Sortieren von acht Elementen; Rechts: AlphaDev hat festgestellt, dass bei Verwendung seiner Kopieraktion nur max(B,min(A ,C)) ist erforderlich.

Skalierungsfähigkeitstest: Von „Sortieren“ zu „Hash“

Nachdem das Team einen schnelleren Sortieralgorithmus entdeckt hatte, testete es, ob AlphaDev einen anderen Informatikalgorithmus verallgemeinern und verbessern konnte: Hashing.

Hashing ist ein grundlegender Algorithmus, der in der Informatik zum Abrufen, Speichern und Komprimieren von Daten verwendet wird. Genau wie ein Bibliothekar, der ein Klassifizierungssystem verwendet, um ein bestimmtes Buch zu finden, helfen Hashing-Algorithmen den Benutzern dabei, zu wissen, wonach sie suchen und wo sie es finden können. Diese Algorithmen nehmen Daten für einen bestimmten Schlüssel (z. B. Benutzername „Jane Doe“) und hashen sie – ein Prozess, der die Rohdaten in eine eindeutige Zeichenfolge (z. B. 1234ghfty) umwandelt. Der Computer verwendet diesen Hash, um schnell Daten zum Schlüssel abzurufen, anstatt alle Daten zu durchsuchen.

Das Team wandte AlphaDev auf einen der am häufigsten verwendeten Hashing-Algorithmen in Datenstrukturen an, um einen schnelleren Algorithmus zu finden. Bei der Anwendung auf Hash-Funktionen im 9-16-Byte-Bereich stellte AlphaDev eine Verbesserung der Algorithmusgeschwindigkeit um 30 % fest.

In diesem Jahr wurde der neue Hashing-Algorithmus von AlphaDev in der Open-Source-Bibliothek Abseil veröffentlicht und steht damit Millionen von Entwicklern auf der ganzen Welt zur Verfügung, wo er mittlerweile wahrscheinlich Billionen Mal am Tag verwendet wird.

Open-Source-Adresse: https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e

Fazit

Google DeepMind verbessert die Sortierung und haha ​​Optimierung und Einführung des verfügbaren Hash-Algorithmus Die Welt AlphaDev wird von Entwicklern verwendet und demonstriert seine Fähigkeit, neue Algorithmen mit Auswirkungen auf die reale Welt zu verallgemeinern und zu entdecken. AlphaDev kann als Schritt zur Entwicklung universeller KI-Tools angesehen werden, die dazu beitragen können, das gesamte Computerökosystem zu optimieren und andere Probleme zum Wohle der Gesellschaft zu lösen.

Während die Optimierung im Low-Level-Assembly-Anweisungsraum sehr leistungsfähig ist, weist AlphaDev immer noch Einschränkungen auf, wenn die Algorithmen wachsen, und das Team erforscht derzeit seine Fähigkeit, Algorithmen direkt in High-Level-Sprachen wie C++ zu optimieren nützlich für Nützlicher für Entwickler.

Die Entdeckungen von AlphaDev, wie z. B. Swap- und Copy-Aktionen, zeigen, dass es nicht nur Algorithmen verbessern, sondern auch neue Lösungen finden kann. Diese Erkenntnisse könnten Forscher und Entwickler dazu inspirieren, Technologien und Methoden zu entwickeln, die die zugrunde liegenden Algorithmen weiter optimieren können, um ein robusteres und nachhaltigeres Computer-Ökosystem zu schaffen.

Das obige ist der detaillierte Inhalt vonKI schreibt den Sortieralgorithmus neu und ist 70 % schneller: DeepMind AlphaDev erneuert die Computergrundlage und aktualisiert die Bibliothek, die Billionen Mal am Tag aufgerufen wird. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!