Document Open Access Logo

Compiler-based Extraction of Event Arrival Functions for Real-Time Systems Analysis

Authors Dominic Oehlert, Selma Saidi, Heiko Falk

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECRTS.2018.4.pdf
  • Filesize: 0.6 MB
  • 22 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
  • Software and its engineering → Compilers
  • Mathematics of computing → Integer programming
Keywords
  • compiler
  • real-time
  • event arrival functions
  • extraction

Metrics

Abstract

Event arrival functions are commonly required in real-time systems analysis. Yet, event arrival functions are often either modeled based on specifications or generated by using potentially unsafe captured traces. To overcome this shortcoming, we present a compiler-based approach to safely extract event arrival functions. The extraction takes place at the code-level considering a complete coverage of all possible paths in the program and resulting in a cycle accurate event arrival curve. In order to reduce the runtime overhead of the proposed algorithm, we extend our approach with an adjustable level of granularity always providing a safe approximation of the tightest possible event arrival curve. In an evaluation, we demonstrate that the required extraction time can be heavily reduced while maintaining a high precision.

Cite As Get BibTex

Dominic Oehlert, Selma Saidi, and Heiko Falk. Compiler-based Extraction of Event Arrival Functions for Real-Time Systems Analysis. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ECRTS.2018.4

Author Details

Dominic Oehlert
  • Hamburg University of Technology, Hamburg, Germany
Selma Saidi
  • Hamburg University of Technology, Hamburg, Germany
Heiko Falk
  • Hamburg University of Technology, Hamburg, Germany

