More Web Proxy on the site http://driver.im/

research-article

Worst-Case Response Time Analysis of a Synchronous Dataflow Graph in a Multiprocessor System with Real-Time Tasks

Authors:

Soonhoi HaAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 22, Issue 2

Article No.: 36, Pages 1 - 26

https://doi.org/10.1145/2997644

Published: 20 January 2017 Publication History

Abstract

In this article, we propose a novel technique that estimates a tight upper bound of the worst-case response time (WCRT) of a synchronous dataflow (SDF) graph when the SDF graph shares processors with other real-time tasks. When an SDF graph is executed at runtime under a self-timed or static assignment scheduling policy on a multi-processor system, static scheduling of the SDF graph does not guarantee the satisfaction of latency constraints since changes to the schedule may result in timing anomalies. To estimate the WCRT of an SDF graph with a given mapping and scheduling result, we first construct a task instance dependency graph that depicts the dependency between node executions in a static schedule. The proposed technique combines two techniques in a novel way: schedule time bound analysis and response time analysis. The former is used to consider the interference between task instances in the same SDF graph, and the latter is used to consider the interference from other real-time tasks. Through extensive experiments with synthetic examples and benchmarks, we verify the superior performance of the proposed technique compared to other existent techniques.

References

[1]

H. I. Ali, B. Akesson, and L. M. Pinho. 2015. Generalized extraction of real-time parameters for homogeneous synchronous dataflow graphs. In Proceedings of the 2015 23rd Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP’15). 701--710.

Digital Library

[2]

Mohamed Bamakhrama and Todor Stefanov. 2011. Hard-real-time scheduling of data-dependent tasks in embedded streaming applications. In Proceedings of the 9th ACM International Conference on Embedded Software (EMSOFT’11). ACM, New York, NY, 195--204.

Digital Library

[3]

Mohamed A. Bamakhrama and Todor P. Stefanov. 2013. On the hard-real-time scheduling of embedded streaming applications. Des. Autom. Embedd. Syst. 17, 2 (June 2013), 221--249.

Digital Library

[4]

Neal Bambha, Vida Kianzad, Mukul Khandelia, and Shuvra S. Bhattacharyya. 2002. Intermediate representations for design automation of multiprocessor DSP systems. Des. Autom. Embedd. Syst. 7, 4 (2002), 307--323.

Digital Library

[5]

G. Bilsen, M. Engels, R. Lauwereins, and J. A. Peperstraete. 1995. Cyclo-static data flow. In Proceedings of the 1995 International Conference on Acoustics, Speech, and Signal Processing 1995 (ICASSP-95), Vol. 5. 3255--3258 vol. 5.

[6]

B. Bodin, A. Munier-Kordon, and B. D. de Dinechin. 2013. Periodic schedules for cyclo-static dataflow. In Proceedings of the 2013 IEEE 11th Symposium on Embedded Systems for Real-time Multimedia (ESTIMedia). 105--114.

[7]

Alan Burns and Sanjoy Baruah. 2008. Sustainability in real-time scheduling. J. Comput. Sci. Eng. (2008), 74--97.

[8]

Junchul Choi and Soonhoi Ha. 2016. A java implementation of the proposed technique. Retrieved from https://github.com/hinomk2/TODAES_implementation.

[9]

Junchul Choi, Hyunok Oh, Sungchan Kim, and Soonhoi Ha. 2012. Executing synchronous dataflow graphs on a SPM-based multicore architecture. In Proceedings of the 49th Annual Design Automation Conference (DAC’12). ACM, New York, NY, 664--671.

Digital Library

[10]

Jonas Diemer and Philip Axer. 2012. Python implementation of Compositional Performance Analysis. (2012). Retrieved from http://pycpa.readthedocs.org/en/latest/.

[11]

A. H. Ghamarian, M. C. W. Geilen, S. Stuijk, T. Basten, A. J. M. Moonen, M. J. G. Bekooij, B. D. Theelen, and M. R. Mousavi. 2006. Throughput analysis of synchronous data flow graphs. In Proceedings of the 6th International Conference on Application of Concurrency to System Design, 2006 (ACSD’06). 25--36.

