ASCO23 · Assembleur et compilation¶

L'UE que ce document recommande de laisser. Cette fiche existe pour deux raisons : parce que la recommandation inverse est défendable et qu'il faut pouvoir la juger, et parce que si vous la laissez, il faut savoir quoi rattraper.

Fiche signalétique¶


Code	ASCO23
Crédits	4 ECTS, 42 h
Semestre	3, option — lundi matin
Responsable	BUREL Guillaume
Concurrentes sur le créneau	GADE23, MERR23
Choix	Une seule option au S3, avec l'accord de l'entreprise
Prérequis	Programmation impérative, programmation fonctionnelle
Effectif max	62

Ce que dit la brochure¶

Objectifs cités :

« Le code binaire exécuté sur les machines peut être représenté de façon lisible par un langage assembleur. Cet UE présente les notions de base de l'assembleur, puis explique comment passer d'un langage de programmation de haut niveau à de l'assembleur grâce à la compilation. Transformer un ensemble de sources écrites dans des langages de haut niveau en code exécutable par la machine tout en l'optimisant est une tâche complexe chaînant de nombreuses étapes. »

L'objet est triple : décrire comment les abstractions de haut niveau sont traduites en langage machine ; faire découvrir les mécanismes d'un compilateur, ainsi que « plusieurs techniques mathématiques utiles dans de nombreux domaines de l'informatique (réécriture, calcul de point fixe) » ; faire connaître les outils automatisant les premières étapes de la compilation au cours d'un projet.

Contenu cité :

code machine et langage assembleur ;
langage assembleur RISC-V ;
architecture d'un compilateur ;
analyse syntaxique, générateurs d'analyseurs syntaxiques (lex/yacc) ;
analyse sémantique ;
sélection d'instructions ;
graphe de flot de contrôle ;
explicitation des conventions d'appel ;
analyse de durée de vie ;
allocation des registres.

Dix-neuf compétences sont listées, la plupart au niveau « 2 – Maîtrise ».

Ce que ça vaut pour le HPC¶

Variable selon la moitié considérée, et c'est tout l'enjeu de la décision.

La moitié qui rapporte¶

Code machine et assembleur. Savoir lire l'assembleur généré est une compétence quotidienne en optimisation : c'est ainsi qu'on vérifie qu'une boucle a été vectorisée, qu'un appel a été inliné, qu'une division a été remplacée par une multiplication.
Graphe de flot de contrôle et analyse de durée de vie. Ce sont les structures sur lesquelles reposent toutes les analyses d'un compilateur optimisant, donc le vocabulaire de COAV35 au semestre 5.
Conventions d'appel. Utile pour comprendre le coût d'un appel de fonction, et indispensable pour interfacer C, C++ et Fortran — ce qui arrive tout le temps en HPC.
Allocation de registres. Explique pourquoi une boucle avec trop de variables vivantes déborde en mémoire (spilling) et perd brutalement en performance. C'est un phénomène qu'on rencontre en vrai quand on déroule trop agressivement une boucle.

La moitié qui ne rapporte pas directement¶

Analyse lexicale et syntaxique, lex et yacc. De la belle informatique, utile si vous écrivez un langage ou un analyseur, sans effet sur la performance d'un code de calcul.
RISC-V. Excellent choix pédagogique — le jeu d'instructions est propre, petit et libre, ce qui en fait un support d'enseignement idéal. Mais les machines que vous optimiserez seront en x86-64 ou en ARM64, dont les jeux d'instructions sont beaucoup plus larges et dont les extensions vectorielles (AVX, AVX-512, NEON, SVE) sont précisément ce qui compte. RISC-V monte dans le HPC — l'Europe y investit avec l'European Processor Initiative — mais ce n'est pas encore ce qu'on trouve dans un centre de calcul.

Le calcul de la décision¶

En FISA, ASCO23 est en concurrence directe avec GADE23 et MERR23 sur le créneau du lundi matin, et surtout avec les deux autres candidates HPC du semestre, PRPA23 et ARSE23 — puisque vous n'avez qu'une seule option.

Argument	Pour ASCO23	Contre
Recouvrement avec une UE du S5	COAV35 reprend le back-end, vous arriverez avec le vocabulaire	Ce n'est pas un prérequis : la fiche COAV35 n'exige que « programmation type C/C++ »
Rattrapable seul	—	Oui, ⏱ 40 h. C'est l'UE la plus facile à rattraper en autodidacte du cursus
Matériel nécessaire	Aucun : un portable et Compiler Explorer suffisent	C'est précisément l'argument qui la fait perdre face à PRPA23, dont les TP demandent des machines
Utilité en compétition	Indirecte	PRPA23 et ARSE23 sont directes
Utilité pour une carrière compilateur	Décisive	—
Effectif	62 places, aucune tension	30 places pour PRPA23 et ARSE23

La recommandation de ce document reste PRPA23, parce que c'est le seul enseignement de MPI du cursus FISA et qu'il ne se rattrape pas sur un portable, alors qu'ASCO23 se rattrape intégralement seul : il existe d'excellents livres, un outil parfait (Compiler Explorer) et aucune machine coûteuse n'est nécessaire.

Prenez ASCO23 si la compilation, les langages ou la sécurité bas niveau vous attirent réellement. Dans ce cas, ASCO23 au S3 puis COAV35 au S5 dessinent un profil rare et très employable — et vous aurez de toute façon COAV35 sans ASCO23 si vous préférez l'inverse.

Programme de rattrapage · ⏱ 40 h¶

