Optimisation de programmes par reconnaissance de templates
Institution:
Versailles-St Quentin en YvelinesDisciplines:
Directors:
Abstract EN:
Most of compiler optimization techniques apply local transformations on the code, replacing sub-optimal fragments with better ones. They are often low-level, and applied without knowing what the code is supposed to do. Unfortunately, these optimizations are not enough to produce an optimal code, and lead the programmer to use performance libraries. For the moment, the library functions must be called by hand. However, learning and using a new library remains fastidious, and it is surprising how little the compiler helps the programmer in this task. A natural solution would be to search naïve occurrences of library functions through the program, and to replace them by the corresponding call. In this thesis, we propose a fully automatic approach to recognize occurrences of library functions in a program. In this thesis, we propose a fully automatic approach to recognize occurrences of library functions in a program, and to substitute them, whenever it is possible and interesting, by a call to the library. Our approach is able to recognize all the program slices computing the same mathematical formula than the searched function. This allow to cope with organization, data structure and control variations, and more generally with any program transformation which does not take operators properties (associativity, commutativity, ect…) into account. In addition to functions descriptions, we are also able to find template instances in the source code. Such a characteristic enable the recognition of template libraries, and the rewriting of a program to use templates. Once the proper instances are found within the program, it remains to select the slices whose replacement by a library call is possible, and interesting. We propose a complete algorithmic framework to select all valid substitutions, and to generate the corresponding code. To select a good substitution set, we propose a preliminary solution based on a system of marks. Two other experimental approaches based on benchmarking are also investigated. Our approach has been implemented in the TeMa tool (Teplate Matcher). TeMa represents more than 17000 lines of code, and was applied to the detection of the BLAS functions (Basic Linear Algebra Subroutines) within the kernels of the SpecFP 2000 and thePerfect Club benchmarks. Experimental results report a substantial acceleration factor for the kernels sim, mgrid and applu.
Abstract FR:
La plupart des optimisations appliquent des transformations locales bas-niveau, sans se soucier du calcul exprimé par le programme. Bien que ces optimisations produisent des résultats satisfaisants, elles ne sont pas encore suffisantes, et amènent bien souvent le programmeur à utiliser des bibliothèques optimisées. Pour le moment, les bibliothèques optimisées doivent être appelées à la main. Apprendre et utiliser une nouvelle bibliothèque est malheureusement très fastidieux, et il est surprenant de voir le peu d’aide apporté par le compilateur. Une solution naturelle serait de chercher les occurrences immédiates des fonctions d’une bibliothèque dans le programme, et de les remplacer par l’appel correspondant. Dans cette thèse, nous proposons une approche totalement automatique pour reconnaitre dans un programme les occurrences des fonctions d’une bibliothèque optimisée, et les substituer par l’appel de fonction lorsque c’est possible et intéressant. Notre méthode est capable de détecter toutes les tranches de programme équivalentes aux fonctions recherchées au sens de l'équivalence de Herbrand, un sous-ensemble de l'équivalence sémantique qui ne tient pas compte de la sémantique des opérations atomiques. En plus des fonctions, nous sommes capables de trouver des instances de templates dans un programme. Une telle caractéristique rend possible la reconnaissance de bibliothèques de templates, et la réécriture d'un programme pour utiliser des templates. Une fois les instances trouvées dans le programme, il reste à sélectionner les candidats dont le remplacement par un appel de fonction est possible et améliore effectivement les performances du programme. Nous proposons également un algorithme pour sélectionner les substitutions valides, et pour générer le code avec la substitution. La sélection du bon ensemble de substitution se fait par un système de notes. Deux autres solutions expérimentales basées sur du benchmarking sont proposées, l’une décrivant exhaustivement l’espace des substitutions, et l’autre testant les substitutions en suivant une approche gloutonne. Notre approche a été implémentée dans l'outil TeMa (Template Matcher). TeMa représente plus de 17000 lignes de code C++ et OCaml, et a été appliqué à la détection des fonctions de la bibliothèque BLAS (Basic Linear Algebra Subroutines) dans les noyaux des benchmarks SpecFP 2000 et Perfect ClubLes résultats expérimentaux montrent un facteur d'accélération substantiel sur les noyaux swim, mgrid et mdg.