Добірка наукової літератури з теми "Systèmes embarqués (informatique) – Esterel (langage de programmation)"

Esterel est un langage de spécification utilisé dans le développement de systèmes embarqués. Sa sémantique formelle permet des traductions en automates explicites ou en circuits digitaux synchrones, donnant lieu à deux implantations logicielles dont les propriétés essentielles sont héritées du modèle correspondant. Ces méthodes de compilation sont donc sémantiquement complètes, mais en contrepartie n’arrivent pas à générer du code efficace (à la fois compact et rapide) pour des modèles de taille conséquente. Pour cette raison, de nouvelles techniques ont été proposées récemment pour la génération de code C efficace, consistant essentiellement dans la simulation directe des opérations réactives du programme Esterel. Ces nouvelles techniques doivent être conciliées maintenant avec les aspects spécifiques à la sémantique d’Esterel qui sont la causalité constructive et la cyclicité. Elles doivent aussi être munies de techniques adaptées d’analyse et d’optimisation. Pour atteindre ces objectifs, nous proposons une nouvelle technique de compilation dont la puissance découle de l’utilisation d’un nouveau format intermédiaire, nommé GRC. La représentation GRC d’un programme Esterel se compose d’une représentation de l’état hiérarchique du programme et d’un graphe déstructuré de flot de contrôle. Les deux composants, séparés au niveau syntaxique, sont sémantiquement interdépendants. Le nouveau format permet la représentation de tout programme Esterel. Il est un bon support pour des algorithmes d’optimisation efficaces à ce niveau et pour des algorithmes d’implantation (ordonnancement et encodage) efficaces. Notre travail apporte les contributions suivantes : - une définition précise de la sémantique du langage Esterel avec données ; - la définition du format GRC et de la correspondance formelle entre le code GRC et les circuits générés à partir d’Esterel ; - la caractérisation, au niveau du code GRC, de la classe de programmes Esterel générant des circuits cycliques ; - le développement d’un compilateur Esterel-C qui utilise GRC comme unique format intermédiaire. Le prototype traite actuellement les programmes Esterel dont la représentation GRC est acyclique. Le code C est obtenu dans ces cas par une planification statique du graphe de flot de contrôle GRC. Le compilateur implémente un bon nombre de techniques d’optimisation, en partie originales. Une comparaison entre notre prototype et les autres compilateurs montre l’intérêt de l’approche
Esterel is a design language for reactive embedded systems. It enjoys a full-fledged formal operational semantics, and can customarily be compiled into either explicit Finite State Machines or Digital Sequential Circuit models, thereby providing implementation codes with very distinctive flavors. While being semantically complete, the model-based techniques do not support the generation of efficient (fast and small) code for large specifications. For this reason, new compilation schemes were proposed for the generation of efficient sequential ( C) code. Consisting essentially in direct actual simulation of the language reactive features, the new approach now needs to be accommodated with similar semantic issues as the previous ones (FSM- and circuit-based). Such issues include dealing with the whole class of constructively causal programs, or performing optimization and analysis of this level. To this end, we propose here a new format/model (named GRC) for the intermediate representation of Esterel programs. The new format has formal constructive semantics, being able to represent all the Esterel programs. It describes with separate (but interdependent) structures the hierarchic state of the Esterel program and its destructured control flow. Thus, it is a good support for both (1) efficient low-cost optimizations based on static analysis that use high-level structural information and (2) low-level control flow optimizations. Finally, the format is a good starting point for efficient scheduling algorithms. Our contribution consists in the following : - The precise definition of the semantics of the full Esterel language ; - The definition of the GRC format (including the formal correspondence between its semantics and the “circuit” semantics) ; - A characterization, at GRC level, of the programs that are translated into cyclic circuits ; - The development of an optimizing GRC-based prototype C code generator. The prototype is currently able to compile the programs whose GRC representation is acyclic. Sequential code is generated in these cases by statically scheduling the acyclic GRC flowgraph. The compiler includes novel optimization algorithms, based on static analysis, and an efficient state encoding technique. The results are encouraging, as our prototype seems to compare well against existing compilers