C'est le contenu du chapitre Arbitrages, détaillé ici.

Volet 1 · Lire l'assembleur · ⏱ 15 h¶

La méthode

Faites du x86-64 et de l'ARM64, pas du RISC-V. Objectif : lire, pas écrire.

Bryant & O'Hallaron, Computer Systems: A Programmer's Perspective, 3ᵉ éd., chapitre 3 — la meilleure introduction existante à l'assembleur x86-64 pour un programmeur. ⏱ 8 h.
Compiler Explorer (godbolt.org) en permanence. Le réflexe à acquérir : chaque fois que vous vous demandez « est-ce que le compilateur fait ceci ? », vous collez dix lignes dans Godbolt et vous regardez. ⏱ pratique continue.
Les manuels d'Agner Fog (agner.org/optimize) : quatre volumes gratuits, dont un sur l'optimisation en C++, un sur l'optimisation en assembleur et surtout les tables d'instructions donnant latence et débit de chaque instruction sur chaque microarchitecture. C'est la référence que les professionnels de l'optimisation utilisent. ⏱ 5 h de lecture ciblée.
L'Intel Intrinsics Guide en ligne, et l'Intel 64 and IA-32 Architectures Optimization Reference Manual. ⏱ consultation.

Exercice de contrôle : prendre une boucle de produit scalaire, la compiler en -O0, -O2, -O3, -O3 -march=native, et commenter les quatre sorties assembleur. Identifier l'instruction vfmadd231pd (ou équivalent) qui prouve la vectorisation et la fusion multiplication-addition.

Volet 2 · Comprendre un compilateur · ⏱ 25 h¶

Les livres, par ordre d'utilité pour le HPC

Ken Kennedy, Randy Allen, Optimizing Compilers for Modern Architectures: A Dependence-Based Approach, Morgan Kaufmann, 2001. Le livre sur les transformations de boucles : analyse de dépendance, échange de boucles, fusion, distribution, tiling, vectorisation, parallélisation automatique. C'est exactement la matière de COAV35 et de l'optimisation HPC. Si vous ne lisez qu'un livre de compilation, lisez celui-là.
Keith Cooper, Linda Torczon, Engineering a Compiler, 3ᵉ éd., 2022. L'ouvrage d'introduction le plus équilibré, avec un bon traitement de l'allocation de registres et de la forme SSA.
Steven Muchnick, Advanced Compiler Design and Implementation, 1997. Le catalogue exhaustif des optimisations classiques. Référence, pas lecture.
Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, 2ᵉ éd., 2006 — le dragon book. Excellent sur l'analyse syntaxique, ce qui est justement la partie la moins utile ici.
La documentation de LLVM (llvm.org/docs), en particulier LLVM Language Reference et Writing an LLVM Pass. Gratuit et à jour.

Projet de contrôle · ★★★ ⏱ 15 h : écrire un mini-compilateur d'expressions arithmétiques avec variables et affectations, vers de l'assembleur x86-64 fonctionnel. Analyse par descente récursive écrite à la main (ni lex ni yacc), allocation de registres naïve, génération de code. Le programme produit doit s'assembler avec as et se lier avec ld ou gcc. C'est largement suffisant pour comprendre la chaîne, et COAV35 fera le reste.

Ce que le rattrapage ne donnera pas¶

Le projet encadré d'ASCO23, qui est probablement un compilateur plus complet avec lex et yacc, et la culture RISC-V. Aucun des deux n'est nécessaire pour faire du HPC.

Ressources supplémentaires si vous prenez l'UE¶

Si vous choisissez ASCO23, ajoutez les compléments suivants pour en tirer une valeur HPC maximale :

Orienter le projet vers l'optimisation. Si l'énoncé le permet, ajoutez à votre compilateur une passe d'optimisation locale : propagation de constantes, élimination de code mort, ou réduction de force (remplacer une multiplication par un décalage). Le calcul de point fixe mentionné dans les objectifs de l'UE est exactement la technique pour cela.
Comparer votre génération de code à celle de GCC sur les mêmes entrées, et mesurer l'écart. Vous constaterez un facteur considérable, et comprendrez où il se niche : allocation de registres, ordonnancement d'instructions, vectorisation.
Faire le lien avec l'architecture : lire en parallèle le chapitre 3 de Hennessy & Patterson sur le parallélisme d'instructions, pour comprendre pourquoi l'ordre des instructions émises par le compilateur compte.

Comment l'UE s'articule avec le reste¶

UE ou chapitre	Lien
COAV35 (S5)	La suite naturelle, mais accessible sans ASCO23
Architecture et mémoire	Le complément matériel : pipeline, SIMD, caches — absent du catalogue FISA
Architecture et mémoire	Le complément matériel : pipeline, caches, SIMD
LASF24 (S4, tronc commun)	Recouvrement sur les langages et systèmes formels, automates

À retenir¶

ASCO23 en trois phrases

C'est l'UE à laisser dans un parcours orienté HPC, parce qu'elle n'est prérequis de rien — pas même de COAV35 — et parce qu'elle est la seule des trois candidates du S3 qui se rattrape intégralement sur un portable. Sa moitié utile — lire l'assembleur, graphe de flot, durée de vie, conventions d'appel — se rattrape en quarante heures avec Bryant & O'Hallaron, Compiler Explorer et Kennedy & Allen. Prenez-la si et seulement si la compilation est votre projet de carrière, et sachez qu'alors vous n'aurez ni MPI ni système dans votre cursus.

Chapitre suivant : Vue d'ensemble du semestre 4.