{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T10:10:31Z","timestamp":1767262231748,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2019,10,14]],"date-time":"2019-10-14T00:00:00Z","timestamp":1571011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Ministry of Education Joint Foundation for Equipment Pre-Research","award":["6141A020333"],"award-info":[{"award-number":["6141A020333"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61772123 and 61672140"],"award-info":[{"award-number":["61772123 and 61672140"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Key R8D Program of China","award":["2018YFB1702000"],"award-info":[{"award-number":["2018YFB1702000"]}]},{"name":"Research Grants Council of Hong Kong","award":["GRF 15204917 and 15213818"],"award-info":[{"award-number":["GRF 15204917 and 15213818"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2019,11,30]]},"abstract":"<jats:p>\n            Real-time and embedded systems are shifting from single-core to multi-core processors, on which the software must be parallelized to fully utilize the computation capacity of the hardware. Recently, much work has been done on real-time scheduling of\n            <jats:italic>parallel<\/jats:italic>\n            tasks modeled as directed acyclic graphs (DAG). However, most of these studies assume tasks to have implicit or constrained deadlines. Much less work considered the general case of arbitrary deadlines (i.e., the relative deadline is allowed to be larger than the period), which is more difficult to analyze due to intra-task interference among jobs. In this article, we study the analysis of Global Earliest Deadline First (GEDF) scheduling for DAG parallel tasks with arbitrary deadlines. We develop new analysis techniques for GEDF scheduling of a single DAG task and this new analysis techniques can guarantee a better capacity augmentation bound 2.41 (the best known result is 2.5) in the case of a single task. Furthermore, the proposed analysis techniques are also extended to the case of multiple DAG tasks under GEDF and federated scheduling. Finally, through empirical evaluation, we justify the out-performance of our schedulability tests compared to the state-of-the-art in general.\n          <\/jats:p>","DOI":"10.1145\/3358603","type":"journal-article","created":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T16:35:58Z","timestamp":1571157358000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Real-Time Scheduling of DAG Tasks with Arbitrary Deadlines"],"prefix":"10.1145","volume":"24","author":[{"given":"Kankan","family":"Wang","sequence":"first","affiliation":[{"name":"Northeastern University, Shenyang, Liaoning, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xu","family":"Jiang","sequence":"additional","affiliation":[{"name":"University of Electronic Science and Technology of China, China and The Hong Kong Polytechnic University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nan","family":"Guan","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Di","family":"Liu","sequence":"additional","affiliation":[{"name":"Yunnan University, Yunnan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weichen","family":"Liu","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qingxu","family":"Deng","sequence":"additional","affiliation":[{"name":"Northeastern Universityt, Shenyang, Liaoning, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,10,14]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"OpenMP ARB. 2013. OpenMP Application Program Interface Version 4.0. OpenMP 4.0 Complete Specifications. OpenMP ARB.  OpenMP ARB. 2013. OpenMP Application Program Interface Version 4.0. OpenMP 4.0 Complete Specifications. OpenMP ARB."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.7873\/DATE.2015.0200"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.33"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2830865.2830866"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2012.59"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-007-9022-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2013.32"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-016-9255-2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4108\/ICST.SIMUTOOLS2010.8667"},{"volume-title":"Proceedings of the IEEE 26th Real-Time Systems Symposium (RTSS\u201905)","author":"UmaMaheswari","key":"e_1_2_1_10_1","unstructured":"UmaMaheswari C. Devi and James H. Anderson. 2005. Tardiness bounds under global EDF scheduling on a multiprocessor . In Proceedings of the IEEE 26th Real-Time Systems Symposium (RTSS\u201905) . IEEE, Miami, FL, USA, 330--341. UmaMaheswari C. Devi and James H. Anderson. 2005. Tardiness bounds under global EDF scheduling on a multiprocessor. In Proceedings of the IEEE 26th Real-Time Systems Symposium (RTSS\u201905). IEEE, Miami, FL, USA, 330--341."},{"volume-title":"A Guide to the Theory of NP-Completeness","author":"Garey Michael R.","key":"e_1_2_1_11_1","unstructured":"Michael R. Garey . 1979. A Guide to the Theory of NP-Completeness . W. H. Freeman 8 Co. Michael R. Garey. 1979. A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2017.00015"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2016.031"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 25th Euromicro Conference on Real-Time Systems (ECRTS\u201913)","author":"Li Jing","year":"2013","unstructured":"Jing Li , Kunal Agrawal , Chenyang Lu , and Christopher Gill . 2013 . Analysis of global EDF for parallel tasks . In Proceedings of the 25th Euromicro Conference on Real-Time Systems (ECRTS\u201913) . IEEE, Paris, France, 3--13. Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher Gill. 2013. Analysis of global EDF for parallel tasks. In Proceedings of the 25th Euromicro Conference on Real-Time Systems (ECRTS\u201913). IEEE, Paris, France, 3--13."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2014.23"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2516821.2516836"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2659787.2659818"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.2297919"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9166-9"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3358603","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3358603","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:13Z","timestamp":1750202593000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3358603"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,14]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,11,30]]}},"alternative-id":["10.1145\/3358603"],"URL":"https:\/\/doi.org\/10.1145\/3358603","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2019,10,14]]},"assertion":[{"value":"2019-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}