Document Open Access Logo

Dynamic Interference-Sensitive Run-time Adaptation of Time-Triggered Schedules

Authors Stefanos Skalistis , Angeliki Kritikakou

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2020.4.pdf
  • Filesize: 0.79 MB
  • 22 pages

Document Identifiers

Author Details

Stefanos Skalistis
  • Raytheon Technologies, Cork, Ireland
Angeliki Kritikakou
  • University of Rennes, Inria, IRISA, France

Funding

Partially supported by ARGO (http://www.argo-project.eu/), funded by the European Commission under Horizon 2020 Research and Innovation Action, Grant Agreement Number 688131.

Cite As Get BibTex

Stefanos Skalistis and Angeliki Kritikakou. Dynamic Interference-Sensitive Run-time Adaptation of Time-Triggered Schedules. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ECRTS.2020.4

Abstract

Over-approximated Worst-Case Execution Time (WCET) estimations for multi-cores lead to safe, but over-provisioned, systems and underutilized cores. To reduce WCET pessimism, interference-sensitive WCET (isWCET) estimations are used. Although they provide tighter WCET bounds, they are valid only for a specific schedule solution. Existing approaches have to maintain this isWCET schedule solution at run-time, via time-triggered execution, in order to be safe. Hence, any earlier execution of tasks, enabled by adapting the isWCET schedule solution, is not possible. In this paper, we present a dynamic approach that safely adapts isWCET schedules during execution, by relaxing or completely removing isWCET schedule dependencies, depending on the progress of each core. In this way, an earlier task execution is enabled, creating time slack that can be used by safety-critical and mixed-criticality systems to provide higher Quality-of-Services or execute other best-effort applications. The Response-Time Analysis (RTA) of the proposed approach is presented, showing that although the approach is dynamic, it is fully predictable with bounded WCET. To support our contribution, we evaluate the behavior and the scalability of the proposed approach for different application types and execution configurations on the 8-core Texas Instruments TMS320C6678 platform, obtaining significant performance improvements compared to static approaches.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Embedded software
  • Computer systems organization → Multicore architectures
  • Computer systems organization → Real-time systems
Keywords
  • Worst-Case Execution Time
  • Interference-sensitive
  • Run-time Adaptation
  • Time-Triggered
  • Response Time Analysis
  • Multi-cores

Metrics

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

References

  1. Marko Bertogna. Real-time scheduling analysis for multiprocessor platforms. PhD thesis, Scuola Superiore Sant’Anna, Pisa, 2008. Google Scholar
  2. Alessandro Biondi and Marco Di Natale. Achieving predictable multicore execution of automotive applications using the let paradigm. In Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 240-250. IEEE, April 2018. URL: https://doi.org/10.1109/RTAS.2018.00032.
  3. Alan Burns and Sanjoy K. Baruah. Timing faults and mixed criticality systems. In CliffB. Jones and JohnL. Lloyd, editors, Dependable and Historic Computing, volume 6875 of Lecture Notes in Computer Science, pages 147-166. Springer Berlin Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-24541-1_12.
  4. Alan Burns and Robert I. Davis. A survey of research into mixed criticality systems. ACM Comput. Surv. (CSUR), 50(6):82:1-82:37, 2018. URL: https://doi.org/10.1145/3131347.
  5. Robert I. Davis and Alan Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv. (CSUR), 43(4):35, 2011. URL: https://doi.org/10.1145/1978802.1978814.
  6. Jean-François Deverge and Isabelle Puaut. Safe measurement-based WCET estimation. In Reinhard Wilhelm, editor, 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05), volume 1 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany, 2007. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.WCET.2005.808.
  7. Alexandre Esper, Geoffrey Nelissen, Vincent Nélis, and Eduardo Tovar. An industrial view on the common academic understanding of mixed-criticality systems. Real-Time Systems, 54(3):745-795, 2018. Google Scholar
  8. Namhoon Kim, Bryan C. Ward, Micaiah Chisholm, Cheng-Yang Fu, James H. Anderson, and F. Donelson Smith. Attacking the one-out-of-m multicore problem by combining hardware management with mixed-criticality provisioning. In Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 1-12. IEEE, 2016. Google Scholar
  9. Angeliki Kritikakou, Olivier Baldellon, Claire Pagetti, Christine Rochange, and Matthieu Roy. Run-time control to increase task parallelism in mixed-critical systems. In ECRTS, 2014. Google Scholar
  10. Angeliki Kritikakou, Thibaut Marty, and Matthieu Roy. DYNASCORE: dynamic software controller to increase resource utilization in mixed-critical systems. ACM Trans. Design Autom. Electr. Syst. (TODAES), 23(2):13:1-13:26, 2018. URL: https://doi.org/10.1145/3110222.
  11. Angeliki Kritikakou, Christine Rochange, Madeleine Faugère, Claire Pagetti, Matthieu Roy, Sylvain Girbal, and Daniel Gracia Pérez. Distributed run-time WCET controller for concurrent critical tasks in mixed-critical systems. In International Conference on Real-Time Networks and Systems (RTNS), pages 139-148. ACM, 2014. URL: https://doi.org/10.1145/2659787.2659799.
  12. Claire Maiza, Hamza Rihani, Juan M Rivas, Joël Goossens, Sebastian Altmeyer, and Robert I Davis. A survey of timing verification techniques for multi-core real-time systems. ACM Computing Surveys (CSUR), 52(3):56, 2019. Google Scholar
  13. Sébastien Martinez, Damien Hardy, and Isabelle Puaut. Quantifying wcet reduction of parallel applications by introducing slack time to limit resource contention. In Proceedings of the 25th International Conference on Real-Time Networks and Systems, pages 188-197. ACM, 2017. Google Scholar
  14. C. Moreno and S. Fischmeister. Accurate measurement of small execution times—getting around measurement errors. IEEE Embedded Systems Letters, 9(1):17-20, March 2017. Google Scholar
  15. Jan Nowotsch and Michael Paulitsch. Quality of service capabilities for hard real-time applications on multi-core processors. In International Conference on Real-Time Networks and Systems (RTNS), pages 151-160. ACM, 2013. URL: https://doi.org/10.1145/2516821.2516826.
  16. Jan Nowotsch, Michael Paulitsch, Daniel Bühler, Henrik Theiling, Simon Wegener, and Michael Schmidt. Multi-core interference-sensitive wcet analysis leveraging runtime resource capacity enforcement. In Euromicro Conference on Real-Time Systems (ECRTS),, pages 109-118. IEEE, 2014. Google Scholar
  17. Hamza Rihani, Matthieu Moy, Claire Maiza, Robert I. Davis, and Sebastian Altmeyer. Response time analysis of synchronous data flow programs on a many-core processor. In Proceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS '16, pages 67-76, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2997465.2997472.
  18. Benjamin Rouxel, Steven Derrien, and Isabelle Puaut. Tightening contention delays while scheduling parallel applications on multi-core architectures. ACM Trans. Embed. Comput. Syst. (TECS), 16(5s):164:1-164:20, September 2017. URL: https://doi.org/10.1145/3126496.
  19. Benjamin Rouxel, Stefanos Skalistis, Steven Derrien, and Isabelle Puaut. Hiding communication delays in contention-free execution for spm-based multi-core architectures. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  20. Andreas Schranzhofer, Jian-Jia Chen, and Lothar Thiele. Timing analysis for TDMA arbitration in resource sharing systems. In 2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 215-224. IEEE, 2010. Google Scholar
  21. Stefanos Skalistis, Federico Angiolini, Alena Simalatsar, and Giovanni De Micheli. Safe and efficient deployment of data-parallelizable applications on many-core platforms: Theory and practice. IEEE Design & Test, 35(4):7-15, 2018. Google Scholar
  22. Stefanos Skalistis and Angeliki Kritikakou. Timely fine-grained interference-sensitive run-time adaptation of time-triggered schedules. In Real-Time Systems Symposium (RTSS). IEEE, 2019. Google Scholar
  23. Stefanos Skalistis and Alena Simalatsar. Worst-case execution time analysis for many-core architectures with NoC. In International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS), pages 211-227. Springer, 2016. Google Scholar
  24. Stefanos Skalistis and Alena Simalatsar. Near-optimal deployment of dataflow applications on many-core platforms with real-time guarantees. In Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 752-757. IEEE, 2017. Google Scholar
  25. Texas Instruments. TMS320C6678 Multicore fixed and floating-point digital signal processor. Technical Report SPRS691D, TI, 2013. Google Scholar
  26. William Thies and Saman Amarasinghe. An empirical characterization of stream programs and its implications for language and compiler design. In International Conference on Parallel Architectures and Compilation Techniques (PACT), pages 365-376. ACM, 2010. Google Scholar
  27. Heechul Yun, Gang Yao, Rodolfo Pellizzoni, Marco Caccamo, and Lui Sha. Memguard: Memory bandwidth reservation system for efficient performance isolation in multi-core platforms. In Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 55-64, 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact