Aujourd'hui, les systèmes embarqués sont de plus en plus utilisés pour contrôler les systèmes complexes. Dans ce travail de thèse, nous nous intéressons aux systèmes embarqués critiques utilisés pour la commande de systèmes de transport comme les systèmes ferroviaires. Le but de ce travail est de permettre la conception de systèmes tolérants aux fautes pour le contrôle-commande des systèmes de transport. Nous proposons une nouvelle approche de modélisation des systèmes embarqués temporisés pour le diagnostic de leurs fautes. Elle est basée sur une décomposition structurelle du système et sur une extension de la diagnosticabilité modulaire au contexte des systèmes temporisés. On distingue deux approches de base pour le diagnostic de fautes des SED, une approche basée sur les diagnostiqueurs et une approche basée sur les signatures temporelles causales (STC). La principale limite de l’approche diagnostiqueur réside dans la gestion de l’explosion combinatoire. Dans ce travail, notre verrou principal est de combattre cette limite. Nous proposons une nouvelle méthode basée sur l’ingénierie par les modèles pour le diagnostic des systèmes embarqués critiques. D’autre part, la limite majeure de l’approche STC est la garantie de la cohérence d’une base de STC. Un deuxième niveau de difficulté réside dans l’interprétation des événements en entrée du système de diagnostic dans le cadre de l’hypothèse de défaillances multiples. Dans ce travail, nous proposons deux méthodes différentes pour la vérification de la cohérence d’une base de STC et nous proposons un algorithme d’interprétation basé sur le concept de monde qui garantit la correction du diagnostic / Today, embedded systems are increasingly used to control complex systems. In this thesis, we are interested in critical embedded systems used for the control of transport systems such as railway systems. The aim of this work is to enable the design of fault-tolerant systems for the control of transport systems. We propose a new timed embedded systems modeling approach to diagnose their faults. It is based on decomposition of the system and structural extension of diagnosability context of modular timed systems. In DES, there are two basic approaches for diagnosis: diagnoser based approach and chronicles (Causal Temporal Signature (CTS)) based approach. The major limitation of diagnoser approaches rely in the management of the combinatorial explosion related to the formalism of automata. In this work, our main lock is to combat this limit. We propose new engineering models based method for the diagnosis of critical embedded systems. On the other hand, the major limitation of chronicles approach is first to be able to guaranty the consistency of a database. A second level of difficulty is in interpreting some sequences of events at the input of the diagnostic system under the hypothesis of multiple failures. In this work, we propose two different methods to verify the consistency of a set of CTS and we propose an interpretation algorithm based on a concept of worlds which guarantees the correct diagnosis

Bien que de nombreux appareils numériques soient aujourd'hui capables de lire des contenus vidéo en temps réel et d'offrir une restitution de grande qualité, le décodage vidéo dans les systèmes embarqués n'en est pas pour autant devenu une opération anodine. En effet, les codecs récents tels que H.264 et HEVC sont d'une complexité telle que le recours à des architectures mixtes logiciel/matériel est presque incontournable. Or les plateformes de ce type sont notoirement difficiles à programmer efficacement. Cette thèse relève le défi du développement d'applications à flux de données pour les cibles embarquées hybrides et de leur exécution efficace, et propose plusieurs contributions. La première est une extension des heuristiques d'ordonnancement de liste pour tenir compte des contraintes mémorielles. La seconde est un modèle d'exécution à flot de données compatible avec la plupart des modèles existants et avec une large classe de plateformes matérielles, ainsi qu'un ordonnanceur dynamique. Enfin, de nombreux développements ont été menés sur une architecture réelle de STMicroelectronics pour démontrer la faisabilité de l'approche. / Although numerous electronic devices are nowadays able to play video contents in real time and offer high-quality reproduction, video decoding in embedded systems has not become a trivial process yet. As a mater of fact, recent codecs such as H.264 and HEVC exhibit such a complexity that resorting to mixed sofware-hardware architecture is almost unavoidable. However, programming efficiently this kind of platforms is well-known to be tricky. This thesis addresses the issue of developing streaming applications for hybrid embedded targets and executing them efficiently, and proposes several contributions. The first one is an extension of the classical list-scheduling heuristics to take memory constraints into account. Te second one is a datafow execution model compatible with most existing models and with a large set of hardware platforms, as well as a dynamic scheduler. Lastly, numerous developments have been carried out on a real-world architecture from STMicroelectronics so as to demonstrate the feasibility of the approach.

