back

Transformation d'Esterel Pur v5 en Graphe de Flots de Contrôle Concurrents Comparaison des formats intermédiaires

Présentation

Ce document a pour but de montrer les différentes manières de transformer un programme Esterel en un CCFG ( Concurrent Control-Flow Graph ) qui pourra entrer facilement dans un processus de compilation séquentielle traditionnelle. Ces techniques sont en effet déjà largement utilisées par les compilateurs Esterel existants. Esterel est un langage composé de moins d'une dizaine d'instructions noyau permettant un considérable pouvoir d'expression.


Nous traiterons ainsi en premier lieu du format IC/LC actuellement utilisé dans la version V5 du compilateur Esterel INRIA/Esterel Technologies[1]. Ce format est directement obtenu à partir du code source Esterel.

En second lieu, nous présenterons un format CCFG[2] hiérarchique aidant à la visualisation de la structure de contrôle. Il conserve la structure d'un graphe de contrôle IC/LC mais rend sa potentielle synthèse en un code séquentiel plus facile. En effet, le code source n'augmentera pas exponentiellement en synthétisant une net-list mais conservera une taille proche de celle du source IC/LC. Il est en l'occurence utilisé comme format intermédiaire par le compilateur propriétaire EC[3] de Synopsys.

Nous terminerons par l'analyse du format GRC[4] développé à l'INRIA prenant en compte, toujours à un niveau structurel, certains problèmes de duplication de code inhérents à la sémantique d'Esterel. Ces portions de code peuvent potentiellement être exécutées en plusieurs instances dans différents contextes lors d'une même réaction.




Ce document à pour but de présenter les différents CCFG proposés pour un modèle Esterel et non de montrer comment transformer un fichier source IC en un autre format. Sur ce sujet, de plus amples renseignements se trouvent en [2, 3].

1   Exemple en Pure Esterel v5

L'exemple suivant à pour but d'illustrer dans la suite des transformations en différents formats, la traduction de cet exemple Esterel dans ces formats. L'exemple choisi est ABO, certes réduit en instructions du noyau mais suffisament simple pour concevoir les approches dans les différents formats.

module ABO:
   input A, B;
   output O;
   loop
      [ await A || await B ];
      emit O
   end loop
end module
Nous remarquons l'instruction await qui n'est pas une instruction du noyau. await I est une macro expansée en

trap T in
   loop
      pause;
      present I then 
         exit T 
      else 
         nothing 
      end present
   end loop
end trap

2   Terminologie

Une terminologie récurrente liée au domaine des langages synchrones est commune aux formats présentés ici.

Le tick
représente une réaction. Les entrées sont figées et les sorties sont positionnées en une durée de réaction nulle.

Le start
représente le premier appel d'un programme à la fonction de réaction.

Le restart
représente tous les autres appels à la fonction de réaction jusqu'à la terminaison du programme.

Le statut d'un signal
peut être présent si il a été émis, absent si il n'est pas émis ou indéterminé lors de sa déclaration.

Le statut d'un noeud
dans un graphe représentant un programme Esterel peut être actif ou inactif. Ce statut est déterminé en fonction de ceux des noeuds fils qui lui propagent l'information.

Le contrôle
permet de préciser l'état d'activité ou d'inactivité de l'instruction. Une instruction s'exécute dès qu'elle acquiert le contrôle. Dès qu'elle termine son exécution elle passe le contrôle à l'instruction suivante.

3   Format IC/LC

3.1   Instructions

Le format IC/LC définit 12 constructions présentées ci-dessous. Leurs équivalents graphiques sont décrits dans la figure 1.

ccfg001.gif

Figure 1: Constructions graphiques IC/LC

IC/LC fait apparaitre deux arbres en un:
Première exécution: start
Le noeud est associé à la première exécution de l'application.

Exécutions suivantes: restart
L'action est réalisée lors des exécutions suivantes.

