Vous êtes ici : UVSQ RechercheDoctoratSoutenances de thèse

Méthodes d’optimisation de programmes bas niveau

le 30 juin 2010

Le Mercredi 30 juin 2010 à 10h30

UFR des Sciences
Bâtiment Descartes Salle Archiméde
45 avenue des Etats Unis

Présenté par : Sid TOUATI Spécialité : INFORMATIQUE Laboratoire : PRISM


Résumé :
Notre exposé synthétise plus d'une décade de recherche académique sur le sujet d'optimisation de codes bas niveau, dont le but est une intégration dans un compilateur optimisant ou dans un outil d'optimisation semi-automatique. Dans les programmes bas niveau, les caractéristiques du processeur sont connues et peuvent être utilisées pour générer des codes fonctionnant en harmonie avec le matériel. Bien qu’efficace en pratique, nous expliquerons pourquoi la compilation itérative n’est pas une réponse fondamentale à l’optimisation de code, puis nous développerons nos résultats sur l’antagonisme entre parallélisme d’instructions et contraintes de registres. Nous considérons des ordonnancements acycliques (blocs de base et super-blocs d’instructions) et des ordonnancements cycliques (pipeline logiciel pour boucles). Nous étudierons un des volets de la minimisation de la taille de code sans perte de performances, qui est un enjeu important pour les systèmes embarqués. Nous expliquerons également avec une approche pragmatique comment prendre en compte le comportement de la hiérarchie mémoire pour calculer des ordonnancements d’instructions avec des latences incertaines. Sachant que les performances observées des programmes sont variables en pratique, nous présenterons un protocole statistique pour vérifier si l’optimisation d’un code a effectivement amélioré la performance moyenne ou médiane. Nous conclurons par un descriptif des problèmes ouverts non traités et par des orientations de recherche pour la prochaine décennie.
 
Summary:
Our presentation is a synthesis of a decade in academic research on backend code optimisation, where the objective is the integration of modules inside optimising compilers or inside semi-automatic optimisation tools. In low-level programs, processor characteristics are known and may be used to generate codes working in harmony with the hardware. While efficient in practice, we explain why iterative compilation is not a fundamental answer to code optimisation. Then we develop our results on solving the antagonism between register constraints and instruction scheduling, by considering both acyclic scheduling (basic blocks and super-blocks) and cyclic scheduling (software pipelining in loops). We study the problem of minimal loop unrolling factor for periodic register allocation, which is a crucial issue for embedded code compaction. Furthermore, we provide a pragmatic approach for dealing with memory hierarchy at instruction level parallelism, where operation latencies are statically unknown. Knowing that the observed program performances may be variable in practice, we present a statistical protocol to check if a speedup of the mean or median execution time has occurred. We conclude by a description of open problems and future research proposals.
Informations complémentaires
·        Denis TRYSTRAM, Professeur des Universités à l’École nationale supérieure d'informatique et de mathématiques appliquées de Grenoble ENSIMAG – Rapporteur
·        Jens KNOOP, Professeur des Universités à l’Institut für Comptersprachen Autriche  – Rapporteur
·        Jagannathan RAMANUJAM, Professeur des Universités à Louisiana State University, Etats Unis d’Amériques – Rapporteur
·        Christian BERTIN, Docteur Chef de Division compilation chez ST-MICROELECTRONICS - Examinateur
·        Alain DARTE, Directeur de Recherche du CNRS, LIP, Ecole Normale Supérieure de Lyon – Examinateur
·        William JALBY, Professeur des Universités à l’Université de Versailles Saint-Quentin-en-Yvelines – Examinateur
·        Pascal SAINRAT, Professeur des Universités à l’Université de Paul SABATIER Toulouse III – Examinateur
Contact :
Direction de la Recherche des Etudes Doctorales et de la Valorisation - DREDVAL :