Document Open Access Logo

Non-Simultaneity as a Design Constraint

Authors Jean Guyomarc'h , François Guerret, Bilal El Mejjati, Emmanuel Ohayon, Bastien Vincke, Alain Mérigot

PDF
Thumbnail PDF

File

LIPIcs.TIME.2020.13.pdf
  • Filesize: 0.59 MB
  • 15 pages

Document Identifiers

Author Details

Jean Guyomarc'h
  • Krono-Safe, Massy, France
  • Université Paris-Saclay, CNRS, Systèmes et Applications des Technologies de l'Information et de l'Energie, Orsay, France
François Guerret
  • Krono-Safe, Massy, France
Bilal El Mejjati
  • Krono-Safe, Massy, France
Emmanuel Ohayon
  • Krono-Safe, Massy, France
Bastien Vincke
  • Université Paris-Saclay, CNRS, Systèmes et Applications des Technologies de l'Information et de l'Energie, Orsay, France
Alain Mérigot
  • Université Paris-Saclay, CNRS, Systèmes et Applications des Technologies de l'Information et de l'Energie, Orsay, France

Funding

This research is supported by the company Krono-Safe.

Acknowledgements

We would like to thank Fabien Siron, Matthieu Texier for their interesting and constructive discussions and other engineers from Krono-Safe who helped contributing to this paper. We would also like to thank the anonymous reviewers for their feedback and suggestions.

Cite AsGet BibTex

Jean Guyomarc'h, François Guerret, Bilal El Mejjati, Emmanuel Ohayon, Bastien Vincke, and Alain Mérigot. Non-Simultaneity as a Design Constraint. In 27th International Symposium on Temporal Representation and Reasoning (TIME 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 178, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.TIME.2020.13

Abstract

Whether one or multiple hardware execution units are activated (i.e. CPU cores), invalid resource sharing, notably due to simultaneous accesses, proves to be problematic as it can yield to unexpected runtime behaviors with negative implications such as security or safety issues. The growing interest for off-the-shelf multi-core architectures in sensitive applications motivates the need for safe resources sharing. If critical sections are a well-known solution from imperative and non-temporized programming models, they fail to provide safety guarantees. By leveraging the time-triggered programming model, this paper aims at enforcing that identified critical windows of computations can never be simultaneously executed. We achieve this result by determining, before an application is compiled, the exact dates during which a task accesses a shared resource, which enables the off-line validation of non-simultaneity constraints.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • Temporal reasoning
  • Temporal constraints
  • Specification and verification of systems

Metrics

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

Supplementary Materials

