Document Open Access Logo

The W-SEPT Project: Towards Semantic-Aware WCET Estimation

Authors Claire Maiza, Pascal Raymond, Catherine Parent-Vigouroux, Armelle Bonenfant, Fabienne Carrier, Hugues Cassé, Philippe Cuenot, Denis Claraz, Nicolas Halbwachs, Erwan Jahier, Hanbing Li, Marianne de Michiel, Vincent Mussot, Isabelle Puaut, Christine Rochange, Erven Rohou, Jordy Ruiz, Pascal Sotin, Wei-Tsun Sun

PDF
Thumbnail PDF

File

OASIcs.WCET.2017.9.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Claire Maiza
Pascal Raymond
Catherine Parent-Vigouroux
Armelle Bonenfant
Fabienne Carrier
Hugues Cassé
Philippe Cuenot
Denis Claraz
Nicolas Halbwachs
Erwan Jahier
Hanbing Li
Marianne de Michiel
Vincent Mussot
Isabelle Puaut
Christine Rochange
Erven Rohou
Jordy Ruiz
Pascal Sotin
Wei-Tsun Sun

Cite As Get BibTex

Claire Maiza, Pascal Raymond, Catherine Parent-Vigouroux, Armelle Bonenfant, Fabienne Carrier, Hugues Cassé, Philippe Cuenot, Denis Claraz, Nicolas Halbwachs, Erwan Jahier, Hanbing Li, Marianne de Michiel, Vincent Mussot, Isabelle Puaut, Christine Rochange, Erven Rohou, Jordy Ruiz, Pascal Sotin, and Wei-Tsun Sun. The W-SEPT Project: Towards Semantic-Aware WCET Estimation. In 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017). Open Access Series in Informatics (OASIcs), Volume 57, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/OASIcs.WCET.2017.9

Abstract

Critical embedded systems are generally composed of repetitive tasks that must meet hard timing constraints, such as termination deadlines. Providing an upper bound of the worst-case execution time (WCET) of such tasks at design time is necessary to guarantee the correctness of the system. In static WCET analysis, a main source of over-approximation comes from the complexity of the modern hardware platforms: their timing behavior tends to become more unpredictable because of features like caches, pipeline, branch prediction, etc. Another source of over-approximation comes from the software itself: WCET analysis may consider potential worst-cases executions that are actually infeasible, because of the semantics of the program or because they correspond to unrealistic inputs. The W-SEPT project, for "WCET, Semantics, Precision and Traceability", has been carried out to study and exploit the influence of program semantics on the WCET estimation. This paper presents the results of this project : a semantic-aware WCET estimation workflow for high-level designed systems.

Subject Classification

