Temps d'exécution dans le pire des cas - Worst-case execution time

Le temps d'exécution dans le pire des cas ( WCET ) d'une tâche de calcul est la durée maximale que la tâche pourrait prendre pour s'exécuter sur une plate-forme matérielle spécifique .

A quoi ça sert

Le temps d'exécution dans le pire des cas est généralement utilisé dans les systèmes en temps réel fiables , où la compréhension du comportement de synchronisation du logiciel dans le pire des cas est importante pour la fiabilité ou un comportement fonctionnel correct.

Par exemple, un système informatique qui contrôle le comportement d'un moteur dans un véhicule peut avoir besoin de répondre à des entrées dans un laps de temps spécifique. Un composant qui compose le temps de réponse est le temps passé à exécuter le logiciel. Par conséquent, si le temps d'exécution du pire cas du logiciel peut être déterminé, le concepteur du système peut l'utiliser avec d'autres techniques telles que l'analyse d'ordonnancement pour s'assurer que le système répond. assez rapide.

Alors que WCET est potentiellement applicable à de nombreux systèmes en temps réel, dans la pratique, une assurance de WCET est principalement utilisée par les systèmes en temps réel qui sont liés à une fiabilité ou à une sécurité élevées. Par exemple, dans le logiciel aéroporté, une certaine attention au logiciel est requise par la section 6.3.4 de la DO178B . L'utilisation croissante de logiciels dans les systèmes automobiles entraîne également le besoin d'utiliser l'analyse WCET des logiciels.

Dans la conception de certains systèmes, WCET est souvent utilisé comme entrée pour l'analyse d'ordonnancement , bien qu'une utilisation beaucoup plus courante de WCET dans les systèmes critiques consiste à s'assurer que les budgets de synchronisation pré-alloués dans un système à partition planifiée tel que ARINC 653 sont pas violé.

Calcul

Depuis les premiers jours de l'informatique embarquée, les développeurs de logiciels embarqués ont soit utilisé :

  • mesures de code de bout en bout, par exemple effectuées en définissant une broche d'E/S sur l'appareil à l'état haut au début de la tâche, et à l'état bas à la fin de la tâche et en utilisant un analyseur logique pour mesurer l'impulsion la plus longue largeur, ou en mesurant dans le logiciel lui-même en utilisant l'horloge du processeur ou le nombre d'instructions.
  • techniques d'analyse statique manuelle telles que le comptage des instructions assembleur pour chaque fonction, boucle, etc., puis leur combinaison.

Ces deux techniques ont des limites. Les mesures de bout en bout imposent une lourde charge aux tests logiciels pour obtenir le chemin le plus long ; les instructions de comptage ne s'appliquent qu'aux logiciels et matériels simples. Dans les deux cas, une marge d'erreur est souvent utilisée pour tenir compte du code non testé, des approximations des performances matérielles ou des erreurs. Une marge de 20 % est souvent utilisée, bien qu'il y ait très peu de justifications utilisées pour ce chiffre, sauf pour la confiance historique ("ça a marché la dernière fois").

Au fur et à mesure que les logiciels et le matériel sont devenus de plus en plus complexes, ils ont entraîné le besoin de support d'outils. La complexité devient de plus en plus un problème à la fois dans l'analyse statique et les mesures. Il est difficile de juger de l'étendue de la marge d'erreur et de la qualité des tests du système logiciel. Les arguments de sécurité du système basés sur une note élevée obtenue lors des tests sont largement utilisés, mais deviennent plus difficiles à justifier à mesure que le logiciel et le matériel deviennent moins prévisibles.

À l'avenir, il est probable qu'une exigence pour les systèmes critiques pour la sécurité soit qu'ils soient analysés en utilisant à la fois des approches statiques et basées sur des mesures.

Considérations

Le problème de trouver le WCET par analyse est équivalent au problème de l' arrêt et n'est donc pas résolvable en général. Heureusement, pour le type de systèmes pour lesquels les ingénieurs veulent généralement trouver WCET, le logiciel est généralement bien structuré, se terminera toujours et est analysable.