Ce travail de these vise essentiellement a fournir des methodes et outils pour la conception de systemes temps-reel. Du fait de la forte composante reactive de ces systemes, nous preconisons une approche synchrone. Le domaine du temps-reel etant particulierement vaste, nous nous interessons plus particulierement aux applications de controle ce qui nous a conduit a utiliser le langage esterel. Nous abordons les differentes phases de la modelisation, conception, programmation et realisation en apportant pour chacune d'elles une solution synchrone. Les transitions entre ces phases sont systematiques et sans rupture. Nous proposons de modeliser ces systemes par des boites hierarchiques reactives synchrones (bhrs). Le but d'une bhrs est de fournir une assistance a des non-specialistes des langages, pour la conception synchrone de leurs applications. Ce modele permet une decomposition par niveaux et une description modulaire des systemes. Ce modele est dote d'une semantique comportementale rigoureuse. Le passage du modele vers le langage synchrone esterel s'effectue de maniere systematique par une traduction des comportements des bhrs en esterel. Nous etudions ensuite le probleme de l'implementation effective de programme synchrone. Nous definissons pour cela des environnements d'execution de programmes synchrones qui prennent en compte les caracteristiques temps-reel des systemes. Des specifications de machine d'execution sont fournies. La derniere partie est consacree a la mise en uvre de programmes synchrones sur une architecture cible de type microcontroleur. L'implantation sur ce microcontroleur est realisee de maniere automatique. Lors de cette phase, nous quantifions l'approximation de reactions en temps nul faite par le langage esterel, par une evaluation formelle des performances de l'application. Des supports logiciels sont fournis pour realiser ceci

Les systèmes embarqués sont caractérisés par des ressources matérielles réduites. Bien que ces ressources ne cessent de s’étendre, elles restent tout de même insuffisantes. L’espace mémoire est l’une des ressources les plus critiques. La compression du code dédié aux systèmes embarqués représente une solution intéressante pour réduire l’encombrement mémoire. Notre travail de recherche se focalise sur la compression du code Java sous format de fichiers class Java. Notre contribution consiste à concevoir et mettre en œuvre un système basé sur un profiler pour guider la compression des fichiers class Java. Ce profiler permet d'établir une stratégie de compression efficace offrant le meilleur taux de compression en tenant compte des caractéristiques du code en entrée et des dépendances entre les techniques de compression. La démarche suit quatre points : 1- l'examen du code Java afin d’en extraire les informations utiles pour le guidage du processus de compression. 2 - l'analyse des dépendances des opérations de compression en terme d'interaction mutuelle des unes avec les autres. Pour ce faire, nous avons mis au point deux méthodes, l'une numérique basée sur l'estimation des performances, l'autre analytique permettant de déterminer la nature des dépendances entre les opérations de compression. 3 - l'évaluation statistique des performances permettant le choix de la stratégie de compression. Nous avons, à ce propos, identifié les paramètres relatifs à chaque opération permettant ainsi leur évaluation. 4- La définition d’heuristiques appropriées pour identifier le chemin de compression le plus efficace dans l'espace de recherche représenté par un graphe orienté
The embedded systems are characterized by reduced hardware resources. Although these resources are constantly increasing, they remain insufficient. The memory space is one of the most critical resources. The compression of the code designed for embedded systems constitutes an interesting solution to reduce the memory footprint. Our study focuses on the compression of Java code represented by Java Class format files. Our contribution consists in designing and implementing a profiler based system in order to guide the compression of Java class files. Our profiler enables us to set up, on the basis of elementary compression techniques, an efficient compression strategy which delivers the best rate of compression. This strategy takes into consideration the features of the code given in input and dependencies between compression techniques. Our approach is based on four points: 1 - the study of the input files in order to extract the necessary information for the guidance of the compression process. 2 - the analysis of compression techniques dependencies in terms of effects produced by each technique to the others. To do so, we developed two methods: one numerical, based on the estimation of performance, the other analytical in order to determine whether there are common points between the different compression methods. 3 - the statistic performance assessment which allows to choose a strategy of compression: we have identified the parameters, related to each method, that enable this assessment. 4 - the definition of heuristics in order to identify the most efficient compression path in a research space characterized by an oriented graph