Il est important que les logiciels pilotant les systèmes critiques (avions, centrales nucléaires, etc.) fonctionnent correctement — alors que la plupart des systèmes informatisés de la vie courante (micro-ordinateur, distributeur de billets, téléphone portable) ont des dysfonctionnements visibles. Il ne s'agit pas là d'un simple problème d'ingéniérie : on sait depuis les travaux de Turing et de Cook que la preuve de propriétés de bon fonctionnement sur les programmes est un problème intrinsèquement difficile.<br /><br />Pour résoudre ce problème , il faut des méthodes à la fois efficaces (coûts en temps et en mémoire modérés), sûres (qui trouvent tous les problèmes possibles) et précises (qui fournissent peu d'avertissements pour des problèmes inexistants). La recherche de ce compromis nécessite des recherches faisant appel à des domaines aussi divers que la logique formelle, l'analyse numérique ou l'algorithmique « classique ».<br /><br />De 2002 à 2007 j'ai participé au développement de l'outil d'analyse statique Astrée. Ceci m'a suggéré quelques développements annexes, à la fois théoriques et pratiques (utilisation de techniques de preuve formelle, analyse de filtres numériques...). Plus récemment, je me suis intéressé à l'analyse modulaire de propriétés numériques et aux applications en analyse de programme de techniques de résolution sous contrainte (programmation semidéfinie, techniques SAT et SAT modulo théorie).

Les systèmes embarqués sont des dispositifs électroniques et informatiques autonomes, dédiés à une tâche bien précise. Leur utilisation s'est désormais démocratisée à de nombreux domaines d'applications et en particulier au multimédia. Ce type d'application est caractérisé par un besoin important en puissance de calcul et en échange de données. Les architectures matérielles au cœur de ces systèmes sont généralement dotées d'accélérateurs chargés de l'exécution des noyaux de calcul intensif. Les architectures reconfigurables à gros grain (CGRA) sont particulièrement adaptées à l'accélération d'applications multimédia car elles répondent au mieux aux contraintes de performance, d'efficacité énergétique, de flexibilité et de coût de conception. En effet, ce type d'architecture est un compromis entre les processeurs à usage général, les architectures dédiées et celles reconfigurables à grain fin. Cette thèse traite de certains aspects liés aux problématiques de conception et de compilation d'applications pour CGRA. Nos travaux s'inscrivent dans une démarche d'adéquation applications multimédia / CGRA / conception et compilation basées sur la programmation par contraintes (CP). Notre méthodologie nous a permis, grâce à la CP, de modéliser et de résoudre un ensemble de problèmes combinatoires complexes. Le premier modèle présenté a trait à la fusion d'unités fonctionnelles reconfigurables sous contraintes architecturales et technologiques. Les deux autres modèles abordent les problèmes de : placement, ordonnancement et routage des données pour le déploiement d'une application sur CGRA. Notre approche permet, dans la majorité des cas, de prouver l'optimalité de la solution obtenue.

Les applications temps réel modernes deviennent plus exigeantes en termes de ressources et de débit amenant la conception d'architectures multiprocesseurs. Ces systèmes, des équipements embarqués au calculateur haute performance, sont, pour des raisons d'autonomie et de fiabilité, confrontés des problèmes cruciaux de consommation d'énergie. Pour ces raisons, cette thèse propose de nouvelles techniques d'optimisation de la consommation d'énergie dans l'ordonnancement de systèmes multiprocesseur. La premiére contribution est un algorithme d'ordonnancement hiérarchique á deux niveaux qui autorise la migration restreinte des tâches. Cet algorithme vise á réduire la sous-optimalité de l'algorithme global EDF. La deuxiéme contribution de cette thèse est une technique de gestion dynamique de la consommation nommée Assertive Dynamic Power Management (AsDPM). Cette technique, qui régit le contrôle d'admission des tâches, vise á exploiter de manière optimale les modes repos des processeurs dans le but de réduire le nombre de processeurs actifs. La troisiéme contribution propose une nouvelle technique, nommée Deterministic Stretch-to-Fit (DSF), permettant d'exploiter le DVFS des processeurs. Les gains énergétiques observés s'approchent des solutions déjà existantes tout en offrant une complexité plus réduite. Ces techniques ont une efficacité variable selon les applications, amenant á définir une approche plus générique de gestion de la consommation appelée Hybrid Power Management (HyPowMan). Cette approche sélectionne, en cours d'exécution, la technique qui répond le mieux aux exigences énergie/performance.

