An Implementation of Constructive Synchronous Programs in POLIS

Gérard Berry1, Ellen M. Sentovich2
1Ecole des Mines de Paris and INRIA, Sophia-Antipolis Cedex, France
2Cadence Berkeley Laboratories, Berkeley, USA

Tóm tắt

Design tools for embedded reactive systems commonly use a model of computation that employs both synchronous and asynchronous communication styles. We form a junction between these two with an implementation of synchronous languages and circuits (Esterel) on asynchronous networks (POLIS). We implement fact propagation, the key concept of synchronous constructive semantics, on an asynchronous non-deterministic network: POLIS nodes (CFSMs) save state locally to deduce facts, and the network globally propagates facts between them. The result is a correct implementation of the synchronous input/output behavior of the program. Our model is compositional, and thus permits implementations at various levels of granularity from one CFSM per circuit gate to one CFSM per circuit. This allows one to explore various tradeoffs between synchronous and asynchronous implementations.

Từ khóa


Tài liệu tham khảo

R. Amadio and P.L. Curien, Domains and Lambda-Calculi, Cambridge University Press, 1998.

C. André, “Representation and analysis of reactive behaviors: A synchronous approach,” in Proc. CESA'96, Lille, France, July 1996.

F. Balarin, M. Chiodo, P. Giusto, H. Hsieh, A. Jurecska, L. Lavagno, C. Passerone, A. Sangiovanni-Vincentelli, E. Sentovich, K. Suzuki, and B. Tabbara, Hardware-Software Co-Design of Embedded Systems: The POLIS Approach, Kluwer Academic Press, June 1997.

F. Balarin, H. Hsieh, A. Jurecska, L. Lavagno, and A. Sangiovanni-Vincentelli, “Formal verification of embedded systems based on CFSM networks,” in Proceedings of the Design Automation Conference, 1996.

G. Berry, The Constructive Semantics of Esterel, Draft book, preliminary version available from www.esterel.org, 1995.

G. Berry, “The foundations of Esterel,” in G. Plotkin, C. Stirling, and M. Tofte (Eds.), Proof, Language, and Interaction: Essays in Honour of Robin Milner, MIT Press, 2000.

G. Berry and G. Gonthier, “The Esterel synchronous programming language: Design, semantics, implementation,” Science of Computer Programming, Vol. 19, No. 2, pp. 87–152, 1992.

J.A. Brzozowski and C.-J. Seger, Asynchronous Circuits, Springer-Verlag, New York, 1995, Monographs in Computer Science.

B. Caillaud, P. Caspi, A. Girault, and C. Jard, “Distributing automata for asynchronous networks of processors,” European Journal of Automation (RAIRO-APII-JESA), Vol. 31, No. 3, pp. 503–524, 1997.

P. Caspi, A. Girault, and D. Pilaud, “Distributing reactive systems,” in Seventh International Conference on Parallel and Distributed Computing Systems, PDCS'94, Las Vegas, USA, Oct. 1994. ISCA.

P. Le Guernic, M. Le Borgne, T. Gauthier, and C. Le Maire, “Programming real-time applications with signal,” Another Look at Real Time Programming, Proceedings of the IEEE, Special Issue, Sept. 1991.

N. Halbwachs, Synchronous Programming of Reactive Systems, Kluwer, 1993.

N. Halbwachs, P. Caspi, and D. Pilaud, “The synchronous dataflow programming language Lustre,” Another Look at Real Time Programming, Proceedings of the IEEE, Special Issue, Sept. 1991.

D. Harel, “Statecharts: A visual approach to complex systems,” Science of Computer Programming, Vol. 8, pp. 231–274, 1987.

C.A.R. Hoare, Communicating Sequential Processes, Prentice-Hall, UK, 1985, International Series in Computer Science.

G. Kahn, “The semantics of a simple language for parallel programming,” in Proc. of the IFIP Congress 74, North-Holland Publishing Co., 1974.

S. Malik, “Analysis of cyclic combinational circuits,” IEEE Trans. Computer-Aided Design, Vol. 13, No. 7, pp. 950–956, 1994.

G. Plotkin, “LCF as a programming language,” Theoretical Computer Science, Vol. 5, No. 3, pp. 223–256, 1977.

T. Shiple, “Formal analysis of cyclic circuits,” PhD thesis, U.C. Berkeley, 1996.

T. Shiple, G. Berry, and H. Touati, “Constructive analysis of cyclic circuits,” in Proceedings of European Design and Test Conference, March 1996.

H. Toma, “Analyse Constructive et Optimisation Séquentielle des Circuits Génerés 'a partir du Langage Synchrone Réactif Esterel,” PhD thesis, Ecole des Mines de Paris, Centre de Mathématiques Appliquées, 1997.