Plan de cours optimisation Introduction à l'optimisation de code Notion de dépendances de données Optimisations de code indépendantes de la cible Exploitation du parallélisme d'instructions Optimisations de la localité Vectorisation, etc. 1. Introduction 1. Introduction aux dépendances de données 1. Introduction 1. Introduction 1. Introduction 1. Composantes fortement connexes 2. SimpleCPL 2. Les dépendances de données inter-itération 2. Supprimer des calculs inutiles 2. L'ordonnancement de code 2. La localité spatiale 2. Boucles vectorielles 3. Bibliographie 3. Graphes des dépendances 3. Élimination des sous-expressions communes 3. Graphes acycliques 3. La localité temporelle 3. Vectorisation 4. Le processus d'optimisation-1 4. Espace d'itérations 4. La propagation des copies 4. Le list scheduling 4. L'échange de boucles 4. Exploitation des instructions multimédia 5. Le processus d'optimisation-2 5. Vecteurs de distance de dépendance 5. La propagation des constantes 5. Le déroulage de boucles 5. Le blocage de boucle 5. Transformations unimodulaires 6. Mesure de la performance 6. Boucles parallèles 6. Variable d'induction 6. Cas des réductions 6. Interférences dans les caches 6. Directions de localité 7. Compilation et optimisations 7. Renommage de variables 7. Réduction de force pour les variables d'induction 7. Le pipeline logiciel 7. Array padding 7. Optimisations diverses 8. Les options de compilation 8. Expansion de ...
Plan de cours optimisation
Introduction à l'optimisation de code Notion de dépendances de données Optimisations de code indépendantes de la cible Exploitation du parallélisme d'instructions Optimisations de la localité Vectorisation, etc.
1. Introduction 1. Introduction aux dépendances de données 1. Introduction 1. Introduction 1. Introduction 1. Composantes fortement connexes
2. SimpleCPL 2. Les dépendances de données inter-itération 2. Supprimer des calculs inutiles 2. L'ordonnancement de code 2. La localité spatiale 2. Boucles vectorielles
3. Bibliographie 3. Graphes des dépendances 3. Élimination des sous-expressions communes 3. Graphes acycliques 3. La localité temporelle 3. Vectorisation
4. Le processus d'optimisation-1 4. Espace d'itérations 4. La propagation des copies 4. Le list scheduling 4. L'échange de boucles 4. Exploitation des instructions multimédia
5. Le processus d'optimisation-2 5. Vecteurs de distance de dépendance 5. La propagation des constantes 5. Le déroulage de boucles 5. Le blocage de boucle 5. Transformations unimodulaires
6. Mesure de la performance 6. Boucles parallèles 6. Variable d'induction 6. Cas des réductions 6. Interférences dans les caches 6. Directions de localité
7. Compilation et optimisations 7. Renommage de variables 7. Réduction de force pour les variables d'induction 7. Le pipeline logiciel 7. Array padding 7. Optimisations diverses
8. Les options de compilation 8. Expansion de variables 8. Extraction des calculs invariants 8. Le modulo scheduling 8. Unroll-and-jam
9. Représentations des programmes 9. Elimination de code mort 9. L'ordonnancement de trace 9. Fenêtres de références
10. Arbre de syntaxe abstraite 10. Optimiser les appels de fonctions 10. Les superblocs
11. Arbre des appels de fonctions 11. L'inlining 11. Les hyperblocs
12. Les blocs de base
13. Le graphe de flot de contrôle
file:///D|/Francois/CoursCD/HTML/Cours/sommaireArpo.htm [25/01/2002 13:30:40]Transformer pour la performance
Index
Transformer pour la performance
L'accroissement de performance des ordinateurs réside dans l'augmentation de
la fréquence d'horloge des processeurs et dans l'utilisation du parallélisme
entre instructions (les architectures superscalaires telles que le Pentium
d'Intel, l'Alpha de Digital). Cependant, à mesure que la performance de crête
augmente la structure des codes influe de plus en plus sur leurs temps
d'exécution effectifs. Dans ce cours nous abordons l'ensemble des notions
nécessaires à la compréhension des performances des codes. D'un coté, nous
introduisons les principaux mécanismes architecturaux influençant les
performances des programmes (pipeline, parallélisme entre instructions,
hiérarchie mémoire, etc.). De l'autre coté, nous montrons au travers des
techniques de transformations de programme l'impact de la structure des
programmes sur les performances.
caps@irisa.fr
Attention ceci est une version très
préliminaire
Dernière mise à jour : juin 2001
file:///D|/Francois/CoursCD/HTML/accueil.htm [25/01/2002 13:30:42]Transformer pour la performance
Index
Les fonctions principales du compilateur exemple
Le compilateur SimpleCPL est une mise en oeuvre simple (et inefficace) ayant pour but d'illustrer les principaux algorithmes utilisés lors de la
compilation. Le code produit est de l'assembleur VAS destiné à la machine VAM. Le langage d'entrée utilisé est VSL. Ce compilateur est mis en
oeuvre à l'aide du logiciel Salto qui fournit l'infrastructure de lecture du code intérmédiaire et de construction du graphe de contrôle de flot. Les
simplications suivantes ont été faites:
l Séparation du compilateur en une partie haute et une partie basse. La partie haute génère un code exécutable (de mauvaise qualité), la
partie basse implémente les analyses et les optimisations. En conséquence, l'allocation mémoire et la sélection des instructions sont
effectuées avant l'analyse de flot de données plutôt qu'après habituellement. Ceci pour avoir un code exécutable sur la machine VAM
avant la mise en oeuvre des optimisations et de l'allocation de registres (la machine VAM accepte les registres virtuels). Ceci permet de
comparer l'exécution avec et sans allocation de registres et de mettre en oeuvre les optimisations et l'analyse de flot de données dans
l'infrastructure Salto, plus appropriée pour cela.
l Il y a une correspondance directe entre les opérations du code intermédiaire et le code de la machine VAM. La phase de sélection des
instructions est donc triviale.
Etapes du compilateur SimpleCPL
La documentation du code du compilateur est ici.
caps@irisa.fr
Attention ceci est une version très
préliminaire
Dernière mise à jour : 07 août 2001
file:///D|/Francois/CoursCD/HTML/Docs/SimpleCPL.htm [25/01/2002 13:30:42]Transformer pour la performance
Index
Bibliographie
Adve (Sarita V.), Burger (Doug), Eigenmann (Rudolf),
Rawsthorne (Alasdair), Smith (Michael D.), Gebotys (Catherine
H.), Kandemir (Mahmut T.), Lilja (David J.), Choudhary (Alok
Adve97
N.), Fang (Jesse Z.) et Yew (Pen-Chung). "Theme feature:
Changing interaction of compiler and architecture". Computer,
vol. 30, no 12, décembre 1997, p. 51-58
Alfred V. Aho & Ravi Sethi & Jeffrey D. Ullman, " Compilers
principles, Techniques, and Tools ", Edition : Addison-Wesley,
1986Aho86
Compilateurs, principes, techniques et outils. Alfred Aho, Ravi
Sethi, Jeffrey Ullman. Dunod, 2000
A. Aiken et A. Nicolau. "Perfect Pipelining : a New Loop
Aiken88 Parallelization Technique". Lecture Note In Computer Science,
no300, 1988, pp. 221-235.
V.H. Allan, R.B. Jones, R.M. Lee et Allan S.J. "Software
Allan95 Pipelining". ACM Computing Surveys, vol. 27, no 3, septembre
1995, pp. 367-432.
R. Allen, K. Kennedy, Automatic Translation of FORTRAN
Programs to Vector Form, "ACM Transaction on Programming
Allen87
Languages and Systems", 1987, vol. 9, no 4, pp 491-542
http://www.acm.org/pubs/contents/journals/toplas/1987-9/#4
Amdahl G. M. "Validity of a single processor approach to
achieving large scale computing capabilities'' Proc. AFIPS 1967
Amdahl67
Spring Joint Computer Conference 30, Atlantic City, New Jersey
(Apr)483-485, 1967.
Amme (Wolfram), Braun (Peter), Thomasset (François) et
Amme98 Zehendner (Eberhard). "Data dependence analysis of assembly
code. In : PACT'98. octobre 1998.
Ancourt (C.) et Irigoin (F.). "Scanning Polyhedra with Do
Ancourt91 Loops". Third ACM SIGPLAN Symposium on Principles and
Practice of Parallel Programming, avril 1991, pp. 39-50.
Numerical C Extensions Group of ANSI X3J11. "Restricted
ANSIX3J11
pointers", août 1995. Site Internet
file:///D|/Francois/CoursCD/HTML/TablesDesMatieres/Bibliographie/index.htm (1 of 17) [25/01/2002 13:30:44]Transformer pour la performance
The Zephyr Compiler Infrastructure. A. Appel and J. Davidson
and N. Ramsey. Princeton University, novembre 1998. SiteAppel98a
Internet
A. Appel, "Modern compiler implementation in C", Cambridge,
Appel98b
1998
ARMARM
Matthew Arnold, Stephen Fin, Vivek Sarkar et Peter F. Sweeney,
"A comparative study of static and profile-based heuristics for
inlining", Proceedings of the ACM Sigplan Workshop onArnold00
Dynamic and Adaptive Compilation and Optimization
(DYNAMO-00), 2000. Site Internet
ATOM94 DEC. "ATOM User Manual", mars 1994.
D.F. Bacon, S.L. Graham, O.J. Sharp, Compiler Transformations
for High-Performance Computing, "ACM Computing Surveys",
Bacon94
December 1994, vol. 26, no 4, pp 345-420
http://www.acm.org/pubs/contents/journals/surveys/1994-26/#4
David H. Bailey, "Twelve Ways to Fool the Masses When
Giving Performance Results on Parallel Supercomputers"
Bailey91
,Technical report RNR-91-020, NAS Applied Research Branch
(RNR), Nov 91.
David Bailey, "Misleading Performance Specifications in the
Bailey92 Supercomputer Field" ,Technical report RNR-92-005, NAS
Applied Research Branch (RNR), Dec 92.
David Bailey "NAS Parallel Benchmarks" ,Technical report
Bailey94
94-007, NAS Applied Research Branch (RNR), 94
Ball (Thomas) et Larus (James R.). "Optimally profiling and
Ball94 tracing programs". In : ACM Transactions on Programming
Languages and Systems, p. 1319-1360. juillet 1994.
Ball (Thomas), Mataga (Peter) et Sagiv (Mooly). "Edge profiling
versus path profiling: The showdown". In : Conference Record of
Ball98 POPL'98: The 25th ACM SIGPLAN-SIGACT Symposium on
Principles of Programming Languages, p. 134-148. San Diego,
California, 19-21 janvier 1998.
Banerjee (U.). "Dependence Analysis for Supercomputing".
Banerjee88
Kluwer Academic Publishers, 1988.
Belady (L. A.). "A Study of Replacement Algorithms for a
Belady66 Virtual Storage Computer". IBM Systems Journal, vol. 5, no 2,
1966, pp. 78-101.
D. Bernstein, Dina Q. Goldin, Martin C. Golumbic, H.
Krawczyk, Y. Mansour, I. Nahshon et R.Y. Pinter. "Spill code
Bernstein89
minimization techniques for optimizing compilers", SIGPLAN
Notices, 24(7):258-263, Juillet 1989, PLDI'89.
file:///D|/Francois/CoursCD/HTML/TablesDesMatieres/Bibliographie/index.htm (2 of 17) [25/01/2002 13:30:45]Transformer pour la performance
Bernstein (D.) et Rodeh (M.). "Global instruction scheduling for
superscalar machines". In : Conference on Programming
Bernstein91
Language Design and Implementation, p. 241-255. "Toronto,
Ontario, Canada, juin 1991.
Berson (D.), Gupta (R.) et Soa (M. L.). "Resource spackling: A
framework for integrating register allocation in local and global
Berson94
schedulers". In : International Conference on Parallel
Architectures and Compilation Techniques. -août 1994.
Berson (David A.), Chang (Pohua), Gupta (Rajiv) et Soa (Mary
Lou). "Integrating program optimizations and transformations
Berson96
with the scheduling of instruction level parallelism". In : Lecture
Notes in Computer Science, p. 207-221. août 1996.
Bik (Aart J. C.). "MT1: A Prototype Restructuring Compiler.
Bik93
"Rapport technique, Rijksuniversiteit te Leiden, octobre 1993.
A. Bik, M. Girkar, P. Grey and X. Tian. Experiments with
Automatic Vectori