Les applications modernes embarquées à hautes performances telles que l'on trouve dans les domaines du multimédia, du traitement de signaux biomédicaux et du traitement de données biométriques, sont de plus en plus complexes et exigeantes en termes de ressources. L'augmentation des performances de puces, contenant un seul processeur, n'est plus une solution adoptée. Par conséquent, une solution prometteuse est les systèmes-sur-puce multiprocesseurs (MPSoC). Cependant, la conception de MPSoC dédiés aux traitements d'applications hautes performances est un travail très difficile en raison d'un certain nombre de contraintes à assurer : la correction fonctionnelle, les performances temporelles, l'efficacité énergétique et la taille optimisée de mémoire. Parmi les ingrédients nécessaires pour une construction correcte et optimisée, nous citons premièrement le besoin de modèles de programmation assez expressifs pour décrire le parallélisme potentiel inhérent des applications cibles. Deuxièmement, nous devons trouver des moyens pour éviter des explorations fastidieuses afin de trouver la meilleure configuration d'architecture pour l'exécution d'une application (par exemple le type et la fréquence des processeurs, l'empreinte mémoire), en particulier pour des applications complexes manipulant de grandes quantités de données et exécutées par des architectures massivement parallèles. Troisièmement, plusieurs niveaux d'abstraction doivent être pris en compte afin de mieux traiter la complexité de la conception. En considérant un niveau de simulation unique où tous les détails d'implémentations sont considérés, les résultats obtenus auront une grande précision. Cependant, cette technique de simulation est longue et fastidieuse, voir parfois impossible en raison de la grande complexité de systèmes. Pour cette raison, le commencement du processus de conception, à un haut niveau d'abstraction, où seulement des informations essentielles de systèmes sont décrites, rend plus facile, et à un très faible coût, la prise de décision sur des choix de configuration. Afin de relever les défis mentionnés ci-dessus concernant la conception des applications MPSoC à haute performance, nous proposons dans le cadre de cette thèse, l'utilisation du profil UML/Marte pour la modélisation de fonctionnalité, d'architectures et d'associations des deux dernières. Ce profil est suffisamment expressif pour décrire des applications hautes performances (par exemple les paquetages RSM et GCM et le langage CCSL) et des architectures MPSoC massivement parallèles (par exemple le paquetage HRM). Pour l'analyse et la vérification de systèmes et l'exploration de l'espace de conception, nous définissons une abstraction de modèles obtenue via des horloges abstraites, inspirées de ceux des langages réactifs synchrones. Les traces d'horloges abstraites capturent les comportements de systèmes en représentant l'activité des unités de traitements durant l'exécution de fonctionnalités. Une technique d'analyse, également inspirée de l'approche synchrone, est définie. Cette technique permet de vérifier des contraintes temporelles : dépendances de données induites par un modèle Marte, les taux d'activations entre des composants. En outre, elle permet d'analyser des contraintes non fonctionnelles : estimation de temps d'exécution, le respect des temps d'échéance, estimation de la consommation d'énergie. Ces propriétés sont directement liées au nombre de processeurs impliqués dans l'exécution du système ainsi que la valeur de leurs fréquences associées. D'un point de vue général, la contribution principale de cette thèse est la définition d'un cadre de travail, à base d'horloges abstraites, qui facilite l'exploration de l'espace de conception des MPSoC à un haut niveau d'abstraction. Le travail a été concrétisé dans un environnement, dénommé Gaspard2, dédié à la conception conjointe de systèmes embarqués à hautes performances. Notre solution est validée sur une étude de cas d'un encodeur JPEG, et retournant des résultats prometteurs.

