Soutenance mémoire
Les langages synchrones ont été fondés dans les années 1980 pour modéliser, concevoir et implémenter les systèmes réactifs temps réel critiques. Avec la complexité toujours croissante des systèmes contrôlés, la vitesse d’exécution devient un critère important. Dans le même temps, les processeurs gagnent plus en nombre de cœurs qu’en vitesse. 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 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, fonctionnel flot de données, des réseaux de Kahn [Kah74]. 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 synchronisation ni information extérieur au modèle. 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 fonctionnel du calcul.
Parmi les trois langages synchrones originaux, seul Esterel [BC84] est impératif et non flots de données. Le langage Signal [Le +91], orienté modélisation, est relationnel. Lustre [Cas+87] est le premier langage synchrone fonctionnel à flots de données. Sa première sémantique dénotationnelle [Ber86] ressemblait déjà à une sémantique de Kahn. Ce sont les travaux de Caspi et Pouzet sur les réseaux de Kahn synchrones [CP96] qui ont définitivement lié Lustre à la sémantique de Kahn, en remplaçant la primitive current par merge. Cela a mené au langage synchrone fonctionnel d’ordre supérieur Lucid Synchrone [Pou02]. De cette lignée est né Heptagon, dont la première version s’appelait MiniLustre [Bie+08] et fut développée dans l’optique de compiler source à source les automates, avec un langage minimaliste [CPP05]. Heptagon est un langage fonctionnel du premier ordre, dont le compilateur est un prototype universitaire, apparenté à l’outil industriel Scade [Tec13]. Ce dernier est largement utilisé dans les industries concevant des systèmes embarqués critiques. Grâce à sa sémantique de Kahn, un programme Heptagon s’assimile à un réseau de Kahn. Typiquement, chaque appel de fonction en Heptagon peut se comprendre comme un processus indépendant, communiquant avec le reste du programme aux travers de files. Dans le modèle général, il est impossible de borner la taille des files. Les langages synchrones assurent, grâce à des horloges marquant la présence des flots à des instants logiques, que toute valeur produite est consommée dans le même instant. Ainsi, un programme Heptagon a une sémantique de Kahn synchrone, assurant que les files du réseau sont vides entre les instants. Dans ce cas, il est assuré que le réseau, même désynchronisé, peut s’exécuter avec des files d’une seule place [Pla10]. Ainsi, une fois la découpe du programme effectuée, la distribution en tant que telle ne pose plus de question, son efficacité beaucoup plus [GN03].
Assurer l’efficacité 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. Pour obtenir un gain de performance, l’outil Ocrep [Gir94; GNP06] a recours à une analyse statique flots de données pour optimiser le contrôle et les communications du code généré. Dans ce cadre, le programmeur décide de l’emplacement des calculs, mais le découplage et les synchronisations entre calculateurs sont automatiques. La distribution de certains programmes Signal peut être faite à l’aide de l’outil généraliste SynDEx [KS08] ou avec Polychrony [Ma10]. De ces travaux nous faisons 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 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 granularité des calculs est une problématique 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 de Lucid Synchrone [Cas+09], mais aussi proposer une analyse pleinement modulaire de Lucy-n [Pla10] le langage synchrone le plus fidèle aux réseaux de Kahn.
Le force du modèle des réseaux de Kahn est de représenter le comportement d’un réseau interagissant avec son environnement comme une fonction continue. Toute la structure est dans le domaine de cette fonction. Les entrées et les sorties d’une telle fonction sont des flots : la suite finie ou infinie des valeurs vues au cours du temps. Ne reste donc que le comportement fonctionnel du réseau, représenté par une fonction f : si l’exécution du système donne le flot x en entrée, alors la sortie a le flot y = f(x).
|
Table des matières
INTRODUCTION
1 Heptagon un langage synchrone fonctionnel flots de données
1.1 Tour d’horizon
1.1.1 Code généré et boucle de simulation
1.1.2 Le registre synchrone fby, aussi appelé délai unité
1.1.3 Opérateurs combinatoires
1.1.4 Appel de fonction
1.2 Rythmes différents et horloges des flots
1.2.1 La primitive when
1.2.2 La primitive merge
1.2.3 Versions non booléennes
1.2.4 Ne pas confondre merge et if then else
1.2.5 Horloges et pointeaux
1.2.6 Signature d’horloge
1.3 Automates et réinitialisation
1.3.1 Automates
1.3.2 Réinitialisation
1.4 Principe de substitution
1.5 Paramètres statiques
1.6 Les tableaux
1.7 Conclusion
2 Sémantiques et compilation d’Heptagon
2.1 Sémantique de Kahn
2.1.1 Noyau fonctionnel du langage
2.1.2 Domaine de Kahn
2.1.3 Sémantique de Kahn
2.2 Sémantique de Kahn Synchrone
2.2.1 Le registre synchrone
2.2.2 Les constantes
2.2.3 Les horloges
2.2.4 Programme et fonctions
2.2.5 Lien avec la sémantique non synchrone
2.3 Noyau équationnel et pointage
2.3.1 Noyau équationnel
2.3.2 Pointage (clocking ou calcul d’horloges)
2.3.3 Cohérence du pointage
2.4 Sémantique de Kahn synchrone implicite (sans réaction à abs)
2.5 Compilation vers du code séquentiel
2.5.1 Ordonnancement
2.5.2 Obc un langage impératif intermédiaire
2.5.3 Traduction du noyau
2.5.4 Optimisation du contrôle
2.5.5 Memalloc
2.6 Réinitialisation
2.6.1 Réinitialisation hyperchrone
2.6.2 Traduction source à source de la réinitialisation
2.6.3 Gestion de la réinitialisation dans le noyau
2.6.4 Sémantiques de la réinitialisation
2.6.5 Sémantique synchrone implicite de la réinitialisation d’équations
2.7 Conclusion
CONCLUSION
Télécharger le rapport complet
