Les optimisations jouent un rôle majeur dans la compilation des programmes embarqués. Elles interviennent à tous les niveaux, et sur les différentes représentations intermédiaires. En effet, les systèmes embarqués imposent souvent de lourdes contraintes à la fois sur l'espace disponible en mémoire et sur la puissance de calcul utilisable. La structure habituelle d'un compilateur lui fait collecter les informations de débogage au début du processus de compilation, pour les ajouter au fichier binaire à la toute fin. De ce fait, si le programme est modifié par les optimisations, les informations de débogage présentes dans le fichier binaire sont en partie incorrectes. Or le débogueur s'appuie sur ces informations afin de répondre aux requêtes de l'utilisateur. Si elles ne correspondent plus à la réalité du programme, les informations données à l'utilisateur seront erronées. Ainsi la méthode classique de débogage de programme est de développer sans optimisation de compilation durant la phase de mise au point et quand le produit est prêt à être livré, le compiler avec le maximum d'optimisations. Cette méthode ne convient pas au cycle de développement dans le contexte des systèmes embarqués. Notre approche est de présenter l'exécution du programme optimisé au développeur, de manière à ce qu'il comprenne aisément le lien avec le code source, malgré les transformations appliquées par le compilateur. L'idée est de ne pas émuler l'exécution du programme non-optimisé à partir de l'exécution du programme optimisé. Le développeur de programmes embarqués a des connaissances que nous allons exploiter. À partir d'une analyse de l'état de l'art du débogage de code optimisé et des outils fournis par STMicroelectronics, nous avons cherché à développer une solution viable industriellement. Notre parti est de montrer la réalité à l'utilisateur, de faire ce que P. Zellweger et J. Hennessy ont défini comme étant du débogage non-transparent. Il offre au développeur la possibilité de comprendre l'exécution de son programme. Afin de tracer les modifications effectuées par le compilateur, nous proposons d'étiqueter chaque instruction du code source lors de la compilation. Il s'agit ensuite pour le compilateur de maintenir de manière précise les étiquettes utilisées par optimisation et de propager cette information tout au long de la compilation. Ajoutées au fichier binaire en tant qu'informations de débogage, elles sont ensuite utilisées par le débogueur afin de répondre sans erreurs aux interrogations de l'utilisateur. L'ensemble des expérimentations est fait sur le compilateur mmdspcc et l'infrastructure IDbug.

Nous avons proposé des mécanismes pour mettre en œuvre la mémoïsation de fonction au niveau logiciel dans le cadre de nos efforts pour améliorer les performances du code séquentiel. Nous avons analysé le potentiel de la mémoïsation de fonction sur des applications et le gain de performance qu'elle apporte sur des architectures actuelles. Nous avons proposé trois approches - une approche simple qui s'applique au chargement et qui fonctionne pour toute fonction de bibliothèque liée dynamiquement, une approche à la compilation utilisant LLVM qui peut permettre la mémoïsation pour toute fonction du programme, ainsi qu'une proposition d'implémentation de la mémoïsation en matériel et ses avantages potentiels. Nous avons démontré avec les fonctions transcendantales que l'approche au chargement est applicable et donne un bon avantage, même avec des architectures et des compilateurs (avec la restriction qu'elle ne peut être appliquée que pour les fonctions liées dynamiquement) modernes. Notre approche à la compilation étend la portée de la mémoïsation et en augmente également les bénéfices. Cela fonctionne pour les fonctions définies par l’utilisateur ainsi que pour les fonctions de bibliothèque. Nous pouvons gérer certains types de fonctions non pures comme les fonctions avec des arguments de type pointeur et l'utilisation de variables globales. La mémoïsation en matériel abaisse encore le seuil de profitabilité de la mémoïsation et donne plus de gain de performance en moyenne. / We have proposed mechanisms to implement function memoization at a software level as part of our effort to improve sequential code performance. We have analyzed the potential of function memoization on applications and its performance gain on current architectures. We have proposed three schemes - a simple load time approach which works for any dynamically linked function, a compile time approach using LLVM framework which can enable memoization for any program function and also a hardware proposal for doing memoization in hardware and its potential benefits. Demonstration of the link time approach with transcendental functions showed that memoization is applicable and gives good benefit even under modern architectures and compilers (with the restriction that it can be applied only for dynamically linked functions). Our compile time approach extends the scope of memoization and also increases the benefit due to memoization. This works for both user defined functions as well as library functions. It can handle certain kind of non pure functions like those functions with pointer arguments and global variable usage. Hardware memoization lowers the threshold for a function to be memoized and gives more performance gain on average.

