Calcul efficace du pire temps d'exécution symbolique à base d'arbres

Abstract

Un système temps réel est un système informatique soumis à descontraintes de temps, et en particulier à des échéances. Les systèmestemps réels critiques sont une sous-classe de ces systèmes qui doiventimpérativement respecter leurs échéances. Dans ce genre de systèmes,manquer une échéance peut avoir des conséquences catastrophiquespouvant aller jusqu'à la perte de vies humaines. Pour s'assurer queces systèmes ne manquent jamais leurs échéances, l'analyse de piretemps d'exécution (PTE, ou WCET en anglais) calcule une limitesupérieure au temps d'exécution des programmes qui doivent êtreexécutés.Traditionnellement, l'analyse statique du PTE produit un entier quireprésente une borne supérieure au nombre de cycles du processeurnécessaires à l'exécution de ce programme. Cependant, le tempsd'exécution d'un programme peut dépendre de paramètres matériels,l'état du cache notamment, ou de paramètres logiciels, comme lesparamètres d'entrée du programme. Calculer un seul PTE sous la formed'un entier, peu importe la valeur des paramètres, est donc souventpessimiste. Pour résoudre ce problème, l'analyse paramétrique du PTEproduit une formule arithmétique qui dépend de différents paramètreschoisis. Instancier cette formule avec des valeurs pour chaqueparamètre permet d'obtenir un PTE plus précis qui prend en compte lavaleur de ces paramètres.Parmi les différentes analyses paramétriques, les techniques à based'arbres montrent une complexité faible. En effet, elles utilisent unestructure arborescente qui peut facilement être transformée en uneformule arithmétique, ce qui permet de calculer le PTE en incluant dessymboles, et donc des paramètres, de manière efficace. Néanmoins, cesapproches ont aussi des inconvénients. Tout d'abord, ces méthodes sontconnues pour leurs difficultés à tenir compte des effets descomposants matériels sur le PTE. Ensuite, elles montrent également desdifficultés à prendre en compte certains aspects sémantiques duprogramme, qui peuvent avoir un impact conséquent sur lePTE. Finalement, tout comme les autres analyses paramétriques, lesparamètres proposés doivent être déterminés par l'utilisateur.Dans cette thèse, nous étendons une technique de calcul symbolique duPTE pour aborder trois problèmes liés à des techniques de calcul dePTE paramétrique:- nous avons développé une technique qui élimine les cheminssémantiquement infaisables de la représentation du programmeutilisée pour calculer le PTE;- nous avons adapté une technique existante d'analyse de pipeline,qui fonctionne avec les techniques non paramétriques de calcul duPTE à base de graphes, afin de l'utiliser dans une techniqued'analyse paramétrique du PTE utilisant des arbres;- nous avons développé une technique paramétrique qui prendautomatiquement en compte les effets des paramètres d'entrée duprogramme sur le PTE. Cette technique produit une formule dont lesparamètres sont les paramètres d'entrée du programme et ne requiertaucune connaissance du programme de la part de l'utilisateur.