Auf dem Weg zu einer besseren Zukunft für intelligente Compiler

Jetzt ist das Thema maschinelles Lernen und künstliche Intelligenz derzeit äußerst beliebt. Dank der Rechenleistung von Computern können Ideen und Algorithmen, die seit langem entstanden sind, implementiert und erheblich verbessert werden. Fast jeden Tag können Sie Nachrichten über neue Erfolge in diesem Bereich lesen. Darüber hinaus wird maschinelles Lernen in fast allen Bereichen eingesetzt ... und die Entwicklung von Compilern ist keine Ausnahme. Das Gebiet ist jedoch sehr spezifisch und hat seine eigenen Merkmale und Schwierigkeiten bei der Erstellung intelligenter Compiler. Gleichzeitig gibt es viele Studien zu diesem Thema, die seit langem sowohl im akademischen Umfeld als auch in verschiedenen Unternehmen durchgeführt werden.

Wo genau wird versucht, beim Erstellen von Compilern Methoden des maschinellen Lernens anzuwenden? Und warum sind die „intelligenten“ Compiler bisher nicht Teil des täglichen Lebens des Entwicklers geworden?

Optionen für die Verwendung von maschinellem Lernen in der Compilerentwicklung

Beginnen wir mit der ersten Frage zu bestimmten Anwendungen des maschinellen Lernens. Tatsache ist, dass moderne Compiler komplexe Systeme mit einer Vielzahl von Optimierungen sind, mit denen Sie effizienteren Maschinencode erhalten. Einige der Optimierungen und andere Aufgaben, wie z. B. die Registerzuordnung, sind jedoch NP-vollständig, was Compilerentwickler dazu zwingt, heuristische Algorithmen zu verwenden. Infolgedessen verfügen die meisten Compiler über eine große Anzahl von Optimierungsflags, mit denen Sie die verwendeten Heuristiken konfigurieren können. In LLVM verfügt fast jede Passage über mehrere versteckte Optionen, die sich auf den Betrieb auswirken können. Sie können entweder mit dem Flag –mllvm beim Aufrufen von clang oder im Dienstprogramm opt verwendet werden. Diese Vielzahl von Flags verbirgt sich jedoch hinter den viel häufiger verwendeten Optionen, die viele Einstellungen gleichzeitig enthalten und normalerweise als Optimierungsstufen bezeichnet werden. Für C / C ++ - Compiler sind diese den meisten -O1, -O2, -O3 zur Optimierung der Laufzeit und -Os zur Optimierung der Codegröße bekannt. Leider ist der optimale Code nicht immer das Ergebnis (Assembler-Experten können den generierten Code optimal umschreiben). Viel hängt vom Quellcode in einer Hochsprache, der Prozessorarchitektur, den Sprachfunktionen usw. ab.

Trotz der Tatsache, dass moderne Prozessoren heute über genügend RAM und eine recht hohe Leistung verfügen, gibt es immer noch Bereiche, in denen Anwendungsleistung, Energieeffizienz und Maschinencodegröße eine Schlüsselrolle spielen. Beispiele für solche Bereiche umfassen Softwareentwicklung für eingebettete Systeme mit einer begrenzten Menge an RAM, digitale Signalverarbeitung, Echtzeitsysteme usw. In Fällen, in denen Sie leistungsstarken Maschinencode für ausreichend große Systeme benötigen, ist die Auswahl der richtigen Kompilierungsoptionen, die das beste Ergebnis liefern, eine wichtige Aufgabe. Darüber hinaus ist das Worst- Case -Laufzeitproblem ( WCET ) nicht verschwunden, wenn Echtzeitsysteme die Ausführungszeit einer bestimmten Aufgabe auf der Plattform berechnen und nach Möglichkeit minimieren müssen. Bisher können sich Programmierer, die mit Systemen mit begrenztem RAM arbeiten, nicht vollständig auf Compiler verlassen und optimieren den generierten Maschinencode häufig unabhängig voneinander.

