La plupart des systèmes critiques sont dits «temps-réel durs» puisqu'ils requièrent des garanties temporelle fortes. Ces systèmes sont de plus en plus complexes et les processeurs mono-coeurs traditionnels ne sont plus assez puissants. Les multi-coeurs et les pluri-coeurs sont des alternatives plus puissantes, cependant ils contiennent des ressources partagées. Les accès concurrents à ces ressources provoquent des interférences qui doivent être prises en compte puisqu'elles rendent les délais d'accès non prédictibles. Pour les pluri-coeur, le réseau sur puce (NoC) doit être configuré pour éviter les interblocages et garantir des pires temps de traversée précis. Le MPPA2 de Kalray est un pluri-coeur avec de bonnes propriétés temporelles.Les langages Synchrones flot de données tels que Lustre ou Scade sont largement utilisés dans l'industrie aéronautique. Les programmes sont des réseaux de noeuds de calcul communicants. Nous présentons une méthode pour extraire le parallélisme des programmes Synchrones. Nous générons du code pour déployer les tâches parallèles sur la puce et pour implémenter les communications en mémoire partagée ou à travers le NoC. Notre solution permet la traçabilité du code. Elle est basée sur un modèle d'exécution dirigé par le temps où chaque tâche a une date de début. L'ordonnancement est statique et minimise les interférences grâce à l'utilisation de bancs mémoire. Une borne de pire temps d'exécution (WCET) est calculée. Elle inclut les interférences mémoire et les pires temps de traversée NoC. Nous générons la configuration du processeur qui permet une allocation équitable des bandes passantes sur le NoC, la garantie de temps de traversées bornés et la synchronisation des horloges. Enfin, nous appliquons notre outils sur des exemples de programmes aéronautiques et un exemple synthétique utilisant 64 coeurs. / Most critical systems are subject to hard real-time requirements. These systems are more and more complex and the computational power of the predictable single-core processors is no longer sufficient. Multi- or many-core architectures are good alternatives but interferences on shared resources must be taken into account to avoid unpredictable timing effects. For many-core, the Network-on-Chip (NoC) must be configured such that deadlocks are avoided and a tight Worst Case Traversal Time (WCTT) of the communications can be computed. The Kalray MPPA2 is a many-core architecture with good timing properties.Dataflow Synchronous languages such as Lustre or Scade are widely used for avionics critical software. In these languages, programs are described by networks of computational nodes. We introduce a method to extract parallel tasks from synchronous programs. Then, we generate parallel code to deploy tasks on the chip and implement NoC and shared-memory communications. The generated code enables traceability. It is based on a time-triggered execution model which relies on a static schedule and minimizes the memory interferences thanks to usage of memory banks. The code enables the computation of a worst case execution time bound accounting for the memory interferences and the WCTT of NoC transmissions. We generate a configuration of the platform to enable a fair bandwidth attribution on the NoC, bounded transmissions through the NoC and clock synchronization. Finally, we apply this toolchain on avionic case studies and synthetic benchmarks running on 64 cores.

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. Ils sont devenus un concept fondamental dans les procédés employés par les outils de conception assistée par ordinateur, pour la conception de systèmes informatiques. 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 utilisons cette algèbre pour définir un système de modules dont le paradigme de typage est basé sur la notion de contrats. Le type d'un module est un contrat caractérisé par les hypothèses faites par l'environnement et les garanties offertes par les comportements du module. Nous illustrons cette présentation avec la spécification d'un moteur à quatre temps.

