Context-sensitive timing analysis of Esterel programs

ABSTRACT

Traditionally, synchronous languages, such as Esterel, have been compiled into hardware, where timing analysis is relatively easy. When compiled into software -- e.g., into sequential C code -- very conservative estimation techniques have been used, where the focus has only been on obtaining safe timing estimates and not on the cost of the implementation. While this was acceptable in avionics, efficient implementations and hence tight timing estimates are needed in more cost-sensitive application domains. Lately, a number of advances in Worst-Case Execution Time (WCET) analysis techniques, coupled with the growing use of software in domains such as automotives, have led to a considerable interest in timing analysis of code generated from Esterel specifications. In this paper we propose techniques to obtain tight estimates on the processing time of input events by sequential C code generated from Esterel programs. Execution of an Esterel program -- as in all other synchronous languages -- is logically made up of a sequence of clock ticks. In reality, they take non-zero time which depends on the generated C code as well as the underlying hardware platform on which this code is executed. Apart from exploiting the specific structure of this C code to obtain tight WCET estimates, we capture program-level contexts across ticks in order to obtain tight estimates on response times of events whose processing spans across multiple clock ticks. Such tighter estimates immediately translate into more cost-effective implementations. Our experimental results with realistic case studies show 30% reduction in timing estimates when program level context information is taken into account.

REFERENCES

• 1: AbsInT GmbH, http://www.absint.com/.
• 2: M. Boldt, C. Traulsen, and R. von Hanxleden. Worst Case Reaction Time Analysis of Concurrent Reactive Programs. Electronic Notes in Theoretical Computer Science (ENTCS), 203(4):65--79, 2008.
• 3: F. Boussinot and R. de Simone. The Esterel language. Proceedings of the IEEE, 9(79):1270--1282, 1991.
• 4: S. A. Edwards. The Estbench Esterel Benchmark Suite. http://www1.cs.columbia.edu/sedwards/software.html, 2003.
• 5: S. A. Edwards and J. Zeng. Code Generation in the Columbia Esterel Compiler. EURASIP Journal on Embedded Systems, 2007.
• 6: A. Benveniste et al. The synchronous languages 12 years later. Proceedings of the IEEE, 91(1):64--83, 2003.
• 7: 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.
• 8: V. Bertin et al. TAXYS = Esterel + Kronos. A tool for verifying real-time properties of embedded systems. 2001.
• 9: X. Li et al. Chronos: A timing analyzer for embedded software. Science of Computer Programming, 69(1--3), 2007. http://www.comp.nus.edu.sg/~rpembed/chronos.
• 10: L. Ju, B. K. Huynh, A. Roychoudhury, and S. Chakraborty. Performance debugging of Esterel specifications. In International Conference on Hardware Software Codesign and System Synthesis (CODES-ISSS), 2008.
• 11: G. Logothetis, K. Schneider, and C. Metzler. Generating formal models for real-time verification by exact low-level runtime analysis of synchronous programs. In RTSS, 2003.
• 12: M. J. K. Nielsen. TURBOchannel. In 36th IEEE Computer Society International Conference, COMPCON, 1991.
• 13: D. Potop-Butucaru, S. A. Edwards, and G. Berry. Compiling ESTEREL. Springer, 2007.
• 14: T. Ringler. Static worst-case execution time analysis of synchronous programs. In 5th Ada-Europe International Conference, LNCS 1845, 2000.
• 15: R. K. Shyamasundar and J. V. Aghav. Realizing real-time systems from synchronous language specifications. In RTSS Work-in-Progress Session, 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Design, Languages, Performance

Keywords:
Esterel, synchronous programming, worst-case execution time (WCET) analysis