Compilation avancée et optimisation de programmes
Cours de recherche (24h de cours, travail
sur des articles scientifiques)
Cours : Alain Darte, Paul Feautrier (Alain.Darte, Paul.Feautrier)
Filière(s) : architecture et compilation, informatique distribuée
Présentation générale
Ce cours s'inscrit naturellement en complément aux cours de base
« Compilation » de Tanguy Risset, « Recherche Opérationnelle » de Paul
Feautrier et « Algorithmique et ordonnancement sur grappes de calcul »
de Frédéric Vivien et Frédéric Desprez. Néanmoins, il est accessible
à tout étudiant ayant des connaissances de base en programmation,
architecture, complexité et algorithmique.
Le but du cours est de présenter quelques problèmes de compilation
et d'optimisation de codes, liés à l'utilisation du parallélisme et
de la mémoire. Les principaux champs d'application sont la
parallélisation automatique de programmes, l'exploitation logicielle
du parallélisme disponible dans les (mono)-processeurs récents, et
la synthèse automatique de haut niveau de circuits spécialisés. On
sera donc amené à évoquer différents types de plates-formes,
machines parallèles, micro-processeurs modernes (super-scalaires,
VLIW ou EPIC) ou même circuits dédiés, mais le cours s'intéressera
essentiellement non pas à des architectures particulières mais aux
aspects fondamentaux (modélisation, résultats théoriques généraux et
algorithmique) des optimisations de codes étudiées. On abordera des
problèmes d'analyse de code, de transformation de code,
d'ordonnancement cyclique (incluant le pipeline logiciel et les
systèmes d'équations récurrentes uniformes), d'allocation de
registres et de la mémoire, etc.
Plan détaillé du cours (indicatif)
- Introduction
- Champ d'applications et présentation des sujets
abordés: a) machines parallèles, problèmes de placement des
données et des calculs, d'optimisation des communications, langage
HPF; b) micro-processeurs VLIW et EPIC, fonctionnalités, problèmes
d'allocation de registres et d'ordonnancement; c) conception de
circuits, réseaux systoliques, partitionnement, mémoire (taille
et traffic).
- Analyse de programmes
- Dépendances. Analyse du flot des données.
Méthodes de point fixe. Cas des tableaux: méthodes géométriques.
Présentation de l'outil de programmation linéaire paramétrique PIP.
- Pipeline logiciel
- Rappels d'ordonnancement de base.
Ordonnancement cyclique: complexité, heuristiques. Lien avec le
« retiming », technique de resynchronisation utilisée en synthèse
de circuits. Registres rotatifs. Déroulage de boucles. Codes avec
prédicats.
- Compilation-Parallélisation, premiers pas
- Transformations de
boucles. Algorithme d'Allen et Kennedy.
- Systèmes d'équations récurrentes uniformes
- Calculabilité et
ordonnancement. Liens avec les algorithmes de parallélisation
automatique de boucles. Applications à la synthèse automatique de
réseaux systoliques (méthode temps-espace, partitionnement,
développements récents).
- Génération de code à partir d'un ordonnancement
- Méthode de
Fourier-Motzkin (rappels). Algorithme de Quilleré/Bastoul. Algorithme de
Boulet/Feautrier. Optimisations du code objet. Application à la
synthèse de circuits embarqués. Notation RTL. Construction de
l'automate de contrôle.
- Localité et allocation mémoire
- Fusion de boucles avec et sans
décalage. Contraction de tableaux. Réutilisation de la mémoire et
application à la synthèse automatique d'accélérateurs matériels.
Localité pour les systèmes distribués. Localité pour les caches.
Bibliographie
-
Architecture
-
-
John L. Hennessy et David A. Patterson. Computer
architecture: a quantitative approach (2nd edition). Morgan
Kaufmann, 1996.
- W. A. Triebel. Itanium Architecture for Software
Developers. Intel Press, 2000.
- Compilation et parallélisation automatique
-
- Hans Zima et Barbara Chapman. Supercompilers for Parallel
and Vector Computers. ACM Press, 1990.
- Michael Wolfe. High Performance Compilers For Parallel
Computing. Addison-Wesley Publishing Company, 1996.
- A. W. Appel. Modern Compiler Implementation in ML (or
Java). Cambridge University Press, 1998.
- Alain Darte, Yves Robert et Frédéric Vivien. Scheduling
and Automatic Parallelization. Birkhauser, 2000.
- J. Xue. Loop Tiling for Parallelism. Kluwer Academic
Publishers, 2000.
- Randy Allen et Ken Kennedy. Optimizing Compilers for
Modern Architectures. Morgan Kaufman Publishers, 2002.
- Ordonnancement
-
-
R. G. Parker. Deterministic Scheduling Theory. Chapman and
Hall, 1995.
- P. Chrétienne et E. G. Coffman. Scheduling Theory and its
Applications. J. Wiley and Sons. 1995.
- P. Brucker. Scheduling Algorithms. Springer, 1998.