Soutenance mémoire
Analyse formelle
On parle de vérification de modèle (model-checking) [Sc99]. Par un travail d’abstraction du système, il est possible de construire une représentation du système dans un formalisme particulier. Ce modèle offre ensuite la possibilité d’être exploré par des techniques automatiques de manière à vérifier des propriétés sur le système, telles que l’atteignabilité (assurant qu’un état du système peut être atteint), la sûreté (il est sûr que rien de mauvais ne peut se produire) ou la vivacité (il est sûr que quelque chose de bon peut inévitablement se produire). Dans les formalismes utilisés, on retrouve généralement les automates ou les réseaux de Petri, pour ce qui est des modèles discrets. Mais il existe de nombreuses extensions et, notamment, pour intégrer les propriétés temporelles : les automates temporisés et les réseaux de Petri T-temporels. Située durant la phase de conception, cette approche permet d’anticiper et de répondre au plus tôt aux problèmes constatés. Elle présente aussi l’avantage d’offrir un caractère exhaustif aux propriétés vérifiées. Les algorithmes d’exploration assurent que les propriétés sont vérifiées ou non, dans tous les cas de figure possibles. Ces résultats, qui s’appuient sur des preuves mathématiques, peuvent toutefois être limités dans leur portée du fait de la distance incertaine entre l’implantation réelle et le modèle étudié. L’analyse formelle se confronte à une autre difficulté : les limitations de puissance de calcul. Quand le système est complexe à modéliser, la construction du modèle peut faire face à une explosion combinatoire des états, empêchant toute étude.
Analyse par simulation
Contrairement aux méthodes précédentes, la simulation n’offre pas de caractère exhaustif aux résultats. En effet, elle n’apporte qu’une assurance sur les cas simulés, qui ne peuvent pas prétendre à la généralité. L’analyse par simulation consiste à se donner la possibilité d’effectuer des tests au travers d’un modèle qui simule fidèlement le fonctionnement de l’application. Dans le domaine du temps réel, effectuer des tests sur la cible pose de nombreuses difficultés. Le matériel, nécessairement réduit en embarqué, n’offre pas toujours les fonctionnalités requises pour la vérification. L’environnement en interaction n’est pas toujours à portée d’expérimentation ou manipulable pour mettre en œuvre des tests prédéfinis et répétables. Enfin, effectuer des tests sur cibles peut représenter un certain coût, du fait des machines utilisés (prenons, par exemple, les crash tests de voiture). La simulation répond à ces différents problèmes. Elle a notamment la capacité d’offrir des résultats complémentaires aux phases de tests, grâce à la large palette de résultats qu’elle peut fournir. Il existe plusieurs moteurs de simulation. On peut, par exemple, citer parmi les plus connus : Matlab, Simulink, SystemC. Ces simulateurs peuvent être à temps discret ou continu. Un simulateur à temps continu effectue un rafraîchissement de l’état du système à chaque pas du temps. Tandis qu’un simulateur à temps discret attend la venue d’un évènement pour effectuer ce rafraîchissement. Matlab et Simulink utilisent la simulation à temps continu. SystemC utilise la simulation à temps discret. L’analyse par simulation fait face aux mêmes défauts que l’utilisation de phases de tests. Elle peut notamment demander un nombre conséquent de scénarios à simuler pour valider le système. Cela implique un certain choix dans les scénarios de telle manière à faire apparaître les différentes contraintes du système. À ceci s’ajoute que, ayant recours à une modélisation du système, le résultat d’une simulation peut différer sensiblement de la réalité si la distance entre le modèle et le système est trop grande. La validation par simulation de systèmes temps réel impose de travailler sur les temps d’exécution. On distingue des simulateurs fonctionnels et des simulateurs temporels. Dans le cadre de cette thèse, ce sont ces seconds qui nous intéressent.
Langage de description d’architecture
Il n’est pas possible de tout représenter dans le modèle de simulation. Un certain niveau d’abstraction est nécessaire pour éviter que la taille du modèle ne porte préjudice aux performances de la simulation. Un modèle de simulation doit donc être choisi en fonction du domaine étudié, des objectifs poursuivis et du niveau d’abstraction requis, de manière à mettre en avant les éléments pertinents à l’étude. La simulation d’architectures matérielles demande un niveau d’abstraction bas, par conséquent son implantation en est complexe et peut prendre beaucoup de temps. De plus, dans un développement « à la main », des erreurs sont difficiles à éviter et rendent la distance vis-à-vis du système réel plus incertaine. On peut compter près d’une année à la conception d’un simulateur avec ce type de développement. En outre, le travail effectué pour une cible donnée est difficilement capitalisable. Si l’architecture évolue un peu, c’est tout le simulateur qu’il faut réécrire. Pour résoudre les problèmes de développement des simulateurs, des techniques existent pour automatiser cette tâche. On fait pour cela appel à des langages de description d’architecture matérielle, Hardware Architecture Description Language (HADL). On retrouve plus usuellement le terme de Architecture Description Language (ADL), mais il peut prêter à confusion avec les ADL logiciels. Les HADL sont nés de l’intérêt croissant pour les Application Specific Instruction set Processors (ASIP), les Digital Signal Processors (DSP), les System On Chips (SOC). La spécialisation de processeurs demandait de pouvoir manipuler dans un langage la description d’une architecture. Les HADL présentent de nombreux avantages. Ils permettent :
• de vérifier l’architecture, grâce au niveau d’abstraction qu’ils offrent,
• d’apporter des modifications rapides et évaluer les performances qu’elles entraînent,
• d’accélérer ainsi l’obtention d’un modèle de processeur.
On trouve de nombreux HADL dans la littérature. Ceux-ci peuvent avoir différents emplois et décrire différents niveaux d’une architecture. C’est pour cette raison que l’on utilise une double classification : selon l’objectif et selon le contenu [MD08]. On distingue généralement deux niveaux dans la description d’une architecture : la structure et le jeu d’instructions. Selon ce qui est décrit, il n’est pas possible de remplir les mêmes objectifs. On peut toutefois décrire les deux niveaux. HADL orientés structure : Il décrit la structure interne de l’architecture, pour décrire les connexions entre les différents composants et leur fonctionnement. (MIMOLA [BBH+94])
HADL orientés jeu d’instructions : Il décrit le jeu d’instructions, mais pas les composantes matérielles. On retrouve donc le codage des instructions et leur comportement. (nML [FVPF95] ou son extension SIM-nML [Raj96], ISDL [HHD97])
HADL mixtes : Il décrit à la fois le jeu d’instructions et la structure interne et permet ainsi de s’adapter à tous les objectifs : validation, synthèse, simulation, compilation. (LISA [PHZM99], EXPRESSION [HGa99], MADL [QRM04])
Un HADL peut trouver de multiples applications, dans la conception d’architectures ou la simulation, par exemple. Sa structure varie nécessairement selon la fonction qu’il veut porter, aussi faire une distinction des HADL suivant leur objectif a son importance.
HADL orientés validation : ils ont l’ambition de permettre aux concepteurs de générer des tests pour valider fonctionnellement les processeurs.
HADL orientés synthèse : ils représentent un outil flexible pour la conception d’architectures matérielles. Un de leurs avantages, à ce niveau-là, est d’offrir la possibilité de mettre en place des techniques de vérification sur les architectures proposées en analysant sa description.
HADL orientés compilation : ils permettent de générer automatiquement des compilateurs « reciblables ».
HADL orientés simulation : ils offrent la possibilité de construire des simulateurs d’architectures sur la base de leur description. Ce sera cette utilisation qui nous intéressera dans ce mémoire.
On peut noter que ces deux classifications ne sont pas indépendantes. Faire de la synthèse ou de la validation, nécessite de travailler sur la structure de l’architecture et donc de détenir des informations s’y rapportant dans le HADL. En revanche, un HADL ayant pour fin la compilation ou la simulation focalise son travail sur le fonctionnement des programmes et passe donc par la description du jeu d’instructions. Un HADL mixte est adapté à tous les objectifs, puisqu’il renferme toutes les informations requises pour chacun des objectifs. (Voir la Figure 1.3.) Comme c’est l’aspect de la simulation qui nous intéresse dans ce mémoire, il est utile de noter que, bien qu’un simulateur fonctionnel (ISS) ne nécessite qu’un HADL décrivant le jeu d’instructions, dans le cadre d’un simulateur temporel, il est nécessaire de posséder une description de la structure de l’architecture. En effet, le comportement temporel est fortement influencé par la structure de l’architecture (dont le pipeline, comme on le verra), et sa simulation passe par une modélisation de celle-ci. Un simulateur temporel ne peut donc être généré qu’à partir d’un HADL mixte.
Simulation compilée
De même que pour la simulation interprétée, le terme de simulation compilée provient du langage de la programmation. Pour certains langages de programmation, une compilation est nécessaire pour exécuter le programme (comme C++ ou ADA). Lors de cette phase, le compilateur traduit le code source pour produire le code binaire exécutable. Cependant, le terme ne se transpose pas tel quel dans la simulation. En effet, il y a dans celle-ci deux processus qu’il faut distinguer et que l’on peut compiler : la conception du simulateur et la simulation du programme. La conception d’un simulateur repose usuellement sur des langages de programmation compilés, réputés plus efficaces, et demande donc une compilation. Dans le cas d’un simulateur compilé, la simulation du programme passe également par une phase de compilation, mais celle-ci est intégrée à la compilation du simulateur. Ainsi, en une seule phase de compilation, le simulateur est conçu et certaines tâches de simulation du programme sont traitées. Avec ce type de chaîne de développement, il est à noter que le simulateur ainsi conçu est propre à un programme donné : celui avec lequel la compilation a été effectuée. Pour en simuler un nouveau, il faut une autre compilation pour concevoir un autre simulateur. C’est ce qui rend la chaîne de développement moins flexible. D’une façon générale, on peut décrire la compilation comme un procédé visant à traduire en amont le programme dans un langage intermédiaire, plus simple à exécuter. Dans le cas de la programmation, il s’agit de traduire en code machine. Dans le cas de la simulation, il s’agit d’une représentation du comportement des instructions, pour les exécuter plus simplement. C’est la raison pour laquelle elle se révèle une technique efficace de simulation. Comme elle déplace des tâches de la phase d’exécution à celle de compilation, la simulation compilée [MAF91] présente naturellement de meilleures performances durant l’exécution. Il faut toutefois faire remarquer que ces tâches ne disparaissent pas de la phase de développement complète, puisqu’elles se retrouvent durant la compilation. Pareille configuration peut s’avérer utile pour certains types de développement et moins pour d’autres. En effet, s’il est nécessaire de compiler le simulateur pour chaque exécution, comme c’est le cas quand l’on souhaite simuler des programmes différents, alors le gain peut se trouver nul, voire plus mauvais. Dans le cas d’une phase de tests contenant plusieurs scénarios par programme, on retrouve un cas de figure d’une compilation pour plusieurs exécutions, ce qui rentabilise le coût de la compilation. Ainsi, pour ce qui est d’un développement où chaque programme est testé avec un ensemble de scénarios de manière à mettre en évidence les différentes utilisations du programme et obtenir des résultats statistiques consistants, la simulation compilée représente un grand intérêt. Nous avons représenté le schéma de développement d’un simulateur compilé sur la Figure 2.2. On y voit la distinction entre les deux phases de compilation et d’exécution. La première coïncidant avec la compilation du simulateur. Les tâches qui sont traitées durant la compilation sont variables selon les simulateurs. On retrouve généralement trois tâches se retrouvant durant la phase de compilation :
• Le décodage des instructions : interpréter le code opérationnel des instructions pour en extraire les informations sur son comportement de telle manière à ce qu’elle soit directement utilisable par le simulateur.
• Le séquençage des instructions : organiser la gestion des ressources matérielles par les instructions, ce qui est notamment utile en cas d’exécution des instructions dans le désordre.
• L’instanciation des instructions : générer le code exécutable des différentes opérations qui forment le comportement des instructions.
En fonction du nombre de tâches qui sont traitées durant la compilation, on peut parler de simulateur compilé à un plus ou moindre niveau. Comme le présente la Figure 2.3, on retrouve habituellement les degrés suivant pour une simulation compilée. Lorsque le séquençage des instructions est effectué à la compilation, on qualifie le simulateur d’ordonnancement dynamique. Si, en outre, l’instanciation des instructions est opérée à la compilation, on parle d’ordonnancement statique. Si la simulation compilée présente une meilleure vitesse d’exécution, cela se fait au prix d’une perte de flexibilité. Comme nous l’avons dit, cette perte en flexibilité s’exprime d’abord par la spécificité du simulateur à un programme particulier. Du fait de cette propriété, on peut comprendre que la simulation de programmes auto-modifiants n’est pas envisageable. Cependant, ce genre de programmes ne se trouve pas dans le contexte de l’embarqué temps réel. Le fait de traiter des tâches de simulation durant la compilation impose une autre contrainte : hors de l’exécution, certaines informations ne peuvent pas être extraites. Par exemple, sans exécuter un programme, il n’est pas possible de calculer l’évolution du contenu de la mémoire. On parle d’analyse statique dans la compilation, que l’on oppose à l’aspect dynamique de l’exécution. Du fait de cette restriction, il n’est pas possible de simuler certains codes, comme les branchements indirects, par exemple (de façon générale, car nous verrons par la suite que certains branchements indirects sont traitables). On utilise le terme de branchement indirect lorsque la cible du branchement est calculée au cours de l’exécution. On l’oppose donc aux branchements directs, dont la cible est fixe (même si le branchement peut être conditionnel). Pour les branchements indirects, la cible se trouve dans un registre, pour les branchements directs, elle est codée dans l’instruction. Par conséquent, pour déterminer le flot de contrôle avec des branchements, il faut être en mesure de calculer le contenu d’un registre, ce qui ne peut se faire par une analyse statique, dans le cas général. Comme exemple d’utilisation, un tel simulateur a été conçu à l’aide du langage LISA [PHM00]. Le niveau de compilation de ce simulateur correspond à un ordonnanceur dynamique, i.e. le décodage et le séquençage des instructions sont effectués durant la compilation. La contribution du papier présente une vitesse de simulation allant de 37 à 170 fois plus grande que les simulateurs commerciaux. La simulation compilée est une technique propre à améliorer le temps de simulation de l’exécution des instructions. En ce sens, c’est une technique de simulation fonctionnelle : elle accélère le temps de calcul pour simuler le comportement des instructions. Dans la mesure où le fonctionnement d’un CAS peut reposer sur les services d’un ISS, typiquement pour calculer le flot de contrôle, on peut retrouver cette technique dans la simulation temporelle. Cependant, cela en fait une technique d’un moindre intérêt. En effet, elle ne permet alors de réduire que la part spécifiquement fonctionnelle du simulateur et pas le calcul des informations temporelles. Ainsi, du fait de la prédominance en temps de calcul de la manipulation du modèle du processeur pour obtenir les informations temporelles, si une partie des techniques utilisées par les ISS peuvent se retrouver dans les CAS, elles ne permettent généralement plus d’améliorer significativement le temps d’exécution.
Dynamic Binary Translation
La Dynamic Binary Translation (DBT), à la manière du JIT, traduit le code à la volée. Elle utilise également un cache pour rentabiliser cette opération. Elle couple de cette manière la simulation interprétée avec la SBT, comme le montre le schéma de la Figure 2.6. Comme nous l’avons vu, dans le cas d’une boucle, le code déjà exploré est simplement exécuté depuis le cache, sans besoin de traduction. Des techniques d’optimisation plus poussées sont possibles pour les sections du code fréquemment appelées. Dans ces cas, la DBT peut inclure dans le cache des informations supplémentaires, comme le contenu des registres ou le flot de contrôle, dans le but d’appliquer à ce niveau des optimisations plus brutales. Ainsi, la cohérence de ces informations est préservée dans les premières exécutions, et les ayant mémorisées elles peuvent ne plus être respectées pour améliorer la vitesse de simulation. Ce type d’optimisations n’est, par exemple, pas possible dans le cadre d’une SBT. Parmi les simulateurs utilisant cette technique, on peut citer SHADE [CK94] et le projet EMBRA [WR96]. La SBT traduit le programme suivant des blocs de code, semblables à des pas de simulation optimisés. Le simulateur SHADE enchaîne directement ces blocs sans passer par la boucle de simulation, du moment qu’aucun contrôle n’est nécessaire. Le simulateur vérifie l’appartenance des instructions à suivre dans les blocs présents dans le cache. S’il ne les trouve pas, il peut faire appel à des blocs fragmentés dans un cache spécifique ou construire lui-même un fragment de code à traduire. le simulateur EMBRA fonctionne sur les mêmes bases. Il est en outre capable de simuler les codes auto-modifiants. Lorsqu’une telle opération est détectée, il vide simplement la partie du cache correspondante. Plus les blocs peuvent être de taille importante et plus la vitesse de simulation augmente, en effet moins de contrôle est nécessaire. Des pistes d’optimisation de cette technique reposent sur l’amélioration de la taille des blocs traduits par la BT. Ces blocs définissent un pas dans la simulation Des techniques existent pour améliorer la taille des blocs traduits par la BT : Large Translation Unit DBT [JT09]. Par la flexibilité qui la distingue de la SBT, cette technique est utilisable par la simulation temporelle. En effet, puisqu’elle utilise en première approche les techniques de la simulation interprétée (qu’elle optimise ensuite lors d’un retour sur la section du code), on peut retrouver les informations nécessaires à la manipulation d’un modèle du processeur pour obtenir des résultats temporels. Elle constitue ainsi une bonne alternative à la simulation interprétée, et permet d’atteindre une vitesse d’exécution dix fois supérieure à celle-ci.
|
Table des matières
1 Introduction générale
1.1 Système temps réel
1.2 Validation des systèmes temps réel
1.2.1 Validation sur modèle
Analyse formelle
Analyse d’ordonnançabilité
Analyse par simulation
1.2.2 Validation sur cible
1.3 Simulation d’architectures matérielles
1.3.1 Architectures matérielles
1.3.2 Instruction Set Simulator et Cycle Accurate Simulator
Instruction Set Simulator
Cycle Accurate Simulator
1.3.3 Langage de description d’architecture
1.4 Motivation de la thèse et contributions
1.5 Organisation du mémoire
2 État de l’art
2.1 Simulation interprétée
2.2 Simulation compilée
2.3 Just In Time
2.4 Binary Translation
2.4.1 Static Binary Translation
2.4.2 Dynamic Binary Translation
2.5 Échantillonnage
2.6 Conclusion
3 HARMLESS
3.1 Le Langage de description d’architectures matérielles
3.2 Modèle du pipeline simple
3.2.1 États du modèle
3.2.2 Transitions du modèle
3.2.3 Formalisation
3.2.4 Estimation théorique de la taille du modèle
3.2.5 Construction du modèle
3.3 Le Simulateur
3.3.1 Exécution du simulateur
3.3.2 Analyse des performances du simulateur
4 Simulation compilée — 1er modèle
4.1 Objectifs
4.2 Modélisation
4.2.1 Chaîne de développement
4.2.2 Modèle
4.2.3 Gestion des branchements
4.2.4 Gestion des retours de fonction
4.3 Algorithme
4.3.1 Chaîne de développement
4.3.2 Analyse du code
4.3.3 Construction de l’automate
4.3.4 Génération du simulateur
4.4 Gestion des dépendances de données
4.5 Estimation théorique de la taille du modèle
4.5.1 Configuration linéaire
4.5.2 Début du programme
4.5.3 Configuration de branchement
4.5.4 Utilisation de la pile des appels
4.6 Résultats
4.6.1 Taille des automates
4.6.2 Temps d’exécution
4.7 Conclusion
5 Simulation compilée — 2e modèle
5.1 Objectifs
5.2 Modélisation
5.2.1 Automate à pile
5.2.2 Modèle
5.3 Algorithme
5.3.1 Manipulation de la pile
5.3.2 Factorisation de l’automate
5.3.3 Gestion de la structure de données
5.3.4 Structure de données
5.3.5 Algorithme
5.3.6 Exécution
5.4 Résultats
5.4.1 Taille des automates
5.5 Conclusion
6 Macro-instructions
6.1 Objectifs
6.2 Modélisation
6.3 Contrôle du cache d’instructions
6.3.1 Objectifs
6.3.2 Principes
6.3.3 Impact théorique sur la taille du modèle
6.3.4 Algorithme
6.4 Algorithme
6.4.1 Réduction de l’automate
6.4.2 Exécution
6.5 Résultats
6.5.1 Taille des automates
6.5.2 Temps d’exécution
6.6 Conclusion
7 Abstraction du code simulé
7.1 Objectifs
7.2 État de l’art
7.2.1 Bibliographie
7.2.2 Analyse
7.3 Modélisation
7.4 Algorithme
7.4.1 Calcul du slicing
Construction du flot de contrôle
Remontée des dépendances de données
7.4.2 Exécution
7.5 Conclusion
8 Conclusion
8.1 Résultats synthétiques
8.2 Perspectives
A Le Pipeline
A.1 Les Bases
A.2 Les Différents types d’aléas
A.2.1 Aléas de données
Télécharger le rapport complet