Les travaux de cette thèse portent sur l'amélioration et l'optimisation de l'algorithme de suivi d'objet couleur Mean-Shift à la fois d’un point de vue robustesse du suivi et d’un point de vue architectural pour améliorer la vitesse d’exécution. La première partie des travaux a consisté en l'amélioration de la robustesse du suivi. Pour cela, l'impact des espaces de représentation couleur a été étudié, puis une méthode permettant la sélection de l'espace couleur représentant le mieux l'objet à suivre a été proposée. L'environnement de la cible changeant au cours du temps, une stratégie est mise en place pour resélectionner un espace couleur au moment opportun. Afin d'améliorer la robustesse dans le cas de séquences particulièrement difficile, le Mean-Shift avec stratégie de sélection a été couplé avec un autre algorithme plus coûteux en temps d'exécution : le suivi par covariance. L’objectif de ces travaux est d’obtenir un système complet fonctionnant en temps réel sur processeurs multi-cœurs SIMD. Une phase d’étude et d'optimisation a donc été réalisée afin de rendre les algorithmes paramétrables en complexité pour qu’ils puissent s’exécuter en temps réel sur différentes plateformes, pour différentes tailles d’images et d’objets suivi. Dans cette optique de compromis vitesse / performance, il devient ainsi possible de faire du suivi temps-réel sur des processeurs ARM type Cortex A9. / The work of this thesis focuses on the improvement and optimization of the Mean-Shift color object tracking algorithm, both from a theoretical and architectural point of view to improve both the accuracy and the execution speed. The first part of the work consisted in improving the robustness of the tracking. For this, the impact of color space representation on the quality of tracking has been studied, and a method for the selection of the color space that best represents the object to be tracked has been proposed. The method has been coupled with a strategy determining the appropriate time to recalculate the model. Color space selection method was also used in collaboration with another object tracking algorithm to further improve the tracking robustness for particularly difficult sequences : the covariance tracking which is more time consuming. The objective of this work is to obtain an entire real time system running on multi-core SIMD processors. A study and optimization phase has been made in order to obtain algorithms with a complexity that is configurable so that they can run in real time on different platforms, for various sizes of images and object tracking. In this context of compromise between speed and performance, it becomes possible to do real-time tracking on processors like ARM Cortex A9.

Le but est de développer d'un cadriciel permettant de définir les transformations de code source que nous jugeons judicieuses et sur la base de métriques dynamiques.Ce cadriciel sera ensuite intégré à la suite d'outil MAQAO, développée à l'UVSQ/ECR.Nous présentons des transformations source-à-source automatique guidées par l'utilisateur ansi que par les métriques dynamiques qui proviennent des différents outils d'analyse de MAQAO, afin de pouvoir travailler à la fois sur des objets sources et binaires.Ce cadriciel peut aussi servir de pré-processeur pour simplifier le développement en permettant d'effectuer certaines transformations simples mais chronophage et sources d'erreurs (i.e.: spécialisation de boucle ou fonction). / Our goal is to develop a framework allowing the definition of source code transformations based on dynamic metrics.This framework be integrated to the MAQAO tool suite developed at the UVSQ / ECR.We present a set of source-to-source transformations guidable by the end user and by the dynamic metrics coming from the various MAQAO tools in order to work at source and binary levels.This framework can also be used as a pre-processor to simplify the development by enabling to perform cleanly and automatically some simple but time-consuming and error-prone transformations (i.e .: loop/function specialization, ...).