Für eine Person ist es schwierig vorherzusagen, welche Optimierungen zu einem guten Ergebnis führen und welche zu Regressionen führen können, da Sie hierfür ein gutes Verständnis der Feinheiten der verwendeten heuristischen Algorithmen, eine gute Kenntnis der Struktur und der Passagen des verwendeten Compilers sowie eine vollständige Kenntnis des Codes des kompilierten Programms benötigen Der aktuelle Anwendungsentwicklungsprozess ist nicht möglich. Infolgedessen wird das Identifizieren der besten Kompilierungsoptionen für ein Programm für eine Person zu einer Aufgabe der umfassenden Suche nach verschiedenen Kombinationen von Optionen und Messungen der Leistung und der Codegrößen.

Darüber hinaus gibt es eine Einschränkung in Form einer Kompilierungseinheit, mit der Sie arbeiten und für die Sie Optionen auswählen können. Für C / C ++ ist dies also immer noch eine Datei, die viel Code enthalten kann. Vielleicht wäre es nützlich, sie auf verschiedene Arten zu optimieren, aber im Moment ist dies nicht möglich. Daher ist ein „intelligenter“ Compiler, der Code trainieren und dann für eine Vielzahl von Fällen gut optimieren kann, für einige Entwickler ein Traum.

Bestehende Forschung und Lösungen

Natürlich ist das Problem der automatisierten Auswahl von Kompilierungsoptionen für Forscher seit vielen Jahren von Interesse. Eines der bekanntesten Projekte ist die Entwicklung von G. Fursin und Forschern aus seinem MILEPOST GCC- Team, einer Version des gcc-Compilers, der Optimierungsdurchläufe auf der Grundlage vorheriger Schulungen anhand der erhaltenen Datenprobe auswählen kann. In dieser Arbeit verwendeten wir einen Satz von 55 Merkmalen zur Lösung des Problems und ein ziemlich einfaches Modell, das auf der Idee basiert, gute Lösungen basierend auf dem K-Algorithmus der nächsten Nachbarn zu verteilen. Diese Entwicklung hat gezeigt, dass Optimierungsdurchläufe zu Code führen können, der doppelt so schnell ist wie Code, der mit der Standardoption für maximale Optimierung -O3 erhalten wird.

Es gibt auch Studien von G. Pekhimenko und A.D. Braun für IBMs TPO ( Toronto Portable Optimizer ). Ihre Hauptaufgabe bestand darin, heuristisch auswählbare Werte für Optimierungen und genau die Code-Transformationen auszuwählen. Für die Implementierung wurde eine logistische Regression verwendet, die es ermöglichte, effektive Bußgeldeinstellungen für ein schnelleres Training vorzunehmen. Der Klassifikator wurde in Matlab gebaut. Die Nutzungswahrscheinlichkeit wurde für jeden Durchgang berechnet und bei mehr als 50% verwendet. Aufgrund der Eigenschaft, die sie in dieser Studie zu reduzieren versuchten, war es die statische Kompilierungszeit.

A.Askhari war mit der direkten Auswahl von Kompilierungsoptionen für das gesamte Programm beschäftigt, um Ausführungszeit, Kompilierungszeit, Codegröße und Stromverbrauch zu minimieren. Hierzu wurden das von G. Fursin und A. Lokhmotov (ebenfalls auf GitHub entwickelt ) entwickelte cTuning Framework und das Collective Mind Framework verwendet.

Es gibt auch Studien von M. Stephenson und S. Amarasinge zur Auswahl von Optimierungen für bestimmte besonders wichtige Algorithmen (Zuweisung von Registern, DATENPRÄFETCHING, HYPERBLOCK-FORMATION). Für jede Funktion wurden entsprechend ihre eigenen Eigenschaften verwendet. Für die Lösung wurde ein genetischer Algorithmus verwendet. Das getestete Produkt wurde am Open Research Compiler (ORC) getestet.

Es gibt auch ein MAGEEC-Projekt (Machine Guided Energy Efficient Compiler), dessen Ziele etwas anders sind. Die entwickelte Infrastruktur verwendet maschinelles Lernen, um die Optimierungen auszuwählen, die erforderlich sind, um den Code mit maximaler Energieeffizienz für Hochleistungsrechnersysteme zu generieren. MAGEEC wurde entwickelt, um sowohl mit gcc als auch mit LLVM zu arbeiten. Dieser Compiler ist Teil des größeren TSERO-Projekts (Total Software Energy Reporting and Optimization).

