From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation

Thomas Carle, Dumitru Potop-Butucaru, Yves Sorel, David Lesens

Abstract


Our objective is to facilitate the development of complex time-triggered systems by automating the allocation and scheduling steps. We show that full automation is possible while taking into account the elements of complexity needed by a complex embedded control system. More precisely, we consider deterministic functional specifications provided (as often in an industrial setting) by means of synchronous data-flow models with multiple modes and multiple relative periods. We first extend this functional model with an original real-time characterization that takes advantage of our time-triggered framework to provide a simpler representation of complex end-to-end flow requirements. We also extend our specifications with additional non-functional properties specifying partitioning, allocation, and preemptability constraints. Then, we provide novel algorithms for the off-line scheduling of these extended specifications onto partitioned time-triggered architectures à la ARINC 653. The main originality of our work is that it takes into account at the same time multiple complexity elements: various types of non-functional properties (real-time, partitioning, allocation, preemptability) and functional specifications with conditional execution and multiple modes. Allocation of time slots/windows to partitions can be fully or partially provided, or synthesized by our tool. Our algorithms allow the automatic allocation and scheduling onto multi-processor (distributed) systems with a global time base, taking into account communication costs. We demonstrate our technique on a model of space flight software system with strong real-time determinism requirements.

Keywords


Time-triggered;Off-line real-time scheduling;Temporal partitioning

Full Text:

PDF

References


Vicki H. Allan, Reese B. Jones, Randall M. Lee, and Stephen J. Allan. Software pipelining. ACM Computing Surveys, 27(3):367–432, 1995. doi: 10.1145/212094.212131.

Mouaiad Alras, Paul Caspi, Alain Girault, and Pascal Raymond. Model-based design of embedded control systems by means of a synchronous inter mediate model. In Tianzhou Chen, Dimitrios N. Serpanos, and Walid Taha, editors, International Conference on Embedded Software and Systems, ICESS’09, Hangzhou, Zhejiang, P. R. China, May 25-27, 2009., pages 3–10. IEEE Computer Society, 2009. doi:10.1109/ICESS.2009.36.

ARINC 653: Avionics application software stand- ard interface, 2005. URL: http://www.arinc.org.

Cédric Auger. Compilation certifiée de SCADE/LUSTRE. PhD thesis, Université Paris Sud – Paris XI, 2013. In French. URL: https://tel.archives-ouvertes.fr/tel-00818169.

Autosar (automotive open system architecture), re- lease 4, 2009. URL: http://www.autosar.org/specifications/release-40/.

Sanjoy K. Baruah. Dynamic- and static-priority scheduling of recurring real-time tasks. Real-Time Systems, 24(1):93–128, 2003. doi:10.1023/A:1021711220939.

Jacek Blazewicz. Scheduling dependent tasks with different arrival times to meet deadlines. In Heinz Beilner and Erol Gelenbe, editors, Modelling and Performance Evaluation of Computer Systems, Proceedings of the International Workshop organized by the Commision of the European Communit- ies, Ispra (Varese), Italy, October 4-6, 1976, pages 57–65. North-Holland, 1976.

Vicent Brocal, Miguel Masmano, Ismael Ripoll, Alfons Crespo, Patricia Balbastre, and Jean- Jacques Metge. Xoncrete: a scheduling tool for partitioned real-time systems. In Embedded and Realime Software Systems (ERTS2 2010), Toulouse, France, 2010. URL: http://www.fentiss.com/documents/xoncrete_overview.pdf.

Thomas Carle. Efficient compilation of embedded control specifications with complex functional and non-functional properties. Theses, Université Pierre et Marie Curie – Paris VI, October 2014. URL: https://hal.inria.fr/tel-01088786.

Thomas Carle and Dumitru Potop-Butucaru. Predicate-aware, makespan-preserving software pipelining of scheduling tables. ACM Transactions on Architecture and Code Optimization, 11(1):12, 2014. doi:10.1145/2579676.

Paul Caspi, Adrian Curic, Aude Maignan, Christos Sofronis, Stavros Tripakis, and Peter Niebert. From simulink to scade/lustre to TTA: a layered approach for distributed embedded applications. In Frank Mueller and Ulrich Kremer, editors, Proceedings of the 2003 Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES’03). San Diego, California, USA, June 11-13, 2003, pages 153–162. ACM, 2003. doi:10.1145/780732.780754.

