La compilation est l’un des sujets d’étude fondamentale de l’informatique. Apparu avec les langages de haut niveau, et quasiment dès ses origines, elle a été utilisée pour améliorer les performances des applications. Tentant de suivre l’évolution des architectures et des nouveaux usages, la compilation s’est rapidement heurtée à des difficultés à pleinement exploiter les capacités du matériel. Depuis la naissance de l’informatique, nous sommes passés d’un monde réservé à des domaines précis (cryptanalyse avec Colossus) à un monde connecté et distribué utilisant des architectures variées et hétérogènes. Les objectifs ont aussi évolué, autrefois centré sur la vitesse d’exécution, ils intègrent maintenant des problématiques de mémoires, de consommations énergétiques ou de portabilité. Autant d’objectifs qui vont mener à des approches différentes.
Les stratégies de génération de code ont progressivement évoluée. À l’origine purement statique, les stratégies emploient aujourd’hui de plus en plus de dynamisme dû à différents besoins :
Portabilité : la segmentation du marché en matière de matériel impose aux concepteurs de fournir des solutions portables de leurs applications. Cela a pour corollaire que lors du développement d’une application on ne sait pas nécessairement sur quel jeu d’instruction cette application sera exécutée.
Performances : il y a un besoin d’avoir des applications rapides, réactives, économes en énergie ou avec une empreinte mémoire acceptable. Pour la vitesse d’exécution, on parle aujourd’hui de bogue de performance, l’application est fonctionnelle mais trop lente, entraînant une sensation d’application chancelante. Avec l’explosion du marché des smartphones et celui grandissant de l’Internet des Objets (IoT), les besoins en performances incluent aujourd’hui la consommation électrique et l’empreinte mémoire.
Contexte et nouveaux challenges
La question de la plate-forme peut se poser d’un point de vue de la portabilité qui trouve une réponse dans la virtualisation. La question de la performance vis-à-vis de la plate-forme est plus délicate. Quand la plate-forme est parfaitement connue cela autorise l’optimisation et la génération statique du code. Mais la durée de vie d’un logiciel est plus longue que celle du matériel et donc il est fort probable que la plate-forme change pendant la vie de l’application. L’utilisation de technologie de virtualisation peut alors permettre aux applications de suivre les évolutions de la plate-forme [20]. l’avantage de l’utilisation de la virtualisation dans le cas du suivi de l’évolution d’une architecture. Dans le premier cas , une application est compilée pour le CPU 1, pour lequel le compilateur sait qu’il existe une extension et sera donc en mesure de l’exploiter. Quant au CPU 2, il est de la même famille que le CPU 1 mais propose une extension supplémentaire. Le code ayant été généré de façon statique le programme n’est pas en mesure de l’utiliser. Dans le deuxième cas, l’application est compilée dans un code à octet. Le compilateur juste-à-temps présent sur les deux plates-formes a la pleine connaissance des extensions présentes sur les deux CPU, et est donc en mesure de créer un code utilisant les extensions présentes sur la machine.
Néanmoins, l’utilisation de ces techniques de virtualisation ne permet pas garantir les performances et la pleine utilisation du matériel. Si on prend le cas des GPU (“Graphical Processing Units”, Unité de Traitement Graphique), les constructeurs fournissent des couches de virtualisation afin de garantir une portabilité fonctionnelle des bases de code. Par contre les performances obtenues ne seront pas nécessairement à la hauteur des capacités du matériel. La sensibilité aux données de certains algorithmes a été elle aussi changée avec l’arrivée des architectures massivement multi-cœurs. Le traitement étant découpé en fonction des données, celles-ci influent sur le nombre de processus obtenus, les accès mémoires etc. Enfin, les techniques de virtualisation ne sont utilisables que s’il existe des ressources allouables à ces fins de générations. Ces outils vont prendre une place non négligeable dans le système, consommer de la RAM, des cycles CPU et de l’énergie. Dans le contexte de l’IoT par exemple, ces ressources coûtent cher du fait de leurs raretés. Mais même pour des systèmes moins contraints, il peut être difficile d’utiliser ces techniques à des fins d’adaptation de l’algorithme aux données.
Les temps de compilations
Introduction à la compilation et transformation de code
Aho et al. [3] définissent de façon générique le compilateur comme étant “un programme lisant un programme dans un langage, le langage source, et le traduit en un programme équivalant dans un autre langage, le langage cible”. Bien qu’étant large et simple, elle englobe bien le spectre des différentes méthodes existantes. Le premier compilateur est apparu dans les années 50 avec le A-0 System développé par Grace Hopper pour l’UNIVAC [89]. Ce compilateur n’effectuait que des opérations d’assemblage de routines qu’il avait préalablement chargé. À la fin des années 50, le premier compilateur complet et optimisant pour le langage FORTRAN apparut permettant ainsi la création de programmes exécutables sans le passage par la représentation assembleur. Au fil des années, les compilateurs ont continué à se développer en parallèle des langages, levant de nouvelles problématiques d’optimisations à mesure que les langages deviennent de plus haut niveau. La conception de ces compilateurs a aussi évolué vers une plus grande modularité et une architecture plus ou moins commune aujourd’hui. Les compilateurs modernes sont le plus souvent architecturés autour de 3 étages :
Partie frontale (front-end) : étage chargé de la lecture du langage source, du rapport des erreurs, d’optimisations spécifiques au langage et de la traduction vers la représentation intermédiaire (RI) de l’étage suivant. On pourra aussi désigner cette partie “le frontal” (du compilateur).
Partie intermédiaire (middle-end) : étage chargé des analyses et des transformations indépendantes du langage cible du programme dans la RI.
Partie arrière (back-end) : étage chargé des optimisations spécifiques au langage cible et de l’émission du programme dans le langage cible.
L’avantage de ce découpage, et notamment du passage par la RI, est qu’il permet de déconnecter le langage source du langage cible. Ainsi lors de l’ajout du support d’un nouveau langage source ou cible seul l’étage de la partie frontale, respectivement de la partie arrière, est à écrire. La partie frontale construit une représentation du programme d’entrée dans une forme proche du langage pour s’assurer que le programme est bien formé (respect de la syntaxe et de la grammaire). Une fois cette phase de vérifications effectuée il peut éventuellement effectuer des transformations propres au langage ou au domaine. Enfin une phase de traduction (“lowering” dans le vocabulaire de LLVM) permet de générer la représentation intermédiaire du programme dans celle de la partie intermédiaire du compilateur. Par traduction, on désigne le passage d’une représentation intermédiaire à une autre, normalement plus proche de la cible. La partie intermédiaire orchestre les phases d’optimisations indépendantes des cibles. Durant ces phases, d’autres représentations peuvent être utilisées selon les besoins. Dans la pratique, des optimisations spécifiques à des cibles ou familles de cibles peuvent aussi être lancées à ce niveau de façon à pouvoir tirer parti de ses représentations intermédiaires. La partie arrière va être responsable de la traduction du programme vers son langage. Cette étape effectue l’émission du code dans le langage de destination. Dans le cas de l’émission dans un langage machine, la partie arrière effectue une sélection d’instructions, l’allocation des registres, l’ordonnancement et des optimisations spécifiques à la cible comme le peephole optimisation, if-conversion, strengh reduction etc. En règle générale, les compilateurs modernes vont utiliser plusieurs représentations intermédiaires suivant les opérations à effectuer . Par exemple, LLVM [51] utilise comme représentation intermédiaire LLVA [2] pour sa partie intermédiaire, le SDAG, MI (Machine Instruction) et MC (Machine Code) dans sa partie arrière. Le greffon Polly [40], qui effectue des transformations polyédriques dans LLVM, intervient dans la partie intermédiaire et utilise aussi plusieurs autres représentations du programme pour communiquer avec CLooG, l’outil d’optimisation polyédrique. Selon la nature du langage source et cible, on peut désigner différents types de compilateurs que l’on pourra replacer dans les différents moments dans lesquels ils interviennent.
|
Table des matières
1 Introduction
1.1 Contexte et nouveaux challenges
1.2 Contributions
1.3 Plan du manuscrit
2 État de l’art
2.1 Les temps de compilations
2.2 Architectures
2.3 Temps de compilation et optimisations
2.4 Rétroaction et anticipation
2.5 Conclusion
3 Les verrous de la génération de code
3.1 Contexte général
3.2 Lien entre données et performances sur GPU
3.3 Gains et coûts de la spécialisation dynamique de code
3.4 Conclusion
4 Outillages développés
4.1 Motivation et approches
4.2 Approche orientée générateur : deGoal
4.3 Approche orientée fonctionnelle : Kahuna
4.4 Conclusion
5 Adaptation de la GEMM aux données sur GPU
5.1 Programmation des GPU
5.2 Produit matriciel
5.3 Solution proposée
5.4 Auto-tuning
5.5 Apprentissage machine
5.6 Résultats & discussion
5.7 Pistes d’évolution et améliorations
5.8 Conclusion
6 Étude de l’impact de la génération de code
6.1 Filtre biquad
6.2 Expérimentations
6.3 Résultats & discussions
6.4 Conclusion de l’expérimentation
6.5 Évolution de Kahuna
6.6 Conclusion
7 Conclusion
7.1 Résumé des réalisations
7.2 Discussions
7.3 Perspectives
Bibliographie Personnelle
Bibliographie
