Soutenance mémoire
Depuis les premiers ordinateurs personnels du début des années quatre-vingt, les systèmes informatisés se sont largement diversifiés et font maintenant partie intégrante de notre quotidien. Nous les utilisons dans le cadre de notre travail, de nos loisirs mais, également pour améliorer notre confort et notre sécurité. Nous les retrouvons par exemple dans nos ordinateurs personnels, dans nos téléphones portables, dans nos appareils multimédia, dans nos véhicules. . . Entre les différents systèmes informatisés, nous pouvons distinguer les systèmes temps réel qui exécutent des applications interagissant avec l’environnement dans lequel ils se situent. La communication avec l’environnement est effectuée d’une part à l’aide de capteurs servant à collecter des informations sur l’environnement. Ces informations sont ensuite traitées par les calculateurs du système déterminant les actions à réaliser par les actionneurs en fonction des événements générés par l’environnement.
Ces systèmes sont de plus en plus utilisés dans de nombreux domaines comme l’avionique, les centrales nucléaires ou encore l’automobile. De tels systèmes doivent bien sûr fournir des résultats valides en réponse aux événements de l’environnement mais ils doivent en plus fournir ces résultats en un temps déterminé afin de respecter les contraintes temporelles du système dont la plus courante est l’échéance de terminaison au plus tard. Le respect des contraintes temporelles est plus ou moins important suivant que l’on se place dans le cadre du temps réel souple ou strict. Pour les systèmes temps-réel souple, les contraintes sont définies pour assurer une certaine qualité de service et le non-respect occasionnel n’entraîne pas de problèmes importants. Par contre, le respect des contraintes de temps est impératif dans les systèmes temps-réel strict pour en assurer le bon fonctionnement. Le non respect des contraintes temporelles peut dans de tels systèmes entraîner des conséquences économiques, écologiques, humaines catastrophiques. Pour valider le bon fonctionnement des systèmes temps-réel, il est donc impératif de garantir la terminaison au plus tard à l’échéance de chacune des tâches s’exécutant sur le système. Cette validation repose sur une connaissance du temps d’exécution pire cas de chacune des tâches s’exécutant sur le système et pouvant être déterminé soit par mesures, soit par analyse statique.
La validation des systèmes temps-réel, vis-à-vis des contraintes temporelles, se doit de garantir la terminaison au plus tard à l’échéance de chaque tâche composant le système en se basant sur la faisabilité de l’ordonnancement [55, 14, 5, 21, 37]. Cette validation repose sur le pire temps d’exécution (en anglais : Worst Case Execution Time (WCET)) de chacune des tâches, celui-ci représentant une borne supérieure de tous les temps d’exécution possibles. Les systèmes temps-réel se doivent également d’être performants pour offrir de plus en plus de fonctionnalités à l’utilisateur. Pour cela, les architectures exécutant ces systèmes, disposent notamment d’une hiérarchie mémoire. L’intérêt principal de cette hiérarchie mémoire est d’offrir à l’utilisateur le plus grand espace mémoire disponible tout en gardant un temps d’accès le plus rapide possible en se basant sur les principes de localité spatiale et temporelle des applications. Pour ce faire, elle dispose de différents types de mémoires tels que les mémoires cache et la mémoire principale ayant chacun des capacités de stockage et des temps d’accès différents. La gestion de la hiérarchie mémoire est d’une part transparente pour le programmeur et d’autre part gérée dynamiquement afin d’améliorer le temps moyen d’exécution. Cependant, cette gestion dynamique amène de l’indéterminisme sur les temps d’accès mémoire. En effet, pour deux exécutions différentes, le contenu de chacun des composants de la hiérarchie mémoire est potentiellement différent. Ainsi, prévoir le temps d’accès à une donnée dans la hiérarchie mémoire s’avère complexe car il est fonction de son emplacement dans la hiérarchie lors de l’exécution. Dans les systèmes temps-réel, cette dynamicité se trouve donc être une source de difficultés pour l’estimation du pire temps d’exécution.
Méthodes d’estimation du temps d’exécution pire cas : vue d’ensemble
Comme nous venons de le voir, la validation des systèmes temps-réel, vis-àvis des contraintes temporelles, permet de garantir la terminaison au plus tard à l’échéance de chaque tâche composant le système en se basant sur la faisabilité de l’ordonnancement. Cette validation repose sur le pire temps d’exécution (en anglais : Worst Case Execution Time (WCET)) de chacune des tâches, celuici représentant une borne supérieure de tous les temps d’exécution possibles. Cependant, l’obtention du pire temps d’exécution d’une tâche est dans le cas général un problème indécidable [18, 88] nous amenant de ce fait à estimer une borne supérieure du WCET. L’estimation de cette borne est calculée en nombre de cycles processeurs et afin d’être correcte et la plus exploitable possible elle doit être sûre et précise.
Définition 1.1 (sûreté) Une borne du WCET d’une tâche est sûre si elle est supérieure à tous les temps d’exécution possibles.
Cette condition permet de garantir le respect des contraintes de temps. En effet, lors de la phase de validation, il est nécessaire de s’assurer que chaque tâche termine bien son exécution avant son échéance de terminaison au plus tard. Une telle vérification est valide si le temps d’exécution considéré est bien supérieur à tous les temps d’exécution possibles.
Définition 1.2 (précision) Plus une borne du WCET d’une tâche est proche du maximum de tous les temps d’exécution possibles plus elle est précise.
Il est important que l’estimation du WCET sur-approxime le moins possible le WCET réel. Une trop grande sur-approximation peut entraîner un échec de faisabilité sur un système donné ou amener les concepteurs à surestimer les ressources matérielles nécessaires amenant à un coût de réalisation plus important. Afin de simplifier l’analyse d’un système, l’estimation du pire temps d’exécution d’une application temps-réel est généralement effectuée en considérant de façon indépendante chaque tâche la composant. De ce fait, l’estimation du pire temps d’exécution n’est valide que si les tâches sont exécutées en isolation. L’impact du système sur le temps d’exécution de la tâche comme par exemple les interruptions ou encore les délais liés aux préemptions dans le cas de systèmes préemptifs multi-tâches, n’est pas directement intégré dans l’estimation du pire temps d’exécution des tâches. Cette considération est néanmoins réaliste pour des architectures uni-cœur, car les interférences causées par le système d’exploitation peuvent être prises en compte lors des tests d’ordonnançabilité [55, 14, 5, 21, 37] en se basant sur des méthodes de calcul de temps de préemption [71, 98, 97, 84, 16]. Bien que l’obtention d’une borne supérieure du pire temps d’exécution soit un problème simple à énoncer, il n’en reste pas moins un problème complexe à traiter car dans le cas général, un programme exécuté sur une architecture cible ne dispose pas d’un temps d’exécution unique. En effet, le temps d’exécution d’une application peut varier en fonction de différents critères liés d’une part à l’application elle-même et d’autre part aux caractéristiques de l’architecture matérielle sur laquelle elle est exécutée. Pour de nombreuses applications, les calculs à réaliser lors de l’exécution sont dépendant de ses données d’entrée. En fonction de celles-ci, différents traitements peuvent être réalisés par l’application, amenant à des chemins d’exécution différents et donc des temps d’exécution potentiellement différents. Les méthodes d’estimation de WCET doivent donc être en mesure de prendre en compte cette source de variabilité. L’autre source de variation du temps d’exécution provient de l’architecture matérielle sur laquelle l’application est exécutée. Les processeurs sont conçus avec comme objectif d’améliorer le temps moyen d’exécution des applications. Pour ce faire, différents mécanismes matériels comme les caches, les pipelines, les prédicteurs de branchements. . . sont maintenant présents dans la plupart des processeurs actuels. Cependant, ces mécanismes gérés dynamiquement afin d’améliorer le temps moyen d’exécution sont sources d’indéterminisme et peuvent pour deux instances d’exécution d’une application disposant du même jeu d’entrée amener à des temps d’exécution différents en fonction de leur état initial. Les méthodes d’estimation de WCET doivent donc prendre en compte le comportement dynamique de ces mécanismes matériels de façon précise afin de ne pas ni sous-estimer ni trop surestimer le pire temps d’exécution. Ces deux sources de variation ne sont pas décorrelées l’une de l’autre, impliquant que le temps d’exécution d’une tâche est dépendant à la fois du chemin d’exécution emprunté et de l’état initial des mécanismes matériels. Les méthodes d’estimation doivent donc prendre en compte conjointement ces deux sources de variation lors de l’estimation du pire temps d’exécution. L’estimation du pire temps d’exécution est un problème réputé difficile par la communauté temps-réel qui est étudié depuis plus de vingt ans et a donné lieu à de nombreuses méthodes d’estimation synthétisées dans [79, 106]. Elles peuvent être regroupées dans les deux catégories suivantes : méthodes dynamiques et méthodes statiques.
Classe de méthodes dynamiques
Les méthodes dynamiques consistent à exécuter chacune des tâches, composant une application, sur un système réel ou sur un simulateur avec différents jeux d’entrées et à mesurer le temps d’exécution de chacune des instances. L’estimation du pire temps d’exécution se dérive simplement en retournant le pire temps d’exécution mesuré. Les jeux d’entrées peuvent être fournis de façon explicite par l’utilisateur ou générés de façon automatique. Cette génération peut utiliser une recherche exhaustive sur la longueur des chemins [108] mais, le temps de génération de tous les jeux de test ainsi que le temps d’évaluation pour chacun d’eux est généralement trop long pour que l’approche soit exploitable en pratique. Un autre type d’approche consiste à utiliser un algorithme génétique [103] ou du recuit simulé afin d’obtenir des jeux de test maximisant le temps d’exécution de l’application. A l’exception des méthodes dynamiques exhaustives qui sont peu exploitables en pratique, les méthodes dynamiques posent un problème vis-à-vis de la propriété de sûreté requise pour la validation des systèmes. En effet, générer des paramètres d’entrées couvrant le pire chemin d’exécution de l’application s’avère très difficile voire impossible. De ce fait, ces méthodes ne sont pas en mesure de garantir que le plus grand temps d’exécution ainsi mesuré est toujours supérieur à toutes les exécutions possibles. Elles ont cependant l’avantage d’éliminer la phase de modélisation du comportement des mécanismes matériels complexes. Dans le cas de systèmes temps-réel souple, ce type d’approche peut s’avérer suffisante pour garantir la qualité de services des applications.
Classe de méthodes statiques
Les méthodes statiques analysent la structure du programme sans l’exécuter permettant ainsi de fournir une estimation du pire temps d’exécution indépendante du jeu d’entrée et de l’état initial des mécanismes matériels, garantissant ainsi la sûreté de l’estimation du WCET. Généralement, les méthodes d’analyse statique réalisent un découplage entre l’analyse du comportement pire cas des mécanismes matériels, appelé communément analyse bas niveau et l’analyse du flot de contrôle de l’application, appelé communément analyse haut niveau. L’analyse bas niveau fournit une estimation du temps d’exécution pire cas d’une portion du programme en se basant sur un modèle d’architecture matérielle, typiquement les caches, les pipelines. . . Le résultat de l’analyse bas niveau est ensuite utilisé par l’analyse haut niveau pour déterminer le pire temps d’exécution de la tâche en se basant sur une représentation de sa structure modélisant les chemins d’exécution possibles. Dans [2], un découpage physique est même réalisé entre l’analyse bas niveau, effectuée sur la machine cible, et l’analyse haut niveau, effectuée sur un calculateur, afin de garantir d’une part le respect des contraintes de temps mais également la confidentialité d’applications critiques comme celles s’exécutant sur les cartes à puce.
|
Table des matières
Introduction
1 État de l’art
1.1 Introduction
1.1.1 Organisation du chapitre
1.2 Méthodes d’estimation du temps d’exécution pire cas : vue d’ensemble
1.2.1 Classe de méthodes dynamiques
1.2.2 Classe de méthodes statiques
1.3 Méthodes d’estimation haut niveau du pire temps d’exécution
1.3.1 Méthode basée sur l’arbre syntaxique
1.3.2 Méthode d’énumération implicite des chemins
1.4 Analyse bas niveau : analyse du comportement temporel pire cas des mémoires cache
1.4.1 Architectures des mémoires cache
1.4.2 Mémoires cache et estimation du pire temps d’exécution
1.4.3 Tour d’horizon des méthodes d’analyse statique du comportement temporel pire cas des mémoires cache
1.4.4 Méthode d’analyse statique pour les caches d’instructions basée sur la théorie de l’interprétation abstraite
1.4.5 Résultats théoriques permettant la prise en compte de différentes politiques de remplacement de cache
1.4.6 Interaction entre mémoire cache et pipeline
1.5 Autres travaux relatifs aux caches pour les systèmes temps-réel
1.5.1 Solutions à base d’analyse statique
1.5.2 Approches matérielles pour plus de déterminisme
1.5.3 Compilation orientée pire temps d’exécution
1.6 Discussion
2 Analyse du contenu des hiérarchies de caches
2.1 Introduction
2.1.1 Contributions
2.1.2 Hypothèses et notations
2.1.3 Organisation du chapitre
2.2 Approche existante et limitation
2.3 Analyse statique des hiérarchies de caches non-inclusives
2.3.1 Vue d’ensemble de l’analyse
2.3.2 La classification d’accès au cache (CAC)
2.3.3 Prise en compte de la classification d’accès lors de l’analyse d’un niveau de cache
2.3.4 Sûreté de l’analyse
2.3.5 Terminaison de l’analyse
2.3.6 Exemple
2.3.7 Analyse indépendante des différents niveaux de caches de la hiérarchie mémoire
2.4 Analyse statique des hiérarchies de caches inclusives
2.4.1 Fonctionnement et propriétés
2.4.2 Problématique de l’analyse
2.4.3 Vue d’ensemble de l’analyse
2.4.4 Détection des lignes de cache potentiellement évincées
2.4.5 Modélisation du procédé d’invalidation : modification de la classification de comportement
2.4.6 Raffinement de l’analyse
2.4.7 Terminaison de l’analyse
2.4.8 Exemple
2.5 Analyse statique des hiérarchies de caches exclusives
2.5.1 Fonctionnement et propriétés
2.5.2 Problématique de l’analyse
2.5.3 Modélisation et analyse des hiérarchies de caches exclusives
2.5.4 Exemple
2.6 Extension à d’autres politiques de remplacement de cache
2.6.1 Utilisation des bornes mls et evict
2.6.2 Sûreté et terminaison de l’analyse
2.7 Calcul de l’estimation du pire temps d’exécution
2.8 Expérimentations
2.8.1 Conditions expérimentales
2.8.2 Résultats expérimentaux
2.9 Conclusion
3 Analyse du contenu pire cas de caches partagés pour architecture multi-cœurs
3.1 Introduction
3.1.1 Contributions
3.1.2 Organisation du chapitre
3.2 Approche existante
3.3 Hypothèses et notations
3.4 Détection et prise en compte des conflits dans les caches partagés
3.4.1 Détection des conflits dans un niveau de cache partagé
3.4.2 Prise en compte des conflits dans un niveau de cache partagé
3.4.3 Traitement des conflits dus au code partagé
3.5 Réduction des conflits en utilisant un mécanisme de bypass
3.5.1 Identification statique des lignes de cache à usage unique
3.5.2 Prise en compte du mécanisme de bypass lors de l’analyse de cache des niveaux partagés
3.5.3 Support matériel pour utiliser notre stratégie de bypass
3.6 Expérimentations
3.6.1 Conditions expérimentales
3.6.2 Résultats expérimentaux
3.7 Conclusion
Conclusion
Annexes
Télécharger le rapport complet
