Résumé
Cette séance a été dédiée à la production de circuits et codes logiciels efficaces à partir de programmes Esterel. Elle a d’abord traité le cas des boucles dans la traduction en circuits, qui pose le problème particulièrement délicat de la réincarnation des instructions, c’est-à-dire de la possibilité d’exécuter plusieurs fois successivement mais simultanément une même instruction au cours d’une même réaction. Cela ne pose pas de difficultés pour un interpréteur, mais, pour une compilation efficace, il faut recopier un nombre de fois suffisant une partie de ces instructions.
Nous avons montré comment passer graduellement d’une méthode triviale mais exponentielle à des méthodes quadratiques puis quasi linéaires, adoptées dans les compilateurs industriels, en rappelant pourquoi la sémantique constructive conduit à des circuits corrects même s’ils comportent des cycles combinatoires (voir le cours du 26 mars 2014).
Le cours a ensuite brièvement présenté une méthode radicalement différente de compilation plus efficace pour les cibles logicielles, initiée par Stephen Edwards à l’université de Columbia. Une fois la réincarnation traitée, et en tirant parti d’un encodage subtil des états et du fait que les tests logiciels n’évaluent qu’une seule branche alors que la propagation booléenne parcourt toujours les deux dans les circuits, cette méthode conduit à des performances meilleures que celles obtenues par la traduction de circuit, pouvant même devenir sublinéaire en la taille du programme. Une variante en a été implémentée dans le compilateur industriel Esterel v7 d’Esterel technologies dont j’ai dirigé le développement.
