💻 computer science

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

MileStone is een modulaire, meerdoelige compilerframework die gebruikmaakt van grafische neurale netwerken en versterkend leren om optimale reeksen van transformatiestappen te ontdekken, waardoor de uitvoeringstijd aanzienlijk wordt verkort terwijl wordt voldaan aan energiebeperkingen en bestaande optimalisatiemethoden worden overtroffen.

Oorspronkelijke auteurs: Amirhosein Sadr, Mehran Alidoost Nia

Gepubliceerd 2026-05-25

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Amirhosein Sadr, Mehran Alidoost Nia

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert de perfecte taart te bakken. Je hebt een lijst met ingrediënten (jouw computercode) en een reeks mogelijke stappen die je kunt nemen: langer mixen, heter bakken, meer suiker toevoegen of het beslag voorzichtig vouwen. In de wereld van computers worden deze stappen compiler passes genoemd.

Het probleem is dat er miljoenen manieren zijn om deze stappen te ordenen. Sommige volgorde zorgen voor een taart die heerlijk smaakt, maar eeuwig lang in de oven moeten staan. Andere zorgen voor een snelle bak, maar laten de taart droog achter. De standaardmanier waarop computers hiermee omgaan, is door een "vooraf ingesteld" recept te kiezen (zoals "Optimalisatie Niveau 3") dat voor iedereen acceptabel werkt, maar zelden perfect is voor jouw specifieke taart.

Dit artikel introduceert MileStone, een slim, door AI aangedreven systeem dat is ontworpen om de perfecte volgorde van stappen te vinden voor elk specifiek programma, waarbij drie concurrerende doelen in evenwicht worden gebracht:

Snelheid (Hoe snel draait het?)
Grootte (Hoeveel geheugen neemt het in beslag?)
Energie (Hoeveel batterij verbruikt het?)

Hier is hoe MileStone werkt, opgesplitst in eenvoudige concepten:

1. De Kaart: Code omzetten in een Grafiek

In plaats van code regel voor regel te lezen zoals een mens, zet MileStone het programma om in een Control and Data Flow Graph (CDFG) (Stroom- en Dataflowgrafiek).

De Analogie: Denk aan de code als een stad. De instructies zijn de gebouwen en de lijnen die ze verbinden zijn de wegen. Sommige wegen tonen de volgorde waarin je moet rijden (Control Flow), en andere tonen waar de lading (data) wordt verplaatst (Data Flow).
Waarom dit helpt: Deze kaart laat de AI de structuur van het programma zien, niet alleen de tekst. Het begrijpt hoe verschillende delen van de code op elkaar zijn aangewezen.

2. De Kristallen Bol: Het Graph Neural Network (GNN)

MileStone gebruikt een speciaal type AI, een Graph Neural Network (GNN), om te fungeren als een kristallen bol.

De Analogie: Stel je voor dat je een meesterkok hebt die duizenden taarten heeft geproefd. Als je hen een nieuw recept laat zien (de grafiek), kunnen ze direct voorspellen: "Als je dit bakt op 175 graden, duurt het 45 minuten, weegt het 1 kilo en gebruikt het 500 calorieën."
Wat het doet: In plaats van het programma daadwerkelijk uit te voeren (wat tijd en energie kost), kijkt het GNN naar de grafiek en voorspelt het de snelheid, grootte en energieverbruik. Dit bespaart een enorme hoeveelheid tijd.

3. De Ontdekker: Reinforcement Learning (RL)

Zodra de AI zijn kristallen bol heeft, moet hij het beste pad door de stad vinden. Dit wordt gedaan door een Reinforcement Learning (RL) agent.

De Analogie: Denk aan deze agent als een bezorger die probeert de snelste route te vinden. Hij begint aan het begin van de grafiek. Bij elke kruising (elk deel van de code) moet hij beslissen: "Neem ik de afkorting (optimaliseren voor snelheid) of de schilderachtige route (optimaliseren voor grootte)?"
Het Doel: De bestuurder krijgt pas aan het einde een "beloning". Als hij aankomt met een snel, klein en energiezuinig pakket, krijgt hij een hoge score. Als hij de batterij leegrijdt of te lang doet, krijgt hij een lage score. De bestuurder leert van duizenden pogingen om de perfecte route te vinden.

