nach oben

Real-Time Systems

Erschienen in:

21.05.2018

Uniprocessor scheduling of real-time synchronous dataflow tasks

verfasst von: Abhishek Singh, Pontus Ekberg, Sanjoy Baruah

Erschienen in: Real-Time Systems | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Nächster Artikel Stretching algorithm for global scheduling of real-time DAG tasks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Most SDFG models allow for multigraphs, in which there may be multiple edges between the same pair of vertices. This feature is not particularly relevant to determining how they are scheduled and we, therefore, ignore them in this paper. For the same reason, we also ignore edges that are self-loops: lead from a vertex back to itself. We point out that our results are easily extended to deal with multiple edges and self-loops.

In addition to requiring that each buffer be of finite size, many SDFG scheduling algorithms seek to minimize the maximum number of tokens each buffer will need to hold. However the algorithms of Singh et al. (2017) do not consider buffer-size minimization while seeking to construct schedules in which real-time constraints are met, and we will do likewise here—require that buffers be of finite size, but leave as future work the problem of determining the minimum sizes needed.

An SDFG G is said to be connected if the undirected graph formed by taking the actors as vertices and channels as undirected edges is connected.

The rank of a matrix is the maximum number of linearly independent columns in it. Efficient polynomial-time algorithms are known for computing rank.

One may choose to think of src as a dummy actor that queues the external input tokens directed at \(v_{\mathrm {in}}\) until it has accumulated \(\mathbf {q}(v_{\mathrm {in}})\) tokens, at which instant it releases them all simultaneously to a; hence, a does not have to deal with the possibility of unbounded durations between the arrivals of the three tokens. (However, an unbounded duration may elapse before the next set of three tokens are released to it.) A similar interpretation may be made for dst.

We will show, in Lemma 2, that this skip vector is uniquely defined for a given G.

As we have stated in Sect. 2.3 in this paper we have assumed \(\delta =0\) in order to keep things simple. However, our algorithm may be extended to handle non-zero dependency distances: we briefly describe the extension in Sect. 4.3.

These are auxiliary variables in the sense that they will not appear in the actual code that implements the algorithm. They are defined solely to record information that is useful in proving properties (in our case, computational complexity) of the algorithm.

As with the \(\varvec{\pi }[\cdot ]\) auxiliary variables, the constraint graph is a concept used only in our proofs—no such graph is explicitly constructed by our algorithm.

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–35CrossRef

Lee EA, Messerschmitt DG (1987b) Synchronous data flow. Proc IEEE 75(9):1235–1245. https://doi.org/10.1109/PROC.1987.13876 CrossRef

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–61MathSciNetCrossRefMATH

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–39CrossRef

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 MathSciNetCrossRefMATH

Titel: Uniprocessor scheduling of real-time synchronous dataflow tasks
verfasst von: Abhishek Singh
Pontus Ekberg
Sanjoy Baruah
Publikationsdatum: 21.05.2018
Verlag: Springer US
Erschienen in: Real-Time Systems / Ausgabe 1/2019
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI: https://doi.org/10.1007/s11241-018-9310-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2019

DeepRT: predictable deep learning inference for cyber-physical systems

Real-time analysis of priority-preemptive NoCs with arbitrary buffer sizes and router delays

Stretching algorithm for global scheduling of real-time DAG tasks

Correspondence article: a correction of the reduction-based schedulability analysis for APA scheduling

Many suspensions, many problems: a review of self-suspending tasks in real-time systems