Le parallélisme: fork
Ce noeud correspond à donner immédiatement le contrôle à toutes les branches qui s'exécutent en parallèle. Le statut du noeud dépend de celui des branches parallèles qui l'informent de leur terminaison.

Instructions séquentielles dans les branches: parallel
Chaque branche du noeud --- appelé thread --- regroupe un ensemble d'instructions purement séquentielles terminées par un registre. Il connait le statut de terminaison de ses branches, et peut décider en fontion de celui-ci, dans le même instant, de donner le contrôle à de nouvelles instructions.


Comment clarifier en d'autres termes la différence fondamentale entre parallel et fork qui peuvent paraitre équivalents dans le lexique informatique? L'instruction parallel donne le contrôle à toutes ses branches filles alors que le fork donnera certes lui aussi le contrôle à toutes ses branches qui possèdent les propriété suivantes:
Condition d'activation d'une branche: watchdog
Une branche du graphe de contrôle peut être activée si et seulement si la branche de graphe de sélection associée est active. Ce noeud permet de déterminer si la branche du graphe de sélection portant un registre est active ou pas.

Condition de statut: conditional
Le noeud teste le statut du signal X. Si celui-ci est présent alors la branche true obtiendra le contrôle, si il est absent alors la branche false l'obtiendra.

Emission d'un signal: emit
Le signal X est instantanément émis, donnant le contrôle à l'instruction suivante.

Terminaison: exit
La branche termine avec le statut X, représenté par un entier naturel. Les statuts sont les suivants: Ces codes de terminaison sont transmis au parallel associé aux threads les ayant produits puis interprétés par celui-ci. A titre d'exemple, lorsque toutes les branches ont retourné 0 alors l'instruction parallel associée est terminée et passe le contrôle à l'instruction suivante.

Suspension: stay
Ce noeud gêle le contrôle des branches situées en-dessous de celui-ci, jusqu'à la prochaine réactivation. Nécessairement précédé d'un watchdog, celui-ci vérifiera son état à chaque restart. Dans le cas où la condition de réactivation est vérifiée par le watchdog alors l'exécution reprendra là où elle a été gelée.

Registres: halt
Le noeud représente les registres dénotés par un identifiant. Il est actif dès qu'il obtient le contrôle. Nécessairement précédé d'un watchdog, celui-ci vérifiera son état à chaque restart.

Flux de contrôle
La flèche sequential donne instantanément le contrôle obtenu par le noeud ou l'instruction ne portant pas la flèche à l'instruction ou au noeud cible.

Flux de reconstruction
Le trait reconstruction permet de combiner les différents threads au restart.

3.2   Exemple

ccfg002.gif

Figure 2: ABO en IC/LC

La figure 2 décrit la traduction de ABO en IC/LC. La traduction actuelle produit néanmoins un code bien plus complexe car elle est structurelle. Au start, la seule action est d'activer les registres X et Y. Une branche fork réalise cette opération en créant deux branches d'exécution en même temps. L'application ne compte, outre le registre dédié de start, que deux registres. Ainsi, deux threads sont créés portant chacun un registre respectivement X et Y. Lors de chaque restart le watchdog des threads détermine si le thread est actif. Si c'est le cas, alors le contrôle est donné aux instructions associées. Dès qu'une instruction termine sur un test de présence des signaux A ou B, le code de terminaison normale est transmis à l'instruction thread. Dans le cas contraire, le test est falsifié et le registre associé reste toujours actif. Lorsque cette instruction a reçu les statut de terminaison normale de ses deux threads alors elle donne le contrôle à l'instruction chargée de l'émission du signal O. Elle boucle ensuite instantanément sur le fork chargé de rendre le contrôle aux registres X et Y (instruction loop).

4   Format CCFG de EC

4.1   Compilateur EC