4. De Zelfverbeterende Bibliotheek

MileStone heeft een uniek kenmerk: het bouwt zijn eigen kennisbibliotheek.

De Analogie: Elke keer dat de bestuurder een nieuwe route probeert en de "kok" (het GNN) het resultaat voorspelt, schrijft MileStone het op in een notitieboekje. Na verloop van tijd wordt dit notitieboekje een enorme database van wat wel en wat niet werkt.
Het Voordeel: Naarmate het systeem dit notitieboekje gebruikt, wordt de "kok" beter in het voorspellen en wordt de "bestuurder" beter in het vinden van routes. Het is een zelfverbeterende cyclus die slimmer wordt naarmate het meer wordt gebruikt.

De Grote Overwinning: Het Balanceren van Afwegingen

Het belangrijkste wat MileStone doet, is omgaan met conflicterende doelen.

Meestal zorgt het sneller maken van code ervoor dat het groter wordt en meer energie verbruikt.
Standaard compilers kiezen gewoon één doel (meestal snelheid).
MileStone stelt je in staat een regel te stellen, zoals: "Ik heb een strikt batterijlimiet van 5 Joule." Het vindt vervolgens de snelst mogelijke snelheid zonder dat batterijlimiet te schenden.

De Resultaten

Toen de onderzoekers MileStone testten op standaard benchmarks:

Vond het "Pareto-optimale" oplossingen. In gewone taal zijn dit de "sweet spots" waar je één ding (zoals snelheid) niet kunt verbeteren zonder iets anders (zoals energie) erger te maken.
Het sloeg standaard compiler-instellingen (zoals het beroemde niveau -O3) aanzienlijk.
Onder hetzelfde energiebudget verkleinde MileStone de uitvoeringstijd met maximaal 45%.
Het was veel beter in het voldoen aan specifieke energielimieten dan traditionele methoden of andere AI-benaderingen.

Kort samengevat: MileStone is als een superslim, zelflerend navigatiesysteem voor computercode. In plaats van een generieke kaart te gebruiken, tekent het een aangepaste kaart voor elk programma, voorspelt het de uitkomst van elke mogelijke route en rijdt je naar de bestemming die de perfecte balans is tussen snelheid, grootte en energie-efficiëntie.

Technische Samenvatting: MileStone – Een Raamwerk voor Multi-Doel Compilerfaseordening

1. Probleemdefinitie

