Calcul de majorants sûrs de temps d'exécution au pire pour des tâches d'application temps-réel critique pour des systèmes disposants de caches mémoire
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
This PhD Thesis presents a new approach for Worst Case Execution Time (WCET) computation for hard real-time systems, especially for cache memories hazard issues. A general overview of issues and state of the art in this matter is drawn, but the main point is the theory in itself and its formalism, first, in single task execution, then in multitasking environment. The method being used relies on abstract interpretation, like many other methods of WCET computation, but its formalism is a probabilistic approach (although it is deterministic in the single task field) with the use of Markov chains. Generalization to the multitask field make use of this probabilistic base to compute a pessimistic evaluation of the WCET and of its maximum deviation, thanks to a clever modification of the propagator. First evaluation of the model results, hand-coded from the compilation output of rather simple tasks, shows that results are promising in order to apply it to real-life applications.
Abstract FR:
Cette thèse présente une nouvelle approche pour le calcul de temps d'exécution au pire (WCET) de tâche temps réel critique, en particulier en ce qui concerne les aléas dus aux caches mémoire. Le point général est fait sur la problématique et l'état de l'art en la matière, mais l'accent est mis sur la théorie elle-même et son formalisme, d'abord dans le cadre monotâche puis dans le cadre multitâche. La méthode utilisée repose sur une technique d'interprétation abstraite, comme la plupart des autres méthodes de calcul de WCET, mais le formalisme est dans une approche probabiliste (bien que déterministe dans le cadre monotâche) de par l'utilisation de chaînes de Markov. La généralisation au cadre multitâche utilise les propriétés probabilistes pour faire une évaluation pessimiste d'un WCET et d'un écart maximum, grâce à une modification astucieuse du propagateur dans ce cadre. Des premières évaluations du modèle, codées manuellement à partir des résultats de compilation d'applications assez simples montrent des résultats prometteurs quant à l'application du modèle sur des programmes réels en vraie grandeur.