Eine Forschung, die in direktem Zusammenhang mit LLVM steht, ist LLVMTuner , ein Softwareprodukt, das an der Universität von Illinois von I. Chen und W. Adwe entwickelt wurde. 2017 wurde ein Bericht vorgelegt, in dem die zu diesem Zeitpunkt verfügbaren Ergebnisse beschrieben wurden. In dieser Arbeit haben wir einzelne „heiße“ Zyklen optimiert. Dieses Framework wurde für die automatisierte Konfiguration großer Programme entwickelt. LLVMTuner läuft auf LLVM IR-Middleware, verwendet Profiling zur Identifizierung von Hot Loops und passt die Heuristik automatisch an. Der Fokus liegt auf Zyklen der obersten Ebene. Die ausgewählten Zyklen und eventuelle Aufruffunktionen werden an ein separates Modul übertragen, das weiter den notwendigen Optimierungen unterzogen wird. Mit dieser Lösung können Sie die Leistung großer Programme verbessern.

Bestehende Probleme

Es gibt jedoch keinen weit verbreiteten Compiler, der die Heuristiken zur Optimierung von Durchläufen unabhängig anpasst. Was ist das Problem? Wie Sie wissen, hängen die Effektivität der Methoden des maschinellen Lernens und die Qualität der erhaltenen Modelle von der richtigen Auswahl der Merkmale und der Qualität der Daten für das Training ab (trotz der Existenz von Algorithmen, die weniger empfindlich auf „verrauschte“ Daten reagieren). Ohne die Struktur und die im Compiler verwendeten Algorithmen zu kennen, ist es nicht einfach, einen vollständigen und ausreichenden Satz von Merkmalen für das Training auszuwählen, obwohl es ziemlich klare und logische gibt, zum Beispiel die Größe des Zyklus, die Anzahl der Ausgänge aus dem Zyklus usw. Daher ist es schwierig, eine universelle Lösung zu entwickeln, die für viele Compiler gleichzeitig geeignet ist, und es ist keine Tatsache, dass dies im Allgemeinen möglich ist. Darüber hinaus ist dies wahrscheinlich nicht erforderlich.

Da die Entwicklung von Compilern in relativ kurzer Zeit effizient und machbar sein sollte, ist es selbstverständlich, dass selbst große Unternehmen ihre industriellen Compiler auf der Grundlage vorgefertigter Lösungen entwickeln. Die meisten modernen Lösungen lassen sich in zwei Kategorien einteilen: Ausführung auf virtuellen Maschinen, z. B. JVM - JIT-Compiler, und Compiler auf Basis von LLVM, einem System, das eine virtuelle Maschine mit RISC-ähnlichen Anweisungen implementiert - statische und dynamische Compiler. Natürlich gibt es immer noch firmeneigene Lösungen, aber diese werden weniger wettbewerbsfähig, da keine große Community an der Entwicklung der in ihnen verwendeten Technologien beteiligt ist. Daher verwenden heute viele große Unternehmen wie Google, Apple, Adobe und ARM LLVM, um ihre eigenen Lösungen zu entwickeln. Natürlich bleibt gcc der Hauptcompiler für C / C ++, es gibt andere Lösungen für andere Sprachen, aber wenn beispielsweise eine Lösung für LLVM gefunden wird, wird dies bereits einen anständigen Teil der derzeit vorhandenen Compiler abdecken.

Das Sammeln von Merkmalen für das Training wird ebenfalls zu einem großen Problem, da Multi-Pass-Compiler die Zwischendarstellung stark transformieren und die im Anfangsstadium gesammelten Merkmale für spätere Compiler-Optimierungen nicht ganz relevant sind. Diese Merkmale können sich mit hoher Wahrscheinlichkeit ändern. Darüber hinaus ist es sinnvoll, Merkmale für verschiedene Arten von Elementen getrennt zu erfassen: Module, Zyklen, Basisblöcke, da Optimierungen normalerweise so ausgelegt sind, dass sie einen bestimmten Elementtyp ändern. In LLVM werden die Passagen auch nach diesem Kriterium unterteilt.

