Calcul de majorants sûrs de temps d'exécution au pire pour des tâches d'applications temps-réels critiques, pour des systèmes disposants de caches mémoire

This report is a presentation of a new approach for Worst Case Execu- tion 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 environ- ment. 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 prob- abilistic base to compute a pessimistic evaluation of the WCET and of its standard 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.Ce mémoire 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 proba- bilistes pour faire une évaluation pessimiste d'un WCET et d'un écart type au pire, grâce à une modification astucieuse du propagateur dans ce cadre. Des premières évaluations du modèle, codées à la main à partir des résultats de compilation d'applications assez simples montrent des résultats promet- teurs quant à l'application du modèle sur des programmes réels en vraie grandeur