Les langages synchrones ont été fondés pour modéliser et implémenter les systèmes réactifs temps-réels critiques. Avec la complexité toujours croissante des systèmes contrôlés, la vitesse d'exécution devient un critère important. Nous sommes donc à la recherche d'une exécution parallèle, combinant efficacité et sûreté.Les langages synchrones ont toujours intégré la notion de parallélisme, mais ce, pour l'expressivité de la modélisation. Leurs compilations visent principalement les circuits ou la génération de code séquentiel. Tous ont une sémantique formelle, qui rend possible la distribution correcte du code. Mais la préservation de cette sémantique peut être un obstacle à l'efficacité du code généré, particulièrement s'il est nécessaire de préserver une notion d'instant global au système.Le modèle sémantique qui nous intéresse est celui des réseaux de Kahn. Ces réseaux modélisent des calculateurs distribués, communiquant au travers de files de taille non bornée. Dans ce cadre, la distribution ne demande aucune communication ni synchronisation supplémentaire. En considérant l'histoire des files de communication, la sémantique de Kahn permet de s'abstraire de l'exécution effective, tout en garantissant le déterminisme du calcul. Pour cela, chaque nœud du réseau doit avoir une sémantique fonctionnelle continue.Le langage que nous développons est Heptagon, un langage synchrone fonctionnel du premier ordre, déscendant de Lustre. Son compilateur est un prototype universitaire, apparenté à l'outil industriel Scade. Grâce à sa sémantique de Kahn, la distribution d'un programme Heptagon ne pose pas de question, son efficacité beaucoup plus.L'efficacité requiert de minimiser les synchronisations. Cela revêt deux aspects non indépendants. Avoir un découplage suffisant des calculs : il y a des délais dans les dépendances entre calculs. Avoir une granularité importante des calculs : un fort ratio temps de calcul sur fréquence de communication. Or la sémantique synchrone et les horloges d'un programme Heptagon reflètent exactement l'inverse. Elles permettent au programmeur de se contenter d'un découplage d'un instant et à chaque instant, au maximum une valeur est calculée. De plus, les instants sont typiquement courts, pour assurer que le système réagit rapidement.Des précédents travaux sur le sujet, nous tirons deux constats.Le premier est que nous souhaitons le contrôle du parallélisme par le programmeur, directement dans le code source. Il doit pouvoir maîtriser à quels instants il y a communication ou synchronisation. La solution que nous proposons dans ce manuscrit est l'utilisation des futures dans Heptagon. Ils fournissent ce pouvoir au programmeur, tout en restant des annotations qui peuvent être supprimées sans changer la sémantique dénotationnelle du programme.Le deuxième constat est que la question de la granularité des calculs est une question profonde, touchant en particulier aux questions de dépendance de données, de choix des horloges et de compilation modulaire. Heptagon, comme ses parents, restreint les réseaux de Kahn qui peuvent être écrits, de telle sorte que ces trois questions se traitent séparément. Pour mieux comprendre le lien entre ces éléments, nous revenons aux réseaux de Kahn. Notre principal résultat est la définition de la sous-classe des réseaux ordonnés réactifs. Ceux-ci sont les seuls pour lesquels nous pouvons décrire modulairement le comportement avec des horloges, sans restreindre les contextes d'appels. Ces réseaux ont une signature d'horloge en forme normale, qui maximise la granularité. Pour l'exprimer, nous introduisons les horloges entières, décrivant la communication de plusieurs valeurs en un seul instant. Nous appliquons ensuite nos résultats pour voir sous un nouveau jour Heptagon, Signal, les politiques des objets de Lucid Synchrone, mais aussi proposer une analyse pleinement modulaire de Lucy-n langage synchrone le plus fidèle aux réseaux de Kahn.

Les langages synchrones ont été fondés pour modéliser et implémenter les systèmes réactifs temps-réels critiques. Avec la complexité toujours croissante des systèmes contrôlés, la vitesse d'exécution devient un critère important. Nous sommes donc à la recherche d'une exécution parallèle, combinant efficacité et sûreté.Les langages synchrones ont toujours intégré la notion de parallélisme, mais ce, pour l'expressivité de la modélisation. Leurs compilations visent principalement les circuits ou la génération de code séquentiel. Tous ont une sémantique formelle, qui rend possible la distribution correcte du code. Mais la préservation de cette sémantique peut être un obstacle à l'efficacité du code généré, particulièrement s'il est nécessaire de préserver une notion d'instant global au système.Le modèle sémantique qui nous intéresse est celui des réseaux de Kahn. Ces réseaux modélisent des calculateurs distribués, communiquant au travers de files de taille non bornée. Dans ce cadre, la distribution ne demande aucune communication ni synchronisation supplémentaire. En considérant l'histoire des files de communication, la sémantique de Kahn permet de s'abstraire de l'exécution effective, tout en garantissant le déterminisme du calcul. Pour cela, chaque nœud du réseau doit avoir une sémantique fonctionnelle continue.Le langage que nous développons est Heptagon, un langage synchrone fonctionnel du premier ordre, déscendant de Lustre. Son compilateur est un prototype universitaire, apparenté à l'outil industriel Scade. Grâce à sa sémantique de Kahn, la distribution d'un programme Heptagon ne pose pas de question, son efficacité beaucoup plus.L'efficacité requiert de minimiser les synchronisations. Cela revêt deux aspects non indépendants. Avoir un découplage suffisant des calculs : il y a des délais dans les dépendances entre calculs. Avoir une granularité importante des calculs : un fort ratio temps de calcul sur fréquence de communication. Or la sémantique synchrone et les horloges d'un programme Heptagon reflètent exactement l'inverse. Elles permettent au programmeur de se contenter d'un découplage d'un instant et à chaque instant, au maximum une valeur est calculée. De plus, les instants sont typiquement courts, pour assurer que le système réagit rapidement.Des précédents travaux sur le sujet, nous tirons deux constats.Le premier est que nous souhaitons le contrôle du parallélisme par le programmeur, directement dans le code source. Il doit pouvoir maîtriser à quels instants il y a communication ou synchronisation. La solution que nous proposons dans ce manuscrit est l'utilisation des futures dans Heptagon. Ils fournissent ce pouvoir au programmeur, tout en restant des annotations qui peuvent être supprimées sans changer la sémantique dénotationnelle du programme.Le deuxième constat est que la question de la granularité des calculs est une question profonde, touchant en particulier aux questions de dépendance de données, de choix des horloges et de compilation modulaire. Heptagon, comme ses parents, restreint les réseaux de Kahn qui peuvent être écrits, de telle sorte que ces trois questions se traitent séparément. Pour mieux comprendre le lien entre ces éléments, nous revenons aux réseaux de Kahn. Notre principal résultat est la définition de la sous-classe des réseaux ordonnés réactifs. Ceux-ci sont les seuls pour lesquels nous pouvons décrire modulairement le comportement avec des horloges, sans restreindre les contextes d'appels. Ces réseaux ont une signature d'horloge en forme normale, qui maximise la granularité. Pour l'exprimer, nous introduisons les horloges entières, décrivant la communication de plusieurs valeurs en un seul instant. Nous appliquons ensuite nos résultats pour voir sous un nouveau jour Heptagon, Signal, les politiques des objets de Lucid Synchrone, mais aussi proposer une analyse pleinement modulaire de Lucy-n langage synchrone le plus fidèle aux réseaux de Kahn. / Synchronous languages are used to program critical reactive systems. Today, systems require to find a way to execute them safely and in parallel. Parallelism has always been part of synchronous langages, but for modeling purpose. Their formal semantics allow to distribute them, but preserving the semantics may be ressource costly and prevent good parallel execution.The Kahn networks model is of great interest. It models distributed computers, communicating through unbounded FIFOs, ensuring that the computed values are deterministic, without any need of added synchronization.We develop the langage Heptagon, a first order functional synchronous son of Lustre.The compiler is an academic prototype of the industrial tool Scade. Thanks to its Kahn semantics, it can be distributed. In order to be efficient, one need to maximize the decoupling of computations and maximize the computation granularity. However, synchronous langages allow for very tight computation coupling and usually require thin computation granularity to ensure reactivity of the system.We opt for two research directions. The first one is to give the control of the execution parallelism to the programer. To this mean, we add futures to the source langage Heptagon. They provide control over starting and end of parallel computations, while preserving the functional semantics. Moreover, we provide a compilation for embedded systems, using statically allocated memory. The second one is to study Kahn synchronous semantics to understand data dependencies and maximize granularity of the computations. This touches deeply to the synchronous languages, mixing the usually separated questions of causality and clock calculus. We define the class of reactive ordered Kahn networks. They are the one which may be modularly compiled and whose behavior may be expressed with a clock signature. Moreover, we show that their is a normal form for this signature, maximizing the granularity of the network. To express it, we extend clocks to integer clocks. Then we come back to the synchronous languages we know to understand how to use it. The result is fully used and explained on Lucy-n, the synchronous language closest to Kahn networks.

.