Digital Library

[12]

A. H. Ghamarian, S. Stuijk, T. Basten, M. C. W. Geilen, and B. D. Theelen. 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’07). 189--196.

Digital Library

[13]

R. L. Graham. 1969. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17, 2 (1969), 416--429.

Digital Library

[14]

Michael Gonzlez Harbour. 2001. MAST: Modeling and Anlysis Suite for Real-Time Applications. Retrieved from http://mast.unican.es/.

[15]

R. Henia, A. Hamann, M. Jersak, R. Racu, K. Richter, and R. Ernst. 2005. System level performance analysis—The SymTA/S approach. IEEE Proceedings of Computers and Digital Techniques 152, 2 (Mar 2005), 148--166.

[16]

Jinwoo Kim, Hyunok Oh, Junchul Choi, Hyojin Ha, and Soonhoi Ha. 2013. A novel analytical method for worst case response time estimation of distributed embedded systems. In Proceedings of the 2013 50th ACM/EDAC/IEEE Design Automation Conference (DAC). 1--10.

Digital Library

[17]

E. Lee and S. Ha. 1989. Scheduling strategies for multiprocessor real-time DSP. In Proceedings of the Global Telecommunications Conference and Exhibition &rsquor;Communications Technology for the 1990s and Beyond&lsquor; (GLOBECOM), 1989. IEEE. 1279--1283 vol. 2.

[18]

Edward A. Lee and David G. Messerschmitt. 1987. Synchronous data flow. Proc. IEEE 75, 9 (Sep. 1987), 1235--1245.

[19]

J. Lehoczky, Lui Sha, and Y. Ding. 1989. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In Proceedings of the Real Time Systems Symposium, 1989. 166--171.

[20]

J. C. Palencia and M. González Harbour. 1998. Schedulability analysis for tasks with static and dynamic offsets. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’98). IEEE Computer Society, Washington, DC, USA, 26--.

Digital Library

[21]

Rodolfo Pellizzoni and Giuseppe Lipari. 2007. Holistic analysis of asynchronous real-time transactions with earliest deadline scheduling. J. Comput. Syst. Sci. 73, 2 (March 2007), 186--206.

Digital Library

[22]

Manar Qamhieh, Sanjoy K. Baruah, Maryline Chetto, Liliana Cucu-Grosjean, Laurent George, Serge Midonnet, and Pascal Richard. 2015. Scheduling of parallel real-time DAG tasks on multiprocessor systems. Retrieved from http://igm.univ-mlv.fr/&sim;qamhieh/src/ManarQamhieh_PhDThesis.pdf.

[23]

Tae-ho Shin, Hyunok Oh, and Soonhoi Ha. 2011. Minimizing buffer requirements for throughput constrained parallel execution of synchronous dataflow graph. In Proceedings of the 16th Asia and South Pacific Design Automation Conference (ASPDAC’11). IEEE Press, Piscataway, NJ, 165--170.

Digital Library

[24]

J. Spasic, Di Liu, E. Cannella, and T. Stefanov. 2015. Improved hard real-time scheduling of CSDF-modeled streaming applications. In Proceedings of the 2015 International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS). 65--74.

Digital Library

[25]

Sander Stuijk, Marc Geilen, and Twan Basten. 2006a. Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs. In Proceedings of the 43rd Annual Design Automation Conference (DAC’06). ACM, New York, NY, 899--904.

Digital Library

[26]

Sander Stuijk, Marc Geilen, and Twan Basten. 2006b. SDF3:SDF For Free. Retrieved from http://www.es.ele.tue.nl/sdf3/download/examples.php.

[27]

S. Stuijk, M. Geilen, and T. Basten. 2008. Throughput-buffering trade-off exploration for cyclo-static and synchronous dataflow graphs. Computers, IEEE Transactions on 57, 10 (Oct. 2008), 1331--1345.

Digital Library

[28]

Ken Tindell and John Clark. 1994. Holistic schedulability analysis for distributed hard real-time systems. Microprocess. Microprogram. 40, 2--3 (Apr. 1994), 117--134.

Digital Library

[29]

R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, and P. Stenström. 2008. The worst-case execution-time problem - overview of methods and survey of tools. ACM Trans. Embed. Comput. Syst. 7, 3, Article 36 (May 2008), 53 pages.

Digital Library

[30]

Ti-Yen Yen and Wayne Wolf. 1998. Performance estimation for real-time distributed embedded systems. IEEE Trans. Parallel Distrib. Syst. 9, 11 (Nov. 1998), 1125--1136.

Digital Library

Cited By

Ortiz LGuasque ABalbastre PSimó JCrespo A(2024)Schedulability Analysis in Fixed-Priority Real-Time Multicore Systems with ContentionApplied Sciences10.3390/app1410403314:10(4033)Online publication date: 9-May-2024
https://doi.org/10.3390/app14104033
Xie GXiong CWu WLi RChang W(2023)Holistic WCRT Analysis for Global Fixed-Priority Preemptive Multiprocessor Scheduling2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247970(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247970
Wang LWang CWang H(2022)Improved Scheduling Algorithm for Synchronous Data Flow Graphs on a Homogeneous Multi-Core SystemsAlgorithms10.3390/a1502005615:2(56)Online publication date: 9-Feb-2022
https://doi.org/10.3390/a15020056
Show More Cited By

Index Terms

Worst-Case Response Time Analysis of a Synchronous Dataflow Graph in a Multiprocessor System with Real-Time Tasks
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems
2. Hardware
  1. Electronic design automation
    1. Timing analysis
      1. Static timing analysis

Recommendations

Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption

Fixed-priority scheduling with deferred preemption (FPDS) has been proposed in the literature as a viable alternative to fixed-priority pre-emptive scheduling (FPPS), that obviates the need for non-trivial resource access protocols and reduces the cost ...
Preference-oriented partitioning for multiprocessor real-time systems
Abstract
Recently, real-time application models where tasks may have as early as possible (ASAP) or as late as possible (ALAP) execution preferences, while meeting their deadlines, have been proposed and studied. In this work we consider the ...
Highlights
- A novel Reverse-Preference Priority Assignment scheme for POFP scheduler is proposed
New response time analysis for global EDF on a multiprocessor platform

Time-predictability is the most important requirement for a real-time system, and researchers have therefore paid attention to the duration between the arrival and completion of a real-time task, called response time. RTA (Response Time Analysis) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 22, Issue 2

Special Section of IDEA: Integrating Dataflow, Embedded Computing, and Architecture

April 2017

458 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/3029795

Editor:
Naehyuck Chang
Korea Advanced Institute of Science and Technology, Korea

Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 20 January 2017

Accepted: 01 September 2016

Revised: 01 September 2016

Received: 01 January 2016

Published in TODAES Volume 22, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Ministry of Science
ICT 8 Future Planning
Basic Science Research Program through the National Research Foundation of Korea (NRF)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
260
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ortiz LGuasque ABalbastre PSimó JCrespo A(2024)Schedulability Analysis in Fixed-Priority Real-Time Multicore Systems with ContentionApplied Sciences10.3390/app1410403314:10(4033)Online publication date: 9-May-2024
https://doi.org/10.3390/app14104033
Xie GXiong CWu WLi RChang W(2023)Holistic WCRT Analysis for Global Fixed-Priority Preemptive Multiprocessor Scheduling2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247970(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247970
Wang LWang CWang H(2022)Improved Scheduling Algorithm for Synchronous Data Flow Graphs on a Homogeneous Multi-Core SystemsAlgorithms10.3390/a1502005615:2(56)Online publication date: 9-Feb-2022
https://doi.org/10.3390/a15020056
Kocian AChessa S(2022)Iterative Probabilistic Performance Prediction for Multiple IoT Applications in ContentionIEEE Internet of Things Journal10.1109/JIOT.2022.31423249:15(13416-13424)Online publication date: 1-Aug-2022
https://doi.org/10.1109/JIOT.2022.3142324
Choi JYang HHa S(2018)Optimization of Fault-Tolerant Mixed-Criticality Multi-Core Systems with Enhanced WCRT AnalysisACM Transactions on Design Automation of Electronic Systems10.1145/327515424:1(1-26)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1145/3275154

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents