COAV35 · Compilation avancée¶

L'UE qui répond à la question la plus fréquente d'une session d'optimisation : « pourquoi cette boucle n'est-elle pas vectorisée ? » On y entre dans un compilateur de production, et on y écrit une passe.

Fiche signalétique¶


Code	COAV35
Crédits	5 ECTS
Semestre	5, spécialisation — mardi matin
Responsable	CARRIBAULT Patrick
Concurrentes sur le créneau	PRRU35, DMIA35, MOSA35
Choix	Une des trois UE de spécialisation, en accord avec l'entreprise
Prérequis	Programmation informatique de type C/C++ — ASCO23 n'est pas exigée
Effectif max	30

Ce que dit la brochure¶

Objectifs cités :

« Les thèmes et compétences abordés dans cette UE sont la compilation et l'optimisation de code pour les applications parallèle haute performance. Le compilateur fait partie intégrante de la pile logicielle d'un supercalculateur et sert, au départ, de traducteur pour convertir un code source (par exemple du C++) vers un langage compréhensible par un processeur (assembleur ou langage binaire). Cette UE se focalise sur des capacités supplémentaires d'un compilateur HPC notamment la transformation et l'optimisation du code en entrée afin d'améliorer les performances sur un processeur cible.

L'objet est de présenter les concepts et la structure interne d'un compilateur travaillant sur des applications dédiées au calcul haute performance. Il s'agit ainsi de comprendre les différentes représentations qu'un tel compilateur met en place afin de pouvoir appliquer des transformations (analyses ou optimisations) respectant la sémantique initiale du code. Ce module permet également de découvrir l'organisation de compilateurs de production open-source comme GCC ou LLVM. »

Contenu cité, en trois parties :