La plupart des méthodes pour trouver un WCET impliquent des approximations (généralement un arrondi vers le haut lorsqu'il existe des incertitudes) et, par conséquent, dans la pratique, le WCET exact lui-même est souvent considéré comme impossible à obtenir. Au lieu de cela, différentes techniques pour trouver le WCET produisent des estimations pour le WCET. Ces estimations sont généralement pessimistes, ce qui signifie que le WCET estimé est connu pour être supérieur au WCET réel (ce qui est généralement ce qui est souhaité). Une grande partie du travail sur l'analyse WCET consiste à réduire le pessimisme dans l'analyse afin que la valeur estimée soit suffisamment faible pour être utile au concepteur du système.

L'analyse WCET fait généralement référence au temps d'exécution d'un seul thread, tâche ou processus. Cependant, sur le matériel moderne, en particulier multicœur, d'autres tâches du système auront un impact sur le WCET d'une tâche donnée si elles partagent le cache, les lignes de mémoire et d'autres fonctionnalités matérielles. En outre, les événements de planification de tâches tels que le blocage ou les interruptions doivent être pris en compte dans l'analyse WCET s'ils peuvent se produire dans un système particulier. Par conséquent, il est important de considérer le contexte dans lequel l'analyse WCET est appliquée.

Approches automatisées

Il existe de nombreuses approches automatisées pour calculer le WCET au-delà des techniques manuelles ci-dessus. Ceux-ci inclus:

  • techniques analytiques pour améliorer les cas de test pour augmenter la confiance dans les mesures de bout en bout
  • analyse statique du logiciel (signifiant "statique" sans exécuter le logiciel).
  • approches combinées, souvent appelées analyse « hybride », étant une combinaison de mesures et d'analyse structurelle

Techniques d'analyse statique

Un outil WCET statique tente d'estimer le WCET en examinant le logiciel de l'ordinateur sans l'exécuter directement sur le matériel. Les techniques d'analyse statique ont dominé la recherche dans le domaine depuis la fin des années 1980, bien que dans un environnement industriel, les approches de mesures de bout en bout aient été la pratique standard.

Les outils d'analyse statique fonctionnent à un niveau élevé pour déterminer la structure de la tâche d'un programme , en travaillant soit sur un morceau de code source , soit sur un exécutable binaire désassemblé . Ils fonctionnent également à bas niveau, en utilisant des informations de synchronisation sur le matériel réel sur lequel la tâche s'exécutera, avec toutes ses fonctionnalités spécifiques. En combinant ces deux types d'analyse, l'outil tente de donner une limite supérieure au temps nécessaire pour exécuter une tâche donnée sur une plate-forme matérielle donnée.

Au bas niveau, l'analyse statique WCET est compliquée par la présence de fonctionnalités architecturales qui améliorent les performances moyennes du processeur : caches d' instructions/données , prédiction de branchement et pipelines d'instructions , par exemple. Il est possible, mais de plus en plus difficile, de déterminer des limites WCET strictes si ces caractéristiques architecturales modernes sont prises en compte dans le modèle temporel utilisé par l'analyse.

Les autorités de certification telles que l' Agence européenne de la sécurité aérienne s'appuient donc sur des suites de validation de modèles.

L'analyse statique a donné de bons résultats pour du matériel plus simple, cependant une limitation possible de l'analyse statique est que le matériel (le CPU en particulier) a atteint une complexité extrêmement difficile à modéliser. En particulier, le processus de modélisation peut introduire des erreurs de plusieurs sources : erreurs de conception de la puce, manque de documentation, erreurs de documentation, erreurs de création de modèle ; tout cela conduit à des cas où le modèle prédit un comportement différent de celui observé sur du matériel réel. En règle générale, lorsqu'il n'est pas possible de prédire avec précision un comportement, un résultat pessimiste est utilisé, ce qui peut conduire à une estimation WCET beaucoup plus importante que tout ce qui est obtenu au moment de l'exécution.

L'obtention d'une estimation statique stricte du WCET est particulièrement difficile sur les processeurs multicœurs.

Il existe un certain nombre d'outils commerciaux et universitaires qui mettent en œuvre diverses formes d'analyse statique.

Techniques de mesure et hybrides

Les approches basées sur les mesures et hybrides tentent généralement de mesurer les temps d'exécution de segments de code court sur le matériel réel, qui sont ensuite combinés dans une analyse de niveau supérieur. Les outils prennent en compte la structure du logiciel (par exemple les boucles, les branches), pour produire une estimation du WCET du programme plus large. La raison en est qu'il est difficile de tester le chemin le plus long dans un logiciel complexe, mais il est plus facile de tester le chemin le plus long dans de nombreux composants plus petits. Un effet du pire cas n'a besoin d'être vu qu'une seule fois pendant le test pour que l'analyse puisse le combiner avec d'autres événements du pire cas dans son analyse.

En règle générale, les petites sections du logiciel peuvent être mesurées automatiquement à l'aide de techniques telles que l'instrumentation (ajout de marqueurs au logiciel) ou avec un support matériel tel que des débogueurs et des modules de traçage matériel CPU. Ces marqueurs donnent lieu à une trace d'exécution, qui comprend à la fois le chemin parcouru dans le programme et l'heure à laquelle les différents points ont été exécutés. La trace est ensuite analysée pour déterminer le temps maximum que chaque partie du programme a jamais pris pour s'exécuter, quel est le temps d'itération maximum observé de chaque boucle et s'il y a des parties du logiciel qui ne sont pas testées ( couverture du code ).

L'analyse WCET basée sur les mesures a donné de bons résultats pour le matériel simple et complexe, bien que, comme l'analyse statique, elle puisse souffrir d'un pessimisme excessif dans les situations multicœurs, où l'impact d'un cœur sur un autre est difficile à définir. Une limitation de la mesure est qu'elle repose sur l'observation des effets les plus défavorables pendant les tests (mais pas nécessairement en même temps). Il peut être difficile de déterminer si les pires effets des cas ont nécessairement été testés.

Il existe un certain nombre d'outils commerciaux et universitaires qui mettent en œuvre diverses formes d'analyse basée sur la mesure.

Recherche

Les groupes de recherche les plus actifs se trouvent en Suède (Mälardalen, Linköping), en Allemagne (Saarbrücken, Dortmund, Braunschweig), en France (Toulouse, Saclay, Rennes), en Autriche (Vienne), au Royaume-Uni (University of York et Rapita Systems Ltd), en Italie ( Bologne), Espagne (Cantabrie, Valence) et Suisse (Zurich). Récemment, le sujet de l'analyse temporelle au niveau du code a attiré plus d'attention en dehors de l'Europe par des groupes de recherche aux États-Unis (Caroline du Nord, Floride), Canada, Australie, Bangladesh (MBI LAB et RDS), Royaume d'Arabie saoudite-UQU (HISE LAB) et Singapour.

Défi de l'outil WCET

Le premier WCET Tool Challenge international a eu lieu à l'automne 2006. Il a été organisé par l' Université de Mälardalen et parrainé par le réseau d'excellence ARTIST2 sur la conception de systèmes embarqués. L'objectif du Challenge était d'inspecter et de comparer différentes approches pour analyser le temps d'exécution le plus défavorable. Tous les outils et prototypes disponibles capables de déterminer des limites supérieures sûres pour le WCET des tâches ont participé. Les résultats finaux ont été présentés en novembre 2006 au Symposium international ISoLA 2006 à Paphos , à Chypre.

Un deuxième Challenge a eu lieu en 2008.

Voir également

Les références

  1. ^ " Le pire des cas de problème de temps d'exécution - vue d'ensemble des méthodes et aperçu des outils ", Wilhelm, Reinhard, et al., ACM Transactions on Embedded Computing Systems (TECS), Vol. 7, n° 3, 2008.
  2. ^ "Copie archivée" (PDF) . Archivé de l'original (PDF) le 2011-10-01 . Récupéré le 2010-08-15 .CS1 maint: copie archivée comme titre ( lien )
  3. ^ "Copie archivée" . Archivé de l'original le 2012-02-16 . Récupéré le 2008-08-16 .CS1 maint: copie archivée comme titre ( lien )

Articles et livres blancs

Liens externes