Skip to main content
Erschienen in: Real-Time Systems 5/2012

01.09.2012

Performance debugging of Esterel specifications

verfasst von: Lei Ju, Bach Khoa Huynh, Abhik Roychoudhury, Samarjit Chakraborty

Erschienen in: Real-Time Systems | Ausgabe 5/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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”, which needs to be validated when Esterel specifications get compiled to real implementations (such as C code). In this work, we present a model-driven and architecture-aware timing analysis framework for C code generated from Esterel and executed on general-purpose processors. By integrating model-level information into the traditional timing analysis, we can efficiently compute accurate time estimates via systematically eliminating a large number of infeasible paths in the generated code. Experimental results show that with our proposed intermediate representation level infeasible path analysis in the model compilation, we obtain up to 16.1 % tighter WCET estimates compared to the traditional assembly code level infeasible path detection with substantially less analysis time. Furthermore, by maintaining the traceability links between Esterel specifications and the generated C code, we are able to map the time-critical computations at the C-level back to the Esterel-level.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Subsequent in the sense of the topological order of the control flow DAG.
 
Literatur
Zurück zum Zitat André C (2003) Semantics of synccharts. Technical report, Sophia-Antipolis, France, April 2003 André C (2003) Semantics of synccharts. Technical report, Sophia-Antipolis, France, April 2003
Zurück zum Zitat Austin TM, Larson E, Ernst D (2002) SimpleScalar: an infrastructure for computer system modeling. IEEE Trans Comput 35(2):59–67 Austin TM, Larson E, Ernst D (2002) SimpleScalar: an infrastructure for computer system modeling. IEEE Trans Comput 35(2):59–67
Zurück zum Zitat Benveniste A, Le Guernic P, Jacquemot C (1991) Synchronous programming with events and relations: the SIGNAL language and its semantics. Sci Comput Program 16(2):103–149 MathSciNetMATHCrossRef Benveniste A, Le Guernic P, Jacquemot C (1991) Synchronous programming with events and relations: the SIGNAL language and its semantics. Sci Comput Program 16(2):103–149 MathSciNetMATHCrossRef
Zurück zum Zitat Benveniste A, Caspi P, Edwards SA, Halbwachs N, Le Guernic P, De Simone R (2003) The synchronous languages 12 years later. Proc IEEE 91(1):64–83 CrossRef Benveniste A, Caspi P, Edwards SA, Halbwachs N, Le Guernic P, De Simone R (2003) The synchronous languages 12 years later. Proc IEEE 91(1):64–83 CrossRef
Zurück zum Zitat Bernhard R, Berry G, Boussinot F, Gonthier G, Ressouche A, Rigault JP, Tanzi JM (June 1991) Programming a Reflex game in Esterel v3. Technical report 07/91, Rapport de Recherche, INRIA, Sophia-Antipolis, France Bernhard R, Berry G, Boussinot F, Gonthier G, Ressouche A, Rigault JP, Tanzi JM (June 1991) Programming a Reflex game in Esterel v3. Technical report 07/91, Rapport de Recherche, INRIA, Sophia-Antipolis, France
Zurück zum Zitat Berry G (1992) Esterel on hardware. In: Mechanized reasoning and hardware design. Prentice-Hall, New York Berry G (1992) Esterel on hardware. In: Mechanized reasoning and hardware design. Prentice-Hall, New York
Zurück zum Zitat Bertin V, Closse E, Poize M, Pulou J, Sifakis J, Venier P, Weil D, Yovine S (2001) TAXYS = Esterel + Kronos. A tool for verifying real-time properties of embedded systems. In: Proceedings of the 40th IEEE conference on decision and control, vol 3(4–7) Bertin V, Closse E, Poize M, Pulou J, Sifakis J, Venier P, Weil D, Yovine S (2001) TAXYS = Esterel + Kronos. A tool for verifying real-time properties of embedded systems. In: Proceedings of the 40th IEEE conference on decision and control, vol 3(4–7)
Zurück zum Zitat Boldt M, Traulsen C, von Hanxleden R (2008) Worst case reaction time analysis of concurrent reactive programs. Electron Notes Theor Comput Sci 203(4):65–79 CrossRef Boldt M, Traulsen C, von Hanxleden R (2008) Worst case reaction time analysis of concurrent reactive programs. Electron Notes Theor Comput Sci 203(4):65–79 CrossRef
Zurück zum Zitat Boussinot F, De Simone R (1991) The Esterel language. Proc IEEE 9(79):1270–1282 Boussinot F, De Simone R (1991) The Esterel language. Proc IEEE 9(79):1270–1282
Zurück zum Zitat Chang PY, Hao E, Patt YN (1997) Target prediction for indirect jumps. In: Proceedings of the 24th annual international symposium on computer architecture Chang PY, Hao E, Patt YN (1997) Target prediction for indirect jumps. In: Proceedings of the 24th annual international symposium on computer architecture
Zurück zum Zitat Edwards SA, Zeng J (2007) Code generation in the Columbia Esterel compiler. EURASIP J Embed Syst Edwards SA, Zeng J (2007) Code generation in the Columbia Esterel compiler. EURASIP J Embed Syst
Zurück zum Zitat Ferdinand C (1999) Cache behavior prediction for real-time systems. PhD thesis, Saarland University Ferdinand C (1999) Cache behavior prediction for real-time systems. PhD thesis, Saarland University
Zurück zum Zitat Ferdinand C et al. (2001) Reliable and precise WCET determination for a real-life processor. In: International conference on embedded software (EMSOFT) Ferdinand C et al. (2001) Reliable and precise WCET determination for a real-life processor. In: International conference on embedded software (EMSOFT)
Zurück zum Zitat Gustafsson J, Ermedahl A, Lisper B (2006) Algorithms for infeasible path calculation. In: International workshop on Worst-Case execution time (WCET) analysis Gustafsson J, Ermedahl A, Lisper B (2006) Algorithms for infeasible path calculation. In: International workshop on Worst-Case execution time (WCET) analysis
Zurück zum Zitat Gustafsson J, Ermedahl A, Sandberg C, Lisper B (2006) Automatic derivation of loop bounds and infeasible paths for wcet analysis using abstract execution. In: IEEE international real-time systems symposium (RTSS) Gustafsson J, Ermedahl A, Sandberg C, Lisper B (2006) Automatic derivation of loop bounds and infeasible paths for wcet analysis using abstract execution. In: IEEE international real-time systems symposium (RTSS)
Zurück zum Zitat Halbwachs N, Caspi P, Raymond P, Pilaud D (1991) The synchronous dataflow programming language Lustre. Proc IEEE 79(9) Halbwachs N, Caspi P, Raymond P, Pilaud D (1991) The synchronous dataflow programming language Lustre. Proc IEEE 79(9)
Zurück zum Zitat Heckmann R et al. (2008) 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) Heckmann R et al. (2008) 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)
Zurück zum Zitat Ju L, Huynh BK, Roychoudhury A, Chakraborty S (2008) Performance debugging of Esterel specifications. In: International conference on hardware-software codesign and system synthesis (CODES + ISSS) Ju L, Huynh BK, Roychoudhury A, Chakraborty S (2008) Performance debugging of Esterel specifications. In: International conference on hardware-software codesign and system synthesis (CODES + ISSS)
Zurück zum Zitat Kuo M, Sinha R, Roop P (2011) Efficient WCRT analysis of synchronous programs using reachability. In: Design automation conference (DAC) Kuo M, Sinha R, Roop P (2011) Efficient WCRT analysis of synchronous programs using reachability. In: Design automation conference (DAC)
Zurück zum Zitat Lee C-G et al. (1998) Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Trans Comput 47(6):700–713 MathSciNetCrossRef Lee C-G et al. (1998) Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Trans Comput 47(6):700–713 MathSciNetCrossRef
Zurück zum Zitat Li YTS, Malik S (1995) Performance analysis of embedded software using implicit path enumeration. In: ACM SIGPLAN notices, vol 30, pp 88–98 Li YTS, Malik S (1995) Performance analysis of embedded software using implicit path enumeration. In: ACM SIGPLAN notices, vol 30, pp 88–98
Zurück zum Zitat Li X, von Hanxleden R (2010) Multi-threaded reactive programming—the Kiel Esterel processor. IEEE Trans Comput Li X, von Hanxleden R (2010) Multi-threaded reactive programming—the Kiel Esterel processor. IEEE Trans Comput
Zurück zum Zitat Li YTS, Malik S, Wolfe A (1999) Performance estimation of embedded software with instruction cache modeling. ACM Trans Des Autom Electron Syst 4(3):257–279 CrossRef Li YTS, Malik S, Wolfe A (1999) Performance estimation of embedded software with instruction cache modeling. ACM Trans Des Autom Electron Syst 4(3):257–279 CrossRef
Zurück zum Zitat Li X, Lukoschus J, Boldt M, Harder M, Von Hanxleden R (2005) An Esterel processor with full preemption support and its worst case reaction time analysis. In: International conference on compilers, architectures and synthesis for embedded systems (CASES) Li X, Lukoschus J, Boldt M, Harder M, Von Hanxleden R (2005) An Esterel processor with full preemption support and its worst case reaction time analysis. In: International conference on compilers, architectures and synthesis for embedded systems (CASES)
Zurück zum Zitat Li X, Roychoudhury A, Mitra T (2006) Modeling out-of-order processors for wcet analysis. Real-Time Syst 34(3):195–227 MATHCrossRef Li X, Roychoudhury A, Mitra T (2006) Modeling out-of-order processors for wcet analysis. Real-Time Syst 34(3):195–227 MATHCrossRef
Zurück zum Zitat Logothetis G, Schneider K (2003) Exact high level WCET analysis of synchronous programs by symbolic state space exploration. In: Proceedings of the conference on design, automation and test in Europe (DATE) Logothetis G, Schneider K (2003) Exact high level WCET analysis of synchronous programs by symbolic state space exploration. In: Proceedings of the conference on design, automation and test in Europe (DATE)
Zurück zum Zitat Logothetis G, Schneider K, Metzler C (2003) Exact low-level runtime analysis of synchronous programs for formal verification of real-time systems. In: Forum on design languages (FDL) Logothetis G, Schneider K, Metzler C (2003) Exact low-level runtime analysis of synchronous programs for formal verification of real-time systems. In: Forum on design languages (FDL)
Zurück zum Zitat Logothetis G, Schneider K, Metzler C (2003) Generating formal models for real-time verification by exact low-level runtime analysis of synchronous programs. In: IEEE international real-time systems symposium (RTSS) Logothetis G, Schneider K, Metzler C (2003) Generating formal models for real-time verification by exact low-level runtime analysis of synchronous programs. In: IEEE international real-time systems symposium (RTSS)
Zurück zum Zitat Mendler M, von Hanxleden R, Traulsen C (2009) WCRT algebra and interfaces for Esterel-style synchronous processing. In: Design, automation and test in Europe (DATE) Mendler M, von Hanxleden R, Traulsen C (2009) WCRT algebra and interfaces for Esterel-style synchronous processing. In: Design, automation and test in Europe (DATE)
Zurück zum Zitat Negi HS, Mitra T, Roychoudhury A (2003) Accurate estimation of cache-related preemption delay. In: International conference on hardware-software codesign and system synthesis (CODES + ISSS) Negi HS, Mitra T, Roychoudhury A (2003) Accurate estimation of cache-related preemption delay. In: International conference on hardware-software codesign and system synthesis (CODES + ISSS)
Zurück zum Zitat Potop-Butucaru D, de Simone R, Talpin JP (2004) The synchronous hypothesis and synchronous languages. In: The embedded systems handbook Potop-Butucaru D, de Simone R, Talpin JP (2004) The synchronous hypothesis and synchronous languages. In: The embedded systems handbook
Zurück zum Zitat Potop-Butucaru D, Edwards SA, Berry G (2007) Compiling ESTEREL. Springer, Berlin Potop-Butucaru D, Edwards SA, Berry G (2007) Compiling ESTEREL. Springer, Berlin
Zurück zum Zitat Ringler T (2000) Static worst-case execution time analysis of synchronous programs. In: 5th Ada-Europe international conference. LNCS, vol 1845 Ringler T (2000) Static worst-case execution time analysis of synchronous programs. In: 5th Ada-Europe international conference. LNCS, vol 1845
Zurück zum Zitat Roop P, Andalam S, von Hanxleden R, Yuan S, Traulsen C (2009) Tight WCRT analysis for synchronous C programs. In: International conference on compilers, architectures and synthesis for embedded systems (CASES) Roop P, Andalam S, von Hanxleden R, Yuan S, Traulsen C (2009) Tight WCRT analysis for synchronous C programs. In: International conference on compilers, architectures and synthesis for embedded systems (CASES)
Zurück zum Zitat Shyamasundar RK, Aghav JV (2000) Realizing real-time systems from synchronous language specifications. In: RTSS work-in-progress session Shyamasundar RK, Aghav JV (2000) Realizing real-time systems from synchronous language specifications. In: RTSS work-in-progress session
Zurück zum Zitat Souyris J, Le Pavec E, Himbert G, Jégu V, Borios G, Heckmann R (2005) Computing the worst case execution time of an avionics program by abstract interpretation. In: International workshop on worst-case execution time (WCET) analysis Souyris J, Le Pavec E, Himbert G, Jégu V, Borios G, Heckmann R (2005) Computing the worst case execution time of an avionics program by abstract interpretation. In: International workshop on worst-case execution time (WCET) analysis
Zurück zum Zitat Suhendra V, Mitra T, Roychoudhury A, Chen T (2006) Efficient detection and exploitation of infeasible paths for software timing analysis. In: Design automation conference (DAC) Suhendra V, Mitra T, Roychoudhury A, Chen T (2006) Efficient detection and exploitation of infeasible paths for software timing analysis. In: Design automation conference (DAC)
Zurück zum Zitat Tan L, Wachter B, Lucas P, Wilhelm R (2009) Improving timing analysis for Matlab Simulink/Stateflow. In: MoDELS’09 ACES-MB workshop Tan L, Wachter B, Lucas P, Wilhelm R (2009) Improving timing analysis for Matlab Simulink/Stateflow. In: MoDELS’09 ACES-MB workshop
Zurück zum Zitat von Hanxleden R (2009) SyncCharts in C: a proposal for light-weight, deterministic concurrency. In: International conference on embedded software (EMSOFT) von Hanxleden R (2009) SyncCharts in C: a proposal for light-weight, deterministic concurrency. In: International conference on embedded software (EMSOFT)
Zurück zum Zitat Wilhelm R et al (2008) The worst-case execution time problem—overview of methods and survey of tools. ACM Trans Embed Comput Syst (TECS) 7(3) Wilhelm R et al (2008) The worst-case execution time problem—overview of methods and survey of tools. ACM Trans Embed Comput Syst (TECS) 7(3)
Zurück zum Zitat Yoong LH, Roop P, Salcic Z, Gruian F (2006) Compiling Esterel for distributed execution. In: International workshop on synchronous languages, applications, and programming (SLAP) Yoong LH, Roop P, Salcic Z, Gruian F (2006) Compiling Esterel for distributed execution. In: International workshop on synchronous languages, applications, and programming (SLAP)
Zurück zum Zitat Yuan S, Andalam S, Yoong LH, Roop PS, Salcic Z (2009) Starpro—a new multithreaded direct execution platform for Esterel. Electron Notes Theor Comput Sci 238(1):37–55 CrossRef Yuan S, Andalam S, Yoong LH, Roop PS, Salcic Z (2009) Starpro—a new multithreaded direct execution platform for Esterel. Electron Notes Theor Comput Sci 238(1):37–55 CrossRef
Metadaten
Titel
Performance debugging of Esterel specifications
verfasst von
Lei Ju
Bach Khoa Huynh
Abhik Roychoudhury
Samarjit Chakraborty
Publikationsdatum
01.09.2012
Verlag
Springer US
Erschienen in
Real-Time Systems / Ausgabe 5/2012
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI
https://doi.org/10.1007/s11241-012-9155-z

Premium Partner