Génération de programmes modèles pour la représentation et l'analyse de profils d'exécution : Le modèle périodique-linéaire
Institution:
Université Louis Pasteur (Strasbourg) (1971-2008)Disciplines:
Directors:
Abstract EN:
This work presents a novel approach for program execution traces analysis and modeling. After a short introduction where it is shown that general methods for data analysis are not well-adapted to understand the behavior of programs, we focus on the design of our model, called the Periodic Linear Model. It is based on the representation of a program behavior by another program. The program that models the behavior of the first one is made of sequences of nested loops, in which the functions of the innermost level compute the values of the input program trace from the loop indices. Each sequence of nested loops correspond to a particular definition of a program phase, that is a set of linearly linked intervals; these intervals are identifed through our periodic linear interpolation method. From this representation, we show that many analysis ans optimizations are possible in conjunction with some static analysis methods like the polytope model, and also that the information resulting from our model are more precise, adapted and exploitable than those obtained by general data analysis methods.
Abstract FR:
Cette thèse présente une nouvelle technique de représentation et d'analyse de traces d'exécution de programmes. Après une étude de quelques méthodes générales d'analyse de données, l'accent est mis sur une nouvelle modélisation qui consiste à exprimer le comportement à l'exécution d'un programme par un autre programme. Le programme qui exprime le comportement est constitué d'une séquence de nids de boucles dans lesquelles les fonctions de niveau les plus internes expriment les valeurs de la trace d'entrée à partir des indices de boucles. Chaque séquence de nids de boucles correspond à une définition particulière d'une phase de programme, c'est à dire un ensemble d'intervalles dépendants les uns des autres, et ces intervalles sont identifiés grâce à une méthode d'interpolation périodique et linéaire. A partir de cette représentation, on montre qu'on est en mesure d'effectuer un assez grand nombre d'analyses et d'optimisations, en s'aidant notamment des outils comme le modèle polyédrique d'analyse statique. Au final, on vérifie bien que les informations obtenues suite à notre modélisation et à l'analyse statique des nids de boucles résultants sont plus précises, mieux adaptées, et plus exploitables qu'avec des méthodes générales d'analyse de données.