Soutenance mémoire
Les systèmes temps-réel reposent sur la correction des résultats calculés autant que sur la date de leur production. Les tâches s’ordonnent dans le temps et sont contraintes de terminer avant leur échéance. Ces systèmes sont aussi caractérisés par leur nature critique. Le manquement à une contrainte temporelle peut impliquer pour un système strict, p. ex. de type contrôle aéronautique, des pertes humaines ou financières majeures. Par contraste, on distingue les systèmes tempsréel souples pour lesquels une échéance ratée se résout par une baisse de qualité de service, p. ex. la perte d’images lors du décodage d’une séquence vidéo.
Afin de valider un système temps-réel, il faut pouvoir assurer l’existence d’une organisation de ses tâches dans le temps, un ordonnancement, telle que chaque tâche considérée respecte ses contraintes temporelles dans tous les cas, même le pire. Étant donnée une politique d’ordonnancement, le test d’ordonnançabilité associé exige la connaissance du profil temporel, en particulier le pire temps d’exécution (wcet, worst case execution time), des applications impliquées. L’analyse du comportement temporel d’une tâche pour l’estimation de son wcet est donc une étape pivot des méthodes de validation de systèmes critiques. Cette estimation doit satisfaire aux contraintes de sûreté et de précision. La sûreté est la garantie que le pire temps estimé est supérieur au pire temps effectif. Pour être précis, un pire temps estimé doit être au plus proche du pire temps effectif de l’application.
Remplir ces contraintes de sûreté et de précision suppose la prise en compte de l’environnement matériel sur lequel la tâche analysée s’exécute. Cependant, les architectures généralistes sont orientées vers l’amélioration du temps d’exécution moyen des tâches qu’elles hébergent, temps-réel ou non. Si ces optimisations répondent au besoin croissant de performances des systèmes temps-réel, la complexité matérielle engagée compromet la précision des estimations de wcet et sa méconnaissance porte atteinte à leur sûreté.
État de l’art sur l’estimation du comportement temporel pire-cas de la hiérarchie mémoire
Un système temps-réel se doit d’être valide non seulement vis-à-vis des résultats et des comportements qu’il produit mais aussi de ses contraintes temporelles. Cette validation repose sur une estimation du comportement temporel des applications. Plus spécifiquement, leur pire temps d’exécution (wcet, worst case execution time) est utilisé pour assurer qu’elles satisfont à leurs échéances dans tous les cas, même le pire, et à plus large échelle que le système valide ses contraintes temporelles. Les wcet calculés se doivent d’offrir deux propriétés fondamentales : la sûreté et la précision. Une estimation sûre du pire temps d’exécution d’une tâche est supérieure à son pire temps effectif. Il s’agit d’une propriété cruciale dans le cadre de systèmes temps-réel stricts, où le dépassement d’une échéance peut conduire à des pertes humaines ou financières. Elle peut être plus lâche pour des systèmes dits souples. La précision de l’estimation implique qu’elle est au plus proche du pire temps effectif de la tâche. Une estimation trop lâche conduit à allouer plus de ressources que nécessaire à un système pour garantir sa validation. Le temps d’exécution d’une tâche n’est pas constant et varie en fonction de nombreux facteurs tant matériels, les mécanismes architecturaux mis en œuvre au niveau du processeur, que logiciels, le système d’exploitation et les tâches concurrentes, et environnementaux, notamment les données d’entrée du programme qui peuvent affecter le chemin suivi dans l’application. Durant les deux dernières décennies, nombre de travaux de recherche se sont concentrés sur l’obtention de ces estimations dans le cadre d’architectures unicœurs complexes comprenant par exemple du parallélisme d’instruction. Cet intérêt pour l’obtention d’estimations sûres et précises est porté à la fois par : le coût du pessimisme et de l’imprécision lors de la validation des systèmes, et le caractère critique des systèmes temps-réel. La croissance en complexité des architectures matérielles répond aux besoins de performances des systèmes généralistes. Dans une moindre mesure, les systèmes temps-réel ne sont pas étrangers à de tels besoins. Les solutions matérielles présentent l’avantage indéniable d’être transparentes aux utilisateurs des systèmes impliqués. Néanmoins, plus une architecture est complexe, moins les estimations temporelles sur cette architecture sont précises.
L’un de ces facteurs de complexité est la hiérarchie mémoire, une suite d’antémémoires (cache) assurant la liaison entre le processeur et la mémoire centrale. Chacune d’entre elles contient une image partielle de la mémoire, plus rapide d’accès que cette dernière. De fait, la présence ou l’absence en cache de données requises par une séquence d’instructions peut résulter en un différence de temps d’exécution de plusieurs centaines de cycles processeur.
Estimation de pire temps d’exécution
Les trois principales familles de méthodes d’estimation du comportement temporel d’une tâche sont présentées dans cette section. Les méthodes dynamiques sont basées sur des mesures répétées du temps d’exécution de la tâche dans différents environnements. Les méthodes statiques reposent sur l’analyse statique formelle du code des tâches. Les méthodes hybrides, quant à elles, combinent analyse statique et mesure.
Il est à noter que dans tous les cas, le pire temps d’exécution de la tâche étudiée doit être borné. Le problème de la terminaison d’un programme étant dans le cas général indécidable [95], des contraintes additionnelles sont requises pour les tâches analysées, telle que l’existence de bornes sur le nombre d’itérations de chaque boucle, contraintes réalistes dans ce domaine [1].
Mesure du temps d’exécution, méthodes dynamiques
En théorie, étant données une architecture hôte et une tâche, son profil temporel exact peut être obtenu en effectuant une mesure pour chacune des valeurs de données d’entrée et toutes les configurations environnementales, bref pour toute combinaison possible de facteurs de variation. Des méthodes génétiques [101] ont été proposées pour diriger la recherche d’une configuration optimale, maximisant le temps d’exécution de la tâche étudiée. L’algorithme génétique [29] travaille sur une population composée de jeux d’entrées pour une tâche donnée. Cette population subit de façon itérative des évolutions avec l’objectif de converger vers une solution produisant le pire temps d’exécution. Toutefois, un tel algorithme peut se retrouver piégé autour d’un minima local, dans une zone restreinte de l’espace des solutions, quand un minimum global est requis pour satisfaire à la propriété de sûreté de la solution. Un autre axe de recherche est l’exploration et la mesure du temps d’exécution sur la totalité des chemins possibles de l’application cible [105]. Pour réduire le nombre de cas explorés, des conditions de validité sur l’ensemble des chemins évalués ont été proposées, p. ex. « chaque instruction est exécutée au moins une fois par un des chemins de l’ensemble » Mais des conditions trop précises posent un problème de complexité vis-à-vis du nombre de configurations à explorer. Si les méthodes dynamiques en reproduisant un environnement d’exécution répondent à la contrainte de précision, le pire cas peut toujours éluder la mesure en cas d’exploration non exhaustive des configurations possibles [102] ; pour des systèmes réalistes, le nombre de configurations à considérer est souvent trop important pour qu’une exploration exhaustive soit applicable [79]. Ces méthodes conviennent pour la validation de systèmes temps-réel souples où un comportement divergent de celui estimé met seulement en jeu la qualité de service. Elles s’avèrent aussi utiles pour une estimation rapide du comportement temporel d’applications. Il est à noter que les mesures peuvent être difficiles à réaliser car requérant le matériel hôte et un mécanisme d’observation ne perturbant pas les résultats obtenus (probe effect [28]).
Méthodes d’analyse statique
Pour estimer le pire temps d’exécution d’une application, les méthodes statiques ne reposent sur aucune exécution mais sur l’observation et l’analyse de son code source ou de son exécutable. L’analyse se déroule en deux temps. Une analyse bas niveau calcule le pire temps d’exécution de séquences d’instructions prédéfinies dénommées blocs de base. Basée sur un modèle de la machine hôte, elle prend en compte les effets architecturaux. Une analyse dite de haut niveau compose ensuite ces résultats à partir d’une représentation logique du flot du programme. Le bloc de base, fréquemment considéré comme unité de l’analyse bas niveau, est la plus grande séquence d’instructions consécutives comportant une unique entrée et une seule sortie. Entrée et sortie sont situées respectivement en début et en fin de séquence [2]. Aucune branche n’entre dans la séquence ou n’en sort en dehors de ses deux extrémités. Toutes les instructions de la séquence sont donc exécutées du début à la fin lorsque le bloc de base est exécuté.
|
Table des matières
Introduction
1 État de l’art sur l’estimation du comportement temporel pire-cas de la hiérarchie mémoire
1.1 Estimation de pire temps d’exécution
1.1.1 Mesure du temps d’exécution, méthodes dynamiques
1.1.2 Méthodes d’analyse statique
1.1.3 Méthodes hybrides pour analyse temporelle
1.2 Analyse bas niveau, comportement temporel des caches
1.2.1 Architecture et propriétés des caches
1.2.2 Analyse statique du comportement temporel au pire cas d’un cache
1.2.3 Améliorer la prédictibilité des caches
1.3 Discussion
2 Comportement pire-cas des caches de données partagés en contexte multi-cœur
2.1 Analyse multi-niveau de caches de données
2.1.1 Analyse d’un niveau de cache
2.1.2 Classification d’accès au cache (cac)
2.1.3 Estimation de la contribution temporelle au pire cas des caches
2.2 Impact des interférences sur les analyses de caches de données
2.2.1 Estimation des conflits de cache inter-tâches
2.2.2 Prise en compte des conflits durant l’analyse des caches
2.2.3 Classification des accès aux données partagées
2.3 Réduction des conflits pour les caches partagés, utilisation du bypass
2.3.1 Calcul des réutilisations entre accès mémoire
2.3.2 Heuristiques pour le bypass
2.3.3 Analyse de statique caches de données avec du bypass
2.4 Expérimentations
2.4.1 Conditions expérimentales
2.4.2 Caches de données en environnement uni-cœur
2.4.3 Caches de données en environnement multi-cœur
3 PRETI : Caches partitionnés pour environnements temps-réel
3.1 Fondements de la politique de partitionnement preti
3.1.1 Politiques d’accès et de mise à jour du cache
3.1.2 Implémentation du partitionnement
3.1.3 Analyse de caches partitionnés avec preti
3.2 Expérimentations
3.2.1 Conditions expérimentales
3.2.2 Impact de preti sur l’ordonnançabilité des systèmes
3.2.3 Impact de preti sur les performances mesurées des tâches
3.3 Étendre le comportement des caches preti
3.3.1 Restriction des accès aux données partagées
3.3.2 Contrôle de la croissance des partitions
3.3.3 Extensions à d’autres politiques de remplacement, au delà du lru
Conclusion