Introduction à la structure d'un compilateur optimisant : description des différentes parties (front-end, middle-end, back-end) ; gestion de multiples langages (C, C++, FORTRAN) ; illustration sur compilateurs open-source de production (LLVM et GCC).
Notion de passe d'optimisation et d'analyse : représentation intermédiaire ; focalisation sur les transformations et optimisations pour le HPC ; manipulation des boucles ; vectorisation (génération d'instructions de type SIMD comme AVX).
TD sur compilateur de production (GCC/LLVM) : étude d'une passe d'optimisation ; développement d'une nouvelle passe dans le compilateur ; validation sur des codes de calcul.

Ce que ça vaut pour le HPC¶

Élevé, et l'UE est mal comprise par les étudiants qui la fuient.

Beaucoup d'élèves imaginent qu'un cours de compilation est un cours d'analyse syntaxique. La brochure est explicite : COAV35 traite le middle-end et le back-end, c'est-à-dire la moitié du compilateur qui fait gagner des FLOPS.

Trois raisons de la prendre au sérieux.

1. Le compilateur est votre premier outil d'optimisation, et vous ne le connaissez pas. Une différence entre -O2 et -O3 -march=native -ffast-math peut donner un facteur trois sur le même code source. Savoir ce que fait chaque option, et surtout ce qui l'empêche d'agir, est le levier le moins coûteux de tout le HPC : zéro ligne de code modifiée.

2. La vectorisation est le sujet le plus rentable du semestre. Sur un processeur avec AVX-512, une boucle vectorisée en double précision traite huit éléments par instruction au lieu d'un. Le facteur théorique est de huit, et il est souvent perdu pour des raisons que le compilateur pourrait expliquer si on savait lire ses rapports.

3. « Développement d'une nouvelle passe dans le compilateur ». Écrire une passe LLVM, la faire tourner sur du vrai code et voir l'effet, c'est une expérience formatrice et une ligne de CV qui ouvre des portes. Les équipes de compilateurs — chez Intel, NVIDIA, AMD, Arm, ou dans les laboratoires — recrutent peu de monde et cherchent précisément des gens qui ont fait cela.

Les cinq raisons pour lesquelles une boucle n'est pas vectorisée

À connaître par cœur. C'est le diagnostic le plus fréquent en optimisation.

Dépendance de données réelle. a[i] = a[i-1] + b[i] ne peut pas être vectorisé : chaque itération dépend de la précédente. Pas de remède, sinon changer d'algorithme (ou utiliser une scan parallèle).
Aliasing supposé. Le compilateur ne peut pas prouver que les pointeurs a et b ne se chevauchent pas, donc il n'ose pas. Remède : le mot-clé restrict en C, __restrict__ en C++, ou #pragma omp simd.
Accès non contigus. Un pas différent de 1, ou une indirection (a[idx[i]]), empêche le chargement vectoriel efficace. Remède : changer la disposition des données — c'est la question AoS contre SoA.
Appel de fonction non inlinée dans la boucle. Le compilateur ne peut pas vectoriser à travers un appel opaque. Remède : inline, ou mettre la fonction dans le même fichier, ou activer l'optimisation à l'édition de liens (-flto).
Contrôle de flot complexe. Un break, un return au milieu, ou une borne de boucle inconnue au moment de la compilation. Remède : simplifier, ou utiliser des opérations masquées si l'architecture les propose (AVX-512 le fait).

L'outil de diagnostic : sous GCC, -fopt-info-vec et -fopt-info-vec-missed ; sous Clang, -Rpass=loop-vectorize et -Rpass-missed=loop-vectorize avec -Rpass-analysis=loop-vectorize. Le compilateur vous dit littéralement pourquoi il a refusé. Presque personne ne lui demande.

Arriver prêt¶

⏱ 15 h :

Savoir lire de l'assembleur x86-64. Le chapitre 3 de Bryant & O'Hallaron, et l'habitude de Compiler Explorer. ⏱ 8 h. Si vous avez pris ASCO23, c'est acquis.
Installer LLVM depuis les sources et compiler l'exemple de passe du tutoriel officiel Writing an LLVM Pass. C'est long (la compilation de LLVM prend une à deux heures) et il vaut mieux l'avoir fait avant le premier TP. ⏱ 5 h.
Savoir lire de l'IR LLVM. clang -S -emit-llvm -O2 fichier.c -o - affiche la représentation intermédiaire. Comprendre la forme SSA, les blocs de base, les phi. ⏱ 2 h.

Ressources¶

Priorité 1¶

Ken Kennedy, Randy Allen, Optimizing Compilers for Modern Architectures: A Dependence-Based Approach, Morgan Kaufmann, 2001. Le livre de cette UE. Analyse de dépendance, transformations de boucles (échange, fusion, distribution, skewing, tiling), vectorisation, parallélisation automatique. Ancien mais non remplacé : les fondements n'ont pas changé.
La documentation LLVM (llvm.org/docs) : LLVM Language Reference Manual, Writing an LLVM Pass, LLVM Programmer's Manual, et la documentation du Loop Vectorizer. Gratuite, à jour, et c'est la source de vérité.
Les Internals de GCC (gcc.gnu.org/onlinedocs/gccint/), et la documentation de GIMPLE et de RTL, les deux représentations intermédiaires de GCC. Plus rugueux que celle de LLVM mais nécessaire si le TD porte sur GCC.

Priorité 2¶

Keith Cooper, Linda Torczon, Engineering a Compiler, 3ᵉ éd. Pour la structure d'ensemble, la forme SSA et l'allocation de registres.
Steven Muchnick, Advanced Compiler Design and Implementation. Le catalogue des optimisations classiques. Référence de consultation.
Les LLVM Developers' Meeting : les enregistrements et diapositives sont publics. Chercher les tutoriels d'introduction aux passes et les exposés sur le vectoriseur.
Le blog et les exposés de la communauté MLIR, pour la génération de code moderne et les compilateurs de tenseurs. C'est l'état de l'art actuel pour l'IA et de plus en plus pour le HPC.

Priorité 3 — la vectorisation en pratique¶

Les manuels d'optimisation d'Agner Fog (agner.org/optimize), et surtout les tables d'instructions.
L'Intel Intrinsics Guide et l'Intel 64 and IA-32 Architectures Optimization Reference Manual.
Le Arm Neoverse Software Optimization Guide et la documentation SVE (Scalable Vector Extension), pour l'architecture ARM qui monte fortement en HPC — plusieurs des machines les plus efficaces énergétiquement sont sur ARM.
llvm-mca (Machine Code Analyzer) et uiCA ou OSACA : des outils qui analysent statiquement un bloc d'assembleur et prédisent son débit en cycles. Précieux pour comprendre un goulot d'unité d'exécution.
MAQAO (maqao.org, développé à l'Université de Versailles Saint-Quentin) : analyse les boucles d'un binaire et produit un rapport expliquant les limitations, y compris les raisons de non-vectorisation. Outil français, orienté HPC, peu connu et très utile.

Exercices¶

E1 · ★ ⏱ 2 h — Le voyage des options. Prendre un noyau simple (produit scalaire, ou un stencil 1D) et le compiler avec -O0, -O1, -O2, -O3, -O3 -march=native, -O3 -march=native -ffast-math. Mesurer les six, et lire les six sorties assembleur sur Compiler Explorer. Identifier à quelle étape la vectorisation apparaît, et ce que -ffast-math change exactement.

À propos de -ffast-math

Cette option autorise le compilateur à violer la norme IEEE 754 : réassocier les additions flottantes, supposer qu'il n'y a pas de NaN ni d'infini, remplacer une division par une multiplication par l'inverse. Elle peut apporter un facteur deux, notamment en permettant la vectorisation des réductions. Elle peut aussi rendre un code numériquement faux, et elle est globale, donc elle affecte tout le fichier.

La pratique professionnelle : ne jamais l'activer globalement sur un code scientifique, mais utiliser les options fines (-fno-math-errno, -fassociative-math) sur les fichiers où l'analyse numérique l'autorise, et documenter la décision. Et toujours valider numériquement après.

E2 · ★★ ⏱ 3 h — Le rapport de vectorisation. Écrire cinq boucles, une par raison de non-vectorisation de l'encadré ci-dessus. Compiler avec -fopt-info-vec-missed (GCC) ou -Rpass-missed=loop-vectorize (Clang), et recueillir les messages. Puis corriger chacune — restrict, changement de disposition, inline, simplification — et vérifier que la boucle devient vectorisée et plus rapide. C'est l'exercice le plus directement rentable de toute l'UE.

E3 · ★★ ⏱ 3 h — Lire de l'IR LLVM. Compiler un petit programme en IR (clang -S -emit-llvm), en -O0 puis en -O2, et comparer. Identifier les transformations opérées : propagation de constantes, élimination de code mort, mem2reg (promotion de variables mémoire en registres SSA), déroulement de boucle, inlining. Puis utiliser opt -print-after-all pour voir l'IR après chaque passe.

E4 · ★★★ ⏱ 4 h — Les transformations de boucles à la main. Prendre un nid de boucles de multiplication matricielle et appliquer manuellement les transformations du cours : échange de boucles, tiling à une puis deux dimensions, déroulement, fusion. Mesurer chacune. Puis vérifier lesquelles le compilateur faisait déjà tout seul (indice : le tiling automatique existe mais est timide). Cela répond à une question pratique importante : que faut-il faire à la main et que peut-on laisser au compilateur ?

E5 · ★★★ ⏱ 5 h — Une passe d'analyse LLVM. Écrire une passe qui, pour chaque fonction, compte et rapporte : le nombre de blocs de base, le nombre de boucles, la profondeur maximale d'imbrication, le nombre d'opérations flottantes, et le nombre d'accès mémoire. Autrement dit, une passe qui calcule l'intensité arithmétique statique de chaque boucle. C'est utile en soi, et c'est le pont direct avec le roofline de PDSP35.

E6 · ★★★★ ⏱ 8 h — Une passe de transformation. Écrire une passe qui modifie le code. Suggestions, par difficulté croissante :

insérer un compteur d'exécution à l'entrée de chaque boucle, et un rapport en fin de programme — c'est un profileur par instrumentation, en une passe ;
appliquer une réduction de force : remplacer une multiplication par une constante puissance de deux par un décalage ;
dérouler une boucle d'un facteur fixe, et vérifier l'effet sur la performance ;
détecter les boucles candidates au tiling et émettre un avertissement.

Valider sur des codes de calcul réels, comme le demande le programme.

E7 · ★★★ ⏱ 4 h — llvm-mca et le goulot d'unité. Prendre une boucle chaude vectorisée, extraire son assembleur, et l'analyser avec llvm-mca. Lire le rapport : quelle unité d'exécution est saturée, quel est le débit prédit en cycles par itération, y a-t-il un goulot de port. Comparer la prédiction à la mesure réelle. Vous découvrirez que la prédiction est souvent bonne à 10 % près, ce qui en fait un outil de diagnostic précieux.

Projet¶

Projet COAV35 · Le diagnostic de vectorisation d'une application réelle

⏱ 35 h · ★★★★

Sujet. Prendre une application de calcul réelle et produire un audit complet de sa vectorisation, avec des améliorations implémentées et mesurées.

Candidats : les mini-applications du projet Exascale (LULESH, miniFE, XSBench, SW4lite), ou une application Fortran — ce qui est particulièrement intéressant puisque COAV35 traite explicitement la gestion multi-langages, et que les codes Fortran se vectorisent souvent mieux que les codes C, l'absence d'aliasing de pointeurs y étant garantie par le langage.

Les sept parties :

Recensement des boucles chaudes : profiler, identifier les boucles qui consomment plus de 5 % du temps. En général trois à dix boucles portent 80 % du temps.
Rapport de vectorisation de chacune, avec les options du compilateur, et classement par raison de non-vectorisation.
Analyse statique avec MAQAO ou llvm-mca : quel est le débit prédit, quelle unité limite.
Modèle : pour chaque boucle, l'intensité arithmétique et la position sur le roofline. Une boucle memory bound ne gagnera rien à être vectorisée — savoir cela évite de perdre du temps, et c'est le résultat le plus utile de l'audit.
Interventions : pour les boucles compute bound non vectorisées, appliquer les remèdes et mesurer. Documenter aussi les échecs.
Comparaison de compilateurs : GCC, Clang, et si disponible un compilateur vendeur (icx, nvc, armclang). Les écarts sont parfois considérables sur la même boucle, et c'est un résultat publiable en soi.
Synthèse : un tableau boucle par boucle avec état initial, action, gain, et le gain total sur l'application.

Le résultat attendu. Réaliste : 10 à 40 % de gain sur l'application complète, avec deux ou trois boucles qui gagnent un facteur deux à quatre. Ce n'est pas spectaculaire, et c'est précisément le point : la loi d'Amdahl s'applique à l'optimisation, et savoir mesurer ce gain modeste honnêtement vaut mieux que d'annoncer un facteur dix sur une micro-boucle.

Pourquoi ce projet. Parce que c'est le travail réel des équipes de support applicatif dans les centres de calcul, et parce qu'un audit de vectorisation rigoureux sur une application connue est un document qu'on peut montrer.

Erreurs fréquentes¶

Six fautes de compilation

Mesurer en -O0. Sans optimisation, on mesure le coût des abstractions et non l'algorithme. Aucune conclusion valide.
Activer -ffast-math sans validation numérique. Voir l'encadré ci-dessus. C'est la manière la plus rapide de produire un code rapide et faux.
Oublier -march=native. Sans indication d'architecture cible, le compilateur génère du code pour un x86-64 de base, sans AVX. On perd un facteur quatre à huit sur les boucles vectorisables, gratuitement. Attention toutefois : le binaire ne sera plus portable sur une machine plus ancienne — d'où l'existence de -mtune, des function multiversioning et de la compilation par dispatch d'exécution.
Croire le compilateur quand il dit avoir vectorisé. Il peut vectoriser une boucle et produire un code plus lent, si les accès sont dispersés et nécessitent des instructions de rassemblement (gather). Vérifiez toujours par la mesure, pas par le rapport.
Déroulez trop. Un déroulement agressif augmente la pression sur les registres ; au-delà d'un seuil, le compilateur déverse en mémoire (spilling) et la performance s'effondre. Il y a un optimum, et il se mesure.
Ignorer -flto. L'optimisation à l'édition de liens permet l'inlining entre fichiers, ce qui débloque parfois une vectorisation impossible autrement. Coût : un temps de compilation plus long. Souvent rentable.

Comment l'UE s'articule avec le reste¶

UE ou chapitre	Lien
ASCO23 (S3)	Le prédécesseur naturel, non exigé
Architecture et mémoire	Le versant matériel du SIMD : COAV35 en compense une partie
ICPA24 (S4)	L'outlining d'OpenMP, vu du côté compilateur
PGPU35 (S5)	La compilation pour accélérateur, `nvcc`, la compilation JIT
PDSP35 (S5)	L'intensité arithmétique, que la passe de E5 calcule
PRSA24 (S4)	Le refactoring guidé par le rapport du compilateur
Architecture et mémoire	Le SIMD écrit à la main, les intrinsics

À retenir¶

COAV35 en trois phrases

Ce n'est pas un cours d'analyse syntaxique : c'est le middle-end et le back-end, c'est-à-dire la moitié du compilateur qui fait gagner des FLOPS — transformations de boucles et vectorisation SIMD. La compétence la plus rentable est de savoir demander au compilateur pourquoi il n'a pas vectorisé (-fopt-info-vec-missed, -Rpass-missed=loop-vectorize) et de connaître les cinq remèdes. Le livre est Kennedy & Allen, Optimizing Compilers for Modern Architectures, et écrire une passe LLVM est une ligne de CV qui ouvre des portes rares.

Fiche suivante : IQRO35 · Informatique quantique et recherche opérationnelle.