Aujourd'hui, le fait que la mémoire constitue un goulot d'étranglement pour les performances des programmes est un truisme. Les compilateurs doivent donc optimiser les programmes afin d'éviter de recourir à la mémoire, et ceci en utilisant au mieux les registres disponibles dans le processeur à parallélisme d'instructions (ILP).<br /><br />Cette thèse réexamine le concept de la pression des registres en lui donnant une plus forte priorité par rapport à l'ordonnancement d'instructions, sans ôter à ce dernier ses possibilités d'extraction de parallélisme. Nous proposons de traiter le problème des registres avant la phase d'ordonnancement. Deux grandes stratégies sont étudiées en détail. La première consiste à analyser et manipuler un graphe de dépendance de données (GDD) pour garantir les contraintes de registres sans allonger son chemin critique (si possible). Nous introduisons la notion de saturation en registres qui est la borne exacte maximale du besoin en registres de tout ordonnancement valide, indépendamment des contraintes architecturales. Son but est d'ajouter des arcs au GDD pour que la saturation soit en dessous du nombre de registres disponibles. Réciproquement, la suffisance est le nombre minimal de registres dont il faut disposer pour produire au moins un ordonnancement valide pour le GDD. Si cette suffisance est au dessus du nombre effectif de registres, alors les accès à la mémoire sont inévitables.<br />Notre deuxième stratégie construit une allocation de registres directement dans le GDD en optimisant la perte du parallélisme intrinsèque.<br /><br />Cette thèse considère des blocs de base, des graphes acycliques de flots de contrôles et des boucles internes destinées au pipeline logiciel. Nos expériences montrent que nos heuristiques sont presque optimales. L'étude prouve que nous pouvons et devons traiter les contraintes de registres avant la phase d'ordonnancement tout en garantissant une liberté pour l'extraction et l'exploitation de l'ILP.

