💻 computer science

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

MileStone est un framework de compilation modulaire et multi-objectif qui exploite les réseaux de neurones à graphes et l'apprentissage par renforcement pour découvrir des séquences de passes optimales, réduisant considérablement le temps d'exécution tout en respectant les contraintes énergétiques et en surpassant les méthodes d'optimisation existantes.

Auteurs originaux : Amirhosein Sadr, Mehran Alidoost Nia

Publié 2026-05-25

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Amirhosein Sadr, Mehran Alidoost Nia

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de préparer le gâteau parfait. Vous avez une liste d'ingrédients (votre code informatique) et un ensemble d'étapes possibles que vous pourriez entreprendre : mélanger plus longtemps, cuire à une température plus élevée, ajouter plus de sucre, ou plier la pâte délicatement. Dans le monde de l'informatique, ces étapes sont appelées passes de compilation.

Le problème est qu'il existe des millions de façons d'ordonner ces étapes. Certains ordres donnent un gâteau délicieux mais prennent une éternité à cuire. D'autres permettent une cuisson rapide mais laissent le gâteau sec. La méthode standard utilisée par les ordinateurs consiste à choisir une recette « préréglée » (comme le niveau « Optimisation 3 ») qui fonctionne correctement pour tout le monde, mais elle est rarement parfaite pour votre gâteau spécifique.

Ce document présente MileStone, un système intelligent et alimenté par l'IA conçu pour trouver la séquence d'étapes parfaite pour n'importe quel programme spécifique, en équilibrant trois objectifs concurrents :