Ce travail porte sur la programmation de systèmes de Contrôle-Commande. Ces systèrnes sont constitués d’une boucle de controle qui acquiert l’état actuel du système par l'intermédiaire de capteurs, exécute des algorithmes de contrôle à partir de ces données et calcule en réaction les commandes à appliquer sur les actionneurs du système dans le but de réguler son état et d'accomplir une mission donnée. Les logiciels de commandes de vol d’un aéronef sont des exemples typiques de systèmes de Contrôle-Commande ayant pour objectif de contrôler la position, la vitesse et l’attitude de l'aéronef durant le vol. Les systèmes considérés sont critiques, dans le sens où leur mauvais fonctionnement peut avoir des conséquences catastrophiques. Leur implantation doit donc être déterministe, non seulement sur le plan fonctionnel (produire les bonnes sorties en réponse aux entrées) mais aussi sur le plan temporel (produire les données aux bonnes dates). Nous avons défini un langage formel et son compilateur permettant de programmer de tels systemes. Le langage se situe à un niveau d’abstractron élevé et se présente comme un langage d'architecture logicielle temps réel. Il permet de spécifier avec une sémantique synchrone l'assemblage des composants fonctionnels d’un système multi-rythme. Un programme consiste en un ensemble d'opérations importées, implantées à l'extérieur du programme, reliées par des dépendances de données. Le langage permet de spécifier de multiples contraintes de périodicité ou d’échéance sur les opérations. Il définit de plus un ensemble réduit d’opérateurs de transition de rythme permettant de décrire de manière précise et non ambiguë des schémas de communication entre opérations de périodes différentes. La sémantique du langage est définie formellement et la correction d'un programme, c'est à dire l'assurance que sa sémantique est bien définie, est vérifiée par un ensemble d'analyses statiques. Un programme correct est compilé en un ensemble de tâches temps réel implantées sous forme de threads C communicants. Le code d’un thread est constitué du code (externe) de l'opération correspondante, complété par un protocole de communication gérant les échanges de données avec les autres threads. Le protocole, basé sur des mécanismes de copies dans des mémoires tampons, est non bloquant et déterministe. Le code généré s’exécute à l'aide d’un Systeme d’Exploitation Temps Réel classique disposant de la politique d'ordonnancement EDF. Les opérations du programme s’exécutent de manière concurrente et peuvent donc être préemptées en cours d’éxecution en faveur d’une opération plus urgente. Le protocole de communication proposé permet d’assurer que, malgré les préemptions, l'exécution du programme généré est prédictible et correspond exactement à la sémantique formelle du programme d'origine.

Les contrats basés sur les notions d'hypothèses/garanties constituent un paradigme expressif pour une conception modulaire et compositionnelle de spécification de programmes. Dans cette thèse, nous élaborons des fondements pour la mise en oeuvre de systèmes embarqués basée sur la notion de contrats. Nous proposons ainsi une algèbre de contrats basée sur deux concepts simples : les hypothèses et les garanties des composants sont définies par des filtres, les filtres sont caractérisés par une structure d'algèbre booléenne. Les choix effectués pour définir la structure des filtres permettent de définir une algèbre de Heyting sur l'ensemble des contrats. Un cadre de travail est ainsi défini, dans lequel les contrats sont utilisés pour vérifier la correction des hypothèses faites sur le contexte d'utilisation d'un composant, et pour fournir à l'environnement les garanties qui lui sont demandées. Nous illustrons cette présentation avec la spécification d'un moteur à quatre temps
Contract-based design is an expressive paradigm for a modular and compositional specification of programs. In this thesis, we elaborate new foundations for contract-based embedded system design by proposing a general-purpose algebra of assume/guarantee contracts based on two simple concepts: first, the assumption or guarantee of a component is defined as a filter and, second, filters enjoy the structure of a Boolean algebra. This yields a structure of contracts that is a Heyting algebra. In this framework, contracts are used to negotiate the correctness of assumptions made on the definition of a component at the point where it is used and provides guarantees to its environment. We put this algebra to work for the definition of a general purpose module system whose typing paradigm is based on the notion of contract. We illustrate this presentation with the specification of a simplified 4-stroke engine model

