💻 computer science

MileStone: A Multi-Objective Compiler Phase Ordering Framework for Graph-based IR-Level Optimization

MileStone ist ein modulares, mehrzielorientiertes Compiler-Framework, das Graph-Neuronale-Netzwerke und Reinforcement Learning nutzt, um optimale Pass-Sequenzen zu entdecken, die Ausführungszeit erheblich reduziert, während es Energiebeschränkungen einhält und bestehende Optimierungsmethoden übertrifft.

Ursprüngliche Autoren: Amirhosein Sadr, Mehran Alidoost Nia

Veröffentlicht 2026-05-25

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Amirhosein Sadr, Mehran Alidoost Nia

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, den perfekten Kuchen zu backen. Sie haben eine Liste von Zutaten (Ihren Computercode) und eine Reihe möglicher Schritte, die Sie unternehmen könnten: länger mischen, heißer backen, mehr Zucker hinzufügen oder den Teig vorsichtig unterheben. In der Welt der Computer werden diese Schritte Compiler-Passes genannt.

Das Problem ist, dass es Millionen von Möglichkeiten gibt, diese Schritte zu ordnen. Manche Reihenfolgen lassen den Kuchen großartig schmecken, benötigen aber ewig zum Backen. Andere lassen ihn schnell backen, lassen ihn aber trocken werden. Der Standardweg, wie Computer damit umgehen, besteht darin, ein „voreingestelltes" Rezept (wie „Optimierungsstufe 3") zu wählen, das für alle einigermaßen funktioniert, aber selten perfekt für Ihren spezifischen Kuchen ist.

Diese Arbeit stellt MileStone vor, ein intelligentes, KI-gestütztes System, das entwickelt wurde, um die perfekte Abfolge von Schritten für jedes spezifische Programm zu finden und dabei drei konkurrierende Ziele in Einklang zu bringen:

Geschwindigkeit (Wie schnell läuft es?)
Größe (Wie viel Speicherplatz belegt es?)
Energie (Wie viel Akku verbraucht es?)

Hier ist, wie MileStone funktioniert, aufgeschlüsselt in einfache Konzepte:

1. Die Karte: Umwandlung von Code in einen Graphen

Anstatt Code zeilenweise wie ein Mensch zu lesen, verwandelt MileStone das Programm in einen Steuerungs- und Datenflussgraphen (CDFG).

Die Analogie: Denken Sie an den Code als eine Stadt. Die Anweisungen sind die Gebäude, und die Linien, die sie verbinden, sind die Straßen. Einige Straßen zeigen die Reihenfolge, in der Sie fahren müssen (Steuerungsfluss), und andere zeigen, wo die Fracht (Daten) bewegt wird (Datenfluss).
Warum es hilft: Diese Karte ermöglicht es der KI, die Struktur des Programms zu sehen, nicht nur den Text. Sie versteht, wie verschiedene Teile des Codes voneinander abhängen.

2. Die Kristallkugel: Das Graph-Neuronale Netzwerk (GNN)

MileStone verwendet eine spezielle Art von KI, ein Graph-Neuronales Netzwerk (GNN), als Kristallkugel.

Die Analogie: Stellen Sie sich einen Meisterkoch vor, der Tausende von Kuchen probiert hat. Wenn Sie ihm ein neues Rezept (den Graphen) zeigen, kann er sofort vorhersagen: „Wenn Sie dies bei 350 Grad backen, dauert es 45 Minuten, wiegt 2 Pfund und verbraucht 500 Kalorien."
Was es tut: Anstatt das Programm tatsächlich auszuführen (was Zeit und Energie kostet), betrachtet das GNN den Graphen und prognostiziert Geschwindigkeit, Größe und Energieverbrauch. Dies spart eine enorme Menge an Zeit.

3. Der Entdecker: Reinforcement Learning (RL)

Sobald die KI ihre Kristallkugel hat, muss sie den besten Weg durch die Stadt finden. Dies wird durch einen Reinforcement-Learning-(RL)-Agenten erreicht.

