Performance debugging of Esterel specifications

ABSTRACT

Synchronous languages like Esterel have been widely adopted for designing reactive systems in safety-critical domains such as avionics. Specifications written in Esterel are based on the underlying "synchrony hypothesis", where the computation/communication associated with the processing of all events occurring within the same "clock tick" are assumed to happen instantaneously (or in zero time). In reality, Esterel specifications get compiled to implementations (such as C code) which do not satisfy the perfect synchrony assumption. Hence, platform-specific timing analysis of such implementations is an important research topic. Interest in this area has lately been renewed with the recent advances in Worst-case Execution Time (WCET)analysis techniques. In this paper we perform WCET analysis on sequential C code and exploit the structure of the code generated from Esterel specifications to obtain tight WCET estimates. Such estimates can validate Esterel-level assumptions on the instantaneous processing of signals or events that occur together. More importantly, they can be used to identify parts of the specification which might pose as timing/performance bottlenecks with respect to the underlying platform. This is done by exploiting traceability links between Esterel specifications and the generated C code, which map the time-critical computations at the C-level back to the Esterel-level. This not only allows a designer to optimize or simplify Esterel specifications, but also choose/configure suitable implementation platforms. We show the results of our WCET analysis on a set of standard Esterel benchmarks and illustrate the utility of our model-code traceability technique using an Esterel specification of a reflex game application.

REFERENCES

• 1: A. Benveniste, P. Caspi, S. A. Edwards, N. Halbwachs, P. Le Guernic, and R. de Simone. The synchronous languages 12 years later. Proceedings of the IEEE, 91(1):64--83, 2003.
• 2: Albert Benveniste , Paul Le Guernic , Christian Jacquemot, Synchronous programming with events and relations: the SIGNAL language and its semantics, Science of Computer Programming, v.16 n.2, p.103-149, Sept. 1991 [doi>10.1016/0167-6423(91)90001-E]
• 3: R. Bernhard, G. Berry, F. Boussinot, G. Gonthier, A. Ressouche, J. P. Rigault, and J. M. Tanzi. Programming a Reflex game in Esterel v3. Technical Report 07/91, Rapport de Recherche, INRIA, Sophia-Antipolis, France, June 1991.
• 4: G. Berry. Mechanized reasoning and hardware design, chapter Esterel on hardware. Prentice-Hall, 1992.
• 5: V. Bertin, E. Closse, M. Poize, J. Pulou, J. Sifakis, P. Venier, D. Weil, and S. Yovine. TAXYS= Esterel+Kronos. A tool for verifying real-time properties of embedded systems. Proceedings of the 40th IEEE Conference on Decision and Control, 3(4-7), 2001.
• 6: Marian Boldt , Claus Traulsen , Reinhard von Hanxleden, Worst Case Reaction Time Analysis of Concurrent Reactive Programs, Electronic Notes in Theoretical Computer Science (ENTCS), v.203 n.4, p.65-79, June, 2008 [doi>10.1016/j.entcs.2008.05.011]
• 7: F. Boussinot and R. de Simone. The Esterel language. Proceedings of the IEEE, 9(79):1270--1282, 1991.
• 8: S.A. Edwards. The Estbench Esterel Benchmark Suite. http://www1.cs.columbia.edu/ sedwards/software.html, 2003.
• 9: S.A. Edwards and J. Zeng. Code Generation in the Columbia Esterel Compiler. EURASIP Journal on Embedded Systems, 2007.
• 10: R. Heckmann et al. Combining a high-level design tool for safety-critical systems with a tool for WCET analysis on executables. In 4th European Congress on Embedded and Real Time Software (ERTS), 2008.
• 11: N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud. The synchronous dataflow programming language Lustre. Proceedings of the IEEE, 79(9), 1991.
• 12: Xianfeng Li , Yun Liang , Tulika Mitra , Abhik Roychoudhury, Chronos: A timing analyzer for embedded software, Science of Computer Programming, v.69 n.1-3, p.56-67, December, 2007 [doi>10.1016/j.scico.2007.01.014]
• 13: G. Logothetis , K. Schneider , C. Metzler, Generating Formal Models for Real-Time Verification by Exact Low-Level Runtime Analysis of Synchronous Programs, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.256, December 03-05, 2003
• 14: D. Potop-Butucaru, S.A. Edwards, and G. Berry. Compiling ESTEREL. Springer, 2007.
• 15: Thomas Ringler, Static Worst-Case Execution Time Analysis of Synchronous Programs, Proceedings of the 5th Ada-Europe International Conference on Reliable Software Technologies, p.56-68, June 26-30, 2000
• 16: R. K. Shyamasundar and J. V. Aghav. Realizing real-time systems from synchronous language specifications. In RTSS Work-in-Progress Session, 2000.
• 17: Vivy Suhendra , Tulika Mitra , Abhik Roychoudhury , Ting Chen, Efficient detection and exploitation of infeasible paths for software timing analysis, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147002]
• 18: Reinhard Wilhelm , Jakob Engblom , Andreas Ermedahl , Niklas Holsti , Stephan Thesing , David Whalley , Guillem Bernat , Christian Ferdinand , Reinhold Heckmann , Tulika Mitra , Frank Mueller , Isabelle Puaut , Peter Puschner , Jan Staschulat , Per Stenström, The worst-case execution-time problem—overview of methods and survey of tools, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.3, p.1-53, April 2008 [doi>10.1145/1347375.1347389]

INDEX TERMS

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

General Terms:
Design, Languages, Performance

Keywords:
Esterel, WCET analysis, synchronous programming