Keywords
  • Worst-case execution time analysis
  • Static analysis
  • Program analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Armelle Bonenfant, Fabienne Carrier, Hugues Cassé, Philippe Cuenot, Denis Claraz, Nicolas Halbwachs, Hanbing Li, Claire Maiza, Marianne De Michiel, Vincent Mussot, Catherine Parent-Vigouroux, Isabelle Puaut, Pascal Raymond, Erven Rohou, and Pascal Sotin. When the worst-case execution time estimation gains from the application semantics. In 8th European Congress on Embedded Real-Time Software and Systems (ERTS2 2016), Toulouse, France, 2016. Google Scholar
  2. Remy Boutonnet and Mihail Asavoae. The WCET analysis using counters - a preliminary assessment. In 8th JRWRTC, in conjunction with RTNS, Versailles, France, 2014. Google Scholar
  3. Florian Brandner, Stefan Hepp, and Alexander Jordan. Static profiling of the worst-case in real-time programs. In 20th International Conference on Real-Time and Network Systems (RTNS 12), Pont à Mousson, France, 2012. Google Scholar
  4. Hugues Cassé, Haluk Ozaktas, and Christine Rochange. A framework to quantify the overestimations of static wcet analysis. In 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015), volume 47 of OASIcs, pages 1-10. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2015.1.
  5. Patrick Cousot and Nicolas Halbwachs. Automatic discovery of linear restraints among variables of a program. In 5th ACM Symposium on Principles of Programming Languages (POPL'78), Tucson, Arizona, January 1978. Google Scholar
  6. Jan Gustafsson, Andreas Ermedahl, Christer Sandberg, and Björn Lisper. Automatic derivation of loop bounds and infeasible paths for WCET analysis using abstract execution. In 27th IEEE Real-Time Systems Symposium (RTSS 2006), Rio de Janeiro, Brazil, 2006. Google Scholar
  7. Nicolas Halbwachs, Paul Caspi, Pascal Raymond, and Daniel Pilaud. The synchronous dataflow programming language Lustre. Proceedings of the IEEE, 79(9):1305-1320, September 1991. Google Scholar
  8. Julien Henry, David Monniaux, and Matthieu Moy. Pagai: A path sensitive static analyser. Electronic Notes in Theoretical Computer Science, 289:15-25, 2012. Google Scholar
  9. Erwan Jahier, Simplice Djoko-Djoko, Chaouki Maiza, and Eric Lafont. Environment-model based testing of control systems: Case studies. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2014), Grenoble, France, 2014. Google Scholar
  10. Erwan Jahier, Nicolas Halbwachs, and Pascal Raymond. Engineering functional requirements of reactive systems using synchronous languages. In International Symposium on Industrial Embedded Systems (SIES 2013), 2013. Google Scholar
  11. Raimund Kirner, Peter Puschner, and Adrian Prantl. Transforming flow information during code optimization for timing analysis. Journal on Real-Time Systems, 45(1-2), 2010. Google Scholar
  12. Hanbing Li, Isabelle Puaut, and Erven Rohou. Traceability of flow information: Reconciling compiler optimizations and WCET estimation. In 22nd International Conference on Real-Time Networks and Systems (RTNS'14), Versailles, France, 2014. Google Scholar
  13. Hanbing Li, Isabelle Puaut, and Erven Rohou. Tracing flow information for tighter wcet estimation: Application to vectorization. In 21st IEEE International Conference on Embedded Systems and Real-Time Computing Systems and Applications, RTCSA'15, Hong Kong, China, 2015. Google Scholar
  14. Yau-Tsun Steven Li and Sharad Malik. Performance analysis of embedded software using implicit path enumeration. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 16(12), 1997. Google Scholar
  15. Vincent Mussot, Armelle Bonenfant, Pascal Sotin, Philippe Cuenot, and Denis Claraz. From relevant high-level properties to WCET computation improvement. In International Conference on Embedded Real Time Software and Systems (ERTS2 2013), Toulouse, France, 2013. Google Scholar
  16. Vincent Mussot, Jordy Ruiz, Pascal Sotin, Marianne de Michiel, and Hugues Cassé. Expressing and exploiting path conflicts in wcet analysis. In 16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016), volume 55 of OASIcs, pages 3:1-3:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2016.3.
  17. Vincent Mussot and Pascal Sotin. Improving WCET analysis precision through automata product. In 21st IEEE International Conference on Embedded Systems and Real-Time Computing Systems and Applications, RTCSA'15, Hong Kong, China, 2015. Google Scholar
  18. Pascal Raymond. Synchronous program verification with lustre/lesar. In S. Mertz and N. Navet, editors, Modeling and Verification of Real-Time Systems, chapter 6. ISTE/Wiley, 2008. Google Scholar
  19. Pascal Raymond. A general approach for expressing infeasibility in implicit path enumeration technique. In International Conference on Embedded Software (EMSOFT 2014), New Dehli, India, 2014. Google Scholar
  20. Pascal Raymond, Claire Maiza, Catherine Parent-Vigouroux, Fabienne Carrier, and Mihail Asavoae. Timing analysis enhancement for synchronous program. Real-Time Systems, pages 1-29, 2015. URL: http://dx.doi.org/10.1007/s11241-015-9219-y.
  21. Jordy Ruiz and Hugues Cassé. Using smt solving for the lookup of infeasible paths in binary programs. In 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015), volume 47 of OASIcs, pages 95-104. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2015.95.
  22. Vivy Suhendra, Tulika Mitra, Abhik Roychoudhury, and Ting Chen. Efficient detection and exploitation of infeasible paths for software timing analysis. In 43rd annual Design Automation Conference (DAC'06), San Francisco, California, 2006. Google Scholar
  23. Wei-Tsun SUN. A framework for simulate synchronous reactive programs and measure execution times to aid wcet analysis. Technical Report 27-06-2016, Verimag Research Report, 2016. Google Scholar
  24. 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, and Per Stenström. The worst-case execution-time problem - overview of methods and survey of tools. ACM Transactions on Embedded Computing Systems (TECS), 7(3), 2008. Google Scholar
  25. Youfeng Wu and James R. Larus. Static branch frequency and program profile analysis. In 27th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO94), San Jose, California, 1994. Google Scholar
  26. Jakob Zwirchmayr, Armelle Bonenfant, Marianne de Michiel, Hugues Cassé, Laura Kovács, and Jens Knoop. FFX: A portable WCET annotation language (regular paper). In 20th International Conference on Real-Time and Network Systems (RTNS 12), Pont à Mousson, France, 2012. Google Scholar
  27. Jakob Zwirchmayr, Pascal Sotin, Armelle Bonenfant, Denis Claraz, and Philippe Cuenot. Identifying relevant parameters to improve WCET analysis. In 14th International Workshop on Worst-Case Execution Time Analysis (WCET 2014), volume 39 of OASIcs, pages 93-102. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2014.93.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact