Problème d’optimisation de ressources pour systèmes embarqués

Les contraintes des systèmes embarqués

Les systèmes embarqués ont pour caractéristique commune d’être contraints. Il s’agit aussi bien de contraintes sur le support d’exécution que de contraintes de Qualité de Service (QdS) . Selon la machine sur laquelle un programme embarqué est destiné à être exécuté, il peut
avoir à satisfaire différentes de ces contraintes :
L’encombrement : ils doivent souvent être transportés et doivent donc être de taille réduite ; L’utilisation mémoire : La miniaturisation du matériel entraîne dans certains cas une réduction des capacités mémoires de l’appareil. Le programme embarqué doit donc tenir compte de cette contrainte et, par exemple, ne pas dépasser certaines limites d’occupation mémoire statique et d’utilisation mémoire lors de son exécution.
Le temps de calcul : L’utilisation de programmes embarqués se fait souvent dans des contextes où le temps est un paramètre essentiel du système. Les délais d’exécution sont alors connus et bornés. De tels systèmes ont des propriétés temps réel dur ou mou.
La consommation d’énergie : Le caractère embarqué d’un système fait que ce dernier n’est pas toujours relié à une source infinie d’énergie. Le système doit alors gérer une certaine quantité d’énèrgie fournie par une batterie autonome (panneaux solaires, pile).
La sûreté/sécurité : Certaines pannes de systèmes embarqués peuvent avoir des conséquences désastreuses tant d’un point de vue humain (train d’atterrissage d’un avion, appareillage médical) que d’un point de vue économique (système d’exploitation d’un distributeur d’argent). De tels systèmes sont dits critiques [Ven08].
Forte contraintes : En raison de la nature des systèmes embarqués, la conception des indicateurs tels que la taille, la performance et la consommation imposent de fortes contraintes [all05]. Vu la diversité des domaines d’application et des contraintes à considérer, un système embarqué peut avoir à satisfaire toutes ou parties de ces contraintes bien qu’elles puissent être contradictoires. L’exemple type est le gain de temps d’exécution d’une boucle ordonnancée par pipeline logiciel. Cette optimisation augmente la taille du code généré et donc son occupation en mémoire. Si un programme devait être optimisé de manière à augmenter sa vitesse et diminuer sa taille, le pipeline logiciel demanderait de faire des compromis. La demande d’optimisation du programme à exécuter est très forte, voire primordiale.

Conception des systèmes embarqués

La conception des systèmes embarqués doit être capable d’implémenter une application avec une garantie des propriétés des systèmes critiques, mais elle doit également satisfaire la complexité et l’hétérogénéité de l’architecture. Dans la tendance actuelle de conception industrielle, le coût de la vérification par rapport au coût total de la conception est en augmentation. Les conceptions actuelles dépendent fortement sur les techniques de simulation (qui seront très important dans le futur), mais qui sont besoin de méthodes formelles de vérification.
Mais dans la pratique il est très difficile de capturer les fonctionnalités du système et vérifier les propriétés au niveau système à celle au niveau composant de l’architecture, la conception du système doit commencer dans un niveau d’abstraction plus élevé. Malheureusement, plus le niveau d’abstraction est élevé, plus que les détails de l’implémentation sont manqués, et qui seront nécessaire pour une implémentation efficace. Le processus de conception doit être capable d’ajouter les détails de l’implémentation. La conception système commence par le développement d’un modèle de spécification. Dans cette phase le concepteur formule le modèle selon les exigences données par la spécification, qui est généralement écrite dans le langage naturel, par exemple en français. Il est important que le modèle de spécification soit exprimé dans un langage formel. Un langage formel est un langage qui a une syntaxe et une sémantique formelle, et qui permettent aux outils et la manipulation formelle de détecter les inconsistances, ambiguïtés ou l’incomplétude dans le modèle de spécification.
Plus que le niveau d’abstraction est élevé dans l’étape de spécification, moins que les détails de l’implémentation sont inhérents dans le modèle d’implémentation et l’espace de conception est plus large. L’espace de conception est défini comme l’ensemble des implémentations possibles qui répond à un modèle de spécification donné .

Les types des systèmes embarqués

En général, Les fonctionnalités des systèmes temps réel embarqués combinent les aspects contrôle et les aspects traitement de données, ce type de système peut être classifié selon l’aspect qui dominent leurs fonctionnalités, ils peuvent être soit des systèmes orientés traitement de données ou des systèmes orientés contrôle. Les fonctionnalités de traitement de données consistent en un calcul massif sur des données, alors que le contrôle consiste à séquencer ces calculs en choisissant lequel effectuer parmi différentes alternatives. Il est important de noter que le contrôle n’implique pas la notion d’état [Per05]. En effet, les choix effectués par le contrôle peuvent l’être sans connaissance des calculs antérieurs. Le cas échéant, c’est l’obligation de mémoriser des résultats de calculs précédents qui introduisent la notion d’état. Mais on peut aussi classer les systèmes embarqués selon leurs usages en quatre types :
L’informatique générale (General Computing) : Application similaire à une application de bureau mais empaquetée dans un système embarqué exemple : jeu vidéo, set- top box.
Les systèmes de contrôle (Control Systems) : inclus les applications de contrôle du système temps réel. Exemple : Moteur d’automobile, processus chimique, processus nucléaire, système de navigation aérien.
Traitement du signal (Signal Processing) : qui se caractérise par le calcul sur des quantités importantes de données. Exemple : Radar, Sonar, compression vidéo.
Réseau et communication (Communication & Networking) : Ce type concerne les applications de transmission d’information et commutation. Exemple : Téléphone, Internet.

Propriétés des langages de spécification des systèmes embarqués

Parmi les caractéristiques les plus importantes que doit représenter un langage de spécification, on va citer quelques-uns :
La hiérarchie : Les êtres humains ne sont pas généralement capables de comprendre les systèmes, qui contiennent de nombreux objets (états, composants) ayant complexes relations les uns avec les autres. La hiérarchie est le seul mécanisme qui aide à résoudre ce dilemme. Temporisation : les exigences temporelles sont parmi les caractéristiques explicites des systèmes embarqués, ils doivent être définis dans le cahier des charges.
Le comportement orienté état : les automates peuvent fournir un mécanisme efficace pour la modélisation de systèmes réactifs. Par conséquent, le comportement des automates doit être facile à décrire. Toutefois, les modèles classiques d’automates sont insuffisants, car elles ne peuvent pas modéliser le temps ainsi que la hiérarchie n’est pas supportée.
La portabilité et la flexibilité : La spécification doit être indépendante de la plate-forme matérielle, afin qu’elles puissent être facilement utilisées pour une variété des plates-formes cibles. Elle doit être aussi flexible, de façon que la modification des caractéristiques du système, exige également des changements à la spécification.
Event-Handling : En raison de la nature réactive des systèmes embarqués, des mécanismes pour décrire des événements doivent exister. Ces événements sont des événements extérieurs (causée par l’environnement) ou internes (causée par des composants du système).
Propriétés non fonctionnelles : Les systèmes actuels exposent un certain nombre des aspects non fonctionnelles, telles que la tolérance aux pannes, la taille, l’extension, la durée de vie, la consommation d’énergie, le poids, la disponibilité, la convivialité, la compatibilité électromagnétique (EMC), etc. Il n’y a aucune spécification qui permet de satisfaire tous ces propriétés, et les définies de façon formelle.
Des modèles de calcul ( MOC1 ) : Dont le but est de décrire les calculs, des modèles de calcul sont nécessaires.

Choix d’un modèle de spécification

Le choix judicieux du modèle adopté pour la spécification d’un système est d’une importance primordiale, car il peut avoir une influence directe sur toutes les autres étapes de conception. Ce choix est souvent guidé par l’adéquation des propriétés et caractéristiques du modèle avec les spécificités du système à concevoir.
Dès lors, l’évaluation des différents modèles doit donc être établie en fonction des exigences des systèmes mixtes matériel/logiciel en termes de déterminisme et de sûreté de fonctionnement, de distribution et de parallélisme, ainsi que de la rapidité de la réaction (complexité et synchronisme ). Ces notions, qui constituent quelques-unes des préoccupations parmi les plus importantes des concepteurs d’applications temps réel, sont précisément des concepts fondamentaux qui forment le socle sémantique des modèles de spécification.
Comme on peut le constater certains modèles sont plus appropriés à la modélisation des systèmes qui doivent manipuler de grandes quantités de données, d’autres modèles sont plus appropriés pour les systèmes comportant une forte dominante de contrôle. Ces modèles représentent donc plus exactement soit les données, soit le contrôle mais prennent rarement en compte les deux aspects : les graphes flots de données (DFG), par exemple, sont bien adaptés à décrire les dépendances de données dans un système de traitement du signal, mais ne sont pas aussi si bien adaptés pour la modélisation de la logique de contrôle associée et la gestion des ressources. Les automates à états finis (FSM) sont très bien adaptés pour la modélisation d’une logique de contrôle plus au moins simple, mais sont moins bien adaptés à modéliser les dépendances de données et le calcul numérique. Les processus communicants (CSP) sont adaptés pour la gestion de ressource, mais ils sur spécifient les dépendances de données. Ceci dit, il est rare qu’un système réel ait un traitement exclusivement orienté données ou exclusivement orienté contrôle, ce qui explique la continuité des travaux de recherche visant à proposer de nouvelles solutions pour une spécification complète des systèmes.
On constate aussi que parmi les principaux modèles de spécification cités, nombreux sont ceux qui ne prennent pas en compte la hiérarchie (FSM, PN,…). Cette insuffisance les rend inadéquats, dès que la taille et la complexité des systèmes à modéliser augmentent. Quelques modèles ne permettent pas de prendre en compte la concurrence (FSM, …) et introduisent de ce fait des contraintes qui empêchent le système spécifié de profiter pleinement des ressources disponibles dans l’architecture cible (les processeurs logiciels et les circuits matériels) qui doiventfonctionner en parallèle.
Signalons aussi que la majorité des modèles sont basés sur une sémantique mathématique forte, offrant ainsi des possibilités de vérification formelle et d’optimisations poussées, d’ailleurs c’est une propriété fortement exigée pour un modèle de spécification. On note également une prédominance de modèles asynchrones dans le sens où les transitions ne sont pas pilotées par un signal d’horloge.

Table des matières

Chapitre I : Les Systèmes Embarqués
1. Introduction
2. Caractéristique des systèmes embarqués
3. Les contraintes des systèmes embarqués
4. Conception des systèmes embarqués
5. Les types des systèmes embarqués
6. Conclusion
Chapitre II : Modélisation des systèmes embarqués
1. Introduction
2. Propriétés des langages de spécification des systèmes embarqués
3. Modèles orientés contrôle
3.1. Les réseaux de Petri
3.2. Les machines à états finis
3.3. Modèles réactifs synchrones
3.4. Graphe de tâches
4. Modèles orientés traitement
4.1. Modèles à base de langages impératifs
4.1.1. Langage C
4.1.2. Java
4.2. Processus communicants concurrents / séquentiels
4.3. Modèles à base de graphes de flots
4.3.1 Graphe de flot de données
4.3.2 Graphes de flots mixtes de données et de contrôles
4.3.3 Flots de données synchrones (SDF)
4.4. Modèles hybrides
4.5. Les StateCharts et les CFSM
4.6. Le modèle SDL
4.7. Le modèle PSM
4.8. Modèles au niveau transactionnel
4.8.1. SystemC
4.8.2. Verilog et SystemVerilog
4.9. Modèles orientés objet
5. Divers autres modèles
6. Choix d’un modèle de spécification
7. Motivation du choix d’un modèle flot de données
Chapitre III : Outils de spécification
1. Introduction
2. Gedae
2.1. Algorithme
2.2. Architecture
2.3. Génération de code
2.4. Conclusion
3. PtolemyII
3.1. Algorithme
3.2. Architecture
3.3. Adéquation
3.4. Génération d’exécutif
3.5. Conclusion
4. ForSyDe
4.1. Algorithme
4.2. Architecture
4.3. Génération de code
4.4. Conclusion
5. GrapeII
5.1. Algorithme
5.2. Architecture
5.3. Génération de code
5.4. Conclusion
6. SynDEx
6.1. Présentation
6.2 Méthodologie AAA
6.3. Modèle d’algorithme
6.4. Modèle d’architecture
6.5. Adéquation : Optimisation de l’implantation
6.6. Génération de code
6.7. Conclusion
Chapitre IV : La resynchronisation
1. Les flots de données et la resynchronisation
2. La resynchronisation
3. La minimisation du temps de cycle
3.1. Définition Formelle
3.2. Algorithme de resynchronisation
4. Définition et propriétés
4.1. Filtre FIR
4.2. Une description quantitative de la resynchronisation
4.3. Les propriétés de la resynchronisation
5. Aspect formel de la resynchronisation
6. Exemples de la resynchronisation
7. Conclusion
Chapitre V : Implémentation
1. Introduction
2. Présentation de l’environnement logiciel SynDEx
3. Récapitulatif de notre proposition
4. Exemples d’applications
4.1. Filtre FIR.
4.2. Présentation de l’application Audio Filtre
4.3. Exemple de boucle.
5. Conclusion
Conclusions et perspectives
Références
Annexe A : Les étapes de spécification sous SynDEx
Annexe B : Algorithme de resynchronisation en Ocaml