Le compilateur EC a été défini par S. Edwards [3] dans les laboratoires de Synopsys, Inc. Etant de ce fait un format propriétaire, nous ne pourrons pas l'utiliser. Cependant, une description en est faite ci-dessous de sorte à présenter son potentiel d'expressivité. Il est généré à partir du IC/LC de sorte à interpréter le flot de contrôle du graphe IC beaucoup mieux que le feraient les compilateurs basés sur un système de portes trop bas niveau. Le but est d'éliminer le parallélisme via des noeuds de décision portant un état, modifié tout au long du flot de contrôle. Ainsi, une notion de contexte apparait de sorte à reprendre l'exécution en tenant compte d'une variable d'état.

Ce format résout de plus le problème des dépendances de données par des flèches en pointillés mettant en relation un signal émis et le test de présence sur ce même signal effectué dans une autre branche.

4.2   Instructions

Le format CCFG de EC définit 11 constructions présentées ci-dessous. Leurs équivalents graphiques sont décrits dans la figure 3.

ccfg003.gif

Figure 3: Constructions graphiques CCFG

Les capsules: parallel
Les capsules permettent de déclarer des branches parallèles en y incluant de manière transparente les déclarations de signaux locaux. Ces capsules sont hiérarchiques c'est à dire qu'elles peuvent contenir d'autres capsules. On appellera toplevel l'environnement initial qui n'est contenu dans aucune capsule. Dans chaque branche de la capsule, seront au moins présents trois éléments: Lorsque le contrôle est donné à la capsule alors il est transmis instantanément à toutes les branches. Lorsque toutes les branches ont terminé alors le contrôle est instantanément rendu à l'instruction suivante pour la relation next de la capsule.

Première exécution: start
L'action est réalisée lors de la première exécution , à l'intérieur et à l'extérieur des blocs hiérarchiques. Le contrôle peut néanmoins être redonné, même après la première exécution, à un start via le start représenté sur les capsules.

Exécutions suivantes: restart
L'action est réalisée lors des exécutions suivantes, à l'intérieur et à l'extérieur des blocs hiérarchiques.

Choix de registre actif: switch
L'action correspond à un choix exclusif entre un nombre quelconque de variables. Le contrôle sera donné à la branche portant le nom du registre actif.

Test sur statut: case
L'action correspond à un test if sur X. Si la présence de X est évaluée à vrai alors la branche true sera activée, sinon, celle portant false, le sera

Les registres: register
Les registres portent une lettre les représentant univoquement. Ils sont activés si et seulement si dans le cycle courant --- start ou restart --- une flèche next pointe dessus. Lors du prochain cycle un switch portera sur une de ses branches la lettre associée à ce registre.

Un registre à une portée strictement locale i.e. il est visible uniquement dans la branche de déclaration. La déclaration d'un registre correspond à lui attribuer une lettre différente de celles associées aux autres registres de la même branche. Ainsi, deux registres de même nom déclarés dans deux branches distinctes sont deux registres différents.

Statut de terminaison: exit
L'élément graphique représentant une terminaison ressemble aux registres. Cependant, au lieu de porter une lettre, il porte un chiffre entier naturel qui représente son statut de terminaison dans le cycle courant. Par convention, le statut de terminaison normale portera l'entier 0. Son interprétation sera faite via un switch dont une branche porte l'entier associé. Elle pourra être évaluée lors du prochain restart ou bien dans le cycle courant dès que le contrôle lui parvient.

Emission d'un signal: emit
Les signaux sont émis via une instruction emit portant le nom de ce signal. Sous les hypothèses du broadcasting immédiat des émissions et de la durée nulle de l'instant, les signaux sont émis dans l'environnement et accessibles à tous ceux susceptibles de les capter. La portée d'un signal interne est donné par une capsule parallel. Les signaux globaux i.e. déclarés dans l'interface du module sont visibles par tous.

Arrêt du contrôle: stop
Le contrôle s'achève dès qu'il rencontre un stop. S'il se trouve dans une capsule hiérarchique alors la branche courante est terminée. Dès que toutes les branches sont achevées en aboutissant sur cette instruction stop alors le contrôle est rendu au niveau hiérarchique directement supérieur. Dans le cas où il n'y ait plus de niveau hiérarchique supérieur alors l'exécution du cycle courant s'achève.