La méthodologie présentée distingue dans le logiciel temps-réel une partie commande et une partie opérative. Elle se base sur l'utilisation des réseaux de Petri pour spécifier la partie commande et sur un environnement de programmation pour générer quasi automatiquement le logiciel final

La problématique abordée dans ce travail est celle de la gestion mémoire automatique pour des programmes Java temps-réel embarqués. Dans des langages comme le C ou le C++, la mémoire est typiquement gérée explicitement par le programmeur, ce qui est la source de nombreuses erreurs d'exécution causées par des manipulations hasardeuses. Le coût de correction de telles erreurs est très important car ces erreurs sont rarement reproductibles et donc difficiles à appréhender. En Java la gestion mémoire est entièrement automatique, ce qui facilite considérablement le développement. Cependant, les techniques classiques de recyclage de la mémoire, typiquement basées sur l'utilisation d'un ramasse-miettes, sont souvent considérées comme inapplicables dans le contexte des applications temps-réel embarquées, car il est très difficile de prédire leur temps de réponse. Cette incompatibilité est un frein important à l'adoption de langages de haut niveau comme Java dans ce domaine.
Pour résoudre le problème de la prévisibilité du temps d'exécution des opérations mémoire, nous proposons une approche fondée sur l'utilisation d'un modèle mémoire en régions. Cette technique, en groupant physiquement les objets de durées de vie similaires dans des zones gérées d'un seul bloc, offre en effet un comportement temporel prévisible. Afin de décider du placement des objets dans les différentes régions, nous proposons un algorithme d'analyse statique qui calcule une approximation des relations de connexion entre les objets. Chaque structure de données est ainsi placée dans une région distincte. L'analyse renvoie également au programmeur des informations sur le comportement mémoire du programme, de façon à le guider vers un style de programmation propice à la gestion mémoire en régions, tout en pesant le moins possible sur le développement.
Nous avons implanté un gestionnaire mémoire automatique en régions dans la machine virtuelle JITS destinée aux systèmes embarqués à faibles ressources. Les résultats expérimentaux ont montré que notre approche permet dans la plupart des cas de recycler la mémoire de façon satisfaisante, tout en présentant un comportement temporel prévisible. Le cas échéant, l'analyse statique indique au développeur quels sont les points problématiques dans le code, afin de l'aider à améliorer son programme.

Face à la multiplication et la diversification des services informatisés proposés aux individus, la personnalisation devient un élément majeur de différentiation pour les fournisseurs. Grâce à ses propriétés de sécurité et de mobilité, la carte à puce dispose du potentiel nécessaire pour jouer un rôle clef dans le déploiement de services personnalisés nomades. Les plates-formes logicielles des cartes. à puce de prochaine génération offrent des possibilités accrues en terme de programmation et d'intégration au sein des infrastructures informatiques. Cette évolution des applications encartées nécessite à la fois un enrichissement et une modernisation du processus industriel de personnalisation. Les travaux décrits dans cette thèse constituent une proposition d'approche novatrice, fournissant aux développeurs les moyens méthodologiques et techniques de réaliser une personnalisation fonctionnelle à grande échelle de leurs applications. Dans la perspective d'optimiser le processus industriel de personnalisation, les concepts de code personnalisable et de code personnalisé sont introduits : le second résulte du tissage entre le premier et un ensemble de données utilisateurs structurées dans des profils. Le code des applications encartées personnalisées est produit de manière semi automatisée sur la base d'une démarche exploitant la complémentarité entre les techniques de modélisation et le développement logiciel génératif. Un ensemble de méta-modèles structurés de manière à respecter la séparation des préoccupations permet d'exprimer les besoins de personnalisation, tandis qu'un cadre de conception permet d'implémenter les transformations et les tissages de modèles en Java.