MASL PROPOSE UNE APPROCHE UNIFIEE ET MACROSCOPIQUE A L'EXPRESSION DE CALCULS HETEROGENES ET DISTRIBUES SUR DES AGENTS CONÇUS EN SUIVANT LE MODELE DELIBERATIF, REACTIF OU HYBRIDE. C'EST UN LANGAGE DE HAUT NIVEAU INDEPENDANT DE L'EXECUTIF OU CHAQUE AGENT, VU COMME UNE ENTITE CONCURRENTE, DETERMINE LOCALEMENT SA PARTICIPATION A DES BLOCS D'EXECUTION COLLECTIFS (E-BLOCS). CHAQUE E-BLOC EST UN PROGRAMME COLLECTIF ANONYME POUVANT S'EXECUTER SUR UN RESEAU D'AGENTS SELON DES CRITERES LOCAUX. LE MODE D'ORCHESTRATION (SCALAIRE, SYNCHRONE, ASYNCHRONE) EST DETERMINE STATIQUEMENT PAR UN ATTRIBUT DU BLOC, LES COMMUNICATIONS SUPPORTENT LE MODELE A MEMOIRE PARTAGEE, LE MODELE A ENVOI DE MESSAGES ET LE MODELE D'EVENEMENTS. L'HETEROGENEITE DES AGENTS EST ASSUREE PAR HERITAGE ET POLYMORPHISME ALORS QUE L'AUTONOMIE EST PROPOSEE PAR UN MECANISME (APPELE PERMEABILITE) DE FILTRAGE OU CHAQUE AGENT PEUT MASQUER/OUVRIR SON INTERFACE DYNAMIQUEMENT ET SELON LA POSITION DE L'EMETTEUR DANS LA HIERARCHIE D'E-BLOCS. DANS UN CONTEXTE D'ALLOCATION DYNAMIQUE DES AGENTS, DE REPRISE APRES ECHEC OU DE REMPLACEMENT D'UN AGENT ROBOTIQUE DANS UNE FLOTTE DE ROBOTS (CAS D'UNE PANNE OU PERTE DE FONCTIONNALITE COMPROMETTANT LA MISSION), LE E-BLOC PROPOSE UNE PERSPECTIVE DE POINT D'ENTREE D'UN TRAITEMENT COLLECTIF. DANS LE CAS D'E-BLOC SYNCHRONES, LE PARADIGME SOUS-JACENT EST ISSU DU MODELE DATA-PARALLELE, PERMETTANT ICI DES TRAITEMENTS ITERATIFS PAR VAGUES SUCCESSIVES D'AGENTS. AU FINAL, MASL PROPOSE DES AVANCEES DANS LE DOMAINE DES SMA (APPARTENANCE DYNAMIQUE A DES GROUPES, PRECISION DU RYTHME DES ACTIONS A ENTREPRENDRE POUR PERMETTRE UNE COOPERATION DESIREE) ET AU NIVEAU DE LA GESTION DES ERREURS.

Thèse de doctorat : Informatique : Nice : 2004. / Bibliogr. p. 155-159. Résumés en français et en anglais.

Cette thèse explore les possibilités algorithmiques offertes par la synthèse de haut niveau de circuits dans le cadre de la logique synchrone et à destination d'une Mémoire Active Programmable. Une chaîne de compilation expérimentale permettant de générer automatiquement un circuit reconfigurable à partir d'une spécification de haut niveau y est présentée. Le langage de haut niveau est DSL (Design Source Language). DSL est basé sur le langage fonctionnel Jazz. DSL permet de décrire tout type de circuit dans le modèle de la logique synchrone, d'en faire la simulation et la synthèse, puis de l'exécuter sur une Mémoire Active Programmable. Le compilateur procède par étapes successives pour synthétiser un circuit à partir de son code-source de haut niveau. Chacune des étapes de la compilation génère des annotations qui précisent les propriétés du circuit jusqu'à une forme synthétisable. Les annotations sont pour la plupart ajoutées automatiquement par le compilateur mais sont partie intégrante de la syntaxe de DSL et peuvent ainsi être précisées par le concepteur. DSL prend en charge la génération automatique de l'ensemble des routines systèmes qui permettent au circuit de communiquer avec son hôte. Ce système de prototypage et d'accélération matérielle automatique sur PAM est testé sur des circuits variés, comme des algorithmes de tramage, d'estimation de mouvement et de détection des points de Harris.

Cette thèse a pour objet l'étude de la modélisation du contrôle de la reconfiguration dans les systèmes dynamiques, plus particulièrement les systèmes sur puce dynamiquement et partiellement reconfigurables. Les travaux présentés dans ce manuscrit visent à réaliser une méthodologie de conception par contrainte du contrôle, applicable dans le cadre de la spécification de ces systèmes. Reposant sur le principe d'Ingénierie Dirigée par les Modèles, cette méthodologie - basée sur UML/MARTE - est dotée de transformations appropriées, lui permettant de cibler une représentation synchrone, en langage BZR, de la partie contrôle. Cette représentation est ensuite exploitable par une technique correcte par construction - la synthèse de contrôleur discret -, dans le but d'obtenir automatiquement et de manière sûre les lois de commande correspondant aux contraintes spécifiées en amont. La partie contrôle est plus particulièrement divisée en deux aspects : la sécurité, obtenue formellement par synthèse afin de produire des espaces de configurations accessibles, et l'optimisation, implémentable par le concepteur et produisant un ordre de reconfiguration à partir d'un espace accessible. L'intégration sécurité/optimisation proposée est assimilable à un système réactif avec boucle de rétroaction. Un exemple démontrant la méthodologie est réalisé, et fait apparaître ses avantages tant en terme de simplification de conception (spécification par contraintes, approche automatique) qu'en terme de sécurité (contrôle formel).