Flux de contrôle: next
Les instructions considérées jusqu'à présent doivent inter-agir entre elles en se donnant le contrôle. Les flèches next permet de structurer ces instructions entre elles. L'extrémité qui ne porte pas la flèche signifie que l'instruction associée a été exécutée et que, de ce fait, la prochaine pointée par la flèche peut l'être à son tour.

Dépendances: reference
Nous avons vu que lors de l'émission d'un signal, cette émission était perçue dans tout le sous-programme inclus dans la portée de sa déclaration. Cependant, comment attacher à l'émission d'un signal le fait qu'une autre branche attend sa présence via un case. Les dépendances servent donc a représenter ces liens émission--attente. Elles ne sont pas indispensables mais permettent de visualiser instantanément les relations existantes entre émetteurs/récepteurs.

4.3   Exemple

ccfg004.gif

Figure 4: ABO en CCFG de EC

La figure 4 montre la meilleure manière de traduire le programme Esterel ABO en graphe CCFG d'EC. Une capsule met en parallèle deux automates de structure identique. L'un déclare un registre p1 dont l'activité dépend du signal A, et l'autre un registre p2 dont l'activité dépend de B. Lors du start, le contrôle est transmis aux deux automates qui activent p1 et p2 puis terminent le cycle d'exécution. Lors de restart les switch des deux branches détermineront respectivement si le registre est actif, dans ce cas la présence du signal est évaluée. S'il est absent alors le registre associé est réactivé puis l'instruction termine. S'il est présent, la terminaison est immédiate et le registre associé n'est pas réactivé. Lorsque les deux branches sont terminées i.e. p1 et p2 sont désactivés alors l'instruction parallèle est terminée et le contrôle est rendu pour émettre le signal O puis reboucler sur l'instruction de start symbolisant la boucle.

5   Format GRC

GRC, proposé en [4], distingue arbre de sélection et arbre de flot de contrôle.

5.1   Arbre de sélection

ccfg005.gif

Figure 5: Graphe de sélection

L'arbre de sélection hiérarchise les registres --- les feuilles --- entre eux. La figure 5 présente les types de noeuds utilisés. Les noeuds et les feuilles sont numérotés sur N avec par convention 0 pour le premier noeud et 1 pour le boot register1. Ces indices sont utilisés dans l'arbre de flot de contrôle pour préciser sur quel(s) noeud(s) les actions sont réalisées.

Les noeuds de séquence

Les branches sortantes sont en exclusion i.e. une seule à la fois possède le contrôle. Le contrôle est donné aux branches de la gauche vers la droite. Lorsque la branche la plus à droite devient inactive via le graphe de flot de contrôle alors le contrôle du noeud de séquence est rendu à son noeud père. Si le noeud se fait préempter, alors, à la charge du graphe de flot de gérer la levée de l'exception.

Les noeuds d'exclusion

Les branches sortantes sont en exclusion. Le contrôle peut être donné à n'importe quelle branche i.e. aucun ordre sur celles-ci ne peut être prédit. Ainsi, rendre le contrôle au noeud père du noeud d'exclusion revient entièrement à la charge du graphe de flot de contrôle.

Les noeuds de parallélisation

Toutes les branches sortantes sont activées dès lors que le contrôle atteint le noeud. Lorsque toutes les branches sont désactivées via le graphe de flot de contrôle alors le contrôle est rendu au noeud père du noeud de parallélisation. Si le noeud se fait préempter, alors, à la charge du graphe de flot de gérer la levée de l'exception.

Les noeuds feuilles

Les feuilles de l'arbre portent nécessairement un registre, tel que pause, ou récemment pre. Toutes les macros mettant en jeu l'une de ces primitives noyau contiennent aussi des feuilles: await, halt, ...en l'occurence.

5.2   Arbre de flot de contrôle

ccfg006.gif

Figure 6: Graphe de flot de contrôle

La figure 6 présente les constructions utilisées dans un graphe de contrôle.

