research-article

Feasibility of Fork-Join Real-Time Task Graph Models: Hardness and Algorithms

Authors:

Wang YiAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 15, Issue 1

Article No.: 14, Pages 1 - 28

https://doi.org/10.1145/2809780

Published: 20 February 2016 Publication History

Abstract

In the formal analysis of real-time systems, modeling of branching codes and modeling of intratask parallelism structures are two of the most important research topics. These two real-time properties are combined, resulting in the fork-join real-time task (FJRT) model, which extends the digraph-based task model with forking and joining semantics. We prove that the EDF schedulability problem on a preemptive uniprocessor for the FJRT model is coNP-hard in the strong sense, even if the utilization of the task system is bounded by a constant strictly less than 1. Then, we show that the problem becomes tractable with some slight structural restrictions on parallel sections, for which we propose an exact schedulability test with pseudo-polynomial time complexity. Our results thus establish a borderline between the tractable and intractable FJRT models.

References

[1]

Anne Angermann. 2007. Matlab-Simulink-Stateflow: Grundlagen, Toolboxen, Beispiele {mit CD-ROM}. Oldenbourg Verlag.

[2]

Philip Axer, Sophie Quinton, Moritz Neukirchner, Rolf Ernst, Bjorn Dobel, and Hermann Hartig. 2013. Response-time analysis of parallel fork-join workloads with real-time constraints. In 2013 25th Euromicro Conference on Real-Time Systems (ECRTS’13). IEEE, 215--224.

Digital Library

[3]

Sanjoy Baruah. 2010a. The non-cyclic recurring real-time task model. In 2010 IEEE 31st Real-Time Systems Symposium (RTSS’10). IEEE, 173--182.

Digital Library

[4]

Sanjoy Baruah. 2010b. Preemptive uniprocessor scheduling of non-cyclic GMF task systems. In 2010 IEEE 16th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’10). IEEE, 195--202.

Digital Library

[5]

Sanjoy Baruah. 2014. Improved multiprocessor global schedulability analysis of sporadic DAG task systems. In 2014 26th Euromicro Conference on Real-Time Systems (ECRTS’14). IEEE, 97--105.

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 (RTSS’12). IEEE, 63--72.

Digital Library

[7]

Sanjoy Baruah, Deji Chen, Sergey Gorinsky, and Aloysius Mok. 1999. Generalized multiframe tasks. Real-Time Systems 17, 1, 5--22.

Digital Library

[8]

Sanjoy Baruah and Nathan Fisher. 2005. The partitioned multiprocessor scheduling of sporadic task systems. In 26th IEEE International Real-Time Systems Symposium, 2005 (RTSS’05). IEEE, 9--pp.

Digital Library

[9]

Sanjoy K. Baruah. 2003. Dynamic-and static-priority scheduling of recurring real-time tasks. Real-Time Systems 24, 1, 93--128.

Digital Library

[10]

Sanjoy K. Baruah and Theodore P. Baker. 2008. Global EDF schedulability analysis of arbitrary sporadic task systems. In ECRTS. 3--12.

Digital Library

[11]

Sanjoy K. Baruah, Aloysius K. Mok, and Louis E. Rosier. 1990. Preemptively scheduling hard-real-time sporadic tasks on one processor. In Proceedings of the 11th Real-Time Systems Symposium, 1990.IEEE, 182--190.

[12]

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 (ECRTS’13). IEEE, 24--34.

Digital Library

[13]

Stephen A. Cook. 1971. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing. ACM, New York, NY, 151--158.

Digital Library

[14]

Daniel Ejsing-Duun, Lisa Fontani, Jonas Finnemann Jensen, Jacob Haubach, and Lars Kærlund Østergaard Smedegård. 2013. The concurrent real-time task model. Aalborg University, Denmark, Tech. Rep, 2014, 1--35. Retrieved December 17, 2015 from http://www.lets.dk/downloads/CRT.pdf.

[15]

