Le WCET ou Worst Case Execution Time, en français pire cas de temps d’exécution, équivaut au plus long temps d’exécution d’un programme informatique.
Aujourd’hui, cette information est indispensable pour l’intégrité des systèmes embarqués voués à la sécurité comme un ABS ou un coussin gonflable de sécurité (« airbag ») dans une voiture, les systèmes de contrôle aérien et tout autre système informatique critique. Ces systèmes doivent réagir en temps réel de manière fiable, ce qui implique à la fois d’être sûr du résultat produit par le programme mais aussi de connaître absolument le temps qu’il prendra pour s’exécuter. Pour garantir cela, le plus long temps d’exécution a besoin d’être connu le plus précisément possible. Toutefois, un programme ne se comporte pas toujours de manière identique, son temps d’exécution peut varier en fonction du type de tâche à réaliser mais aussi du type de l’appareil sur lequel il s’exécute. Par conséquent, les caractéristiques du code du programme et les caractéristiques matérielles ont besoin d’être considérées.
Pour déterminer le WCET, plusieurs pratiques existent. La première, utilisée couramment dans l’industrie, s’appuie sur les mesures: c’est la méthode dynamique. Cette méthode a pour principe d’exécuter un certain nombre de fois le programme avec des données d’entrées différentes considérées comme celles provoquant la durée d’exécution la plus longue. Toutefois, les mesures ne donnent pas toutes les garanties que le plus long temps ait été rencontré, ce qui entraîne des erreurs. Une deuxième méthode fonctionne par analyse du programme sans même l’exécuter: c’est la méthode statique. Cette technique alternative dérive par abstraction les propriétés que le programme aurait pour toutes ses exécutions possibles. Son résultat donne un temps qui est garanti pour être plus large que le (ou égal au) plus long temps d’exécution du programme. Elle a donc tendance à surestimer le WCET. Pour réduire ce phénomène, l’analyse a besoin d’être effectuée tant au niveau haut du code qu’au niveau bas. La prise en compte des données micro architecturales telles que les comportements processeurs et mémoires est de plus en plus importante surtout depuis le développement des usages de processeurs à plusieurs cœurs dans les systèmes embarqués. Une troisième méthode tente d’améliorer les calculs du WCET en combinant les techniques dynamiques et statiques: c’est la méthode hybride. Ces différentes méthodes sont disponibles sous forme d’outils issus à la fois du monde universitaire, industriel et commercial.
Motivations Les systèmes temps réel doivent satisfaire des contraintes temporelles strictes, qui sont dérivées des systèmes qu'ils contrôlent. En général, le calcul du WCETWCET pour Worst Case Execution Time qui pourrait être traduit par cas du pire temps d'exécution. est nécessaire pour montrer la satisfaction de ces contraintes. L'obtention systématique des limites supérieures des temps d'exécution des programmes pourrait complètement résoudre le problème de l'arrêt du programme. Cependant, les systèmes temps réel utilisent seulement une forme restreinte de programmation, ce qui garantit que les programmes se terminent toujours.. Ainsi, les secteurs tels que l'industrie spatiale et l'aviation acceptent les coûts élevés et les efforts nécessaires pour obtenir un WCET le plus précis possible. D'autre part, le coût élevé pour re-valider le logiciel en cas de changements même mineurs est une problématique importante à prendre en considération.. Par exemple, dans les secteurs de production de masse où les coûts sont optimisés, les coûts de production sont plus importants que les coûts de développement. Le développeur devra, pour garantir les délais, prendre en compte le WCET des programmes afin de sélectionner le moins cher et celui qui sera suffisamment puissant pour répondre aux besoins. Pour les systèmes où le temps d’exécution est moins critique, les estimations du WCET ne sont pas toujours nécessaires, seulement des parties limitées du logiciel du système sont critiques..
Historique Bien que l'analyse de l’ordonnancement d'un programme soit l'un des domaines traditionnels de recherches, les premières recherches sur l'analyse du WCET ont démarré à la fin des années 1980 (Kligerman et Stoyenko en 1986., Mok et al en 1989., Puschner et Koza en 1989. et Shaw en 1989.). Dans les années 1990, de nombreux scientifiques ont mis l'accent sur l'analyse du WCET, par conséquent, de nombreux progrès ont été effectués dans cette décennie..
Le début des années 2000 a vu naître des outils d'automatisation de l'estimation du WCET. Le WCET Challenge 2006 a été le premier événement qui a comparé différents outils de WCET en utilisant le même ensemble de critères.. Deux équipes de développement d'outils commerciaux, AITOutil AIT consultable sur le site AIT et Bound-TOutil Bound-T consultable sur le site Bound-T, et trois de prototypes d'outils de recherches, MTime, SWEET, et ChronosOutil Chronos consultable sur le site Chronos y ont participé. D'autres groupes de développeurs n'ont pu y participer pour cause de délai de préparation trop court tel que les développeurs d'OTAWAOutil OTAWA consultable sur le site OTAWA (archive), RapiTimeOutil RapiTime consultable sur le site Rapitime, SYMTA/POutil SYMTA/P consultable sur le site SYMTA/P et HeptaneOutil Heptane consultable sur le site Heptane.. Les critères de références utilisés ont été ceux définis par Jan Gustafsson de l'université de Mälardalen.. Un assistant de recherches externe et les équipes de développements ont fait les tests réels des outils suivant ces critères. D'autres Challenges ont eu lieu également en 2008. et 2011..
Par ailleurs un groupe de travail est organisé annuellement sur ce thème en conjonction avec la Conférence des Systèmes Temps RéelsConférence des systèmes temps réel en traduction de Euromicro Conference on Real Time Systems. Cet événement permet d'observer les dernières tendances en termes d'obtention du WCET., à l'image de la conférence de Göteborg en 2014Conférence des systèmes temps réel de Göteborg 2014 ou celle de Paris en 2013Conférence des systèmes temps réel de Paris 2013.
Estimations du WCET L'analyse du WCET permet de calculer les limites supérieures pour les temps d'exécution de morceaux de code pour une application donnée où le temps d'exécution d'un morceau de code est défini comme le temps qu'il faut au processeur pour exécuter ce morceau de code..
vignette|upright=2.5|Ensemble de tous les temps d'exécution d'un système temps réel. Une tâche peut avoir une certaine variation de temps d’exécution en fonction des données d'entrée ou en fonction des différences d'environnement. Le plus court temps d'exécution est appelé « Best Case Execution TimeBest Case Execution Time pourrait être traduit par cas du meilleur temps d'exécution. » (BCET), le pire temps d’exécution du programme est appelé « Worst Case Execution Time » (WCET). Dans la plupart des cas, l'espace d'état est trop grand pour explorer de manière exhaustive toutes les exécutions possibles et déterminer ainsi les temps d'exécution BCET et WCET de manière exacte.
Aujourd'hui, les trois méthodes suivantes sont utilisées pour l'analyse du WCET : la méthode d'analyse dynamique consiste à mesurer le temps d’exécution du programme sur le matériel cible ; la méthode d'analyse statique évite l'exécution du programme ; la méthode d'analyse hybride combine l'analyse dynamique et l'analyse statique.
Avant de choisir une méthode d'obtention du WCET, il est nécessaire de tenir compte des conditions suivantes. : si une estimation fiable est souhaitée: il faudra probablement choisir une méthode d'analyse statique ; si une estimation approximative est suffisante: ce peut être le cas, si le système est un système temps réel souple, ou si le système peut tolérer des dépassements occasionnels. Dans ce cas, les valeurs d'estimation basées sur des mesures peuvent être suffisantes. Les méthodes hybrides sont une autre option, donnant parfois des informations plus détaillées sur le résultat obtenu ; si d'autres informations sont souhaitées : les outils statiques et hybrides d'aujourd'hui fournissent des informations supplémentaires utiles, par exemple l'identification des goulets d'étranglement, et les informations sur le plus long chemin d’exécution.
Méthode dynamique
Les méthodes dynamiques consistent à exécuter le programme dont on veut estimer le WCET (sur un système réel ou sur un simulateur) et à mesurer son temps d’exécution. Des jeux de tests pour l’exécution, qu’ils soient explicites ou symboliques sont indispensables dans ce type de méthode. Pour mesurer le temps d’exécution au pire cas, il faut fournir le jeu de test qui conduit au temps d’exécution maximum..
Jeux de tests explicites
Une des principales difficulté est la possibilité de générer de manière automatique et systématique des jeux de tests suffisant pour l'estimation du WCET.. Plusieurs solutions sont envisageables : Mesurer le temps d’exécution du programme pour tous les jeux d’entrées possibles ; la durée du processus est en général rédhibitoire; Laisser le soin à l’utilisateur de définir le jeu de test pire cas ; sa parfaite connaissance du programme peut lui permettre d’identifier ce jeu de test sans erreur; Générer automatiquement un jeu de test (ou un ensemble de jeux de test) qui conduit au temps d’exécution maximum. Quelques travaux basés sur des algorithmes évolutionnistes ont été menés dans ce sens. L’algorithme commence par une population initiale de paramètres (par exemple les données d’essais en cas de test évolutionnaire). Les membres de la population sont ensuite évalués en fonction de leur comportement. Dans le cas du WCET, la valeur de ces paramètres est remise en cause en fonction de la durée d’exécution du programme. Après cette évaluation, si les conditions sont remplies l’algorithme aura défini des paramètres permettant une estimation du WCET plus précise.. L'algorithme génétique, qui est un type d'algorithme évolutionniste, est le plus souvent utilisé dans le cadre des méthodes dynamiques.. Frank Mueller et Joachim Wegener ont développé une nouvelle approche pour tester le comportement temporel des systèmes temps réels. Grâce à leurs tests évolutionnaires, les jeux de données optimisés sont obtenus automatiquement et permettent de vérifier si les contraintes temporelles spécifiées pour le système sont dépassées.. Amine Marref a également développé un programme génétique pour proposer une alternative aux méthodes d'obtention de jeux de paramètres pour l'analyse du WCET. Les paramètres de test sont capturés automatiquement par le programme génétique à la suite de l'exécution de bout en bout du programme sous analyse.. Un autre travail proposant un framework de génération de jeux de tests généralisés basé sur une technique d'optimisation a également été publié.. Ces méthodes de génération automatique sont dans certaines publications considérées comme méthodes semi-dynamiques ou méthodes hybrides.. Le développement de ces techniques principalement basées sur des algorithmes génétiques entraine un regain d’intérêt des méthodes autres que statiques.. Cet intérêt est d’autant plus fort du fait de l’utilisation principale des méthodes dynamiques par les industriels..
Jeux de tests symboliques
Le principe de cette méthode est de poser l’hypothèse que les données en entrée sont inconnues et d’étendre le jeu d’instructions du processeur cible de sorte qu’il puisse réaliser des calculs à partir d'une ou plusieurs valeurs inconnues. Elle utilise la sémantique d'instructions alternatives pour traiter les opérandes inconnus. La méthode peut exclure de nombreux chemins du programme impossibles (ou non-exécutables) et peut calculer les paramètres du chemin, comme des limites du nombre d'itérations d'une boucle, sans nécessité d'annotations manuelles du programme....
Méthodes de mesures