Vitesse (À quelle vitesse s'exécute-t-il ?)
Taille (Quelle quantité de mémoire occupe-t-il ?)
Énergie (Quelle quantité de batterie consomme-t-il ?)

Voici comment MileStone fonctionne, décomposé en concepts simples :

1. La Carte : Transformer le code en un graphe

Au lieu de lire le code ligne par ligne comme un humain, MileStone transforme le programme en un Graphe de flot de contrôle et de données (CDFG).

L'analogie : Imaginez le code comme une ville. Les instructions sont les bâtiments, et les lignes les reliant sont les routes. Certaines routes indiquent l'ordre dans lequel vous devez conduire (Flot de contrôle), et d'autres montrent où le fret (les données) est déplacé (Flot de données).
Pourquoi cela aide : Cette carte permet à l'IA de voir la structure du programme, et pas seulement le texte. Elle comprend comment les différentes parties du code dépendent les unes des autres.

2. La Boule de cristal : Le Réseau de Neurones à Graphes (GNN)

MileStone utilise un type spécial d'IA appelé un Réseau de Neurones à Graphes (GNN) pour agir comme une boule de cristal.

L'analogie : Imaginez que vous avez un chef étoilé qui a goûté des milliers de gâteaux. Si vous lui montrez une nouvelle recette (le graphe), il peut prédire instantanément : « Si vous cuisez ceci à 180 degrés, cela prendra 45 minutes, pèsera 900 grammes et utilisera 500 calories. »
Ce qu'il fait : Au lieu d'exécuter réellement le programme (ce qui prend du temps et de l'énergie), le GNN examine le graphe et prédit la vitesse, la taille et la consommation d'énergie. Cela économise une quantité massive de temps.

3. L'Explorateur : L'Apprentissage par Renforcement (RL)

Une fois que l'IA a sa boule de cristal, elle doit trouver le meilleur chemin à travers la ville. Cela est réalisé par un agent d'Apprentissage par Renforcement (RL).

L'analogie : Imaginez cet agent comme un livreur essayant de trouver l'itinéraire le plus rapide. Il commence au début du graphe. À chaque intersection (chaque partie du code), il doit décider : « Prends-je la route courte (optimiser pour la vitesse) ou la route pittoresque (optimiser pour la taille) ? »
L'objectif : Le livreur ne reçoit une « récompense » qu'à la toute fin. S'il arrive avec un colis rapide, petit et économe en énergie, il obtient un score élevé. S'il épuise sa batterie ou prend trop de temps, il obtient un score faible. Le livreur apprend de milliers d'essais pour trouver l'itinéraire parfait.

4. La Bibliothèque auto-améliorante

MileStone possède une fonctionnalité unique : il construit sa propre bibliothèque de connaissances.

L'analogie : Chaque fois que le livreur essaie un nouvel itinéraire et que le « chef » (le GNN) prédit le résultat, MileStone l'écrit dans un carnet. Avec le temps, ce carnet devient une base de données massive de ce qui fonctionne et de ce qui ne fonctionne pas.
L'avantage : Au fur et à mesure que le système utilise ce carnet, le « chef » devient meilleur pour prédire, et le « livreur » devient meilleur pour trouver des itinéraires. C'est un cycle d'auto-amélioration qui devient plus intelligent à mesure qu'il est utilisé.

La grande victoire : Équilibrer les compromis

La chose la plus importante que fait MileStone est de gérer les objectifs conflictuels.

Habituellement, rendre le code plus rapide le rend plus volumineux et consomme plus d'énergie.
Les compilateurs standards choisissent simplement un objectif (généralement la vitesse).
MileStone vous permet de définir une règle, comme : « J'ai une limite de batterie stricte de 5 Joules. » Il trouve ensuite la vitesse la plus rapide possible sans dépasser cette limite de batterie.

Les résultats

Lorsque les chercheurs ont testé MileStone sur des benchmarks standard :

Il a trouvé des solutions « optimales au sens de Pareto ». En termes simples, ce sont les « points idéaux » où vous ne pouvez pas améliorer une chose (comme la vitesse) sans empirer quelque chose d'autre (comme l'énergie).
Il a surpassé significativement les paramètres de compilateurs standards (comme le célèbre niveau -O3).
Avec le même budget énergétique, MileStone a réduit le temps d'exécution d'jusqu'à 45 %.
Il était beaucoup plus efficace pour respecter des limites énergétiques spécifiques que les méthodes traditionnelles ou d'autres approches basées sur l'IA.

En résumé : MileStone est comme un système de navigation ultra-intelligent et auto-apprenant pour le code informatique. Au lieu d'utiliser une carte générique, il dessine une carte personnalisée pour chaque programme, prédit le résultat de chaque itinéraire possible, et vous conduit à la destination qui représente l'équilibre parfait entre vitesse, taille et efficacité énergétique.

Résumé Technique : MileStone – Un Cadre d'Ordonnancement de Phases de Compilateur Multi-Objectifs

1. Définition du Problème

L'article traite du problème d'ordonnancement des phases de compilateur, qui consiste à déterminer la séquence optimale de passes d'optimisation pour transformer la Représentation Intermédiaire (IR) d'un programme en code machine efficace. Bien que les niveaux d'optimisation standard des compilateurs (par exemple, -O1, -O2, -O3 de LLVM) fournissent des séquences fixes, ils ne représentent qu'un sous-ensemble limité de l'immense espace de recherche et échouent à équilibrer des objectifs de performance contradictoires.

Le défi central identifié est la nécessité d'optimiser simultanément le temps d'exécution, la taille du code et la consommation énergétique. Ces objectifs sont intrinsèquement conflictuels ; par exemple, un déroulage agressif de boucles peut réduire le temps d'exécution mais augmenter la taille du code et la consommation d'énergie. Les approches traditionnelles reposent souvent sur des heuristiques fixes ou une optimisation mono-objectif, échouant à capturer les compromis nécessaires (solutions Pareto-optimales) requis pour des environnements de déploiement divers, tels que les systèmes embarqués contraints en énergie ou le calcul haute performance. De plus, la recherche exhaustive est computationnellement irréalisable, et les méthodes existantes basées sur l'apprentissage manquent souvent de prise en charge des contraintes multi-objectifs ou dépendent fortement du profilage dynamique.

2. Méthodologie : Le Cadre MileStone

MileStone est un cadre modulaire et piloté par l'apprentissage qui modélise l'ordonnancement des phases de compilateur comme un problème d'Optimisation Multi-Objectifs Contrainte (CMOO). Il intègre des Réseaux de Neurones à Graphes (GNN) pour la prédiction de performances statique et l'Apprentissage par Renforcement (RL) pour l'exploration adaptative. Le cadre se compose de quatre modules étroitement intégrés :

2.1 Générateur de Graphes (GG)

Le GG extrait les Graphes de Flux de Contrôle et de Données (CDFG) de l'IR LLVM après l'étape de compilation front-end. Contrairement aux représentations syntaxiques, les CDFG capturent les relations structurelles et sémantiques du programme. Chaque nœud du CDFG est représenté par un vecteur de caractéristiques binaire à 10 dimensions codant les types de nœuds (bloc de base vs instruction) et les opcodes d'instructions spécifiques (par exemple, opérations mémoire, arithmétiques, flux de contrôle).

2.2 Prédicteur de Performances Basé sur GNN (GNNPP)

GNNPP utilise un Réseau de Convolution de Graphes (GCN) pour prédire les métriques post-compilation (temps d'exécution, taille du code et consommation énergétique) directement à partir des représentations CDFG sans exécuter le code.

Architecture : Le modèle emploie un GCN à deux couches pour agréger les caractéristiques des nœuds et capturer les dépendances multi-sauts, suivi d'un pooling moyen pour générer des plongements au niveau du graphe.
Entraînement : Il est entraîné comme un modèle de régression utilisant l'Erreur Logarithmique Moyenne Quadratique (pour l'énergie et la taille du code) et l'Erreur Absolue Moyenne (pour le temps d'exécution).
Rôle : GNNPP sert de modèle de substitution, fournissant des estimations de performances rapides pour guider l'agent RL, éliminant ainsi le besoin d'exécutions physiques répétées durant le processus de recherche.

2.3 Explorateur Multi-Objectifs Basé sur RL (RLMOE)

RLMOE traite la sélection des passes d'optimisation comme un processus de prise de décision séquentielle modélisé comme un Processus de Décision Markovien (MDP).