David Ferry, Jing Li, Mahesh Mahadevan, Kunal Agrawal, Christopher Gill, and Chenyang Lu. 2013. A real-time scheduling service for parallel tasks. In 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS’13). IEEE, 261--272.

Digital Library

[16]

Aloysius Ka and Lau Mok. 1983. Fundamental design problems of distributed systems for the hard-real-time environment. Vol. 1. MIT Thesis, Cambridge, MA.

[17]

Shinpei Kato and Yutaka Ishikawa. 2009. Gang EDF scheduling of parallel task systems. In 30th IEEE Real-Time Systems Symposium, 2009 (RTSS’09). IEEE, 459--468.

Digital Library

[18]

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

Digital Library

[19]

Chung Laung Liu and James W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM 20, 1, 46--61.

Digital Library

[20]

Aloysius K. Mok and Deji Chen. 1997. A multiframe model for real-time tasks. IEEE Transactions on Software Engineering 23, 10, 635--645.

Digital Library

[21]

Geoffrey Nelissen, Vandy Berten, Joël Goossens, and Dragomir Milojevic. 2012. Techniques optimizing the number of processors to schedule multi-threaded tasks. In 2012 24th Euromicro Conference on Real-Time Systems (ECRTS’12). IEEE, 321--330.

Digital Library

[22]

Abusayeed Saifullah, Kunal Agrawal, Chenyang Lu, and Christopher Gill. 2011. Multi-core real-time scheduling for generalized parallel task models. In 2011 IEEE 32nd Real-Time Systems Symposium (RTSS’11). IEEE, 217--226.

Digital Library

[23]

Abusayeed Saifullah, David Ferry, Kunal Agrawal, Chenyang Lu, and Christopher Gill. 2012. Real-time scheduling of parallel tasks under general DAG model. Washington University in St Louis, USA, Tech. Rep. WUCSE-2012-14, 2012.

[24]

Martin Stigge, Pontus Ekberg, Nan Guan, and Wang Yi. 2011. The digraph real-time task model. In 2011 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’11). IEEE, 71--80.

Digital Library

[25]

Martin Stigge, Pontus Ekberg, and Wang Yi. 2013. The fork-join real-time task model. ACM SIGBED Review 10, 2, 20--20.

Digital Library

[26]

Martin Stigge and Wang Yi. 2013. Combinatorial abstraction refinement for feasibility analysis. In 2013 IEEE 34th Real-Time Systems Symposium (RTSS’13). IEEE, 340--349.

Digital Library

Cited By

NISHIKAWA HSHIMADA KTANIGUCHI ITOMIYAMA H(2022)Simultaneous Scheduling and Core-Type Optimization for Moldable Fork-Join Tasks on Heterogeneous MulticoresIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2021VLP0003E105.A:3(540-548)Online publication date: 1-Mar-2022
https://doi.org/10.1587/transfun.2021VLP0003
Tang YGuan NYi W(2022)Real-Time Task ModelsHandbook of Real-Time Computing10.1007/978-981-287-251-7_29(469-487)Online publication date: 9-Aug-2022
https://doi.org/10.1007/978-981-287-251-7_29
Nishikawa HShimada KTaniguchi ITomiyama HCorporaal H(2020)Scheduling of moldable fork-join tasks with inter- and intra-task communicationsProceedings of the 23th International Workshop on Software and Compilers for Embedded Systems10.1145/3378678.3391875(7-12)Online publication date: 25-May-2020
https://dl.acm.org/doi/10.1145/3378678.3391875
Show More Cited By

Index Terms

Feasibility of Fork-Join Real-Time Task Graph Models: Hardness and Algorithms
1. Networks
  1. Network protocols

Recommendations

Uniform weak tractability

We introduce a new notion of tractability which is called uniform weak tractability. A problem is uniformly weakly tractable if the information complexity n(@e,d) of its d-variate component to be solved to within @e is not exponential in any positive ...
On the Tractability of Digraph-Based Task Models
ECRTS '11: Proceedings of the 2011 23rd Euromicro Conference on Real-Time Systems

In formal analysis of real-time systems, a major concern is the analysis efficiency. As the expressiveness of models grows, so grows the complexity of their analysis. A recently proposed model, the digraph real-time task model (DRT), offers high ...
Quantifying Energy Consumption for Practical Fork-Join Parallelism on an Embedded Real-Time Operating System
RTNS '16: Proceedings of the 24th International Conference on Real-Time Networks and Systems

In this work, we present the experimental assessment of a parallel framework that allows to reduce the energy consumption of MPSoC platforms running hard real-time systems. We use a power-aware Fork-Join task model based on primitives of the OpenMP ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 15, Issue 1

February 2016

530 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/2872313

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

Issue’s Table of Contents

Copyright © 2016 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 February 2016

Accepted: 01 July 2015

Revised: 01 April 2015

Received: 01 September 2014

Published in TECS Volume 15, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Natural Science Foundation of China
National Basic Pre-research Program of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
305
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)2

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

NISHIKAWA HSHIMADA KTANIGUCHI ITOMIYAMA H(2022)Simultaneous Scheduling and Core-Type Optimization for Moldable Fork-Join Tasks on Heterogeneous MulticoresIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2021VLP0003E105.A:3(540-548)Online publication date: 1-Mar-2022
https://doi.org/10.1587/transfun.2021VLP0003
Tang YGuan NYi W(2022)Real-Time Task ModelsHandbook of Real-Time Computing10.1007/978-981-287-251-7_29(469-487)Online publication date: 9-Aug-2022
https://doi.org/10.1007/978-981-287-251-7_29
Nishikawa HShimada KTaniguchi ITomiyama HCorporaal H(2020)Scheduling of moldable fork-join tasks with inter- and intra-task communicationsProceedings of the 23th International Workshop on Software and Compilers for Embedded Systems10.1145/3378678.3391875(7-12)Online publication date: 25-May-2020
https://dl.acm.org/doi/10.1145/3378678.3391875
Sun JShi RWang KGuan NGuo Z(2020)Efficient Feasibility Analysis for Graph-based Real-Time Task SystemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.3012174(1-1)Online publication date: 2020
https://doi.org/10.1109/TCAD.2020.3012174
Sun JGuan NSun JZhang XChi YLi F(2020)Algorithms for Computing the WCRT bound of OpenMP Task Systems with Conditional BranchesIEEE Transactions on Computers10.1109/TC.2020.2984502(1-1)Online publication date: 2020
https://doi.org/10.1109/TC.2020.2984502
Tang YGuan NYi W(2020)Real-Time Task ModelsHandbook of Real-Time Computing10.1007/978-981-4585-87-3_29-1(1-19)Online publication date: 18-May-2020
https://doi.org/10.1007/978-981-4585-87-3_29-1
Nishikawa HShimada KTaniguchi ITomiyama H(2019)A Constraint Programming Approach to Scheduling of Malleable TasksInternational Journal of Networking and Computing10.15803/ijnc.9.2_1319:2(131-146)Online publication date: 2019
https://doi.org/10.15803/ijnc.9.2_131
Nishikawa HShimada KTaniguchi ITomiyama H(2019)Energy-aware scheduling of malleable fork-join tasks under a deadline constraint on heterogeneous multicoresACM SIGBED Review10.1145/3373400.337340916:3(57-62)Online publication date: 25-Nov-2019
https://dl.acm.org/doi/10.1145/3373400.3373409
Sun JGuan NSun JChi Y(2019)Calculating Response-Time Bounds for OpenMP Task Systems with Conditional Branches2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2019.00022(169-181)Online publication date: Apr-2019
https://doi.org/10.1109/RTAS.2019.00022
Nishikawa HShimada KTaniguchi ITomiyama H(2018)Scheduling of Malleable Fork-Join Tasks with Constraint Programming2018 Sixth International Symposium on Computing and Networking (CANDAR)10.1109/CANDAR.2018.00025(133-138)Online publication date: Nov-2018
https://doi.org/10.1109/CANDAR.2018.00025
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.

Media

Figures

Other

Tables

View Issue’s Table of Contents