Die Analogie: Denken Sie an diesen Agenten als einen Lieferfahrer, der die schnellste Route sucht. Er startet am Anfang des Graphen. An jeder Kreuzung (jedem Teil des Codes) muss er entscheiden: „Nehme ich die Abkürzung (Optimierung für Geschwindigkeit) oder die landschaftlich schöne Route (Optimierung für Größe)?"
Das Ziel: Der Fahrer erhält eine „Belohnung" erst ganz am Ende. Wenn er mit einem schnellen, kleinen und energieeffizienten Paket ankommt, erhält er eine hohe Punktzahl. Wenn ihm der Akku ausgeht oder er zu lange braucht, erhält er eine niedrige Punktzahl. Der Fahrer lernt aus Tausenden von Versuchen, um die perfekte Route zu finden.

4. Die sich selbst verbessernde Bibliothek

MileStone verfügt über ein einzigartiges Merkmal: Es baut seine eigene Wissensbibliothek auf.

Die Analogie: Jedes Mal, wenn der Fahrer eine neue Route versucht und der „Koch" (das GNN) das Ergebnis vorhersagt, schreibt MileStone es in ein Notizbuch. Im Laufe der Zeit wird dieses Notizbuch zu einer riesigen Datenbank darüber, was funktioniert und was nicht.
Der Vorteil: Während das System dieses Notizbuch nutzt, wird der „Koch" besser im Vorhersagen und der „Fahrer" besser im Finden von Routen. Es ist ein sich selbst verbessernder Zyklus, der mit zunehmender Nutzung intelligenter wird.

Der große Gewinn: Abwägung der Zielkonflikte

Das Wichtigste, was MileStone leistet, ist der Umgang mit konfliktären Zielen.

Normalerweise führt das Schnellermachen von Code dazu, dass er größer wird und mehr Energie verbraucht.
Standardcompiler wählen einfach ein Ziel aus (meist Geschwindigkeit).
MileStone ermöglicht es Ihnen, eine Regel festzulegen, wie zum Beispiel: „Ich habe ein striktes Batterielimit von 5 Joule." Es findet dann die schnellstmögliche Geschwindigkeit, ohne dieses Batterielimit zu verletzen.

Die Ergebnisse

Als die Forscher MileStone an Standard-Benchmarks testeten:

Es fand „Pareto-optimale" Lösungen. Auf Deutsch gesagt sind dies die „Sweet Spots", an denen man eine Sache (wie Geschwindigkeit) nicht verbessern kann, ohne etwas anderes (wie Energie) schlechter zu machen.
Es übertraf Standardcompiler-Einstellungen (wie das berühmte Niveau -O3) deutlich.
Unter demselben Energiebudget reduzierte MileStone die Ausführungszeit um bis zu 45 %.
Es war viel besser darin, spezifische Energielimits einzuhalten als traditionelle Methoden oder andere KI-Ansätze.

Zusammenfassend: MileStone ist wie ein superintelligentes, sich selbst unterrichtendes Navigationssystem für Computercode. Anstatt eine generische Karte zu verwenden, zeichnet es für jedes Programm eine individuelle Karte, prognostiziert das Ergebnis jeder möglichen Route und bringt Sie zum Ziel, das die perfekte Balance aus Geschwindigkeit, Größe und Energieeffizienz darstellt.

Technische Zusammenfassung: MileStone – Ein Framework für die Mehrziel-Optimierung der Compiler-Phasenreihenfolge

1. Problemdefinition

Die Arbeit behandelt das Problem der Compiler-Phasenreihenfolge, das die Bestimmung der optimalen Abfolge von Optimierungs-Passes umfasst, um die Intermediate Representation (IR) eines Programms in effizienten Maschinencode zu überführen. Während Standard-Optimierungsstufen des Compilers (z. B. LLVMs -O1, -O2, -O3) feste Sequenzen bereitstellen, repräsentieren sie nur einen kleinen Teil des riesigen Suchraums und vermögen es nicht, sich widersprechende Leistungsziele auszugleichen.

Die erkannte Kernherausforderung besteht in der Notwendigkeit, gleichzeitig Ausführungszeit, Codegröße und Energieverbrauch zu optimieren. Diese Ziele sind inhärent konfliktbehaftet; beispielsweise kann eine aggressive Schleifenentfaltung die Ausführungszeit verringern, aber die Codegröße und den Energieverbrauch erhöhen. Traditionelle Ansätze verlassen sich häufig auf feste Heuristiken oder Einzelziel-Optimierung und erfassen die notwendigen Kompromisse (Pareto-optimale Lösungen) für diverse Einsatzumgebungen, wie energiebeschränkte eingebettete Systeme oder High-Performance-Computing, nicht. Darüber hinaus ist eine erschöpfende Suche rechnerisch nicht durchführbar, und bestehende lernbasierte Methoden bieten oft keine Unterstützung für Mehrziel-Beschränkungen oder verlassen sich stark auf dynamisches Profiling.

