Document Open Access Logo

Evaluation of the Age Latency of a Real-Time Communicating System Using the LET Paradigm

Authors Alix Munier Kordon , Ning Tang



PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2020.20.pdf
  • Filesize: 0.65 MB
  • 20 pages

Document Identifiers

Author Details

Alix Munier Kordon
  • Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
Ning Tang
  • Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Cite AsGet BibTex

Alix Munier Kordon and Ning Tang. Evaluation of the Age Latency of a Real-Time Communicating System Using the LET Paradigm. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ECRTS.2020.20

Abstract

Automotive and avionics embedded systems are usually composed of several tasks that are subject to complex timing constraints. In this context, the LET paradigm was introduced to improve the determinism of a system of tasks that communicate data through shared variables. The age latency corresponds to the maximum time for the propagation of data in these systems. Its precise evaluation is an important and challenging question for the design of these systems. We consider in this paper a set of multi-periodic tasks that communicate data following the LET paradigm. Our main contribution is the development of mathematical and algorithmic tools to model precisely the dependency between tasks executions to experiment with an original methodology for computing the age latency of the system. These tools allow to handle the whole graph instead of particular chains and to extract automatically the critical parts of the graph. Experiments on randomly generated graphs indicate that systems with up to 90 periodic tasks and a hyperperiod bounded by 100 can be handled within a reasonable amount of time.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
Keywords
  • Real-Time Systems
  • Logical Execution Time
  • Age Latency

Metrics

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

References

  1. Autosar. URL: https://www.autosar.org.
  2. Matthias Becker, Dakshina Dasari, Saad Mubeen, Moris Behnam, and Thomas Nolte. Synthesizing job-level dependencies for automotive multi-rate effect chains. In 2016 IEEE 22nd International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 159-169, August 2016. URL: https://doi.org/10.1109/RTCSA.2016.41.
  3. Matthias Becker, Dakshina Dasari, Saad Mubeen, Moris Behnam, and Thomas Nolte. End-to-end timing analysis of cause-effect chains in automotive embedded systems. Journal of Systems Architecture, 80:104-113, 2017. Google Scholar
  4. Alessandro Biondi and Marco Di Natale. Achieving predictable multicore execution of automotive applications using the LET paradigm. In IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2018, 11-13 April 2018, Porto, Portugal, pages 240-250, 2018. URL: https://doi.org/10.1109/RTAS.2018.00032.
  5. Bruno Bodin, Alix Munier Kordon, and Benoît Dupont de Dinechin. K-periodic schedules for evaluating the maximum throughput of a synchronous dataflow graph. In 2012 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS XII, Samos, Greece, July 16-19, 2012, pages 152-159, 2012. Google Scholar
  6. Bruno Bodin, Alix Munier Kordon, and Benoît Dupont de Dinechin. Optimal and fast throughput evaluation of CSDF. In Proceedings of the 53rd Annual Design Automation Conference, DAC 2016, Austin, TX, USA, June 5-9, 2016, pages 160:1-160:6, 2016. Google Scholar
  7. Robert de Groote. On the analysis of synchronous dataflow graphs: a system-theoretic perspective. PhD thesis, University of Twente, 2016. Google Scholar
  8. Nico Feiertag, Kai Richter, Johan Nordlander, and Jan Jonsson. A compositional framework for end-to-end path delay calculation of automotive systems under different path semantics. In IEEE Real-Time Systems Symposium, November 30-December 3. IEEE Communications Society, 2009. Google Scholar
  9. Julien Forget, Frédéric Boniol, and Claire Pagetti. Verifying end-to-end real-time constraints on multi-periodic models. In 22nd IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2017, Limassol, Cyprus, September 12-15, 2017, pages 1-8, 2017. Google Scholar
  10. Arne Hamann, Dakshina Dasari, Simon Kramer, Michael Pressler, and Falk Wurst. Communication centric design in complex automotive embedded systems. In 29th Euromicro Conference on Real-Time Systems, ECRTS 2017, June 27-30, 2017, Dubrovnik, Croatia, pages 10:1-10:20, 2017. Google Scholar
  11. Arne Hamann, Dakshina Dasari, Simon Kramer, Michael Pressler, Falk Wurst, and Dirk Ziegenbein. Waters industrial challenge 2017. URL: https://waters2017.inria.fr/challenge/#Challenge17.
  12. Thomas A. Henzinger, Benjamin Horowitz, and Christoph M. Kirsch. Giotto: a time-triggered language for embedded programming. Proceedings of the IEEE, 91(1):84-99, 2003. Google Scholar
  13. Thomas A. Henzinger, Christoph M. Kirsch, Marco A.A Sanvido, and Wolfgang Pree. From control models to real-time code using Giotto. IEEE Control Systems Magazine, 23(1):50-64, February 2003. Google Scholar
  14. Jad Khatib, Alix Munier Kordon, Enagnon Cédric Klikpo, and Kods Trabelsi-Colibet. Computing latency of a real-time system modeled by synchronous dataflow graph. In Proceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS 2016, Brest, France, October 19-21, 2016, pages 87-96, 2016. Google Scholar
  15. Christoph M. Kirsch and Ana Sokolova. The logical execution time paradigm. In Samarjit Chakraborty and Jörg Eberspächer, editors, Advances in Real-Time Systems, pages 103-120. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. Google Scholar
  16. Simon Kramer, Dirk Ziegenbein, and Arne Hamann. Real world automotive benchmarks for free, 2015. URL: https://www.ecrts.org/forum/viewtopic.php?f=20&t=23.
  17. Edward A. Lee and David G. Messerschmitt. Synchronous data flow. Proceeding of the IEEE, vol. 75(no. 9):pp. 1235-1245, 1987. Google Scholar
  18. Qing Li and Caroline Yao. Real-time concepts for embedded systems. Taylor and Francis, Hoboken, NJ, 2014. URL: http://cds.cern.ch/record/1990357.
  19. C. L. Liu and James W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM, 20(1):46-61, 1973. URL: https://doi.org/10.1145/321738.321743.
  20. Jorge Martinez, Ignacio Sañudo, and Marko Bertogna. Analytical characterization of end-to-end communication delays with logical execution time. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 37(11):2244-2254, November 2018. Google Scholar
  21. Claire Pagetti, Julien Forget, Frédéric Boniol, Mikel Cordovilla, and David Lesens. Multi-task implementation of multi-periodic synchronous programs. Discrete Event Dynamic Systems, 21(3):307-338, 2011. Google Scholar
  22. Claire Pagetti, David Saussié, Romain Gratia, Eric Noulard, and Pierre Siron. The ROSACE case study: from simulink specification to multi/many-core execution. In 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 309-318, April 2014. Google Scholar
  23. Rémy Wyss, Frédéric Boniol, Claire Pagetti, and Julien Forget. End-to-end latency computation in a multi-periodic design. In 28th Symposium On Applied Computing (SAC'13), pages 1682-1687, Coimbra, Portugal, April 2013. Google Scholar
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