Uniprocessor scheduling of real-time synchronous dataflow tasks
Tóm tắt
The synchronous dataflow graph (SDFG) model is widely used today for modeling real-time applications in safety-critical application domains. Schedulability analysis techniques that are well understood within the real-time scheduling community are applied to the analysis of recurrent real-time workloads that are represented using this model. An enhancement to the standard SDFG model is proposed, which supports the specification of a real-time latency constraint between a specified input and a specified output of an SDFG. A polynomial-time algorithm is derived for representing the computational requirement of each such enhanced SDFG task in terms of the notion of the demand bound function (dbf), which is widely used in real-time scheduling theory for characterizing computational requirements of recurrent processes represented by, e.g., the sporadic task model. By so doing, the extensive dbf-centered machinery that has been developed in real-time scheduling theory for the hard-real-time schedulability analysis of systems of recurrent tasks may be applied to the analysis of systems represented using the SDFG model as well. The applicability of this approach is illustrated by applying prior results from real-time scheduling theory to construct an exact preemptive uniprocessor schedulability test for collections of independent recurrent processes that are each represented using the enhanced SDFG model.
Tài liệu tham khảo
Ali HI, Akesson B, Pinho LM (2015) Generalized extraction of real-time parameters for homogeneous synchronous dataflow graphs. In: Proceedings of the 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, 2015, pp 701–710. https://doi.org/10.1109/PDP.2015.57
Bamakhrama M, Stefanov T (2011) Hard-real-time scheduling of data-dependent tasks in embedded streaming applications. In: Proceedings of the Ninth ACM International Conference on Embedded Software, ACM, New York, NY, USA, EMSOFT ’11, pp 195–204. https://doi.org/10.1145/2038642.2038672
Bamakhrama MA, Stefanov T (2012) Managing latency in embedded streaming applications under hard-real-time scheduling. In: Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, ACM, New York, NY, USA, CODES+ISSS ’12, pp 83–92. https://doi.org/10.1145/2380445.2380464
Baruah S, Mok A, Rosier L (1990) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proceedings of the 11th Real-Time Systems Symposium, IEEE Computer Society Press, Orlando, FL, pp 182–190
Bouakaz A, Gautier T, Talpin JP (2014) Earliest-deadline first scheduling of multiple independent dataflow graphs. In: Proceedings of the 2014 IEEE Workshop on Signal Processing Systems (SiPS), pp 1–6. https://doi.org/10.1109/SiPS.2014.6986102
Dertouzos M (1974) Control robotics: the procedural control of physical processors. In: Proceedings of the IFIP Congress, pp 807–813
Fisher N, Baker T, Baruah S (2006) Algorithms for determining the demand-based load of a sporadic task system. In: Proceedings of the International Conference on Real-time Computing Systems and Applications, IEEE Computer Society Press, Sydney, Australia
Ghamarian AH, Stuijk S, Basten T, Geilen MCW, Theelen BD (2007) Latency minimization for synchronous data flow graphs. In: Proceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools, 2007. DSD 2007, pp 189–196. https://doi.org/10.1109/DSD.2007.4341468
Khatib J, Kordon AM, Klikpo EC, Trabelsi-Colibet K (2016) 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, pp 87–96. https://doi.org/10.1145/2997465.2997479
Klikpo EC, Kordon AM (2016) Preemptive scheduling of dependent periodic tasks modeled by synchronous dataflow graphs. In: Proceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS 2016, Brest, France, October 19–21, 2016, pp 77–86. https://doi.org/10.1145/2997465.2997474
Lee EA (1986) A coupled hardware and software architecture for programmable digital signal processors. PhD thesis, EECS Department, University of California, Berkeley. http://www2.eecs.berkeley.edu/Pubs/TechRpts/1986/715.html
Lee EA, Messerschmitt DG (1987a) Static scheduling of synchronous data flow programs for digital signal processing. IEEE Trans Comput C 36(1):24–35
Lee EA, Messerschmitt DG (1987b) Synchronous data flow. Proc IEEE 75(9):1235–1245. https://doi.org/10.1109/PROC.1987.13876
Lee EA, Seshia SA (2011) Introduction to embedded systems. A cyber-physical systems approach. MIT Press, Cambridge. http://LeeSeshia.org
Liu C, Layland J (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J ACM 20(1):46–61
Mohaqeqi M, Abdullah J, Yi W (2016) Modeling and analysis of data flow graphs using the digraph real-time task model. In: Proceedings of the 21st Ada-Europe International Conference on Reliable Software Technologies—Ada-Europe 2016, vol 9695, Springer-Verlag New York, Inc., New York, pp 15–29
Mok A (1983) Fundamental design problems of distributed systems for the hard-real-time environment. PhD thesis, Laboratory for Computer Science, Massachusetts Institute of Technology, available as Technical Report No. MIT/LCS/TR-297
Neuendorffer S (2005) The SDF domain. In: Brooks C, Lee EA, Liu X, Neuendorffer S, Zhao Y, Zheng H (eds) Heterogeneous concurrent modeling and design in Java, vol 3 (Ptolemy II Domains). EECS, University of California, Berkeley, chap 3, pp 49–60, memorandum UCB/ERL M05/23
PGM—processing graph method specification (1987) Naval Research Laboratory, prepared by the Naval Research Laboratory for use by the Navy Standard Signal Processing Program Office (PMS-412). Version 1.0
Ripoll I, Crespo A, Mok AK (1996) Improvement in feasibility testing for real-time tasks. Real-Time Syst 11:19–39
Singh A, Ekberg P, Baruah S (2017) Applying real-time scheduling theory to the synchronous data flow model of computation. In: Proceedings of the 29th Euromicro Conference on Real-Time Systems, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017
Siyoum F (2014) Worst-case temporal analysis of real-time dynamic streaming applications. PhD thesis, Eindhoven University of Technology
Stigge M, Ekberg P, Guan N, Yi W (2011) The digraph real-time task model. In: Proceedings of the IEEE Real-Time Technology and Applications Symposium (RTAS), IEEE Computer Society Press, Chicago, pp 71–80
Zhang F, Burns A (2009) Schedulability analysis for real-time systems with EDF scheduling. IEEE Trans Comput 58(9):1250–1258. https://doi.org/10.1109/TC.2009.58