Les systèmes embarqués sont largement utilisés de nos jours. Pour des raisons d'efficacité, les plus contraints en termes de ressources sont toujours programmés en C et en assembleur. L'adoption de langages de plus haut niveau tels que C# ou Java offrirait plus d'abstraction au programmeur, ce qui réduirait les temps de développement et par conséquent le coût de ces systèmes. Certains d'entre eux ont déjà migré vers de tels langages, comme les téléphones mobiles ou les tablettes tactiles, mais ils sont équipés d'une grande quantité de mémoire externe et ne reflètent pas la majorité des systèmes embarqués.Cette thèse s'intéresse à l'implémentation de Java et .NET pour l'embarqué, et plus spécifiquement à la compilation efficace du polymorphisme. Ce polymorphisme génère un certain coût à l'exécution, comme des indirections dans le cas des appels de méthodes (polymorphisme d'inclusion), ou de la duplication de code dans le cas de la généricité (polymorphisme paramétrique). De nombreuses techniques d'implémentation ont été proposées, notamment pour Java. Il reste cependant à identifier lesquelles sont applicables pour le type de systèmes que nous ciblons, et à en concevoir de nouvelles pour certains aspects comme la généricité. Nous partons du principe que les techniques globales (hypothèse du monde clos) sont les mieux adaptées. Par l'analyse de types, nous détectons qu'une partie importante des programmes est monomorphe et qu'elle peut donc être compilée sans surcoût. Pour implémenter le polymorphisme restant, nous choisissons la technique la mieux adaptée au matériel cible. Nous proposons également une implémentation de la généricité qui est adaptée aux systèmes embarqués. D'après nos évaluations, l'impact négatif du polymorphisme sur l'efficacité est largement réduit. L'efficacité du code optimisé devrait s'approcher de celle du C, et les techniques que nous employons pourraient être applicables dans le contexte plus général du chargement dynamique
Nowadays, embedded systems are ubiquitous. For efficiency reasons, most constrained systems are still programmed in C and assembly. Adopting higher-level languages such as C# or Java should enhance the level of abstraction offered to programmers and reduce development time and cost for these systems. A small part of them have migrated to such languages, like smartphones and tablet computers, but they have a large amount of external memory available and do not represent the majority of embedded systems.This thesis focuses on the implementation of Java and .NET for embedded systems, and more especially on the efficient compilation of polymorphism. Polymorphism generates an overhead at run-time, such as indirections when methods are invoked (inclusion polymorphism) or code duplication in the case of generics (parametric polymorphism). Many implementation techniques have been proposed, especially for Java. However, it remains to identify which ones are applicable in the context of low-end embedded systems. We consider that whole program optimization (closed-world assumption) is well-suited in this context. Using type analysis, we observe that most part of programs is monomorph, therefore it can be compiled with no overhead with respect to C. In order to implement the remaining polymorphism, we choose the technique which is better suited for the target hardware. We also propose an appropriate implementation of run-time generics. Our results show that the negative impact of polymorphism is mostly reduced. The efficiency of the optimized code should be comparable with C, and the techniques we employ could be applicable in the context of dynamic loading (open-world assumption)

Nous nous intéressons dans ce manuscrit au langage ReactiveML, qui est une extension de ML avec des constructions inspirées des langages synchrones. L'idée de ces langages est de diviser l'exécution d'un programme en une suite d'instants logiques discrets. Cela permet de proposer un modèle de concurrence déterministe que l'on peut compiler vers du code séquentiel impératif. La principale application de ReactiveML est la simulation discrète, par exemple de réseaux de capteurs. Nous cherchons ici à programmer des simulations à grande échelle, ce qui pose deux questions : sait-on les programmer de façon simple et modulaire ? sait-on ensuite exécuter ces programmes efficacement ? Nous répondons à la première question en proposant une extension du modèle synchrone appelée domaines réactifs. Elle permet de créer des instants locaux invisibles de l'extérieur. Cela rend possible le raffinement temporel, c'est-à-dire le remplacement d'une approximation d'un système par une version plus détaillée sans changer son comportement externe. Nous développons dans ce manuscrit la sémantique formelle de cette construction ainsi que plusieurs analyses statiques, sous forme de systèmes de types-et-effets, garantissant la sûreté des programmes dans le langage étendu. Enfin, nous montrons également plusieurs implémentations parallèles du langage pour tenter de répondre à la question du passage à l'échelle des simulations. Nous décrivons tout d'abord une implémentation avec threads communiquant par mémoire partagée et basée sur le vol de tâches, puis une seconde implémentation utilisant des processus lourds communiquant par envoi de messages.