L'évolution continue des architectures des processeurs a été un moteur important de la recherche en compilation. Une tendance dans cette évolution qui existe depuis l'avènement des ordinateurs modernes est le rapport grandissant entre la puissance de calcul disponible (IPS, FLOPS, ...) et la bande-passante correspondante qui est disponible entre les différents niveaux de la hiérarchie mémoire (registres, cache, mémoire vive). En conséquence la réduction du nombre de communications mémoire requis par un code donnée a constitué un sujet de recherche important. Un principe de base en la matière est l'amélioration de la localité temporelle des données: regrouper dans le temps l'ensemble des accès à une donnée précise pour qu'elle ne soit requise que pendant peu de temps et pour qu'elle puisse ensuite être transféré vers de la mémoire lointaine (mémoire vive) sans communications supplémentaires.Une toute autre évolution architecturale a été l'arrivée de l'ère des multicoeurs et au cours des dernières années les premières générations de processeurs manycoeurs. Ces architectures ont considérablement accru la quantité de parallélisme à la disposition des programmes et algorithmes mais ceci est à nouveau limité par la bande-passante disponible pour les communications entres coeurs. Ceci a amené dans le monde de la compilation et des techniques d'optimisation des problèmes qui étaient jusqu'à là uniquement connus en calcul distribué.Dans ce texte nous présentons les premiers travaux sur une nouvelle technique d'optimisation, le pavage généralisé qui a l'avantage d'utiliser un modèle abstrait pour la réutilisation des données et d'être en même temps utilisable dans un grand nombre de contextes. Cette technique trouve son origine dans le pavage de boucles, une techniques déjà bien connue et qui a été utilisée avec succès pour l'amélioration de la localité des données dans les boucles imbriquées que ce soit pour les registres ou pour le cache. Cette nouvelle variante du pavage suit une vision beaucoup plus large et ne se limite pas au cas des boucles imbriquées. Elle se base sur une nouvelle représentation, le graphe d'utilisation mémoire, qui est étroitement lié à un nouveau modèle de besoins en termes de mémoire et de communications et qui s'applique à toute forme de code exécuté itérativement. Le pavage généralisé exprime la localité des données comme un problème d'optimisation pour lequel plusieurs solutions sont proposées. L'abstraction faite par le graphe d'utilisation mémoire permet la résolution du problème d'optimisation dans différents contextes. Pour l'évaluation expérimentale nous montrons comment utiliser cette nouvelle technique dans le cadre des boucles, imbriquées ou non, ainsi que dans le cas des programmes exprimés dans un langage à flot-de-données. En anticipant le fait d'utiliser le pavage généralisé pour la distribution des calculs entre les cœurs d'une architecture manycoeurs nous donnons aussi des éléments de réponse pour modéliser les communications et leurs caractéristiques sur ce genre d'architectures. En guise de point final, et pour montrer l'étendue de l'expressivité du graphe d'utilisation mémoire et le modèle de besoins en mémoire et communications sous-jacent, nous aborderons le sujet du débogage de performances et l'analyse des traces d'exécution. Notre but est de fournir un retour sur le potentiel d'amélioration en termes de localité des données du code évalué. Ce genre de traces peut contenir des informations au sujet des communications mémoire durant l'exécution et a de grandes similitudes avec le problème d'optimisation précédemment étudié. Ceci nous amène à une brève introduction dans le monde de l'algorithmique des graphes dirigés et la mise-au-point de quelques nouvelles heuristiques pour le problème connu de joignabilité mais aussi pour celui bien moins étudié du partitionnement convexe. / The continuous evolution of computer architectures has been an important driver of research in code optimization and compiler technologies. A trend in this evolution that can be traced back over decades is the growing ratio between the available computational power (IPS, FLOPS, ...) and the corresponding bandwidth between the various levels of the memory hierarchy (registers, cache, DRAM). As a result the reduction of the amount of memory communications that a given code requires has been an important topic in compiler research. A basic principle for such optimizations is the improvement of temporal data locality: grouping all references to a single data-point as close together as possible so that it is only required for a short duration and can be quickly moved to distant memory (DRAM) without any further memory communications.Yet another architectural evolution has been the advent of the multicore era and in the most recent years the first generation of manycore designs. These architectures have considerably raised the bar of the amount of parallelism that is available to programs and algorithms but this is again limited by the available bandwidth for communications between the cores. This brings some issues thatpreviously were the sole preoccupation of distributed computing to the world of compiling and code optimization techniques.In this document we present a first dive into a new optimization technique which has the promise of offering both a high-level model for data reuses and a large field of potential applications, a technique which we refer to as generalized tiling. It finds its source in the already well-known loop tiling technique which has been applied with success to improve data locality for both register and cache-memory in the case of nested loops. This new "flavor" of tiling has a much broader perspective and is not limited to the case of nested loops. It is build on a new representation, the memory-use graph, which is tightly linked to a new model for both memory usage and communication requirements and which can be used for all forms of iterate code.Generalized tiling expresses data locality as an optimization problem for which multiple solutions are proposed. With the abstraction introduced by the memory-use graph it is possible to solve this optimization problem in different environments. For experimental evaluations we show how this new technique can be applied in the contexts of loops, nested or not, as well as for computer programs expressed within a dataflow language. With the anticipation of using generalized tiling also to distributed computations over the cores of a manycore architecture we also provide some insight into the methods that can be used to model communications and their characteristics on such architectures.As a final point, and in order to show the full expressiveness of the memory-use graph and even more the underlying memory usage and communication model, we turn towards the topic of performance debugging and the analysis of execution traces. Our goal is to provide feedback on the evaluated code and its potential for further improvement of data locality. Such traces may contain information about memory communications during an execution and show strong similarities with the previously studied optimization problem. This brings us to a short introduction to the algorithmics of directed graphs and the formulation of some new heuristics for the well-studied topic of reachability and the much less known problem of convex partitioning.

Ce manuscrit synthétise plus d'une décade de notre 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 plus en harmonie avec le matériel. Nous commençons notre document par une vue générale sur le problème d'ordonnancement des phases de compilation. Actuellement, des centaines d'étapes de compilation et d'optimisation de codes existent; un problème fondamental et ouvert reste de savoir comment les combiner et les ordonner efficacement. Pour pallier rapidement cette difficulté, une stratégie du moindre effort consiste à appliquer une compilation itérative en exécutant successivement le programme avant de décider de la technique d'optimisation de code à employer et avec quels paramètres. Nous prouvons que l'approche de compilation itérative ne simpli fie pas fondamentalement le problème, et l'utilisation de modèles statiques de performances reste un choix raisonnable. Un problème classique de con it entre deux étapes de compilation est celui qui lie l'allocation de registres et l'ordonnancement d'instructions. Nous montrons comment gérer efficacement cet antagonisme en séparant les contraintes de registres des contraintes d'ordonnancement d'instructions. Cela est possible grâce à la notion de saturation en registres (RS), qui est le besoin maximal en registres pour tous les ordonnancements possibles d'un graphe. Nous apportons une contribution formelle et une heuristique efficace, qui permettent la détection de contraintes de registres toujours véri fiées; ils peuvent par conséquent être négligées. Nous introduisons la plate-forme SIRA, qui permet de garantir l'absence de code de vidage avant l'ordonnancement d'instructions. SIRA est un modèle basé sur la théorie des graphes permettant de borner le besoin maximal en registres pour tout pipeline logiciel, sans altérer, si possible, le parallélisme d'instructions. SIRA modélise les contraintes cycliques des registres dans différentes architectures possibles : avec plusieurs types de registres, avec tampons ou les d'attente, et avec des bancs de registres rotatifs. Nous apportons une heuristique efficace qui montre des résultats satisfaisants, que ce soit comme outil indépendant, ou comme passe intégrée dans un vrai compilateur. Dans le contexte des processeurs exhibant des retards d'accès aux registres (VLIW, EPIC, DSP), nous attirons l'attention sur le problème qui peut survenir lorsque les contraintes de registres sont traitées avant l'ordonnancement d'instructions. Ce problème est la création de circuits négatifs ou nuls dans le graphe de dépendances de données. Nous montrons comment éliminer ces circuits indésirables dans le contexte de SIRA. SIRA définit une relation formelle entre le nombre de registres alloués, le parallélisme d'instructions et le facteur de déroulage d'une boucle. Nous nous basons sur cette relation pour écrire un algorithme optimal qui minimise le facteur de déroulage tout en sauvegardant le parallélisme d'instructions et en garantissant l'absence de code de vidage. D'après nos connaissances, ceci est le premier résultat qui démontre que le compactage de la taille de code n'est pas un objectif antagoniste à l'optimisation des performances de code. L'interaction entre la hiérarchie mémoire et le parallélisme d'instructions est un point central si l'on souhaite réduire le coût des latences d'opérations de chargement. Premièrement, notre étude pratique avec des micro-benchmarks montre que les processeurs superscalaires ayant une exécution dans le désordre ont un bug de performances dans leur mécanisme de désambiguation mémoire. Nous montrons ensuite qu'une vectorisation des opérations mémoire résoud ce problème pour des codes réguliers. Deuxièmement, nous étudions l'optimisation de préchargement de données pour des codes VLIW embarqués irréguliers. Finalement, avec l'arrivée des processeurs multicoeurs, nous observons que les temps d'exécution des programmes deviennent très variables. A fin d'améliorer la reproductibilité des résultats expérimentaux, nous avons conçu le Speedup-Test, un protocole statistique rigoureux. Nous nous basons sur des tests statistiques connus (tests de Shapiro-Wilk, F de Fisher, de Student, de Kolmogorov-Smirnov, de Wilcoxon- Mann-Whitney) a n d'évaluer si une accélération observée du temps d'exécution médian ou moyen est signi cative.