Les applications modernes embarquées à hautes performances telles que l'on trouve dans les domaines du multimédia, du traitement de signaux biomédicaux et du traitement de données biométriques, sont de plus en plus complexes et exigeantes en termes de ressources. L'augmentation des performances de puces, contenant un seul processeur, n'est plus une solution adoptée. Par conséquent, une solution prometteuse est les systèmes-sur-puce multiprocesseurs (MPSoC). Cependant, la conception de MPSoC dédiés aux traitements d'applications hautes performances est un travail très difficile en raison d'un certain nombre de contraintes à assurer : la correction fonctionnelle, les performances temporelles, l'efficacité énergétique et la taille optimisée de mémoire. Parmi les ingrédients nécessaires pour une construction correcte et optimisée, nous citons premièrement le besoin de modèles de programmation assez expressifs pour décrire le parallélisme potentiel inhérent des applications cibles. Deuxièmement, nous devons trouver des moyens pour éviter des explorations fastidieuses afin de trouver la meilleure configuration d'architecture pour l'exécution d'une application (par exemple le type et la fréquence des processeurs, l'empreinte mémoire), en particulier pour des applications complexes manipulant de grandes quantités de données et exécutées par des architectures massivement parallèles. Troisièmement, plusieurs niveaux d'abstraction doivent être pris en compte afin de mieux traiter la complexité de la conception. En considérant un niveau de simulation unique où tous les détails d'implémentations sont considérés, les résultats obtenus auront une grande précision. Cependant, cette technique de simulation est longue et fastidieuse, voir parfois impossible en raison de la grande complexité de systèmes. Pour cette raison, le commencement du processus de conception, à un haut niveau d'abstraction, où seulement des informations essentielles de systèmes sont décrites, rend plus facile, et à un très faible coût, la prise de décision sur des choix de configuration. Afin de relever les défis mentionnés ci-dessus concernant la conception des applications MPSoC à haute performance, nous proposons dans le cadre de cette thèse, l'utilisation du profil UML/Marte pour la modélisation de fonctionnalité, d'architectures et d'associations des deux dernières. Ce profil est suffisamment expressif pour décrire des applications hautes performances (par exemple les paquetages RSM et GCM et le langage CCSL) et des architectures MPSoC massivement parallèles (par exemple le paquetage HRM). Pour l'analyse et la vérification de systèmes et l'exploration de l'espace de conception, nous définissons une abstraction de modèles obtenue via des horloges abstraites, inspirées de ceux des langages réactifs synchrones. Les traces d'horloges abstraites capturent les comportements de systèmes en représentant l'activité des unités de traitements durant l'exécution de fonctionnalités. Une technique d'analyse, également inspirée de l'approche synchrone, est définie. Cette technique permet de vérifier des contraintes temporelles : dépendances de données induites par un modèle Marte, les taux d'activations entre des composants. En outre, elle permet d'analyser des contraintes non fonctionnelles : estimation de temps d'exécution, le respect des temps d'échéance, estimation de la consommation d'énergie. Ces propriétés sont directement liées au nombre de processeurs impliqués dans l'exécution du système ainsi que la valeur de leurs fréquences associées. D'un point de vue général, la contribution principale de cette thèse est la définition d'un cadre de travail, à base d'horloges abstraites, qui facilite l'exploration de l'espace de conception des MPSoC à un haut niveau d'abstraction. Le travail a été concrétisé dans un environnement, dénommé Gaspard2, dédié à la conception conjointe de systèmes embarqués à hautes performances. Notre solution est validée sur une étude de cas d'un encodeur JPEG, et retournant des résultats prometteurs.

