Expressing and Exploiting Conflicts over Paths in WCET Analysis

Authors Vincent Mussot, Jordy Ruiz, Pascal Sotin, Marianne de Michiel, Hugues Cassé



PDF
Thumbnail PDF

File

OASIcs.WCET.2016.3.pdf
  • Filesize: 0.63 MB
  • 11 pages

Document Identifiers

Author Details

Vincent Mussot
Jordy Ruiz
Pascal Sotin
Marianne de Michiel
Hugues Cassé

Cite AsGet BibTex

Vincent Mussot, Jordy Ruiz, Pascal Sotin, Marianne de Michiel, and Hugues Cassé. Expressing and Exploiting Conflicts over Paths in WCET Analysis. In 16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016). Open Access Series in Informatics (OASIcs), Volume 55, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/OASIcs.WCET.2016.3

Abstract

The presence of infeasible paths in a program is a source of imprecision in the Worst-Case Execution Time (WCET) analysis. Detecting, expressing and exploiting such paths can improve the WCET estimation or, at least, improve the confidence we have in estimation precision. In this article, we propose an extension of the FFX format to express conflicts over paths and we detail two ways of enhancing the WCET analyses with that information. We demonstrate and compare these techniques on the Mälardalen benchmark suite and on C code generated from Esterel.
Keywords
  • WCET analysis
  • Infeasible paths
  • Path conflicts
  • IPET
  • CFG transformation

Metrics

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

References

  1. Clément Ballabriga, Hugues Cassé, Christine Rochange, and Pascal Sainrat. OTAWA: an open toolbox for adaptive WCET analysis. In 8th IFIP WG 10.2 International Workshop on Software Technologies for Embedded and Ubiquitous Systems (SEUS 2010), 2010. URL: http://dx.doi.org/10.1007/978-3-642-16256-5_6.
  2. Armelle Bonenfant, Hugues Cassé, Marianne De Michiel, Jens Knoop, Laura Kovács, and Jakob Zwirchmayr. FFX: a portable WCET annotation language. In 20th International Conference on Real-Time and Network Systems (RTNS 2012), 2012. URL: http://dx.doi.org/10.1145/2392987.2392999.
  3. Jakob Engblom and Andreas Ermedahl. Modeling complex flows for worst-case execution time analysis. In 21st IEEE Real-Time Systems Symposium (RTSS 2000), 2000. URL: http://dx.doi.org/10.1109/REAL.2000.896006.
  4. Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Björn Lisper. The mälardalen WCET benchmarks: Past, present and future. In 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010), 2010. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2010.136.
  5. 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), 2006. URL: http://dx.doi.org/10.1109/RTSS.2006.12.
  6. Raimund Kirner, Jens Knoop, Adrian Prantl, Markus Schordan, and Albrecht Kadlec. Beyond loop bounds: comparing annotation languages for worst-case execution time analysis. Software and System Modeling, 10(3), 2011. URL: http://dx.doi.org/10.1007/s10270-010-0161-0.
  7. Jens Knoop, Laura Kovács, and Jakob Zwirchmayr. WCET squeezing: on-demand feasibility refinement for proven precise wcet-bounds. In 21st International Conference on Real-Time Networks and Systems (RTNS 2013), 2013. URL: http://dx.doi.org/10.1145/2516821.2516847.
  8. Vincent Mussot and Pascal Sotin. Improving WCET analysis precision through automata product. In 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2015), 2015. URL: http://dx.doi.org/10.1109/RTCSA.2015.11.
  9. Pascal Raymond. A general approach for expressing infeasibility in implicit path enumeration technique. In International Conference on Embedded Software (EMSOFT 2014), 2014. URL: http://dx.doi.org/10.1145/2656045.2656046.
  10. 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), 2015. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2015.95.
  11. Vivy Suhendra, Tulika Mitra, Abhik Roychoudhury, and Ting Chen. Efficient detection and exploitation of infeasible paths for software timing analysis. In 43rd Design Automation Conference (DAC 2006), 2006. URL: http://dx.doi.org/10.1145/1146909.1147002.
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