2. Methodik: Das MileStone-Framework

MileStone ist ein modulares, lerngetriebenes Framework, das die Compiler-Phasenreihenfolge als eingeschränktes Mehrziel-Optimierungsproblem (Constrained Multi-Objective Optimization, CMOO) modelliert. Es integriert Graph-Neuronale Netze (GNNs) für die statische Leistungsvorhersage mit Reinforcement Learning (RL) für die adaptive Exploration. Das Framework besteht aus vier eng integrierten Modulen:

2.1 Graph-Generator (GG)

Der GG extrahiert Steuerungs- und Datenflussgraphen (Control and Data Flow Graphs, CDFGs) aus der LLVM-IR nach der Front-End-Kompilierungsphase. Im Gegensatz zu syntaktischen Darstellungen erfassen CDFGs die strukturellen und semantischen Beziehungen des Programms. Jeder Knoten im CDFG wird durch einen 10-dimensionalen binären Merkmalsvektor repräsentiert, der Knotentypen (Basic Block vs. Anweisung) und spezifische Anweisungs-Opcodes (z. B. Speicheroperationen, Arithmetik, Kontrollfluss) kodiert.

2.2 GNN-basierter Leistungsvorhersager (GNNPP)

GNNPP nutzt ein Graph Convolutional Network (GCN), um Post-Kompilierungs-Metriken (Ausführungszeit, Codegröße und Energieverbrauch) direkt aus CDFG-Repräsentationen vorherzusagen, ohne den Code auszuführen.

Architektur: Das Modell verwendet ein zweischichtiges GCN zur Aggregation von Knotenmerkmalen und zur Erfassung von Mehr-Sprung-Abhängigkeiten, gefolgt von einer Mean-Pooling-Schicht zur Generierung von Graph-Level-Embeddings.
Training: Es wird als Regressionsmodell mit dem Mean Squared Logarithmic Error (für Energie und Codegröße) und dem Mean Absolute Error (für Ausführungszeit) trainiert.
Rolle: GNNPP dient als Surrogatmodell, das schnelle Leistungsschätzungen liefert, um den RL-Agenten zu steuern, wodurch wiederholte physische Ausführungen während des Suchprozesses überflüssig werden.

2.3 RL-basierter Mehrziel-Explorer (RLMOE)

RLMOE behandelt die Auswahl von Optimierungs-Passes als sequenziellen Entscheidungsprozess, der als Markov-Entscheidungsprozess (MDP) modelliert ist.

Zustand: Umfasst das CDFG-Graph-Embedding, die aktuelle Knoten-ID, CDFG-Metadaten und benutzerdefinierte Energiebeschränkungen.
Aktion: Bestimmt, ob eine bestimmte Optimierungsanweisung auf den aktuellen Knoten angewendet wird.
Belohnung: Eine spärliche Belohnungsfunktion wird nur im letzten Schritt ( $T$ ) angewendet und berechnet sich als gewichtete Summe aus vorhergesagter Codegröße, Ausführungszeit und der Abweichung vom Ziel-Energieverbrauch. Zwischenbelohnungen sind null.
Algorithmen: Das Framework unterstützt sowohl Deep Q-Network (DQN) als auch Proximal Policy Optimization (PPO). PPO zeigt im Allgemeinen überlegene Stabilität und Leistung, insbesondere für großskalige Programme, indem es ein abgeschnittenes Surrogatziel und Generalized Advantage Estimation (GAE) verwendet.

2.4 RL-basierter Datenbank-Generator (RLDBG)

RLDBG ist eine sich selbst entwickelnde Wissensbasis, die die Sammlung von Trainingsdaten automatisiert. Es ruft RLMOE iterativ auf, um diverse Pass-Sequenzen zu explorieren, kompiliert die resultierenden Konfigurationen und profiliert sie mithilfe eines Evaluators, um Ground-Truth-Metriken zu erhalten. Diese CDFG-Metriken-Paare werden gespeichert, um GNNPP zu trainieren und zu verfeinern, wodurch eine Feedbackschleife entsteht, die die Vorhersagegenauigkeit und die Explorationseffizienz im Laufe der Zeit verbessert.

3. Hauptbeiträge