Dans cette thèse, on explique la conception et la mise au point d'un système de navigation sans GPS pour un véhicule automobile. Ce système exploite des mesures de champs magnétiques réalisées à bord du véhicule en mouvement, combinées à des mesures inertielles réalisées à partir de capteurs MEMS bas coût. Il permet de reconstituer, à partir d'une condition initiale, la trajectoire du véhicule en temps réel. Un prototype fonctionnel complet est présenté ainsi que des résultats expérimentaux. La conception de ce système repose sur une analyse de l'observabilité d'un modèle classique du véhicule, qui permet d'établir comment les différents biais et défauts des capteurs peuvent être estimés grâce à des filtres de Kalman agencés suivant deux schémas d'interconnexion: par partition des variables d'états et par séquencement. Une analyse de convergence des schémas d'estimation est étudiée. En dernière partie du manuscrit, deux autres exemples de systèmes de navigation à base de capteurs MEMS sont décrits, celui du quadricoptère Parrot AR.Drone et celui de fusées expérimentales à propulsion hybride, pour lesquels les mêmes principes de conception sont appliqués.

Les impressionnantes avancées techniques et technologiques dans les deux domaines des semiconducteurs et de l'ingénieurie logicielle ont permis aux Système sur puces (System-on-Chip "SoC") d'intégrer des applications complexes et interdépendantes. Ces progrès vont de pair avec la complexité accrue des systèmes et de leur hétérogénéité. Ainsi, les concepteurs ont été forcé à réévaluer leurs méthodes de conception et d'élever le niveau d'abstraction au niveau système en ciblant la conception de l'ensemble du SoC plutôt que des composants individuels. L'objectif de ce travail de thèse est de fournir aux concepteurs systèmes les moyens nécessaires (au niveau méthodologique et au niveau outils) pour estimer les performances du système et évaluer rapidement les décisions de conception, idéalement trés tôt dans le flot de conception. Notre contribution portera sur deux aspects principaux: (1) L'aspect conceptuel: où nous avons défini (en utilisant les concepts de métamodélisation UML) des concepts de modélisation permettant d'étudier l'effet de la gestion et du partage des ressources sur les performances globales du système (les "noeuds virtuels") . En outre, nous avons introduit le concept de "Patron de communication" pour la modélisation de l'interaction entre les éléments d'architecture afin d'assurer l'orthogonalisation des concepts de l'exécution et de la communication. (2)L'aspect simulation: Un simulateur en SystemC a été développé pour simuler les modèles UML proposés. La simulation est faite à haut niveau d'abstraction et elle est plus rapide que l'exécution en temps réel. L'approche proposée a été appliquée pour la modélisation de la couche physique du protocole de télécommunications mobile de 4ème génération (LTE, Long Term Evolution) sur un DSP muli-core produit par Freescale. Les résultats ont été validés en les comparant avec l'implémentation réelle. Thèmes clés: Modélisation et conception au niveau système, UML pour les systèmes embarqués, la gestion et le partage des ressources, la modélisation de la communication, l'estimation des performances, les systèmes de télécommunication