Houssine Chetto, Maryline Silly, and T. Bouchentouf. Dynamic scheduling of real-time tasks under precedence constraints. Real-Time Systems, 2(3):181–194, 1990. doi:10.1007/BF00365326.

Yi-Sheng Chiu, Chi-Sheng Shih, and Shih-Hao Hung. Pipeline schedule synthesis for real-time streaming tasks with inter/intra-instance precedence constraints. In Design, Automation and Test in Europe, DATE 2011, Grenoble, France, March 14-18, 2011, pages 1321–1326. IEEE, 2011. doi:10.1109/DATE.2011.5763212.

Albert Cohen, Marc Duranton, Christine Eisenbeis, Claire Pagetti, Florence Plateau, and Marc Pouzet. N-synchronous kahn networks: a relaxed model of synchrony for real-time systems. In J. Gregory Morrisett and Simon L. Peyton Jones, editors, Proceedings of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Program- ming Languages, POPL 2006, Charleston, South Carolina, USA, January 11-13, 2006, pages 180– 193. ACM, 2006. doi:10.1145/1111037.1111054.

Albert Cohen, Valentin Perrelle, Dumitru Potop-Butucaru, Elie Soubiran, and Zhen Zhang. Mixed-criticality in Railway Systems: A Case Study on Signalling Application. In Workshop on Mixed Criticality for Industrial Systems (WMCIS’2014), Paris, France, June 2014. URL: https://hal.inria.fr/hal-01095111.

Stephen A. Edwards, Sungjun Kim, Edward A. Lee, Isaac Liu, Hiren D. Patel, and Martin Schoeberl. A disruptive computer design idea: Architectures with repeatable timing. In 27th Inter- national Conference on Computer Design, ICCD 2009, Lake Tahoe, CA, USA, October 4-7, 2009, pages 54–59. IEEE Computer Society, 2009. doi:10.1109/ICCD.2009.5413177.

Stephen A. Edwards and Edward A. Lee. The case for the precision timed (PRET) machine. In Proceedings of the 44th Design Automation Conference, DAC 2007, San Diego, CA, USA, June 4-8, 2007, pages 264–265. IEEE, 2007. doi:10.1145/1278480.1278545.

Peter H. Feiler and David P. Gluch. Model-Based Engineering with AADL – An Introduction to the SAE Architecture Analysis and Design Language. SEI series in software engineering. Addison- Wesley, 2012. URL: http://www.pearsoned.co.uk/bookshop/detail.asp?item=100000000518651.

Sebastian Fischmeister, Oleg Sokolsky, and Insup Lee. Network-code machine: Programmable real-time communication schedules. In 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2006), 4-7 April 2006, San Jose, California, USA, pages 311–324. IEEE Computer Society, 2006. doi:10.1109/RTAS.2006.31.

Gerhard Fohler. Changing operational modes in the context of pre run-time scheduling. IEICE Transactions on Information and Systems, Special Issue on Responsive Computer Systems:1333–1340, November 1993.

Gerhard Fohler and Krithi Ramamritham. Static scheduling of pipelined periodic tasks in distributed real-time systems. In Proceedings of the Ninth Euromicro Workshop on Real-Time Systems, RTS 1997, 11-13 June, 1997, Toledo, Spain, pages 128– 135. IEEE Computer Society, 1997. doi:10.1109/EMWRTS.1997.613773.

Alain Girault, Hamoudi Kalla, Mihaela Sighireanu, and Yves Sorel. An algorithm for automatically obtaining distributed and fault-tolerant static sched- ules. In 2003 International Conference on Dependable Systems and Networks (DSN 2003), 22-25 June 2003, San Francisco, CA, USA, Proceedings, pages 159–168. IEEE Computer Society, 2003. doi:10.1109/DSN.2003.1209927.

