research-article

Timing-Anomaly Free Dynamic Scheduling of Conditional DAG Tasks on Multi-Core Systems

Authors:

Nan GuanAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 18, Issue 5s

Article No.: 91, Pages 1 - 19

https://doi.org/10.1145/3358236

Published: 08 October 2019 Publication History

Abstract

In this paper, we propose a novel approach to schedule conditional DAG parallel tasks, with which we can derive safe response time upper bounds significantly better than the state-of-the-art counterparts. The main idea is to eliminate the notorious timing anomaly in scheduling parallel tasks by enforcing certain order constraints among the vertices, and thus the response time bound can be accurately predicted off-line by somehow “simulating” the runtime scheduling. A key challenge to apply the timing-anomaly free scheduling approach to conditional DAG parallel tasks is that at runtime it may generate exponentially many instances from a conditional DAG structure. To deal with this problem, we develop effective abstractions, based on which a safe response time upper bound is computed in polynomial time. We also develop algorithms to explore the vertex orders to shorten the response time bound. The effectiveness of the proposed approach is evaluated by experiments with randomly generated DAG tasks with different parameter configurations.

References

[1]

Hamid Arabnejad and Jorge G. Barbosa. 2014. List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE Transactions on Parallel and Distributed Systems 25, 3 (2014), 682--694

Digital Library

[2]

Philip Axer, Sophie Quinton, Moritz Neukirchner, Rolf Ernst, Björn Döbel, and Hermann Härtig. 2013. Response-time analysis of parallel fork-join workloads with real-time constraints. In 2013 25th Euromicro Conference on Real-Time Systems. IEEE, 215--224.

Digital Library

[3]

Sanjoy Baruah. 2015. The federated scheduling of systems of conditional sporadic DAG tasks. In Proceedings of the 12th International Conference on Embedded Software. IEEE Press, 1--10.

Digital Library

[4]

Sanjoy Baruah, Marko Bertogna, and Giorgio Buttazzo. 2015. Multiprocessor Scheduling for Real-time Systems. Springer.

[5]

Sanjoy Baruah, Vincenzo Bonifaci, and Alberto Marchetti-Spaccamela. 2015. The global EDF scheduling of systems of conditional sporadic DAG tasks. In 2015 27th Euromicro Conference on Real-Time Systems. IEEE, 222--231.

Digital Library

[6]

Sanjoy Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Leen Stougie, and Andreas Wiese. 2012. A generalized parallel task model for recurrent real-time processes. In 2012 IEEE 33rd Real-Time Systems Symposium. IEEE, 63--72.

Digital Library

[7]

Jean Paul Calvez, Alan Wyche, and Charles Edmundson. 1993. Embedded Real-time Systems. Vol. 23. Wiley New York.

[8]

Hoon Sung Chwa, Jinkyu Lee, Kieu-My Phan, Arvind Easwaran, and Insik Shin. 2013. Global edf schedulability analysis for synchronous parallel tasks on multicore platforms. In 2013 25th Euromicro Conference on Real-Time Systems. IEEE, 25--34.

Digital Library

[9]

Daniel Cordeiro, Grégory Mounié, Swann Perarnau, Denis Trystram, Jean-Marc Vincent, and Frédéric Wagner. 2010. Random graph generation for scheduling simulations. In Proceedings of the 3rd International ICST Conference on Simulation Tools and Techniques. ICST (Institute for Computer Sciences, Social-Informatics and, 60.

[10]

R. L. Graham. 1969. Bounds on multiprocessing timing anomalies. Siam Journal on Applied Mathematics 17, 2 (1969), 416--429.

Digital Library

[11]

Yu-Kwong Kwok and Ishfaq Ahmad. 1996. Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors. IEEE Transactions on Parallel and Distributed Systems 7, 5 (1996), 506--521.

Digital Library

[12]

Yu-Kwong Kwok and Ishfaq Ahmad. 1999. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys (CSUR) 31, 4 (1999), 406--471.

Digital Library

[13]

Karthik Lakshmanan, Shinpei Kato, and Ragunathan Rajkumar. 2010. Scheduling parallel real-time tasks on multi-core processors. In 2010 31st IEEE Real-Time Systems Symposium. IEEE, 259--268.

Digital Library

[14]

Jing Li, Jian Jia Chen, Kunal Agrawal, Chenyang Lu, Chris Gill, and Abusayeed Saifullah. 2014. Analysis of federated and global scheduling for parallel real-time tasks. In 2014 26th Euromicro Conference on Real-Time Systems. IEEE, 85--96.

Digital Library

[15]

Thomas Lundqvist and Per Stenstrom. 1999. Timing anomalies in dynamically scheduled microprocessors. In Proceedings 20th IEEE Real-Time Systems Symposium (Cat. No. 99CB37054). IEEE, 12--21.

Digital Library

[16]

Alessandra Melani, Marko Bertogna, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, and Giorgio Buttazzo. 2017. Schedulability analysis of conditional parallel task graphs in multicore systems. IEEE Trans. Comput. 66, 2 (2017), 339--353.

Digital Library

[17]

Alessandra Melani, Marko Bertogna, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, and Giorgio C. Buttazzo. 2015. Response-time analysis of conditional DAG tasks in multiprocessor systems. In 2015 27th Euromicro Conference on Real-Time Systems. IEEE, 211--221.

[18]

Risat Mahmud Pathan, Petros Voudouris, and Per Stenstrom. 2018. Scheduling parallel real-time recurrent tasks on multicore platforms. IEEE Transactions on Parallel Distributed Systems PP, 99 (2018), 1--1.

[19]

Jan Reineke, Björn Wachter, Stefan Thesing, Reinhard Wilhelm, Ilia Polian, Jochen Eisinger, and Bernd Becker. 2006. A definition and classification of timing anomalies. In 6th International Workshop on Worst-Case Execution Time Analysis (WCET’06). Schloss Dagstuhl-Leibniz-Zentrum für Informatik.

[20]

Abusayeed Saifullah, Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher Gill. 2013. Multi-core real-time scheduling for generalized parallel task models. Real-Time Systems 49, 4 (2013), 404--435.

[21]

Petros Voudouris, Per Stenström, and Risat Pathan. 2017. Timing-anomaly free dynamic scheduling of task-based parallel applications. In 2017 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, 365--376.

Cited By

He QGuan NLv M(2024)Longer Is Shorter: Making Long Paths to Improve the Worst-Case Response Time of DAG TasksIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.340256643:12(4519-4531)Online publication date: Dec-2024
https://doi.org/10.1109/TCAD.2024.3402566
Gao YYi HChen HFang XZhao S(2024)A Structure-Aware DAG Scheduling and Allocation on Heterogeneous Multicore Systems2024 IEEE 14th International Symposium on Industrial Embedded Systems (SIES)10.1109/SIES62473.2024.10767927(26-33)Online publication date: 23-Oct-2024
https://doi.org/10.1109/SIES62473.2024.10767927
Jiang ZZhao SWei RSi XChen GGuan N(2024)ROTA-I/O: Hardware/Algorithm Co-design for Real-Time I/O Control with Improved Timing Accuracy and Robustness2024 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS62706.2024.00024(174-186)Online publication date: 10-Dec-2024
https://doi.org/10.1109/RTSS62706.2024.00024
Show More Cited By

Index Terms

Timing-Anomaly Free Dynamic Scheduling of Conditional DAG Tasks on Multi-Core Systems
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
      1. Embedded hardware
      2. Embedded software

Recommendations

Schedulability analysis of DAG tasks with arbitrary deadlines under global fixed-priority scheduling

One of the major sources of pessimism in the response time analysis (RTA) of globally scheduled real-time tasks is the computation of an upper-bound on the inter-task interference. This problem is further exacerbated when intra-task parallelism is ...
The federated scheduling of systems of conditional sporadic DAG tasks
EMSOFT '15: Proceedings of the 12th International Conference on Embedded Software

A federated approach to the multiprocessor scheduling of systems of independent recurrent tasks is considered, in which each task is either restricted to execute preemptively upon a single processor, or may execute upon multiple processors but gets ...
Dynamic Partitioning Based Scheduling of Real-Time Tasks in Multicore Processors
ISORC '15: Proceedings of the 2015 IEEE 18th International Symposium on Real-Time Distributed Computing

Existing real-time multicore schedulers use either global or partitioned scheduling technique to schedule real-time tasks. Partitioned scheduling is a static approach in which, a task is mapped to a per-processor ready queue prior to scheduling it and ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 18, Issue 5s

Special Issue ESWEEK 2019, CASES 2019, CODES+ISSS 2019 and EMSOFT 2019

October 2019

1423 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/3365919

Editor:
Sandeep K. Shukla
Indian Institute of Technology, India

Issue’s Table of Contents

Copyright © 2019 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: 08 October 2019

Accepted: 01 July 2019

Revised: 01 June 2019

Received: 01 April 2019

Published in TECS Volume 18, Issue 5s

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
406
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)5

Reflects downloads up to 08 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

He QGuan NLv M(2024)Longer Is Shorter: Making Long Paths to Improve the Worst-Case Response Time of DAG TasksIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.340256643:12(4519-4531)Online publication date: Dec-2024
https://doi.org/10.1109/TCAD.2024.3402566
Gao YYi HChen HFang XZhao S(2024)A Structure-Aware DAG Scheduling and Allocation on Heterogeneous Multicore Systems2024 IEEE 14th International Symposium on Industrial Embedded Systems (SIES)10.1109/SIES62473.2024.10767927(26-33)Online publication date: 23-Oct-2024
https://doi.org/10.1109/SIES62473.2024.10767927
Jiang ZZhao SWei RSi XChen GGuan N(2024)ROTA-I/O: Hardware/Algorithm Co-design for Real-Time I/O Control with Improved Timing Accuracy and Robustness2024 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS62706.2024.00024(174-186)Online publication date: 10-Dec-2024
https://doi.org/10.1109/RTSS62706.2024.00024
Zhang YZhao SChen GHuang K(2024)Fault-tolerant DAG Scheduling with Runtime Reconfiguration on Multicore Real-Time Systems2024 IEEE 35th International Conference on Application-specific Systems, Architectures and Processors (ASAP)10.1109/ASAP61560.2024.00015(19-27)Online publication date: 24-Jul-2024
https://doi.org/10.1109/ASAP61560.2024.00015
He QSun YJiang XLv MLee JGuan N(2024)Real-time scheduling for parallel tasks with resource reclamationReal-Time Systems10.1007/s11241-024-09421-960:2(291-327)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s11241-024-09421-9
He QGuan NLv MJiang XChang W(2024)The shape of a DAG: bounding the response time using long pathsReal-Time Systems10.1007/s11241-023-09397-y60:2(199-238)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s11241-023-09397-y
Chen PChen HLiu WLong LChang WGuan N(2023)DAG-Order: An Order-Based Dynamic DAG Scheduling for Real-Time Networks-on-ChipACM Transactions on Architecture and Code Optimization10.1145/363152721:1(1-24)Online publication date: 3-Nov-2023
https://dl.acm.org/doi/10.1145/3631527
He QSun JGuan NLv MSun Z(2023)Real-Time Scheduling of Conditional DAG Tasks With Intra-Task Priority AssignmentIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.324122142:10(3196-3209)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3241221
Tessler CModekurthy PFisher NSaifullah AMurphy A(2023)Co-Located Parallel Scheduling of Threads to Optimize Cache Sharing2023 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS59052.2023.00030(251-264)Online publication date: 5-Dec-2023
https://doi.org/10.1109/RTSS59052.2023.00030
Xu ZZhang YZhao SChen GLuo HHuang K(2023)DRL-based Task Scheduling and Shared Resource Allocation for Multi-Core Real-Time Systems2023 IEEE 3rd International Conference on Intelligent Technology and Embedded Systems (ICITES)10.1109/ICITES59818.2023.10356887(144-150)Online publication date: 27-Oct-2023
https://doi.org/10.1109/ICITES59818.2023.10356887
Show More Cited By

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.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View Issue’s Table of Contents