Loading AI tools
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.
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 WCET[note 1] 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[1]. 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[2]. 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[2]. 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[3].
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[4], Mok et al en 1989[5], Puschner et Koza en 1989[6] et Shaw en 1989[7]). 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[8].
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[9]. Deux équipes de développement d'outils commerciaux, AIT[note 2] et Bound-T[note 3], et trois de prototypes d'outils de recherches, MTime, SWEET, et Chronos[note 4] 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'OTAWA[note 5], RapiTime[note 6], SYMTA/P[note 7] et Heptane[note 8],[10]. Les critères de références utilisés ont été ceux définis par Jan Gustafsson de l'université de Mälardalen[11]. Un assistant de recherches externe et les équipes de développements ont fait les tests réels des outils suivant ces critères[10]. D'autres Challenges ont eu lieu également en 2008[12] et 2011[13].
Par ailleurs un groupe de travail est organisé annuellement sur ce thème en conjonction avec la Conférence des Systèmes Temps Réels[note 9]. Cet événement permet d'observer les dernières tendances en termes d'obtention du WCET[14], à l'image de la conférence de Göteborg en 2014[note 10] ou celle de Paris en 2013[note 11].
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[15].
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 Time[note 12] » (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[1].
Aujourd'hui, les trois méthodes suivantes sont utilisées pour l'analyse du WCET[3] :
- 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[16]:
- 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[17].
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[18]. Plusieurs solutions sont envisageables[17] :
- 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[19]. L'algorithme génétique, qui est un type d'algorithme évolutionniste, est le plus souvent utilisé dans le cadre des méthodes dynamiques[20]. 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[21]. 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[22]. 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é[23]. Ces méthodes de génération automatique sont dans certaines publications considérées comme méthodes semi-dynamiques ou méthodes hybrides[24]. 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[25]. Cet intérêt est d’autant plus fort du fait de l’utilisation principale des méthodes dynamiques par les industriels[26].
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[27],[28],[29].
Méthodes de mesures
De nombreuses méthodes existent pour mesurer le temps d'exécution, chaque technique est un compromis entre plusieurs attributs, tels que la résolution, la précision, la granularité et la difficulté de mise en œuvre[30]. Voici les principales techniques de mesure :
- Stop watch[31],[32]
- La méthode consiste à utiliser un chronomètre pour mesurer le temps d’exécution du programme.
- Commande date et time (UNIX)[31],[32]
- La commande
dateest utilisée comme un chronomètre, sauf qu'elle utilise l'horloge intégrée de l'ordinateur au lieu d'un chronomètre externe. Cette méthode est plus précise que le chronomètre mais a la même granularité de mesure. Pour la commandetime, la mesure du temps d'exécution est déclenchée par le préfixe « time » dans la ligne de commande. Cette commande ne mesure pas seulement le temps entre le début et la fin du programme, mais elle calcule également le temps d'exécution utilisé par les programmes spécifiques. - Prof et Gprof (UNIX)[31],[33]
- Les méthodes prof et gprof sont similaires (la méthode gprof fournit plus d’informations), elles sont généralement utilisées pour mesurer les temps d’exécution des fonctions (nombre minime d’instructions). Ces méthodes peuvent être utilisées pour optimiser du code.
- Clock[34]
- Bien que les méthodes prof et gprof fournissent des informations plus détaillées que les premières méthodes présentées, il est souvent nécessaire de mesurer le temps d'exécution avec une granularité plus fine. Ainsi, les fonctions sont découpées en segments pour permettre, grâce à la commande
clock, de mesurer chacun d'eux. - Analyseur logiciel[34],[35]
- Un analyseur logiciel est un analyseur qui à l’instar des méthodes précédemment définies (prof et gprof) ne se limite pas seulement à mesurer le temps d’exécution d’une fonction mais peut également être utilisé dans des analyses temporelles à plus petite échelle. Exemple : les boucles ou les petits segments de code qui peuvent se limiter à une seule instruction.
- Timer et compteur[36]
- Des timers/compteurs dans les systèmes embarqués sont souvent disponibles. Ils pourront être utilisés pour obtenir des mesures très fines et très précises des temps d’exécutions de petits segments de code. Le temps d’exécution du segment de code est obtenu en calculant la différence entre les valeurs lues dans le timer/compteur au début et à la fin de l’exécution.
La mise bout à bout de mesures de sous-ensembles de programme est possible pour produire une estimation du temps d'exécution et une idée du pire cas d'exécution de son programme, mais elle ne permet pas de trouver de manière précise et certaine ses limites de temps d'exécution. La garantie que les limites de sécurité soient tenues ne peuvent être données que pour les architectures simples. Ces méthodes peuvent être utilisées pour les applications qui n'ont pas de nécessité de garantie de temps d'exécution, typiquement les systèmes temps réel non stricts[37].
Méthode statique
La méthode statique a pour principe d’analyser la structure du programme sans réellement l'exécuter, puis de calculer le WCET à partir de cette structure. À l’inverse de la méthode dynamique, aucune donnée d’entrée n’est connue. Elle est composée de trois phases principales :
- L'analyse de flot détermine les chemins d’exécutions possibles. Pour cela elle exploite :
- une représentation du flot de contrôle (ou Reconstruction du flot de contrôle),
- une évaluation du flot de contrôle;
- L'analyse bas niveau détermine le temps d’exécution d’une séquence d’instructions sur une architecture donnée. Elle repose sur :
- une analyse des caches (analyse globale),
- une analyse des pipelines (analyse locale),
- une analyse des branchements ;
- Le calcul du WCET peut alors être mené en s’appuyant sur les résultats obtenus lors des deux phases précédentes et en utilisant :
- une technique par graphe de flots (path based) ou,
- une technique par arbre syntaxique (tree based) ou,
- une technique par énumération implicite des chemins (IPET).
On retrouve cette architecture type d'analyse statique de temps dans de très nombreux travaux[38],[39],[40],[41],[42] ou outils[43],[44],[45].
Les représentations du flot de contrôle (ou Reconstruction du flot de contrôle)
- Représentation en blocs de base
- Une première étape consiste à analyser le programme en le découpant en blocs de base. Ces blocs de base sont en fait des séquences de code contigües, autrement dit des ensembles d’instructions avec uniquement un point d’entrée et un point de sortie. Ils s’exécutent sans interruption et ne contiennent pas d’instruction de branchement[46].
- Représentation en arbre syntaxique
- L’étape suivante est relative à la description structurelle du code du programme. Elle est réalisée au travers d’une analyse de langage haut niveau en représentant un arbre syntaxique ayant pour feuilles les blocs de base ou les appels de fonction (CALL), et pour nœuds les séquences (SEQ), les conditions (IF), et les boucles (LOOP) d’instructions.
Les premières représentations de programme en arbre syntaxique sont données dès 1989 par Puschner et Koza[6], ou encore par Shaw[7]. - Représentation en graphe de flot de contrôle
- Cette étape va montrer à l’aide d’un graphe les divers enchaînements des blocs de bases entre eux et représenter tous les chemins d’exécution que le programme peut emprunter. Elle est généralement issue d’une analyse du code bas niveau (code compilé). Le graphe est composé de nœuds représentés par les blocs de base, et d’arcs représentant les enchaînements entre chaque nœud. Cette représentation, relative à la théorie des graphes, est visible dans beaucoup de travaux, par exemple[47],[48].
Les évaluations du flot de contrôle
- L’analyse de valeur
- L'analyse de valeur essaye de déterminer statiquement les valeurs stockées dans les registres et les blocs mémoires. Une telle information est nécessaire à la fois pour l’analyse des bornes de boucle, mais aussi pour déterminer le temps d’exécution des instructions arithmétiques dont le temps dépend des valeurs de leurs opérandes, ou encore pour une bonne approximation des adresses des données du programme utiles à l’analyse de bas niveau[49]. Le problème principal de l’analyse de valeur est l’indécidabilité; souvent plusieurs valeurs sont possibles à un même point du programme quand le contrôle passe par ce point plusieurs fois[50],[51].
- L’analyse de borne de boucle
- L'analyse de borne de boucle détermine le poids des extrémités du graphe. Elle identifie les boucles dans le programme et essaye de déterminer des bornes sur le nombre de boucles itératives et récursives. Les difficultés rencontrées sont au niveau des calculs des compteurs de boucle et des conditions de sortie de boucle, tout comme des dépendances entre compteurs de boucle dans les boucles imbriquées. Voir les travaux de Chu et Jaffar[52].
- L’analyse de flot de contrôle
- L’analyse de flot de contrôle, aussi appelée analyse de chemin infaisable, détermine l’ensemble des chemins possibles au travers du programme de manière à resserrer plus précisément les bornes de temps. Ce point est abordé dans le chapitre du calcul path-based. Cette technique permet de pondérer les nœuds et les boucles, mais aussi de fournir les contraintes des chemins. Une optimisation de celle-ci a été démontrée en utilisant le paradigme des chemins invariants par Lokuciejewski, Gedikli et Marwedel[53].
Toutes ces analyses fournissent des informations complémentaires utiles pour le calcul du WCET. La connaissance de données d’entrée d’un nœud peut contribuer à accroître la précision de l’analyse[54]. En effet, ces données peuvent avoir un impact important sur le conditionnement d’une branche, donc le choix du chemin à prendre dans le programme. Toutes ces informations peuvent alors être fournies de deux façons, soit sous forme d’annotations par l’utilisateur[5], ou soit par dérivation automatique. Pour cette dernière, des méthodes d’interprétations abstraites ont été proposées par Gustafson[55]. L’interprétation abstraite est en fait une théorie d’abstraction et d’approximation de structures mathématiques utilisées dans une description formelle de systèmes complexes et une déduction de leurs propriétés combinatoires ou indécidables. Un résumé des différentes interprétations abstraites (paradigmes, méthodes, algorithmes) a été réalisé par Cousot[56]. Un nouvel algorithme appelé “analyse de propagation minimum” (MPA) est notamment proposé par Bygde, Ermedhal et Lisper[57] pour effectuer le calcul paramétrique des programmes. Celui-ci est significativement plus efficace à la fois au niveau vitesse et mémoire que la méthode généralement employée de programmation d’entier paramétrique (PIP) introduite par Feautrier[58]. Cet algorithme est prévu pour être implémenté dans l’outil Sweet afin d’améliorer son analyse de flot.
Analyse bas niveau (ou microarchitecturale)
Cette étape est très complexe mais ses mécanismes de spéculation font preuve d’une perspicacité toujours croissante depuis quelques années car sans cesse en évolution. La précision de l’estimation du WCET en est considérablement améliorée[59]. Pour ce faire, elle utilise l’interprétation abstraite pour calculer les invariants pour chaque point du programme qui caractérisent l’ensemble de tous les états que l’architecture peut rencontrer quand le contrôle atteint ce point. Ces invariants décrivent de manière fiable l’information au sujet des contenus des caches, de l’état du pipeline incluant les contenus de toutes ses queues et mémoires tampon autant que l’occupation de ses unités, ainsi que l’état des bus, des mémoires, et des périphériques. Les invariants calculés sont utilisés pour exclure les transitions dans l’architecture. Par exemple, une transition de cache absent peut être exclue si l’invariant lié à l’état du cache lui permet de prédire un accès cache.
Si pour les architectures simples, les instructions sont séquentielles et leur temps d’exécution dépend essentiellement des opérations qu’elles doivent réaliser, pour les architectures complexes, les instructions peuvent être parallélisées grâce à l’usage de pipeline, et leur temps d’exécution varier en fonction de leur contexte par le biais de cache[60]. Cela rend donc l’analyse de temps beaucoup plus difficile. Ces effets sur le temps d’exécution peuvent avoir deux portées différentes: une portée locale dans le cas d’effet de parallélisme comme celui induit par les pipelines car il n’affecte le temps d’exécution que d’instructions proches l’une de l’autre, ou une portée globale dans le cas d’effet de variations de temps comme celui induit par les caches car il affecte cette fois l’ensemble des instructions du flot[61].
Analyse des caches (analyse globale)
Cette analyse catégorise les instructions en fonction de leur comportement dans le cache mémoire, à savoir si elles sont chargées ou non lors de l’appel processeur, et si elles affectent les autres instructions. L’objectif est d’identifier les instructions susceptibles de provoquer une perte de temps liée à un appel processeur qui ne trouve pas de donnée, soit en fait un conflit de cache mémoire[62]. Quatre catégories sont considérées :
- Always hit : l’accès à l’instruction en cache mémoire est toujours bon (cache hit)
- Always miss : l’accès à l’instruction en cache mémoire est toujours en défaut (cache miss)
- First miss : l’accès à l’instruction en cache mémoire est en défaut seulement à la première exécution de l’instruction
- Conflict : l’accès à l’instruction en cache mémoire est en conflit
La catégorisation se fait en deux phases. La première calcule pour chaque instruction (ou nœud ou bloc de base) tous les contenus du cache mémoire avant et après son exécution. Ces contenus sont nommés états abstraits de cache. Le principe est de trouver les instructions générant un conflit de cache mémoire menant au pire cas. La deuxième phase catégorise les instructions vis-à-vis de l’état abstrait de cache pour être utilisé lors de l’étape de calcul du WCET.
Cette méthode est par exemple utilisé par de nombreux outils d’analyse tels que Heptane[63],[note 8], AIT[64],[note 2], mais aussi détaillée dans les travaux de Lundqvist, Stenström[65] ou encore Puaut[66].
Analyse des pipelines (analyse locale)
.jpeg)
Le pipeline permet la parallélisation des instructions dans le but d’accroître les performances du processeur. Grâce à plusieurs étages dans le pipeline, les instructions peuvent se chevaucher ce qui induit que le temps d’exécution d’un ensemble d’instructions ne peut pas être égal à la somme des temps de chacune de ces instructions. Le calcul du WCET des instructions se fait via une représentation de l’occupation du pipeline par le remplissage de tables de réservation pendant l’exécution de ces instructions simulant ainsi les états d’occupation des étages du pipeline. Une étude de Metzlaff montre et quantifie l'impact des anomalies mémoires sur le calcul[67]. Comme pour l'analyse des caches, on peut retrouver cette méthode dans beaucoup d'outils[68],[69] et travaux[70],[71],[72]. Un cas d'anomalie de timing est illustré ci-contre dans le schéma "Anomalie causée par ordonnancement (pipeline)". Dans cette illustration, considérons que les instructions A, D et E ne peuvent s’exécuter que sur la ressource processeur 1, et que les instructions B et C ne peuvent s’exécuter que sur la ressource processeur 2. Le premier ordonnancement se montre optimal car C peut enchaîner avec les instructions D et E avant que l’instruction A n’enchaîne avec l’instruction B. Dans le deuxième ordonnancement, l’instruction A, exécutée sur la ressource processeur 1 et se terminant avant que la ressource C ne soit prête, va alors enchaîner sur l’instruction B sur la ressource processeur 2. Mais cette dernière instruction va bloquer le départ de l’instruction C car elle aussi ne peut s’exécuter que sur la ressource processeur 2 décalant ainsi le départ des instructions D et E suivantes sur la ressource processeur 1. L’ordonnancement est par conséquent plus long.
Analyse des branchements
.jpeg)
Cette analyse optionnelle peut s’avérer utile pour des architectures munies d’un prédicteur de branchement. La prédiction de branchement optimise l’usage du pipeline. Mais son mécanisme de spéculation peut engendrer des erreurs d’anticipation de chargement d’instruction et donc de la perte de temps. La technique est identique à celle utilisée pour l’analyse des caches. Un classement des instructions de branchement conditionnel est donc réalisé. Une méthode basée sur la technique BBIP (block based instruction prefetching) est proposée par Ni[73]. Des techniques d'optimisation ont aussi été comparées par Plazar en employant un algorithme génétique ou une programmation linéaire en nombres entiers[74],[75].Un cas d'anomalie due à la prédiction de branchement est illustré ci-contre dans le schéma « Anomalie causée par spéculation (cache) ». De mauvaises surprises peuvent se révéler allant à l’encontre de l’intérêt du cache mémoire prévu pour accélérer le traitement des instructions. En effet, dans le premier cas, l’instruction A se termine avant la condition de branchement. Le processeur engage alors une spéculation qui peut s’avérer être mauvaise, décalant alors le départ de l’instruction C attendue à cause du temps de chargement de l’instruction B dans le cache. Tandis que dans le cas de l’absence de prédiction, le traitement des instructions se fait finalement plus rapidement.
Calcul de WCET par graphe de flots (path based)
Cette technique tente de borner le plus long chemin d’exécution dans le graphe de flot, et donc de déduire le WCET[76]. La pratique courante pour y arriver est de travailler sur des petits ensembles de chemins en utilisant l’algorithmique des graphes et considérant les WCET des nœuds connus individuellement. Les chemins infaisables n’ayant aucun intérêt dans la recherche du WCET puisque ne se réalisant jamais, elle va consister à les éliminer du graphe. La borne haute pour une tâche est déterminée en calculant les bornes pour les différents chemins de la tâche, et en cherchant le chemin global ayant le temps d’exécution le plus long. La caractéristique principale de cette technique est que les chemins possibles sont représentés explicitement. Cette approche est valable dans une itération de boucle unique, mais pose des problèmes avec des flots s’étendant à travers des boucles à plusieurs niveaux. Le nombre de chemin étant exponentiel par rapport au nombre de points de ramification, il faut alors utiliser des méthodes de recherche heuristique de chemin[77]. La technique est parfaitement illustrée dans la publication « Overview WCET »[78].
Calcul de WCET par arbre syntaxique tree based
La représentation en arbre syntaxique du programme déjà obtenue en début d'analyse permet d’en découler un arbre de temps. En considérant que l’architecture matérielle n’utilise pas de cache, cet arbre fait la description du code source de la structure syntaxique du programme, des contraintes d’exécution exprimées par le développeur, et des temps d’exécution des différents blocs de base. Il révèle ainsi les WCET à chacun de ses nœuds. La technique consiste à parcourir l’arbre à l’envers en appliquant des formules mathématiques à chaque nœud afin de définir le chemin le plus long, et à chaque bloc de base pour calculer son WCET[79],[78].
Calcul de WCET par énumération implicite des chemins (IPET)
Pour cette étape, les temps d’exécution des blocs de bases sont des informations venant de l’analyse bas niveau. La technique s’appuie sur le graphe de flot. Son principe est de faire correspondre au graphe un ensemble de contraintes à respecter basées sur la programmation linéaire en nombre entier (ILP – Integer linear programming). Falk présente par exemple une méthode ILP basée sur l'allocation de registre[80]. À savoir que :
- Des variables d’entier modélisent le nombre de chemin des nœuds et des extrémités
- Un ensemble de contraintes modélise les flots du programme en utilisant la loi de Kirchhoff (la somme des flots entrants à un nœud doit égaler la somme des flots sortant)
- Un autre ensemble de contraintes modélise les nombres maximums d’itérations de boucle et autres contraintes de chemin déterminés par l’analyse de flot.
- La fonction objective est le produit scalaire des nombres de chemins et des poids des nœuds.
Pour calculer le WCET du plus long chemin, la fonction objective est maximisée. Pascal Raymond explique de manière générale la technique en la détaillant par plusieurs exemples[81].
Méthode hybride
Il existe traditionnellement deux types de méthodes pour le calcul du WCET, les méthodes dynamique et statique. Le désavantage de la méthode dynamique est qu'il est impossible de garantir que tous les chemins de flot de contrôle aient été couverts, de sorte que le résultat ne donne qu'une estimation approximative du WCET[82]. Pour ce qui concerne les méthodes statiques incluant une analyse haut et bas niveau, la complexité croissante des architectures des processeurs rendent l’estimation du WCET trop pessimiste[83]. Pour s’en affranchir, sont donc apparues des méthodes hybrides combinant les techniques d'analyses statiques haut-niveau du WCET et les analyses dynamiques du code[84].
D’une manière générique, les méthodes hybrides incluent les cinq étapes suivantes[82] :
- Analyse statique du code du programme : Il s’agit de l’analyse haut niveau défini dans la section 3.2.
- Identification des segments : Il s’agit, à partir des éléments analysés lors de la phase 1, de déterminer les différents segments à traiter.
- Application des chemins : Il s’agit d’une méthode permettant d’identifier tous les chemins infaisables afin de simplifier et de minimaliser les segments à mesurer.
- Mesure des temps d’exécutions de chaque segment.
- Calcul du WCET.
De nombreuses recherches ont été effectuées afin de faire progresser ces techniques hybrides et permettre de définir un cadre pouvant être utilisé par les milieux industriels. Ces méthodes mettent en jeu différentes techniques vu précédemment, comme l'utilisation de l’analyse statique, ou d'algorithmes évolutionnistes permettant la génération de jeux de test pour les méthodes de mesures dynamiques, afin de consolider le résultat du WCET obtenu[85],[86],[87],[88].
- Analyse temporelle basée sur la mesure
Voici la description d'une techniques d’analyse hybride du WCET : L’analyse temporelle basée sur la mesure (MBTA[note 13]).
- La première opération est donc l’analyse et la décomposition du programme en de multiples segments[89],[90]. La taille des séquences ainsi que leur faisabilité est à définir afin de garantir leur bon traitement lors de la phase de mesure[91]. De plus, la mesure de toutes ces séquences est généralement intraitable de manière exhaustive car tout simplement trop nombreuses. Par conséquent, la réduction du nombre de segments est cruciale.
Afin d’effectuer des mesures durant leur exécution, les techniques de décomposition du programme (bloc de base, graphe de flot) impliquent d’utiliser des techniques heuristiques pour sélectionner des jeux de test représentatifs[90]. - Une fois que le programme est décomposé, le temps d'exécution est mesuré pour chaque segment. Les temps d'exécutions sont mesurées sur le matériel cible, ce qui permet de prendre en considération les caractéristiques du matériel sans effectuer d’analyse statique bas-niveau[89],[90]. Cette phase introduit la notion de calcul optimiste : le temps maximal observé pour chaque segment est supposé être le véritable WCET[89].
- Les temps d'exécutions obtenus et les informations recueillies lors de l’analyse statique sont combinés pour calculer un WCET consolidé final[91].
Quelques études recensent et comparent des outils d’obtention du WCET[43],[9]. Parmi tous les outils existants, voici trois exemples issus du monde universitaire et trois autres du monde du commerce.
Outils universitaires
HEPTANE
Heptane[note 8](Hades Embedded Processor Timing ANalysEr) est un outil d’analyse statique open source sous licence GPL. Il a été conçu au début des années 2000 avec Isabelle Puaut et Antoine Colin. Cet outil[92] déduit le WCET de programmes en langage C en utilisant deux méthodes de calcul, une première basée sur l’arbre syntaxique et une deuxième basée sur la méthode IPET. L’utilisateur doit toutefois lui fournir des annotations symboliques sur le programme source afin de borner les boucles d’itération. L’analyse micro architecturale est par ailleurs assurée via des mécanismes d’analyse de cache, de pipeline et de prédiction de branchement intégrant la méthode de simulation de cache statique de Frank Mueller[93].
OTAWA
OTAWA[note 5] (Open Tool for Adaptative Wcet Analysis) est un outil d’analyse statique open source sous licence LGPL. Développé à l’Institut de recherche de Toulouse, il est issu de la collaboration de Clément Ballabriga, Hugues Cassé, Christine Rochange et Pascal Sainrat. Cet outil[94], utilisable sous la forme d’une bibliothèque C++, calcule le WCET par analyse statique basée sur IPET. La manipulation du code binaire est facilitée (graphe de flot de contrôle, détection de boucle…) et sa conception modulaire peut supporter différentes architectures telles que PowerPC, ARM, Sparc ou M68HCS.
SWEET
SWEET[note 14](SWEdish Execution Time analysis tool) est un outil d’analyse de flot et de calcul BCET/WCET (meilleur et pire cas de temps d’exécution). Il est développé en Suède depuis 2001 par l’équipe de recherche de Västerås et maintenant de Mälardalen. Sweet utilise un langage de programme intermédiaire spécialement conçu pour l’analyse de flot et travaillant au format « ALF ». Il peut analyser les programmes sources ou compilés, et exporter son travail pour le rendre exploitable dans les outils AIT ou Rapitime. Sa principale fonction est d’analyser le flot de contrôle le plus précisément et automatiquement possible en se basant sur trois méthodes différentes : path-based, IPET, ou hybride[95],[69].
Outils commerciaux
AIT (AbsInt)
AIT[note 2] (AbsInt’s Tool) est un outil développé par AbsInt Company et spécialisé pour le calcul WCET des systèmes embarqués[64],[96]. Il répond en particulier aux exigences de l’aéronautique. Basé sur l’interprétation abstraite et s’appuyant sur les méthodes d’analyse de Wilhelm, Ferdinand, Thesing, Langenbach et Theiling[97],[98],[99], AIT fonctionne sur le principe de construction d’un graphe de flot sur lequel des analyses de cache et de pipeline sont effectuées afin de calculer le pire chemin d’exécution par technique ILP. Il est aussi capable de supporter de très nombreuses architectures.
RAPITIME
RapiTime[note 6] est un outil de la société Anglaise Rapita Systems Ltd[note 15] conçu pour les systèmes embarqués de l'industrie automobile, de télécommunication ou aéronautique. Son origine est le prototype pWCET[100] développé par Bernat, Colin et Petters. L’outil fonctionne sur la méthode hybride en combinant des mesures dynamiques et des analyses statiques de type tree-based.
Bound-T
Bound-T[note 3] est un outil développé à l’origine par Space Systems Finland Ltd[note 16] sous contrat de l’Agence Spatiale Européenne (ESA)[note 17] pour les besoins de vérifications des systèmes embarqués spatiaux. Il examine le programme compilé en calculant le WCET via les méthodes d’analyses de flot de contrôle, de boucles d’itération, et d’annotations éventuelles données par l’utilisateur. Bound-T supporte la plupart des plateformes et processeurs.
| Méthode d'analyse | Considération de l'architecture | |
|---|---|---|
| HEPTANE | IPET, Tree-based | Abstraction |
| OTAWA | IPET | Abstraction |
| SWEET | IPET, Path-based, Hybride | Mesure |
| AIT | IPET | Abstraction |
| RAPITIME | Tree-based, Hybride | Mesure |
| BOUND-T | IPET | Abstraction |
MERASA
MERASA[note 18] (Multi-Core Execution of Hard Real-Time Applications Supporting Analysability) est un projet de recherche spécifique faisant partie du septième programme de développement informatique de la commission européenne. Conduit par l’université de Augsburg[note 19] (Professeur Ungerer)[101], il est le fruit d’une collaboration entre le centre de super calcul de Barcelonne[note 20], l’université de Toulouse (IRIT[note 21]), et les entreprises Rapita[note 15] et Honeywell[note 22]. Le projet s’est déroulé entre 2007 et 2010. Son objectif était de tenter d’influer sur la conception de matériel temps réel et de son logiciel en développant un nouveau processeur multicœurs (de 2 à 16 cœurs) et des techniques pour garantir un calcul fiable du WCET. Il s’inscrit dans le besoin croissant de l’industrie d’utiliser ces architectures pour augmenter les performances de leurs systèmes embarqués liés à la sécurité, mais aussi dans la nécessité de répondre aux contraintes d’impossibilité de prédire et d’analyser leur comportement sans amener à un fort pessimisme sur le calcul du WCET. Pour réaliser sa tâche, MERASA s'est appuyé sur deux outils d’analyses statiques existants : Otawa et Rapitime.
Méthodes d'affinage (WCET squeezing)
De nombreuses études tentent d’améliorer le calcul WCET.
Un exemple est donné par Lokuciejewski, Falk, Schwarzer, Marwedel et Theiling[102] en utilisant des procédures de clonage sur le code source pour réduire la surestimation du WCET. Celles-ci rendent le code mieux analysable et plus prévisible à partir de fonctions spécialisées qui permettent une définition explicite des bornes de boucles et optimisent les détections de chemins infaisables. La réduction mesurée avec l'outil de test Mibench-Suite[103] est comprise entre 12 et 95%.
Un deuxième exemple révèle une amélioration du calcul WCET avec un impact faible sur son coût[104]. Il consiste à combiner une exécution de programme symbolique avec la technique d’énumération de chemins implicites (IPET). Cette opération est réalisée en post traitement à tout analyseur incluant IPET. Elle correspond à un algorithme qui peut être stoppé à tout instant sans impact sur la fiabilité du calcul et qui ajoute un cadre de contraintes de temps pour affiner le WCET. Son implémentation a été réalisée dans la chaîne d’outillage r-TuBound[105].
Un troisième exemple apporte de nouvelles approches d’affinage WCET en optimisant l’utilisation des ressources dans un système multiprocesseurs[106]. Celles-ci visent l’ordonnancement des instructions en tenant compte autant des valeurs de TDMA (time division multiple access), autrement dit tranche de temps par processeur, que de la PD (priority division) qui est la priorité de la TDMA[107]. Elles utilisent une optimisation évolutionniste[108] sur le paramétrage de l’ordonnancement des ressources partagées, ainsi qu’une planification d’instruction qui restructure les programmes d’entrée pour accroître leur performance.
Les récents progrès technologiques et les tendances du marché tendent à faire converger l’informatique de haute performance (HPC) et l’informatique des systèmes embarqués (EC)[109]. En effet, le domaine HPC est réservé pour les traitements de volumes de données très élevés. À l’inverse, le domaine EC est focalisé sur l’exigence de connaitre avec sureté le temps d’exécution des systèmes temps réels. Mais aujourd’hui, l’énorme quantité de données à considérer pour de nombreuses applications embarquées fait que la prévisibilité et la performance deviennent des préoccupations communes. Le défi futur va donc être de prédire avec précision le temps d’exécution sur les prochaines architectures à plusieurs processeurs, en tenant compte aussi des contraintes jusqu’alors propres à chaque domaine tels que l’économie d’énergie, la flexibilité et la performance[110],[111]. L’usage de processeur standard devrait aussi permettre de réduire les coûts industriels mais sa non spécificité à un ensemble de tâches comme il est encore courant pour les systèmes embarqués va rendre le calcul du WCET plus difficile. Toute cette complexité a fait l’objet d’une réflexion[112] menée par un groupe de chercheurs du centre de recherche de Porto[note 23], de l’université de Modène[note 24], du centre de super calcul de Barcelone[note 20] et de l’université de Zürich[note 25].
D'autre part, la programmation de systèmes embarqués de sécurité temps réels nécessitant une attention particulière au niveau de la justesse logicielle mais aussi de l’utilisation des ressources, les techniques de conception avancées utilisent de plus en plus des méthodes de développement basées sur le modèle (ou application)[113],[114],[115]. Dans ce cas, l’application existe sur plusieurs niveaux de description équivalent aux résultats d’une suite de transformations. Une solution courante est d’utiliser la conception basée sur le modèle doté de trois composants: un langage de synchronisation pour développer l’application[116], un compilateur[117], et un outil de simulation[118]. Le langage haut niveau permet le développement modulaire, il possède une sémantique formelle et a la capacité de générer du code impératif. Du point de vue de l'analyse WCET, il permet des annotations au niveau conception à l’opposé d’une instrumentation lourde de bas niveau, et le code impératif qui en découle permet une bonne traçabilité car il adhère à certains critères de certification. Comme ce code impératif est systématiquement construit, il ouvre de nouvelles possibilités d’appliquer une découverte spécifique, d’exprimer et transférer les propriétés du flot vers le niveau de l'analyse WCET du code binaire. L’écart entre le haut niveau axé flot MBD (Model Based Design) et le bas niveau axé analyse de flot WCET nécessite un transfert bi directionnel de la sémantique de programmation[114]. Cette technique s’avère très intéressante pour les domaines de l’avionique et de l’automobile car elle affine efficacement le calcul du WCET[119],[120].
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
