Plan de cours optimisation

Sujets

• cours

Informations

• Publié par: Machung
• Nombre de lectures: 184
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

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.     [e-mail] 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.     [e-mail] 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