Raul Gorcitz, Emilien Kofman, Thomas Carle, Dumitru Potop-Butucaru, and Robert de Simone. On the scalability of constraint solving for static/offline real-time scheduling. In Sriram Sankaranarayanan and Enrico Vicario, editors, Formal Modeling and Analysis of Timed Systems – 13th International Conference, FORMATS 2015, Madrid, Spain, September 2-4, 2015, Proceedings, volume 9268 of Lecture Notes in Computer Science, pages 108–123. Springer, 2015. doi:10.1007/978-3-319-22975-1_8.

Paul Le Guernic, Jean-Pierre Talpin, and Jean-Christophe Le Lann. POLYCHRONY for system design. Journal of Circuits, Systems, and Computers, 12(3):261–304, 2003. doi:10.1142/S0218126603000763.

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. doi:10.1109/JPROC.2002.805825.

Thomas A. Henzinger and Christoph M. Kirsch. The embedded machine: Predictable, portable real-time code. ACM Transactions on Programming Languages and Systems (TOPLAS), 29(6), 2007. doi:10.1145/1286821.1286824.

Damir Isovic and Gerhard Fohler. Handling mixed sets of tasks in combined offline and online scheduled real-time systems. Real-Time Systems, 43(3):296–325, 2009. doi:10.1007/s11241-009-9088-3.

Hermann Kopetz. Event-triggered versus time-triggered real-time systems. In Arthur I. Karshmer and Jürgen Nehmer, editors, Operating Systems of the 90s and Beyond, International Workshop, Dagstuhl Castle, Germany, July 8-12, 1991, Proceedings, volume 563 of Lecture Notes in Computer Science, pages 87–101. Springer, 1991. doi:10.1007/BFb0024530.

Hermann Kopetz and Günther Bauer. The time-triggered architecture. Proceedings of the IEEE, 91(1):112–126, 2003.

Edward A. Lee and David G. Messerschmitt. Synchronous data flow. Proceeding of the IEEE, 75(9):1235–1245, September 1987. doi:10.1109/PROC.1987.13876.

Joseph Y.-T. Leung and M. L. Merrill. A note on preemptive scheduling of periodic, real-time tasks. Information Processing Letters, 11(3):115– 118, 1980. doi:10.1016/0020-0190(80)90123-4.

Stéphane Louise, Matthieu Lemerre, Christophe Aussaguès, and Vincent David. The OASIS kernel: A framework for high dependability real-time systems. In Taghi M. Khoshgoftaar, editor, 13th IEEE International Symposium on High-Assurance Systems Engineering, HASE 2011, Boca Raton, FL, USA, November 10-12, 2011, pages 95–103. IEEE Computer Society, 2011. doi:10.1109/HASE.2011.38.

Mohamed Marouf, Laurent George, and Yves Sorel. Schedulability analysis for a combination of non-preemptive strict periodic tasks and preemptive sporadic tasks. In Proceedings of 2012 IEEE 17th International Conference on Emerging Technologies & Factory Automation, ETFA 2012, Krakow, Poland, September 17-21, 2012, pages 1–8. IEEE, 2012. doi:10.1109/ETFA.2012.6489569.

Uml profile for marte: Modeling and ana- lysis of real-time embedded systems, version 1.1, 2011. OMG document number: formal/2011-06- 02. URL: http://www.omg.org/spec/MARTE/1.1/.

James F. Mason, Kenn R. Luecke, and Jahn A. Luke. Device drivers in time and space partitioned operating systems. In 25th Digital Avionics Systems Conference, IEEE/AIAA, pages 1–9, Portland, OR, USA, Oct. 2006. doi:10.1109/DASC.2006.313742.

Alix Munier. The basic cyclic scheduling problem with linear precedence constraints. Discrete Applied Mathematics, 64(3):219–238, 1996. doi:10.1016/0166-218X(94)00126-X.

Claire Pagetti, Julien Forget, Frédéric Boniol, Mikel Cordovilla, and David Lesens. Multitask implementation of multi-periodic synchronous programs. Discrete Event Dynamic Systems, 21(3):307–338, 2011. doi:10.1007/s10626-011-0107-x.

Paul Pop, Petru Eles, and Zebo Peng. Scheduling with optimized communication for time-triggered embedded systems. In Ahmed Amine Jerraya, Luciano Lavagno, and Frank Vahid, editors, Proceedings of the Seventh International Workshop on Hardware/Software Codesign, CODES 1999, Rome, Italy, 1999, pages 178–182. ACM, 1999. doi:10.1145/301177.303812.

