Document Open Access Logo

Applying Real-Time Scheduling Theory to the Synchronous Data Flow Model of Computation

Authors Abhishek Singh, Pontus Ekberg, Sanjoy Baruah

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2017.8.pdf
  • Filesize: 0.59 MB
  • 22 pages

Document Identifiers

Author Details

Abhishek Singh
Pontus Ekberg
Sanjoy Baruah

Cite As Get BibTex

Abhishek Singh, Pontus Ekberg, and Sanjoy Baruah. Applying Real-Time Scheduling Theory to the Synchronous Data Flow Model of Computation. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ECRTS.2017.8

Abstract

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 modeled using the synchronous data-flow graph (SDFG) model. An enhancement to the standard SDFG model is proposed, that permits the specification of a real-time latency constraint between a specified input and a specified output of an SDFG. A technique is derived for transforming such an enhanced SDFG to a collection of traditional 3-parameter sporadic tasks, thereby allowing for the analysis of systems of SDFG tasks using the methods and algorithms that have previously been developed within the real-time scheduling community for the analysis of systems of such sporadic tasks.  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 recurrent processes that are each represented using the enhanced SDFG model.

Subject Classification

Keywords
  • Real-Time Systems
  • Synchronous Dataflow (SDF)
  • Hard Real-Time Streaming Dataflow Applications
  • Algorithms

Metrics

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

References

  1. H. I. Ali, B. Akesson, and L. M. Pinho. Generalized extraction of real-time parameters for homogeneous synchronous dataflow graphs. In 2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, pages 701-710, March 2015. URL: http://dx.doi.org/10.1109/PDP.2015.57.
  2. M. Bamakhrama and T. Stefanov. Hard-real-time scheduling of data-dependent tasks in embedded streaming applications. In Proceedings of the Ninth ACM International Conference on Embedded Software, EMSOFT'11, pages 195-204, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/2038642.2038672.
  3. M. Bamakhrama and T. Stefanov. 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, CODES+ISSS'12, pages 83-92, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2380445.2380464.
  4. S. Baruah, A. Mok, and L. Rosier. Preemptively scheduling hard-real-time sporadic tasks on one processor. In Proceedings of the 11th Real-Time Systems Symposium, pages 182-190, Orlando, Florida, 1990. IEEE Computer Society Press. URL: http://dx.doi.org/10.1109/REAL.1990.128746.
  5. A. Bouakaz, T. Gautier, and J. P. Talpin. Earliest-deadline first scheduling of multiple independent dataflow graphs. In 2014 IEEE Workshop on Signal Processing Systems (SiPS), pages 1-6, Oct 2014. URL: http://dx.doi.org/10.1109/SiPS.2014.6986102.
  6. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009. Google Scholar
  7. M. Dertouzos. Control robotics : the procedural control of physical processors. In Proceedings of the IFIP Congress, pages 807-813, 1974. Google Scholar
  8. E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269-271, December 1959. URL: http://dx.doi.org/10.1007/BF01386390.
  9. N. Fisher, T. Baker, and S. Baruah. 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, Sydney, Australia, August 2006. IEEE Computer Society Press. URL: http://dx.doi.org/10.1109/RTCSA.2006.12.
  10. A. H. Ghamarian, S. Stuijk, T. Basten, M. C. W. Geilen, and B. D. Theelen. Latency minimization for synchronous data flow graphs. In Digital System Design Architectures, Methods and Tools, 2007. DSD 2007. 10th Euromicro Conference on, pages 189-196, Aug 2007. URL: http://dx.doi.org/10.1109/DSD.2007.4341468.
  11. Jad Khatib, Alix Munier-Kordon, Enagnon Cédric Klikpo, and Kods Trabelsi-Colibet. 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'16, pages 87-96, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2997465.2997479.
  12. Enagnon Cédric Klikpo and Alix Munier-Kordon. 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'16, pages 77-86, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2997465.2997474.
  13. E. A. Lee. A Coupled Hardware and Software Architecture for Programmable Digital Signal Processors. PhD thesis, EECS Department, University of California, Berkeley, 1986. URL: http://www2.eecs.berkeley.edu/Pubs/TechRpts/1986/715.html.
  14. E. A. Lee and D. G. Messerschmitt. Static scheduling of synchronous data flow programs for digital signal processing. IEEE Trans. Comput., 36(1):24-35, January 1987. URL: http://dx.doi.org/10.1109/TC.1987.5009446.
  15. E. A. Lee and D. G. Messerschmitt. Synchronous data flow. Proceedings of the IEEE, 75(9):1235-1245, Sept 1987. URL: http://dx.doi.org/10.1109/PROC.1987.13876.
  16. E. A. Lee and S. A. Seshia. Introduction to Embedded Systems, A Cyber-Physical Systems Approach. MIT Press, 2011. URL: http://LeeSeshia.org.
  17. C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 20(1):46-61, 1973. URL: http://dx.doi.org/10.1145/321738.321743.
  18. M. Mohaqeqi, J. Abdullah, and W. Yi. 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 - Volume 9695, pages 15-29, New York, NY, USA, 2016. Springer-Verlag New York, Inc. URL: http://dx.doi.org/10.1007/978-3-319-39083-3_2.
  19. A. Mok. Fundamental Design Problems of Distributed Systems for The Hard-Real-Time Environment. PhD thesis, Laboratory for Computer Science, Massachusetts Institute of Technology, 1983. Available as Technical Report No. MIT/LCS/TR-297. URL: http://hdl.handle.net/1721.1/15670.
  20. Naval Research Laboratory. PGM - Processing Graph Method Specification, December 1987. Prepared by the Naval Research Laboratory for use by the Navy Standard Signal Processing Program Office (PMS-412). Version 1.0. Google Scholar
  21. I. Ripoll, A. Crespo, and A. K. Mok. Improvement in feasibility testing for real-time tasks. Real-Time Systems: The International Journal of Time-Critical Computing, 11:19-39, 1996. Google Scholar
  22. F. Siyoum. Worst-case temporal analysis of real-time dynamic streaming applications. PhD thesis, PhD thesis, Eindhoven University of Technology, 2014. URL: http://dx.doi.org/10.6100/IR780952.
  23. S. Sriram and S. S. Bhattacharya. Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker, Inc., 2000. Google Scholar
  24. M. Stigge. Real-Time Workload Models: Expressiveness vs. Analysis Efficiency. PhD thesis, Ph.D. thesis, Uppsala University, 2014. Google Scholar
  25. M. Stigge, P. Ekberg, N. Guan, and W. Yi. The digraph real-time task model. In 2011 17th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 71-80, April 2011. URL: http://dx.doi.org/10.1109/RTAS.2011.15.
  26. M. Stigge and W. Yi. Graph-based models for real-time workload: A survey. Real-Time Syst., 51(5):602-636, September 2015. URL: http://dx.doi.org/10.1007/s11241-015-9234-z.
  27. S. Stuijk, M. C. W. Geilen, and T. Basten. SDF³: SDF For Free. In Application of Concurrency to System Design, 6th International Conference, ACSD 2006, Proceedings, pages 276-278. IEEE Computer Society Press, Los Alamitos, CA, USA, June 2006. URL: http://www.es.ele.tue.nl/sdf3, URL: http://dx.doi.org/10.1109/ACSD.2006.23.
  28. F. Zhang and A. Burns. Schedulability analysis for real-time systems with edf scheduling. IEEE Transactions on Computers, 58(9):1250-1258, Sept 2009. URL: http://dx.doi.org/10.1109/TC.2009.58.
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