Compiling Esterel into sequential code

ABSTRACT

Embedded real-time software systems often need fine-grained parallelism and precise control over time, things typical real-time operating systems do not provide. The Esterel language has both, but Existing compilers produce slow code for large programs. This paper presents the first Esterel compiler able to produce small, fast code for large programs. It can produce code half the size and up to a hundred times faster than code from existing compilers. Esterel's semantics allow the compiler to statically schedule concurrency and synthesize code that efficiently and predictably simulates context switches. The main contribution is an algorithm that synthesizes an efficient sequential program from the concurrent control-flow graph used as an intermediate representation. These techniques could be applied to any language with fine-grained parallelism.

REFERENCES

• 1: G. Berry. Esterel on hardware. Philosophical Transactions of the Royal Society of London. Series A, 339:87-1o4, 1992.
• 2: G. Berry. The constructive semantics of pure Esterel. Book in preparation, 1996.
• 3: Gérard Berry , Amar Bouali , Xavier Fornari , Emmanuel Ledinot , Eric Nassor , Robert de Simone, Esterel: a formal method applied to avionic software development, Science of Computer Programming, v.36 n.1, p.5-25, Jan.1.2000 [doi>10.1016/S0167-6423(99)00015-5]
• 4: Gérard Berry , Georges Gonthier, The ESTEREL synchronous programming language: design, semantics, implementation, Science of Computer Programming, v.19 n.2, p.87-152, Nov. 1992 [doi>10.1016/0167-6423(92)90005-V]
• 5: V. Bertin, M. Poize, and J. Pulou. Une nouvelle m4thode de compilation pour le language ESTEREL {A new method for compiling the Esterel language}. In Proceedings of GRAISyHM-AAA, Lille, France, Mar. 1999. In French.
• 6: Joseph Buck , Radha Vaidyanathan, Heterogeneous modeling and simulation of embedded systems in El Greco, Proceedings of the eighth international workshop on Hardware/software codesign, p.142-146, May 2000, San Diego, California, United States [doi>10.1145/334012.334042]
• 7: Massimiliano Chiodo , Daniel Engels , Paolo Giusto , Harry Hsieh , Attila Jurecska , Luciano Lavagno , Kei Suzuki , Alberto Sangiovanni-Vincentelli, A case study in computer-aided co-design of embedded controllers, Design Automation for Embedded Systems, v.1 n.1-2, p.51-67, Jan. 1996 [doi>10.1007/BF00134683]
• 8: Massimiliano Chiodo , Paolo Guisto , Attila Jurecska , Luciano Lavagno , Ellen Sentovich , Harry Hsieh , Kei Suzuki , Alberto Sangiovanni-Vincentelli, Synthesis of software programs for embedded control application, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.587-592, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217594]
• 9: François Clouté , Jean-Noël Contensou , Daniel Esteve , Pascal Pampagnin , Philippe Pons , Yves Favard, Hardware/software co-design of an avionics communication protocol interface system: an industrial case study, Proceedings of the seventh international workshop on Hardware/software codesign, p.48-52, March 1999, Rome, Italy [doi>10.1145/301177.301203]
• 10: Luciano Lavagno , Ellen Sentovich, ECL: a specification environment for system-level design, Proceedings of the 36th ACM/IEEE conference on Design automation, p.511-516, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309989]
• 11: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 12: Bill Lin, Software synthesis of process-based concurrent programs, Proceedings of the 35th annual conference on Design automation, p.502-505, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277182]
• 13: Marco Sgroi , Luciano Lavagno , Yosinori Watanabe , Alberto Sangiovanni-Vincentelli, Synthesis of embedded software using free-choice Petri nets, Proceedings of the 36th ACM/IEEE conference on Design automation, p.805-810, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310073]
• 14: Thomas R. Shiple , Gerard Berry , Herve Touati, Constructive Analysis of Cyclic Circuits, Proceedings of the 1996 European conference on Design and Test, p.328, March 11-14, 1996
• 15: Berry et al.'s Esterel site: http://www.inria.fr/meije/esterel/

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Design, Languages, Measurement, Performance, Theory