Dumitru Potop-Butucaru, Akramul Azim, and Sebastian Fischmeister. Semantics-preserving implementation of synchronous specifications over dynamic TDMA distributed architectures. In Luca P. Carloni and Stavros Tripakis, editors, Proceedings of the 10th International conference on Embedded software, EMSOFT 2010, Scottsdale, Arizona, USA, October 24-29, 2010, pages 199–208. ACM, 2010. doi:10.1145/1879021.1879048.

Dumitru Potop-Butucaru, Robert de Simone, Yves Sorel, and Jean-Pierre Talpin. Clock-driven distributed real-time implementation of endochronous synchronous programs. In Samarjit Chakraborty and Nicolas Halbwachs, editors, Proceedings of the 9th ACM & IEEE International conference on Embedded software, EMSOFT 2009, Grenoble, France, October 12-16, 2009, pages 147–156. ACM, 2009. doi:10.1145/1629335.1629356.

Wolfgang Puffitsch, Eric Noulard, and Claire Pagetti. Mapping a multi-rate synchronous language to a many-core processor. In 19th IEEE RealTime and Embedded Technology and Applications Symposium, RTAS 2013, Philadelphia, PA, USA, April 9-11, 2013, pages 293–302. IEEE Computer Society, 2013. doi:10.1109/RTAS.2013.6531101. Krithi Ramamritham, Gerhard Fohler, and Juan Manuel Adan. Issues in the static allocation and scheduling of complex periodic tasks. In 10th IEEE Workshop on Real-Time Operating Systems and Software, RTOSS 1993, pages 11–16, 1993. URL: http://dl.acm.org/citation.cfm?id=192806.185839.

Pascal Richard, Francis Cottet, and Claude Kaiser. Précédences généralisées et ordonnançabilité des tâches de suivi temps réel d’un laminoir. Journal européen des systèmes automatisés, 35:1055–1071, 2001. URL: http://www.lias-lab.fr/publications/5810/2001-jesa-richard.pdf.

John M. Rushby. Bus architectures for safety-critical embedded systems. In Thomas A. Henzinger and Christoph M. Kirsch, editors, Embedded Software, First International Workshop, EMSOFT 2001, Tahoe City, CA, USA, October, 8-10, 2001, Proceedings, volume 2211 of Lecture Notes in Computer Science, pages 306–323. Springer, 2001. doi:10.1007/3-540-45449-7_22.

Ahmad Al Sheikh, Olivier Brun, Pierre-Emmanuel Hladik, and Balakrishna J. Prabhu. Strictly periodic scheduling in ima-based architectures. Real- Time Systems, 48(4):359–386, 2012. doi:10.1007/s11241-012-9148-y.

Jia Xu. Multiprocessor scheduling of processes with release times, deadlines, precedence, and exclusion relations. IEEE Transactions on Software Engineering (TSE), 19(2):139–154, 1993. doi:10.1109/32.214831.

Wei Zheng, Jike Chong, Claudio Pinello, Sri Kanajan, and Alberto L. Sangiovanni-Vincentelli. Extensible and scalable time triggered scheduling. In Fifth International Conference on Application of Concurrency to System Design (ACSD 2005), 6-9 June 2005, St. Malo, France, pages 132–141. IEEE Computer Society, 2005. doi:10.1109/ACSD.2005.13.




DOI: http://dx.doi.org/10.4230/LITES-v002-i002-a001

URN (PDF): http://nbn-resolving.de/urn:nbn:de:0030-lites-v002-i002-a001-pdf3



Copyright (c) 2015 Thomas Carle, Dumitru Potop-Butucaru, Yves Sorel, and David Lesens

Creative Commons License CC BY
This work is licensed under a Creative Commons Attribution 3.0 Germany License (CC BY 3.0 DE).

License URL: http://creativecommons.org/licenses/by/3.0/de/deed.en

Published by the European Design and Automation Association (EDAA) \ EMbedded Systems Special Interest Group (EMSIG) and Schloss Dagstuhl -- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing.