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.
| Identifer | oai:union.ndltd.org:theses.fr/2013PA112202 |
| Date | 25 September 2013 |
| Creators | Gérard, Léonard |
| Contributors | Paris 11, Pouzet, Marc |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text, Image, StillImage |
Page generated in 0.0032 seconds