Initialisation: tick

Ce noeud est utilisée une seule et unique fois dans un graphe de flot de contrôle. Il représente l'initialisation du système lors du premier appel à la fonction de réaction.

Actions: action

Lorsque le contrôle est transmis à ce noeud une série d'actions associées est immédiatement réalisée. Dans le cas où des signaux --- locaux ou déclarés en output du système --- sont émis alors ils sont représentés comme émis dans l'environnement (par exemple S1 et S2 sur ce schéma). Le contrôle est instantanément rendu et le flot propagé au prochain noeud.


Des actions particulières ont été définies. Elles sont représentées dans la figure 6 par le noeud action portant le nom de celles-ci.

Parallélisme: fork

L'expression du parallélisme est incluse au format de description, il s'agit d'un lien [[Lien: link]5.2] qui en engendre deux autres donnant ainsi le contrôle à deux branches. Il est à relier au noeud de parallélisation de l'arbre de sélection.

Choix multiple: switch

Dès que le contrôle arrive à ce noeud, un choix doit être fait de sorte à le propager dans les branches appropriées. Ce noeud est étiqueté par un numéro de noeud du graphe de sélection lui étant associé. Le type du noeud du graphe de sélection indiquera qu'une ou plusieurs branches seront actives. Cependant, quelle(s) branche(s) activer? Le graphe de sélection détermine justement via les numéros des noeuds, les branches à activer. Ainsi, chaque branche sortant du switch est explicitement liée à un noeud du graphe de sélection via son étiquette.

Choix simple: choice

Quand ce noeud reçoit le contrôle, il opère un test (son étiquette) sur des signaux de l'environnement (ils sont représentés par S1 et S2 sur le schéma) ou sur l'activité d'un noeud du graphe de sélection. Le contrôle est immédiatement transmis à la branche true si l'expression est évaluée à vrai ou à la branche false si elle est évaluée à faux.

La synchronisation: synchronize

Ce noeud permet de synchroniser différentes branches parallèles. A chaque terminaison de branche (f1...f2) est associé un statut. Le noeud combinera ces statuts de sorte à décider s'il peut ou pas donner le contrôle aux instructions suivantes.

Lien: link

Les noeuds de l'arbre de flot de contrôle sont liés entre eux via des flêches indiquant le sens de transmission du flot de contrôle.

5.3   Exemple

ccfg007.gif

Figure 7: ABO en GRC

La figure 7 montre la traduction de l'exemple ABO dans la représentation du format GRC.

L'arbre de sélection (en bas à gauche) précise les dépendances entre les registres associés à boot, A et B. Le noeud étiqueté 0 précise qu'un seule des deux branches à la fois pourra être active. Celui étiqueté 2 indique que les deux branches sont mises en parallèle. L'arbre de contrôle montre comment le contrôle se propage dans le graphe lors de chaque start ou restart en fonction des noeuds actifs donnés par l'arbre de sélection.

6   Synthèse

La présentation de ces formats: IC/LC, CCFG de EC et GRC a proposée une manière de traduire un programme écrit en Exterel Pur v5 en graphes. En effet, une telle représentation améliore la compréhension et le travail des compilateurs, optimiseurs, ...Néanmoins, parmi ces représentations quelle serait celle susceptible d'offrir le plus grand potentiel pour une traduction en langage de description de circuits tels que VHDL ou Verilog? Plusieurs paramètres sont à prendre en considération. La section suivante tente de les mettre en lumière afin de nous aider dans notre choix.

6.1   Paramètres de choix

6.1.1   Coût d'accés au format intermédiaire

Notre objectif est de transformer de l'Esterel en VHDL. Ainsi, une alternative possible était de partir d'un langage exprimant le sens d'un programme écrit en Esterel Pur v5, de sorte à faciliter la production d'un prototype. En fonction de ces langages mis à notre disposition nous devons en choisir un qui nécessite peu d'efforts d'interfaçage avec la future application. De ce fait le format EC étant propriété de Synopsys, Inc nous ne pouvons pas l'utiliser.