État : Comprend l'embedding du graphe CDFG, l'identifiant du nœud courant, les métadonnées CDFG et les contraintes énergétiques définies par l'utilisateur.
Action : Détermine s'il faut appliquer une directive d'optimisation spécifique au nœud courant.
Récompense : Une fonction de récompense sparse est appliquée uniquement à l'étape finale ( $T$ ), calculée comme une somme pondérée de la taille du code prédite, du temps d'exécution et de l'écart par rapport à la consommation énergétique cible. Les récompenses intermédiaires sont nulles.
Algorithmes : Le cadre prend en charge à la fois le Deep Q-Network (DQN) et l'Optimisation de Politique Proximale (PPO). PPO démontre généralement une stabilité et des performances supérieures, en particulier pour les programmes à grande échelle, en utilisant un objectif de substitution tronqué et une Estimation Généralisée de l'Avantage (GAE).

2.4 Générateur de Base de Données Basé sur RL (RLDBG)

RLDBG est une base de connaissances auto-évolutive qui automatise la collecte de données d'entraînement. Il invoque itérativement RLMOE pour explorer diverses séquences de passes, compile les configurations résultantes et les profile à l'aide d'un Évaluateur pour obtenir des métriques de vérité terrain. Ces paires CDFG–métriques sont stockées pour entraîner et affiner GNNPP, créant une boucle de rétroaction qui améliore la précision de la prédiction et l'efficacité de l'exploration au fil du temps.

3. Contributions Clés

L'article expose quatre contributions principales :

Cadre Unifié : Introduction de MileStone, un cadre qui formule l'ordonnancement des phases de compilateur comme un problème d'optimisation multi-objectifs équilibrant le temps d'exécution, la taille du code et la consommation énergétique sous des contraintes définies par l'utilisateur.
Modèle Neuronal Basé sur Graphes : Développement d'un modèle GNN qui apprend les propriétés structurelles et sémantiques à partir des graphes IR pour prédire avec précision les métriques de performance des programmes.
Exploration Basée sur RL : Mise en œuvre d'une approche basée sur RL (DQN/PPO) pour explorer les séquences de passes et identifier les compromis Pareto-optimaux entre plusieurs objectifs.
Mécanisme d'Auto-Amélioration : Intégration d'un mécanisme de collecte de données auto-évolutif (RLDBG) qui améliore à la fois la précision prédictive et l'efficacité de l'exploration en agrégeant des résultats d'optimisation divers.

4. Résultats Expérimentaux

Les expériences ont été menées sur des benchmarks standards (PolyBench : gemm, 3mm, floyd-warshall) utilisant un GPU NVIDIA RTX 3090TI. Le cadre a été comparé aux niveaux d'optimisation LLVM (-O1 à -O3), aux méthodes de recherche heuristique (Algorithme Génétique, Optimisation par Essaim de Particules) et à des agents RL autonomes.

Solutions Pareto-Optimales : RLMOE (utilisant à la fois DQN et PPO) a systématiquement surpassé les références, trouvant des solutions occupant des régions de l'espace de solutions avec une consommation énergétique plus faible et des tailles de code plus réduites tout en maintenant des temps d'exécution compétitifs.
Satisfaction des Contraintes : Sous des contraintes énergétiques spécifiées par l'utilisateur, RLMOE a atteint des taux de correspondance significativement plus élevés (90–93 %) par rapport aux agents RL autonomes (83–85 %) et aux niveaux d'optimisation traditionnels (3–9 %).
Réduction du Temps d'Exécution : Sous des budgets énergétiques identiques, MileStone a réduit le temps d'exécution jusqu'à 45 % par rapport à LLVM -O3. Plus précisément, RLMOE-PPO a montré des réductions de 15 à 45 % sur différents benchmarks.
Analyse Architecturale : L'étude a déterminé qu'une architecture GCN à deux couches offrait le meilleur équilibre entre précision de prédiction et évitement du problème de lissage excessif (oversmoothing).

5. Importance et Revendications

L'article revendique que MileStone fournit une solution efficace et évolutive pour l'ordonnancement multi-objectifs des phases de compilateur. Son importance réside dans :

Dépasser l'Optimisation Mono-Objectif : Il navigue avec succès sur la surface de compromis entre le temps d'exécution, la taille du code et l'énergie, permettant aux compilateurs de s'adapter à des exigences matérielles et de charge de travail spécifiques (par exemple, prioriser l'efficacité énergétique dans les appareils IoT).
Efficacité : En combinant la prédiction statique basée sur GNN avec RL, le cadre évite les coûts prohibitifs de la recherche exhaustive et du profilage dynamique répété.
Adaptabilité : La base de données auto-évolutive permet au système de s'améliorer au fil du temps, capturant des configurations Pareto-efficaces diverses que les heuristiques statiques manquent.

Les auteurs concluent que l'intégration de l'apprentissage de graphes statiques avec la recherche basée sur le renforcement offre une voie robuste pour l'optimisation de pipelines de compilateurs complexes, en particulier dans les scénarios où plusieurs métriques de performance contradictoires doivent être équilibrées. Des travaux futurs sont proposés pour étendre le cadre à des charges de travail industrielles plus vastes, intégrer des modèles micro-architecturaux détaillés et prendre en charge des scénarios d'optimisation dynamique.