References

  1. Irune Agirre, Jaume Abella, Mikel Azkarate-Askasua, and Francisco J Cazorla. On the tailoring of cast-32a certification guidance to real cots multicore architectures. In 2017 12th IEEE International Symposium on Industrial Embedded Systems (SIES), pages 1-8. IEEE, 2017. URL: https://doi.org/10.1109/SIES.2017.7993376.
  2. Bowen Alpern and Fred B Schneider. Recognizing safety and liveness. Distributed computing, 2(3):117-126, 1987. URL: https://doi.org/10.1007/BF01782772.
  3. George E Andrews. Number theory. Courier Corporation, 1994. Google Scholar
  4. Christophe Aussagues, Damien Chabrol, and Vincent David. Method for the deterministic execution and synchronisation of an information processing system comprising a plurality of processing cores executing system tasks, April 2010. Patent WO 2010/043706 A2. Google Scholar
  5. Stanley Bak, Gang Yao, Rodolfo Pellizzoni, and Marco Caccamo. Memory-aware scheduling of multicore task sets for real-time systems. In 2012 IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pages 300-309. IEEE, 2012. URL: https://doi.org/10.1109/RTCSA.2012.48.
  6. Thomas G Baker. Lessons learned integrating cots into systems. In International Conference on COTS-Based Software Systems, pages 21-30. Springer, 2002. URL: https://doi.org/10.1007/3-540-45588-4_3.
  7. Matthias Becker, Dakshina Dasari, Borislav Nicolic, Benny Akesson, Vincent Nélis, and Thomas Nolte. Contention-free execution of automotive applications on a clustered many-core platform. In 2016 28th Euromicro Conference on Real-Time Systems (ECRTS), pages 14-24. IEEE, 2016. URL: https://doi.org/10.1109/ECRTS.2016.14.
  8. Jingyi Bin, Sylvain Girbal, Daniel Gracia Pérez, Arnaud Grasset, and Alain Mérigot. Studying co-running avionic real-time applications on multi-core COTS architectures. In Embedded Real Time Software and Systems (ERTS2014), Toulouse, France, February 2014. Google Scholar
  9. Frédéric Boniol, Hugues Cassé, Eric Noulard, and Claire Pagetti. Deterministic execution model on cots hardware. In International Conference on Architecture of Computing Systems, pages 98-110. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-28293-5_9.
  10. Damien Chabrol, Vincent David, Patrice Oudin, Gilles Zeppa, and Mathieu Jan. Freedom from interference among time-triggered and angle-triggered tasks: a powertrain case study. In Embedded Real Time Software and Systems (ERTS2014), Toulouse, France, February 2014. Google Scholar
  11. Airlines Electronic Committee. Avionics application software standard interface - part 1: Required services. Arinc 653p1, Airlines Electronic Committee, August 2015. Google Scholar
  12. Vincent David, Christophe Aussaguès, Stéphane Louise, Philippe Hilsenkopf, Bertrand Ortolo, and Christophe Hessler. The oasis based qualified display system. In Fourth American Nuclear Society International Topical Meeting on Nuclear Plant Instrumentation, Controls and Human-Machine Interface Technologies (NPIC&HMIT 2004), Columbus, Ohio, USA, page 11, 2004. Google Scholar
  13. Stephen A Edwards and Edward A Lee. The case for the precision timed (pret) machine. In Proceedings of the 44th annual Design Automation Conference, pages 264-265. ACM, 2007. URL: https://doi.org/10.1145/1278480.1278545.
  14. Farouk Hebbache, Mathieu Jan, Florian Brandner, and Laurent Pautet. Shedding the shackles of time-division multiplexing. In 2018 IEEE Real-Time Systems Symposium (RTSS), pages 456-468. IEEE, 2018. URL: https://doi.org/10.1109/RTSS.2018.00059.
  15. Mathieu Jan, Jean-Sylvain Camier, and Vincent David. Scheduling safety-critical real-time bus accesses using time-constrained automata. In RTNS, pages 87-96. Citeseer, 2011. Google Scholar
  16. Hermann Kopetz. Real-time systems: design principles for distributed embedded applications. Real-Time Systems Series. Springer, 2011. URL: https://doi.org/10.1007/978-1-4419-8237-7.
  17. Matthieu Lemerre, Vincent David, Christophe Aussagues, and Guy Vidal-Naquet. An introduction to time-constrained automata. In Proceedings of the 3rd Interaction and Concurrency Experience Workshop (ICE’10), volume 38, pages 83-98, June 2010. URL: https://doi.org/10.4204/EPTCS.38.9.
  18. Matthieu Lemerre and Emmanuel Ohayon. A model of parallel deterministic real-time computation. In 2012 IEEE 33rd Real-Time Systems Symposium, pages 273-282. IEEE, 2012. URL: https://doi.org/10.1109/RTSS.2012.78.
  19. Renato Mancuso, Roman Dudko, Emiliano Betti, Marco Cesati, Marco Caccamo, and Rodolfo Pellizzoni. Real-time cache management framework for multi-core architectures. In 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 45-54. IEEE, 2013. URL: https://doi.org/10.1109/RTAS.2013.6531078.
  20. Renato Mancuso, Rodolfo Pellizzoni, Marco Caccamo, Lui Sha, and Heechul Yun. Wcet (m) estimation in multi-core systems using single core equivalence. In 2015 27th Euromicro Conference on Real-Time Systems, pages 174-183. IEEE, 2015. URL: https://doi.org/10.1109/ECRTS.2015.23.
  21. Amira Methni, Emmanuel Ohayon, and François Thurieau. ASTERIOS Checker : A Verification Tool for Certifying Airborne Software. In 10th European Congress on Embedded Real Time Systems (ERTS 2020), Toulouse, France, January 2020. URL: https://hal.archives-ouvertes.fr/hal-02508852.
  22. Jan Nowotsch and Michael Paulitsch. Leveraging multi-core computing architectures in avionics. In 2012 Ninth European Dependable Computing Conference, pages 132-143. IEEE, 2012. URL: https://doi.org/10.1109/EDCC.2012.27.
  23. Rodolfo Pellizzoni, Emiliano Betti, Stanley Bak, Gang Yao, John Criswell, Marco Caccamo, and Russell Kegley. A predictable execution model for cots-based embedded systems. In 2011 17th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 269-279. IEEE, 2011. URL: https://doi.org/10.1109/RTAS.2011.33.
  24. Rodolfo Pellizzoni, Andreas Schranzhofer, Jian-Jia Chen, Marco Caccamo, and Lothar Thiele. Worst case delay analysis for memory interference in multicore systems. In 2010 Design, Automation & Test in Europe Conference & Exhibition (DATE 2010), pages 741-746. IEEE, 2010. URL: https://doi.org/10.1109/DATE.2010.5456952.
  25. Michel Raynal. Concurrent programming: algorithms, principles, and foundations. Springer Science, 2013. URL: https://doi.org/10.1007/978-3-642-32027-9.
  26. Jan Reineke, Isaac Liu, Hiren D Patel, Sungjun Kim, and Edward A Lee. Pret dram controller: Bank privatization for predictability and temporal isolation. In 2011 Proceedings of the Ninth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES+ ISSS), pages 99-108. IEEE, 2011. URL: https://doi.org/10.1145/2039370.2039388.
  27. Zdeněk Sawa. Efficient construction of semilinear representations of languages accepted by unary nondeterministic finite automata. Fundamenta Informaticae, 123(1):97-106, 2013. URL: https://doi.org/10.3233/FI-2013-802.
  28. Nathanaël Sensfelder, Julien Brunel, and Claire Pagetti. Modeling cache coherence to expose interference. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ECRTS.2019.18.
  29. Certification Authorities Software Team. Multi-core processors - position paper. Cast-32a, Certification Authorities Software Team, November 2016. Google Scholar
  30. Theo Ungerer, Francisco Cazorla, Pascal Sainrat, Guillem Bernat, Zlatko Petrov, Christine Rochange, Eduardo Quinones, Mike Gerdes, Marco Paolieri, Julian Wolf, et al. Merasa: Multicore execution of hard real-time applications supporting analyzability. IEEE Micro, 30(5):66-75, 2010. URL: https://doi.org/10.1109/MM.2010.78.
  31. Stephen C Vestal, Pamela Binns, Aaron Larson, Murali Rangarajan, and Ryan Roffelsen. Safe partition scheduling on multi-core processors, 2012. US Patent 8,316,368. Google Scholar
  32. Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, et al. The worst-case execution-time problem—overview of methods and survey of tools. ACM Transactions on Embedded Computing Systems (TECS), 7(3):36, 2008. URL: https://doi.org/10.1145/1347375.1347389.
  33. Heechul Yun, Renato Mancuso, Zheng-Pei Wu, and Rodolfo Pellizzoni. Palloc: Dram bank-aware memory allocator for performance isolation on multicore platforms. In 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 155-166. IEEE, 2014. URL: https://doi.org/10.1109/RTAS.2014.6925999.
  34. 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 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 55-64. IEEE, 2013. URL: https://doi.org/10.1109/RTAS.2013.6531079.
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 Imprint Privacy Contact