References

  1. B. Akesson and K. Goossens. Architectures and modeling of predictable memory controllers for improved system integration. In Proceedings of the 2011 Design, Automation &Test in Europe Conference &Exhibition, 2011. URL: http://dx.doi.org/10.1109/DATE.2011.5763145.
  2. S. Altmeyer, C. Burguière, and R. Wilhelm. Computing the Maximum Blocking Time for Scheduling with Deferred Preemption. In Proceedings of the 2009 Software Technologies for Future Dependable Distributed Systems, 2009. URL: http://dx.doi.org/10.1109/STFSSD.2009.12.
  3. Sebastian Altmeyer, Robert I. Davis, Leandro Indrusiak, Claire Maiza, Vincent Nelis, and Jan Reineke. A Generic and Compositional Framework for Multicore Response Time Analysis. In Proceedings of the 2015 International Conference on Real Time and Networks Systems, 2015. URL: http://dx.doi.org/10.1145/2834848.2834862.
  4. Sebastian Altmeyer, Robert I. Davis, and Claire Maiza. Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. Real-Time Systems, 48(5), 2012. URL: http://dx.doi.org/10.1007/s11241-012-9152-2.
  5. Jonas Diemer, Philip Axer, and Rolf Ernst. Compositional Performance Analysis in Python with pyCPA. In Proceedings of the 2012 International Workshop on Analysis Tools and Methodologies for Embedded and Real-time System, 2012. Google Scholar
  6. Leonardo Ecco, Selma Saidi, Adam Kostrzewa, and Rolf Ernst. Real-time DRAM throughput guarantees for latency sensitive mixed QoS MPSoCs. In Proceedings of the 2015 IEEE International Symposium on Industrial Embedded Systems, 2015. URL: http://dx.doi.org/10.1109/SIES.2015.7185038.
  7. Heiko Falk, Sebastian Altmeyer, Peter Hellinckx, Björn Lisper, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Rasmus Bo Sørensen, Peter Wägemann, and Simon Wegener. TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research. In Proceedings of the 2016 International Workshop on Worst Case Execution Time Analysis, 2016. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2016.2.
  8. Heiko Falk and Paul Lokuciejewski. A Compiler Framework for the Reduction of Worst-Case Execution Times. Real-Time Systems, 46(2), 2010. URL: http://dx.doi.org/10.1007/s11241-010-9101-x.
  9. Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Björn Lisper. The Mälardalen WCET Benchmarks - Past, Present and Future. In Proceedings of the 2010 International Workshop on Worst-Case Execution Time Analysis, 2010. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2010.136.
  10. R. Henia, A. Hamann, M. Jersak, R. Racu, K. Richter, and R. Ernst. System level performance analysis - the SymTA/S approach. IEE Proceedings - Computers and Digital Techniques, 152(2), 2005. URL: http://dx.doi.org/10.1049/ip-cdt:20045088.
  11. Michael Jacobs, Sebastian Hahn, and Sebastian Hack. WCET Analysis for Multi-core Processors with Shared Buses and Event-driven Bus Arbitration. In Proceedings of the 2015 International Conference on Real Time and Networks Systems, 2015. URL: http://dx.doi.org/10.1145/2834848.2834872.
  12. Bisschop Johannes. AIMMS. Optimization Modeling. Haarlem, The Netherlands, 2009. Google Scholar
  13. Timon Kelter. WCET Analysis and Optimization for Multi-Core Real-Time Systems. PhD thesis, TU Dortmund University, Dortmund / Germany, 2015. Google Scholar
  14. J. C. Kleinsorge, H. Falk, and P. Marwedel. Simple analysis of partial worst-case execution paths on general control flow graphs. In Proceedings of the 2013 International Conference on Embedded Software, 2013. URL: http://dx.doi.org/10.1109/EMSOFT.2013.6658594.
  15. Adam Kostrzewa, Selma Saidi, and Rolf Ernst. Dynamic Control for Mixed-Critical Networks-on-Chip. In Proceeding of the 2015 IEEE Real-Time Systems Symposium, 2015. URL: http://dx.doi.org/10.1109/RTSS.2015.37.
  16. Y. Li, H. Salunkhe, J. Bastos, O. Moreira, B. Akesson, and K. Goossens. Mode-controlled data-flow modeling of real-time memory controllers. In Proceedings of the 2015 IEEE Symposium on Embedded Systems For Real-time Multimedia, 2015. URL: http://dx.doi.org/10.1109/ESTIMedia.2015.7351770.
  17. Yau-Tsun Steven Li and Sharad Malik. Performance Analysis of Embedded Software Using Implicit Path Enumeration. In Proceedings of the 1995 Annual ACM/IEEE Design Automation Conference, 1995. URL: http://dx.doi.org/10.1145/217474.217570.
  18. Matthieu Moy and Karine Altisen. Arrival Curves for Real-Time Calculus: The Causality Problem and Its Solutions. In Proceedings of the 2010 International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 2010. URL: http://dx.doi.org/10.1007/978-3-642-12002-2_31.
  19. Dominic Oehlert, Arno Luppold, and Heiko Falk. Bus-aware Static Instruction SPM Allocation for Multicore Hard Real-Time Systems. In Proceedings of the 2017 Euromicro Conference on Real-Time Systems, June 2017. Google Scholar
  20. K. Richter and R. Ernst. Event model interfaces for heterogeneous system analysis. In Proceedings of the 2002 Design, Automation and Test in Europe Conference and Exhibition, 2002. URL: http://dx.doi.org/10.1109/DATE.2002.998348.
  21. Selma Saidi, Rolf Ernst, Sascha Uhrig, Henrik Theiling, and Benoît Dupont de Dinechin. The shift to multicores in real-time and safety-critical systems. In Proceedings of the 2015 International Conference on Hardware/Software Codesign and System Synthesis, 2015. URL: http://dx.doi.org/10.1109/CODESISSS.2015.7331385.
  22. T. Sewell, F. Kam, and G. Heiser. Complete, High-Assurance Determination of Loop Bounds and Infeasible Paths for WCET Analysis. In Proceedings of the 2016 IEEE Real-Time and Embedded Technology and Applications Symposium, 2016. URL: http://dx.doi.org/10.1109/RTAS.2016.7461326.
  23. L. Thiele, S. Chakraborty, and M. Naedele. Real-time calculus for scheduling hard real-time systems. In Proceedings of the 2000 IEEE International Symposium on Circuits and Systems. Emerging Technologies for the 21st Century., 2000. URL: http://dx.doi.org/10.1109/ISCAS.2000.858698.
  24. S. Wasly and R. Pellizzoni. A Dynamic Scratchpad Memory Unit for Predictable Real-Time Embedded Systems. In Proceedings of the 2013 Euromicro Conference on Real-Time Systems, 2013. URL: http://dx.doi.org/10.1109/ECRTS.2013.28.
  25. 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 Trans. Embed. Comput. Syst., 7(3), 2008. URL: http://dx.doi.org/10.1145/1347375.1347389.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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