Performance Debugging Toolbox for Binaries : Sensitivity Analysis and Dependence Profiling

Le débogage, tel qu'il est généralement défini, consiste à trouver et à supprimer les problèmes empêchant un logiciel de fonctionner correctement.Quand on parle de bogues et de débogage, on fait donc habituellement référence à des bogues fonctionnels et au débogage fonctionnel.Dans le contexte de cette thèse, cependant, nous parlerons des bogues de performance et de débogage de performance.Nous ne cherchons donc pas les problèmes engendrant de mauvais comportements du programme, mais les problèmes qui le rendent inefficace, trop lent, ou qui induisent une trop grande utilisation de ressources.À cette fin, nous avons développé des outils qui analysent et modélisent la performance pour aider les programmeurs à améliorer leur code de ce point de vue là.Nous proposons les deux techniques de débogage de performance suivantes: analyse des goulets d'étranglement basée sur la sensibilité et Suggestions d'optimisation polyédrique basées sur les dépendances de données.Analyse des goulets d'étranglement basée sur la sensibilité:Il peut être étonnamment difficile de répondre à une question apparemment anodine sur la performance d'un programme, comme par exemple celle de savoir s'il est limité par la mémoire ou par le CPU.En effet, le CPU et la mémoire ne sont pas deux ressources complètement indépendantes, mais sont composés de multiples sous-systèmes complexes et interdépendants.Ici, un blocage d'une ressource peut à la fois masquer ou aggraver des problèmes avec une autre ressource.Nous présentons une analyse des goulets d'étranglement basée sur la sensibilité qui utilise un modèle de performance de haut niveau implémenté dans GUS, un simulateur CPU rapide pour identifier les goulets d'étranglement de performance.Notre modèle de performance a besoin d'une base de référence pour la performance attendue des différentes opérations sur un CPU, comme le pic IPC et comment différentes instructions se partagent les ressources du processeur.Malheureusement, cette information est rarement publiée par les fournisseurs de matériel, comme Intel ou AMD.Pour construire notre modèle de processeur, nous avons développé un système permettant de récupérer les informations requises en utilisant des micro-benchmarks générés automatiquement.Suggestions d'optimisation polyédrique basées sur les dépendances de données:Nous avons développé MICKEY, un profileur dynamique de dépendances de données qui fournit un retour d'optimisation de haut niveau sur l'applicabilité et la rentabilité des optimisations manquées par le compilateur.MICKEY exploite le modèle polyédrique, un puissant cadre d'optimisation pour trouver des séquences de transformations de boucle afin d'exposer la localité des données et d'implémenter à la fois le parallélisme gros-grain, c'est-à-dire au niveau thread, et grain-fin, c'est-à-dire au niveau vectoriel.Notre outil utilise une instrumentation binaire dynamique pour analyser des programmes écrits dans différents langages de programmation ou utilisant des bibliothèques tierces pour lesquelles aucun code source n'est disponible.En interne MICKEY utilise une représentation intermédiaire (RI) polyédrique qui code à la fois l'exécution dynamique des instructions d'un programme ainsi que ses dépendances de données.La RI ne capture pas seulement les dépendances de données à travers plusieurs boucles mais aussi à travers des appels de procédure, éventuellement récursifs.Nous avons développé l'algorithme de folding, un algorithme efficace de compression de traces qui construit cette RI polyédrique à partir de l'exécution d'un programme.L'algorithme de folding trouve aussi des accès réguliers dans les accès mémoire pour prédire la possibilité et la rentabilité de la vectorisation.Il passe à l'échelle sur de gros programmes grâce à un mécanisme de sur-approximation sûr et sélectif pour les applications partiellement irrégulières.Debugging, as usually understood, revolves around finding and removing defects in software that prevent it from functioning correctly.That is, when one talks about bugs and debugging one usually means functional bugs and functional debugging.In the context of this thesis, however, we will talk about performance bugs and performance debugging.Meaning we want to find defects that do not cause a program to crash or behave wrongly, but that make it run inefficiently, too slow, or use too many resources.To that end, we have developed tools that analyse and model the performance to help programmers improve their code to get better performance.We propose the following two performance debugging techniques: sensitivity based performance bottleneck analysis and data-dependence profiling driven optimization feedback.Sensitivity Based Performance Bottleneck Analysis:Answering a seemingly trivial question about a program's performance, such as whether it is memory-bound or CPU-bound, can be surprisingly difficult.This is because the CPU and memory are not merely two completely independent resources, but are composed of multiple complex interdependent subsystems.Here a stall of one resource can both mask or aggravate problems with another resource.We present a sensitivity based performance bottleneck analysis that uses high-level performance model implemented in GUS, a fast CPU simulator to pinpoint performance bottlenecks.Our performance model needs a baseline for the expected performance of different operations on a CPU, like the peak IPC and how different instructions compete for processor resources.Unfortunately, this information is seldom published by hardware vendors, such as Intel or AMD.To build our processor model, we have developed a system to reverse-engineer the required information using automatically generated micro-benchmarks.Data-Dependence Driven Polyhedral Optimization Feedback:We have developed MICKEY, a dynamic data-dependence profiler that provides high-level optimization feedback on the applicability and profitability of optimizations missed by the compiler.MICKEY leverages the polyhedral model, a powerful optimization framework for finding sequences of loop transformations to expose data locality and implement both coarse, i.e. thread, and fine-grain, i.e. vector-level, parallelism.Our tool uses dynamic binary instrumentation allowing it to analyze program written in different programming languages or using third-party libraries for which no source code is available.Internally MICKEY uses a polyhedral intermediate representation IR that encodes both the dynamic execution of a program's instructions as well as its data dependencies.The IR not only captures data dependencies across multiple loops but also across, possibly recursive, procedure calls.We have developed an efficient trace compression algorithm, called the folding algorithm, that constructs this polyhedral IR from a program's execution.The folding algorithm also finds strides in memory accesses to predict the possibility and profitability of vectorization.It can scale to real-life applications thanks to a safe, selective over-approximation mechanism for partially irregular data dependencies and iteration spaces