Het artikel behandelt het probleem van compilerfaseordening, waarbij de optimale volgorde van optimalisatiepasses wordt bepaald om de Intermediaire Representatie (IR) van een programma om te zetten in efficiënte machinecode. Hoewel standaard compileroptimalisatieniveaus (bijvoorbeeld LLVM's -O1, -O2, -O3) vaste sequenties bieden, vertegenwoordigen ze slechts een klein deel van de enorme zoekruimte en slagen ze er niet in om conflicterende prestatiedoelstellingen in evenwicht te brengen.

De kernuitdaging die wordt geïdentificeerd, is de noodzaak om gelijktijdig te optimaliseren voor uitvoeringstijd, codemaat en energiverbruik. Deze doelstellingen zijn inherent conflicterend; bijvoorbeeld kan agressieve lusontvouw de uitvoeringstijd verminderen, maar de codemaat en het energieverbruik verhogen. Traditionele benaderingen vertrouwen vaak op vaste heuristieken of single-objective optimalisatie, waardoor ze de benodigde afwegingen (Pareto-optimale oplossingen) niet kunnen vastleggen die nodig zijn voor diverse implementatieomgevingen, zoals energie-beperkte ingebouwde systemen of high-performance computing. Bovendien is een exhaustieve zoektocht computationeel onuitvoerbaar, en bestaande op leren gebaseerde methoden missen vaak ondersteuning voor multi-objective beperkingen of vertrouwen sterk op dynamische profilering.

2. Methodologie: Het MileStone-raamwerk

MileStone is een modulair, door leren gedreven raamwerk dat compilerfaseordening modelleert als een beperkt multi-objectief optimalisatieprobleem (CMOO). Het integreert Graph Neural Networks (GNN's) voor statische prestatievoorspelling met Reinforcement Learning (RL) voor adaptieve exploratie. Het raamwerk bestaat uit vier nauw geïntegreerde modules:

2.1 Graph Generator (GG)

De GG extrahereert Besturings- en Dataflow-Graphs (CDFG's) uit LLVM IR na de front-end compilatiefase. In tegenstelling tot syntactische representaties, leggen CDFG's de structurele en semantische relaties van het programma vast. Elke knoop in de CDFG wordt weergegeven door een 10-dimensionale binaire featurevector die knooptypen (basisblok versus instructie) en specifieke instructie-opcodes encodeert (bijvoorbeeld geheugenoperaties, rekenkundige bewerkingen, besturingsflow).

2.2 GNN-gebaseerde Prestatievoorspeller (GNNPP)

GNNPP maakt gebruik van een Graph Convolutional Network (GCN) om post-compilatiemetrics (uitvoeringstijd, codemaat en energieverbruik) direct te voorspellen uit CDFG-representaties zonder de code uit te voeren.

Architectuur: Het model maakt gebruik van een GCN met twee lagen om knoopfeatures te aggregeren en multi-hop-afhankelijkheden vast te leggen, gevolgd door mean pooling om graph-level embeddings te genereren.
Training: Het wordt getraind als een regressiemodel met behulp van Mean Squared Logarithmic Error (voor energie en codemaat) en Mean Absolute Error (voor uitvoeringstijd).
Rol: GNNPP fungeert als een surrogaatmodel en biedt snelle prestatieschattingen om de RL-agent te sturen, waardoor herhaalde fysieke uitvoering tijdens het zoekproces overbodig wordt.

2.3 RL-gebaseerde Multi-Doel Explorer (RLMOE)

RLMOE behandelt de selectie van optimalisatiepasses als een sequentieel besluitvormingsproces gemodelleerd als een Markov Decision Process (MDP).

State: Omvat de CDFG-graph embedding, huidige knoopidentificatie, CDFG-metadata en door de gebruiker gedefinieerde energiebeperkingen.
Actie: Bepaalt of een specifieke optimalisatierichtlijn op de huidige knoop moet worden toegepast.
Beloning: Een spaarzame beloningsfunctie wordt alleen toegepast in de laatste stap ( $T$ ), berekend als een gewogen som van de voorspelde codemaat, uitvoeringstijd en de afwijking van de doel-energiverbruik. Intermediaire beloningen zijn nul.
Algoritmen: Het raamwerk ondersteunt zowel Deep Q-Network (DQN) als Proximal Policy Optimization (PPO). PPO toont over het algemeen superieure stabiliteit en prestaties, vooral voor grootschalige programma's, door gebruik te maken van een geknipt surrogaatdoel en Generalized Advantage Estimation (GAE).

2.4 RL-gebaseerde Database Generator (RLDBG)

RLDBG is een zelfevoluerende kennisbank die de verzameling van trainingsdata automatiseert. Het roept RLMOE iteratief aan om diverse pass-sequenties te exploreren, compileert de resulterende configuraties en profileert deze met behulp van een Evaluator om ground-truth metrics te verkrijgen. Deze CDFG-metric-paren worden opgeslagen om GNNPP te trainen en te verfijnen, waardoor een feedbacklus ontstaat die de voorspellingsnauwkeurigheid en exploratie-efficiëntie in de loop van de tijd verbetert.

3. Belangrijkste Bijdragen

Het artikel schetst vier primaire bijdragen:

Unificerend Raamwerk: Introductie van MileStone, een raamwerk dat compilerfaseordening formuleert als een multi-objectief optimalisatieprobleem dat uitvoeringstijd, codemaat en energieverbruik in evenwicht brengt onder door de gebruiker gedefinieerde beperkingen.
Graph-gebaseerd Neuraal Model: Ontwikkeling van een GNN-model dat structurele en semantische eigenschappen leert uit IR-graphs om programmaprestatiemetrics nauwkeurig te voorspellen.
RL-gebaseerde Exploratie: Implementatie van een RL-gebaseerde aanpak (DQN/PPO) om pass-sequenties te exploreren en Pareto-optimale afwegingen tussen meerdere doelstellingen te identificeren.
Zelfverbeterend Mechanisme: Integratie van een zelfevoluerend dataverzamelmechanisme (RLDBG) dat zowel de voorspellingsnauwkeurigheid als de exploratie-efficiëntie verbetert door diverse optimalisatie-uitkomsten te aggregeren.

4. Experimentele Resultaten

Experimenten werden uitgevoerd op standaard benchmarks (PolyBench: gemm, 3mm, floyd-warshall) met behulp van een NVIDIA RTX 3090TI GPU. Het raamwerk werd vergeleken met LLVM-optimalisatieniveaus (-O1 tot -O3), heuristische zoekmethoden (Genetisch Algoritme, Particle Swarm Optimization) en standalone RL-agents.

Pareto-optimale Oplossingen: RLMOE (met zowel DQN als PPO) presteerde consequent beter dan de baselines, en vond oplossingen die gebieden van de oplossingsruimte innamen met lager energieverbruik en kleinere codematen, terwijl concurrerende uitvoeringstijden werden behouden.
Beperkingen Voldoen: Onder door de gebruiker gespecificeerde energiebeperkingen bereikte RLMOE aanzienlijk hogere matchingspercentages (90–93%) in vergelijking met standalone RL-agents (83–85%) en traditionele optimalisatieniveaus (3–9%).
Vermindering van Uitvoeringstijd: Onder identieke energiebudgetten verlaagde MileStone de uitvoeringstijd met maximaal 45% in vergelijking met LLVM -O3. Specifiek toonde RLMOE-PPO verminderingen van 15–45% over verschillende benchmarks.
Architectuuranalyse: De studie bepaalde dat een GCN-architectuur met twee lagen de beste balans bood tussen voorspellingsnauwkeurigheid en het vermijden van het oversmoothing-probleem.

5. Betekenis en Claims

Het artikel beweert dat MileStone een effectieve en schaalbare oplossing biedt voor multi-objectief compilerfaseordening. De betekenis hiervan ligt in:

Voorbij Single-Objective Optimalisatie: Het navigeert succesvol over het afwegingsoppervlak tussen uitvoeringstijd, codemaat en energie, waardoor compilers zich kunnen aanpassen aan specifieke hardware- en workloadvereisten (bijvoorbeeld prioriteit geven aan energie-efficiëntie in IoT-apparaten).
Efficiëntie: Door GNN-gebaseerde statische voorspelling te combineren met RL, vermijdt het raamwerk de verbodsdure kosten van exhaustieve zoektochten en herhaalde dynamische profilering.
Aanpasbaarheid: De zelfevoluerende database stelt het systeem in staat om in de loop van de tijd te verbeteren, waarbij diverse Pareto-efficiënte configuraties worden vastgelegd die statische heuristieken missen.

De auteurs concluderen dat het integreren van statisch graph-leren met op versterking gebaseerde zoektocht een robuust pad voorwaarts biedt voor het optimaliseren van complexe compilerpijplijnen, vooral in scenario's waarbij meerdere, conflicterende prestatie-metrics in evenwicht moeten worden gebracht. Voor toekomstig werk wordt voorgesteld het raamwerk uit te breiden naar grotere industriële workloads, gedetailleerde micro-architectuurmodellen op te nemen en dynamische optimalisatiescenario's te ondersteunen.