Le format CCFG de EC est une représentation hiérarchique d'un programme Esterel Pur v5. Le langage de départ permettant la synthèse de l'arbre syntaxique abstrait associé à cette représentation dérive de celui représenté en IC/LC. La traduction en VHDL nécessite un langage intermédiaire qui conserve la structure comportementale d'un programme Esterel. Le format CCFG de EC propose une composition hiérarchique qui pourrait être traduite en architecture structurelle, très peu adaptée à une représentation comportementale.

6.1.2   Graphes

Le format intermédiaire d'un programme Esterel Pur v5 est scindé en deux parties:
  1. [a ] un premier graphe qui permet lors des activations de donner les branches (et registres) actives au graphe gérant l'enchaînement des actions
  2. un second graphe qui ordonnance les actions entre elles



Le langage sélectionné devra donc posséder le potentiel d'expression permettant l'accession à ces deux graphes.

6.1.3   Réincarnation

La réincarnation traite de la duplication d'un signal dans un même instant. Le langage devra si possible, pour des raisons de facilité, gérer ce phénomène baptisé schizophrénie des signaux. En l'occurence, IC/LC ne le gère pas alors que GRC le propose dans ses spécifications.


La section de code suivante montre un cas de réincarnation en Esterel où le signal A ne sera jamais émis. 

...
loop
  signal S, A in
    present S then emit A end;
    pause;
    emit S;
  end signal
end loop
...
Le signal S testé est toujours absent. Il est émis au tick suivant, le corps de la boucle se termine et reboucle instantanément créant une instance fraiche de S. C'est ce nouveau signal qui est testé et non celui émis. Pour éviter ce phénomène, le corps de la boucle est dupliqué: 

...
loop
  signal S, A in
    present S then emit A end;
    pause;
    emit S;
  end signal;
  signal S, A in
    present S then emit A end;
    pause;
    emit S;
  end signal
end loop
...
Il est désormais évident que le corps de la boucle ne pourra jamais être entièrement exécuté en un seul instant. Une étude sur la traduction d'un format intermédiaire d'Esterel en VHDL devra préciser comment résoudre ce point. En l'occurence, avec le format GRC, la question ne se pose pas car il traite en interne ce phénomne.

6.1.4   Dépendances

Un signal émis peut être destiné à être réceptionné par un thread concurrent. Ainsi, le langage devra si possible proposer un mécanisme permettant d'associer à un émetteur des récepteurs potentiels.

Conclusion

Ce document a présenté quelques formats représentant fidèlement la structure et la sémantique d'un programme Esterel. Au travers des diverses constructions graphiques images d'une instruction textuelle nous avons été amenés à déterminer quels formats pouvaient être de bons candidats pour une traduction VHDL.

Cependant, cette étude ne nous permet pas de nous prononcer sur le format adequat. De ce fait, quels critères liés à VHDL vont permettre d'exhiber le bon candidat? Une analyse mettant en relation l'expressivité de ces formats et le langage VHDL s'impose donc.

References

[1]
G. Berry & G. Gonthier, The Esterel synchronous programming language: design, semantics, implementation. Science of computer programming, 19(2):87--152, Nov. 1992

[2]
S. Edwards, Synopsys Inc, Compiling Esterel into Sequential Code. Proceedings of the 7th International Workshop on Hardwarw/Software Codesign (CODES'99), Rome, Italy, May 3--5, 1999

[3]
S. Edwards, Columbia University, An Esterel Compiler for Large Control-Dominated Systems. Department of Computer Sciences

[4]
D. Potop--Butucaru Fast Redundancy Elimination Using High-Level Structural Information from Esterel RR 4330 (C) 2002 INRIA Sophia-Antipolis

[5]
D. Potop--Butucaru, R. de Simone Optimizing for Faster Simulation of Esterel Programs ENSMP/CMA/INRIA Sophia-Antipolis
1
registre associé au start
This document was translated from LATEX by HEVEA.