Die Arbeit skizziert vier primäre Beiträge:

Unified Framework: Vorstellung von MileStone, einem Framework, das die Compiler-Phasenreihenfolge als Mehrziel-Optimierungsproblem formuliert, das Ausführungszeit, Codegröße und Energieverbrauch unter benutzerdefinierten Beschränkungen ausbalanciert.
Graph-basiertes Neuronales Modell: Entwicklung eines GNN-Modells, das strukturelle und semantische Eigenschaften aus IR-Graphen lernt, um Programmleistungs-Metriken genau vorherzusagen.
RL-basierte Exploration: Implementierung eines RL-basierten Ansatzes (DQN/PPO) zur Exploration von Pass-Sequenzen und zur Identifizierung von Pareto-optimalen Kompromissen zwischen mehreren Zielen.
Selbstverbessernder Mechanismus: Integration eines sich selbst entwickelnden Datensammelmechanismus (RLDBG), der sowohl die Vorhersagegenauigkeit als auch die Explorationseffizienz durch die Aggregation diverser Optimierungsergebnisse verbessert.

4. Experimentelle Ergebnisse

Experimente wurden an Standard-Benchmarks (PolyBench: gemm, 3mm, floyd-warshall) unter Verwendung einer NVIDIA RTX 3090TI-GPU durchgeführt. Das Framework wurde mit LLVM-Optimierungsstufen (-O1 bis -O3), heuristischen Suchmethoden (Genetischer Algorithmus, Partikelschwarm-Optimierung) und eigenständigen RL-Agenten verglichen.

Pareto-optimale Lösungen: RLMOE (unter Verwendung von DQN und PPO) schnitt bei den Baselines konsistent besser ab und fand Lösungen, die Bereiche des Lösungsraums mit geringerem Energieverbrauch und kleinerer Codegröße besetzten, während gleichzeitig wettbewerbsfähige Ausführungszeiten erhalten blieben.
Einhaltung von Beschränkungen: Unter benutzerspezifischen Energiebeschränkungen erreichte RLMOE signifikant höhere Übereinstimmungsraten (90–93 %) im Vergleich zu eigenständigen RL-Agenten (83–85 %) und traditionellen Optimierungsstufen (3–9 %).
Reduktion der Ausführungszeit: Unter identischen Energiebudgets reduzierte MileStone die Ausführungszeit um bis zu 45 % im Vergleich zu LLVM -O3. Insbesondere zeigte RLMOE-PPO Reduktionen von 15–45 % über verschiedene Benchmarks hinweg.
Architekturanalyse: Die Studie ergab, dass eine zweischichtige GCN-Architektur den besten Ausgleich zwischen Vorhersagegenauigkeit und der Vermeidung des Oversmoothing-Problems bot.

5. Bedeutung und Behauptungen

Die Arbeit behauptet, dass MileStone eine effektive und skalierbare Lösung für die Mehrziel-Optimierung der Compiler-Phasenreihenfolge bietet. Ihre Bedeutung liegt in:

Überwindung der Einzelziel-Optimierung: Es navigiert erfolgreich die Trade-off-Fläche zwischen Ausführungszeit, Codegröße und Energie und ermöglicht es Compilern, sich an spezifische Hardware- und Arbeitslastanforderungen anzupassen (z. B. Priorisierung der Energieeffizienz in IoT-Geräten).
Effizienz: Durch die Kombination von GNN-basierter statischer Vorhersage mit RL vermeidet das Framework die prohibitiven Kosten einer erschöpfenden Suche und wiederholten dynamischen Profiling.
Anpassungsfähigkeit: Die sich selbst entwickelnde Datenbank ermöglicht es dem System, sich im Laufe der Zeit zu verbessern und diverse Pareto-effiziente Konfigurationen zu erfassen, die statische Heuristiken übersehen.

Die Autoren kommen zu dem Schluss, dass die Integration von statischem Graphenlernen mit suchbasiertem Reinforcement Learning einen robusten Weg nach vorne für die Optimierung komplexer Compiler-Pipelines bietet, insbesondere in Szenarien, in denen mehrere, sich widersprechende Leistungsmetriken ausbalanciert werden müssen. Als zukünftige Arbeiten wird vorgeschlagen, das Framework auf größere industrielle Arbeitslasten zu erweitern, detaillierte Mikroarchitekturmodelle einzubeziehen und Szenarien für dynamische Optimierung zu unterstützen.