Les applications de gestion de flux sont responsables de la majorité des calculs des systèmes embarqués (vidéo conférence, vision par ordinateur). Leurs exigences de haute performance rendent leur mise en œuvre parallèle nécessaire. Par conséquent, il est de plus en plus courant que les systèmes embarqués modernes incluent des processeurs multi-cœurs qui permettent un parallélisme massif. La mise en œuvre des applications de gestion de flux sur des multi-cœurs est difficile à cause de leur complexité, qui tend à augmenter, et de leurs exigences strictes à la fois qualitatives (robustesse, fiabilité) et quantitatives (débit, consommation d'énergie). Ceci est observé dans l'évolution de codecs vidéo qui ne cessent d'augmenter en complexité, tandis que leurs exigences de performance demeurent les mêmes. Les modèles de calcul (MdC) flot de données ont été développés pour faciliter la conception de ces applications qui sont typiquement composées de filtres qui échangent des flux de données via des liens de communication. Ces modèles fournissent une représentation intuitive des applications de gestion de flux, tout en exposant le parallélisme de tâches de l'application. En outre, ils fournissent des analyses statiques pour la vivacité et l'exécution en mémoire bornée. Cependant, les applications de gestion de flux modernes comportent des filtres qui échangent des quantités de données variables, et des liens de communication qui peuvent être activés / désactivés. Dans cette thèse, nous présentons un nouveau MdC flot de données, le Boolean Parametric Data Flow (BPDF), qui permet le paramétrage de la quantité de données échangées entre les filtres en utilisant des paramètres entiers et l'activation et la désactivation de liens de communication en utilisant des paramètres booléens. De cette manière, BPDF est capable de exprimer des applications plus complexes, comme les décodeurs vidéo modernes. Malgré l'augmentation de l'expressivité, les applications BPDF restent statiquement analysables pour la vivacité et l'exécution en mémoire bornée. Cependant, l'expressivité accrue complique grandement la mise en œuvre. Les paramètres entiers entraînent des dépendances de données de type paramétrique et les paramètres booléens peuvent désactiver des liens de communication et ainsi éliminer des dépendances de données. Pour cette raison, nous proposons un cadre d'ordonnancement qui produit des ordonnancements de type ``aussi tôt que possible'' (ASAP) pour un placement statique donné. Il utilise des contraintes d'ordonnancement, soit issues de l'application (dépendance de données) ou de l'utilisateur (optimisations d'ordonnancement). Les contraintes sont analysées pour la vivacité et, si possible, simplifiées. De cette façon, notre cadre permet une grande variété de politiques d'ordonnancement, tout en garantissant la vivacité de l'application. Enfin, le calcul du débit d'une application est important tant avant que pendant l'exécution. Il permet de vérifier que l'application satisfait ses exigences de performance et il permet de prendre des décisions d'ordonnancement à l'exécution qui peuvent améliorer la performance ou la consommation d'énergie. Nous traitons ce problème en trouvant des expressions paramétriques pour le débit maximum d'un sous-ensemble de BPDF. Enfin, nous proposons un algorithme qui calcule une taille des buffers suffisante pour que l'application BPDF ait un débit maximum. / Streaming applications are responsible for the majority of the computation load in many embedded systems (video conferencing, computer vision etc). Their high performance requirements make parallel implementations a necessity. Hence, more and more modern embedded systems include many-core processors that allow massive parallelism. Parallel implementation of streaming applications on many-core platforms is challenging because of their complexity, which tends to increase, and their strict requirements both qualitative (e.g., robustness, reliability) and quantitative (e.g., throughput, power consumption). This is observed in the evolution of video codecs that keep increasing in complexity, while their performance requirements remain the same or even increase. Data flow models of computation (MoCs) have been developed to facilitate the design process of such applications, which are typically composed of filters exchanging streams of data via communication links. Data flow MoCs provide an intuitive representation of streaming applications, while exposing the available parallelism of the application. Moreover, they provide static analyses for liveness and boundedness. However, modern streaming applications feature filters that exchange variable amounts of data, and communication links that are not always active. In this thesis, we present a new data flow MoC, the Boolean Parametric Data Flow (BPDF), that allows parametrization of the amount of data exchanged between the filters using integer parameters and the enabling and disabling of communication links using boolean parameters. In this way, BPDF is able to capture more complex streaming applications, like video decoders. Despite the increase in expressiveness, BPDF applications remain statically analyzable for liveness and boundedness. However, increased expressiveness greatly complicates implementation. Integer parameters result in parametric data dependencies and the boolean parameters disable communication links, effectively removing data dependencies. We propose a scheduling framework that facilitates the scheduling of BPDF applications. Our scheduling framework produces as soon as possible schedules for a given static mapping. It takes us input scheduling constraints that derive either from the application (data dependencies) or from the user (schedule optimizations). The constraints are analyzed for liveness and, if possible, simplified. In this way, our framework provides flexibility, while guaranteeing the liveness of the application. Finally, calculation of the throughput of an application is important both at compile-time and at run-time. It allows to verify at compile-time that the application meets its performance requirements and it allows to take scheduling decisions at run-time that can improve performance or power consumption. We approach this problem by finding parametric throughput expressions for the maximum throughput of a subset of BPDF graphs. Finally, we provide an algorithm that calculates sufficient buffer sizes for the BPDF graph to operate at maximum throughput.