Zunächst stellt sich jedoch die Frage, welche Elemente identifiziert werden müssen, für die Merkmale erfasst werden müssen. Es gibt viele Möglichkeiten, eindeutige Bezeichner zu berechnen, die bei allen Optimierungen gespeichert werden können, zum Beispiel:

• AST-basierter Frontend-Hash
• eindeutige Nummern, die beim Front-End-Parsing zugewiesen wurden
• 64-Bit-Zahl, die auf der Grundlage von Bögen in CFG (Kontrollflussdiagramm) unter Verwendung einer Prüfsumme (ähnlich wie PGO (Profilgesteuerte Optimierung) in LLVM) generiert wird

Sie müssen diese Bezeichner jedoch während der Transformationen ordnungsgemäß speichern, wenn die Elemente zu einem zusammengeführt, geteilt, neu erstellt und die ursprünglichen gelöscht werden können. Dies ist keine leichte Aufgabe.

Zweitens ist es im Prinzip schwierig, die Grenzen der im Quellcode geschriebenen Quellzyklen, Basisblöcke usw. auf dem bereits konvertierten IR zu bewerten. Beispielsweise gehen aufgrund der von LLVM übernommenen mehrstufigen Generierung von Maschinencode Informationen über Maschinenbasiseinheiten nach der Codegenerierung auf der Grundlage von Maschinenanweisungen in AsmPrinter verloren. Dementsprechend gehen auch Informationen über die Kennungen der Basisblöcke und Zyklen verloren, für die beispielsweise der Versatz vom Beginn der Funktion gemessen wird, so dass mit diesem Verfahren der Versatz nur in der Phase der Erzeugung des Maschinencodes in Form der Anzahl von Bytes erhalten werden kann. In den nachfolgenden Phasen des Generierens von Maschinencode können jedoch beim Arbeiten mit Maschinenfragmenten verschiedene Ausrichtungen hinzugefügt werden, die die Größe der zuvor berücksichtigten Anweisungen ändern, und es werden auch keine Anweisungen hinzugefügt. Aus diesem Grund kann der Berechnungsfehler für die Basisblöcke am Ende großer Funktionen sehr groß sein, bis zu einer vollständigen Verschiebung zu einem anderen Block / Zyklus. Und obwohl einige der Transformationen in den späteren Phasen verfolgt und berücksichtigt werden können, gibt dies keine Garantie für die Genauigkeit der Messungen, da die Größe der Anweisungen bis zum Linker variieren kann.



Wie Sie sehen, ist selbst die Erfassung von Attributen, auf deren Grundlage Schulungen erforderlich sind, recht kompliziert und zeitaufwändig und wird in Zukunft wahrscheinlich zum Input-Set für das trainierte Modell für die Entscheidungsfindung. Und es gibt keine offensichtlichen Lösungen für diese Probleme, was die unmittelbare Arbeit im Zusammenhang mit maschinellem Lernen erschwert und eine große Anzahl von Menschen anzieht, da nicht genügend Datensätze vorhanden sind. Nun, die typischen Schwierigkeiten, Lösungen für Probleme des maschinellen Lernens zu finden, Modelle, Methoden auszuwählen, die richtige Teilmenge von Attributen mit einer großen Anzahl von Attributen zu bestimmen usw. existieren in diesem Fall. Fast jeder, der auf maschinelles Lernen gestoßen ist, kennt sie und vielleicht gibt es hier nichts Einzigartiges und Spezifisches für Compiler.

Es ist schwer vorherzusagen, wann sich Smart Compiler verbreiten werden. Moderne Compiler haben auch andere Probleme, die mit dieser Methode wahrscheinlich nicht gelöst werden können und die derzeit wahrscheinlich mehr Priorität haben. Compiler sind jedoch bereits viel intelligenter geworden als zu Beginn ihres Erscheinungsbilds, und dieser Prozess wird fortgesetzt, obwohl er möglicherweise etwas langsamer ist, als die meisten Entwickler es wünschen.