{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T05:43:39Z","timestamp":1761198219380,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T00:00:00Z","timestamp":1684972800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T00:00:00Z","timestamp":1684972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Research Grants Council of Hong Kong","award":["GRF 11208522","GRF 15206221"],"award-info":[{"award-number":["GRF 11208522","GRF 15206221"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["NSFC 62102072"],"award-info":[{"award-number":["NSFC 62102072"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2024,6]]},"DOI":"10.1007\/s11241-023-09397-y","type":"journal-article","created":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T16:02:01Z","timestamp":1685030521000},"page":"199-238","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The shape of a DAG: bounding the response time using long paths"],"prefix":"10.1007","volume":"60","author":[{"given":"Qingqiang","family":"He","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5067-8571","authenticated-orcid":false,"given":"Nan","family":"Guan","sequence":"additional","affiliation":[]},{"given":"Mingsong","family":"Lv","sequence":"additional","affiliation":[]},{"given":"Xu","family":"Jiang","sequence":"additional","affiliation":[]},{"given":"Wanli","family":"Chang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,25]]},"reference":[{"key":"9397_CR1","unstructured":"Agrawal K, Baruah S (2018) A measurement-based model for parallel real-time tasks. In: 30th Euromicro Conference on Real-Time Systems (ECRTS 2018), Schloss Dagstuhl\u2013Leibniz\u2013Zentrum fuer Informatik"},{"key":"9397_CR2","doi-asserted-by":"crossref","unstructured":"Baruah S (2007) Techniques for multiprocessor global schedulability analysis. In: 28th IEEE international real-time systems symposium (RTSS), IEEE, pp 119\u2013128","DOI":"10.1109\/RTSS.2007.35"},{"key":"9397_CR3","doi-asserted-by":"crossref","unstructured":"Baruah S (2014) Improved multiprocessor global schedulability analysis of sporadic DAG task systems. In: 2014 26th Euromicro conference on real-time systems, IEEE, pp 97\u2013105","DOI":"10.1109\/ECRTS.2014.22"},{"key":"9397_CR4","doi-asserted-by":"crossref","unstructured":"Baruah S (2015a) The federated scheduling of constrained-deadline sporadic DAG task systems. In: 2015 design, automation & test in Europe conference & Exhibition (DATE), IEEE, pp 1323\u20131328","DOI":"10.7873\/DATE.2015.0200"},{"key":"9397_CR5","doi-asserted-by":"crossref","unstructured":"Baruah S (2015b) Federated scheduling of sporadic DAG task systems. In: 2015 IEEE international parallel and distributed processing symposium, IEEE, pp 179\u2013186","DOI":"10.1109\/IPDPS.2015.33"},{"key":"9397_CR6","doi-asserted-by":"crossref","unstructured":"Baruah S (2015c) The federated scheduling of systems of conditional sporadic DAG tasks. In: Proceedings of the 12th international conference on embedded software, IEEE Press, pp 1\u201310","DOI":"10.1109\/EMSOFT.2015.7318254"},{"key":"9397_CR7","unstructured":"Baruah S, Fisher N (2005) The partitioned multiprocessor scheduling of sporadic task systems. In: 26th IEEE international real-time systems symposium (RTSS), IEEE, pp 9"},{"key":"9397_CR8","doi-asserted-by":"crossref","unstructured":"Bi R, He Q, Sun J, et al (2022) Response time analysis for prioritized DAG task with mutually exclusive vertices. In: 2022 IEEE real-time systems symposium (RTSS), IEEE, pp 460\u2013473","DOI":"10.1109\/RTSS55097.2022.00046"},{"key":"9397_CR9","doi-asserted-by":"crossref","unstructured":"Bonifaci V, Marchetti-Spaccamela A, Stiller S, et al (2013) Feasibility analysis in the sporadic DAG task model. In: 2013 25th Euromicro conference on real-time systems, IEEE, pp 225\u2013233","DOI":"10.1109\/ECRTS.2013.32"},{"key":"9397_CR10","doi-asserted-by":"crossref","unstructured":"Casini D, Biondi A, Nelissen G, et al (2018) Partitioned fixed-priority scheduling of parallel tasks without preemptions. In: 2018 IEEE real-time systems symposium (RTSS), IEEE, pp 421\u2013433","DOI":"10.1109\/RTSS.2018.00056"},{"issue":"5s","key":"9397_CR11","first-page":"1","volume":"18","author":"P Chen","year":"2019","unstructured":"Chen P, Liu W, Jiang X et al (2019) Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems. ACM Trans Embed Comput Syst (TECS) 18(5s):1\u201319","journal-title":"ACM Trans Embed Comput Syst (TECS)"},{"key":"9397_CR12","doi-asserted-by":"crossref","unstructured":"Cordeiro D, Mouni\u00e9 G, Perarnau S, et al (2010) Random graph generation for scheduling simulations. In: Proceedings of the 3rd international ICST conference on simulation tools and techniques, ICST, p 60","DOI":"10.4108\/ICST.SIMUTOOLS2010.8667"},{"key":"9397_CR13","doi-asserted-by":"crossref","unstructured":"Dong Z, Liu C (2017) Analysis techniques for supporting hard real-time sporadic gang task systems. In: 2017 IEEE real-time systems symposium (RTSS), IEEE, pp 128\u2013138","DOI":"10.1109\/RTSS.2017.00019"},{"key":"9397_CR14","doi-asserted-by":"crossref","unstructured":"Fonseca J, Nelissen G, N\u00e9lis V (2017) Improved response time analysis of sporadic DAG tasks for global FP scheduling. In: Proceedings of the 25th international conference on real-time networks and systems, pp 28\u201337","DOI":"10.1145\/3139258.3139288"},{"issue":"2","key":"9397_CR15","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s11241-018-09325-5","volume":"55","author":"J Fonseca","year":"2019","unstructured":"Fonseca J, Nelissen G, N\u00e9lis V (2019) Schedulability analysis of DAG tasks with arbitrary deadlines under global fixed-priority scheduling. Real-Time Syst 55(2):387\u2013432","journal-title":"Real-Time Syst"},{"issue":"2","key":"9397_CR16","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17(2):416\u2013429","journal-title":"SIAM J Appl Math"},{"issue":"11","key":"9397_CR17","doi-asserted-by":"publisher","first-page":"2567","DOI":"10.1109\/TPDS.2019.2916696","volume":"30","author":"M Han","year":"2019","unstructured":"Han M, Guan N, Sun J et al (2019) Response time bounds for typed DAG parallel tasks on heterogeneous multi-cores. IEEE Trans Parallel Distrib Syst 30(11):2567\u20132581","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"10","key":"9397_CR18","doi-asserted-by":"publisher","first-page":"2283","DOI":"10.1109\/TPDS.2019.2910525","volume":"30","author":"Q He","year":"2019","unstructured":"He Q, Jiang X, Guan N et al (2019) Intra-task priority assignment in real-time scheduling of DAG tasks on multi-cores. IEEE Trans Parallel Distrib Syst 30(10):2283\u20132295","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"9397_CR19","unstructured":"He Q, Lv M, Guan N (2021) Response time bounds for DAG tasks with arbitrary intra-task priority assignment. In: 33rd Euromicro conference on real-time systems (ECRTS), Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"9397_CR20","doi-asserted-by":"crossref","unstructured":"He Q, Guan N, Lv M, et al (2022) Bounding the response time of DAG tasks using long paths. In: 2022 IEEE real-time systems symposium (RTSS), IEEE, pp 474\u2013486","DOI":"10.1109\/RTSS55097.2022.00047"},{"key":"9397_CR21","doi-asserted-by":"crossref","unstructured":"He Q, Guan N, Lv M, et al (2023a) On the degree of parallelism in real-time scheduling of DAG tasks. In: 2023 design, automation & test in Europe conference & exhibition (DATE), IEEE","DOI":"10.23919\/DATE56975.2023.10137259"},{"key":"9397_CR22","doi-asserted-by":"crossref","unstructured":"He Q, Sun J, Guan N, et al (2023b) Real-time scheduling of conditional DAG tasks with intra-task priority assignment. IEEE Transactions on computer-aided design of integrated circuits and systems","DOI":"10.1109\/TCAD.2023.3241221"},{"key":"9397_CR23","doi-asserted-by":"crossref","unstructured":"Jiang X, Long X, Guan N, et al (2016) On the decomposition-based global EDF scheduling of parallel real-time tasks. In: 2016 IEEE real-time systems symposium (RTSS), IEEE, pp 237\u2013246","DOI":"10.1109\/RTSS.2016.031"},{"key":"9397_CR24","doi-asserted-by":"crossref","unstructured":"Jiang X, Guan N, Long X, et al (2017) Semi-federated scheduling of parallel real-time tasks on multiprocessors. In: 2017 IEEE real-time systems symposium (RTSS), IEEE, pp 80\u201391","DOI":"10.1109\/RTSS.2017.00015"},{"issue":"1","key":"9397_CR25","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1109\/TC.2019.2936477","volume":"69","author":"X Jiang","year":"2019","unstructured":"Jiang X, Sun J, Tang Y et al (2019) Utilization-tensity bound for real-time DAG tasks under global EDF scheduling. IEEE Trans Comput 69(1):39\u201350","journal-title":"IEEE Trans Comput"},{"issue":"101","key":"9397_CR26","first-page":"742","volume":"108","author":"X Jiang","year":"2020","unstructured":"Jiang X, Guan N, Long X et al (2020) Real-time scheduling of parallel tasks with tight deadlines. J Syst Archit 108(101):742","journal-title":"J Syst Archit"},{"key":"9397_CR27","doi-asserted-by":"crossref","unstructured":"Jiang X, Guan N, Liang H, et al (2021) Virtually-federated scheduling of parallel real-time tasks. In: 2021 IEEE real-time systems symposium (RTSS), IEEE, pp 482\u2013494","DOI":"10.1109\/RTSS52674.2021.00050"},{"key":"9397_CR28","doi-asserted-by":"crossref","unstructured":"Jiang X, Chen Z, Yang M, et al (2022) A unified blocking analysis for parallel tasks with spin locks under global fixed priority scheduling. IEEE transactions on computers","DOI":"10.1109\/TC.2022.3198634"},{"key":"9397_CR29","doi-asserted-by":"crossref","unstructured":"Koike R, Azumi T (2021) Federated scheduling in clustered many-core processors. In: 2021 IEEE\/ACM 25th international symposium on distributed simulation and real time applications (DS-RT), IEEE, pp 1\u20138","DOI":"10.1109\/DS-RT52167.2021.9576150"},{"key":"9397_CR30","doi-asserted-by":"crossref","unstructured":"Lee S, Lee S, Lee J (2022) Response time analysis for real-time global gang scheduling. In: 2022 IEEE real-time systems symposium (RTSS), IEEE, pp 92\u2013104","DOI":"10.1109\/RTSS55097.2022.00018"},{"key":"9397_CR31","doi-asserted-by":"crossref","unstructured":"Li J, Agrawal K, Lu C, et al (2013) Outstanding paper award: analysis of global EDF for parallel tasks. In: 2013 25th Euromicro conference on real-time systems, IEEE, pp 3\u201313","DOI":"10.1109\/ECRTS.2013.12"},{"key":"9397_CR32","doi-asserted-by":"crossref","unstructured":"Li J, Chen JJ, Agrawal K, et al (2014) Analysis of federated and global scheduling for parallel real-time tasks. In: 2014 26th Euromicro conference on real-time systems, IEEE, pp 85\u201396","DOI":"10.1109\/ECRTS.2014.23"},{"key":"9397_CR33","doi-asserted-by":"crossref","unstructured":"Li J, Agrawal K, Lu C (2022) Parallel real-time scheduling. In: Handbook of real-time computing. Springer, p 447\u2013467","DOI":"10.1007\/978-981-287-251-7_28"},{"key":"9397_CR34","doi-asserted-by":"crossref","unstructured":"Lin CC, Shi J, Ueter N, et al (2022) Type-aware federated scheduling for typed DAG tasks on heterogeneous multicore platforms. IEEE transactions on computers","DOI":"10.1109\/TC.2022.3202748"},{"key":"9397_CR35","doi-asserted-by":"crossref","unstructured":"Melani A, Bertogna M, Bonifaci V, et al (2015) Response-time analysis of conditional DAG tasks in multiprocessor systems. In: 2015 27th Euromicro conference on real-time systems, IEEE, pp 211\u2013221","DOI":"10.1109\/ECRTS.2015.26"},{"issue":"2","key":"9397_CR36","first-page":"339","volume":"66","author":"A Melani","year":"2016","unstructured":"Melani A, Bertogna M, Bonifaci V et al (2016) Schedulability analysis of conditional parallel task graphs in multicore systems. IEEE Trans Comput 66(2):339\u2013353","journal-title":"IEEE Trans Comput"},{"key":"9397_CR37","doi-asserted-by":"crossref","unstructured":"Serrano MA, Melani A, Vargas R, et al (2015) Timing characterization of OpenMP4 tasking model. In: 2015 international conference on compilers, architecture and synthesis for embedded systems (CASES), IEEE, pp 157\u2013166","DOI":"10.1109\/CASES.2015.7324556"},{"key":"9397_CR38","doi-asserted-by":"crossref","unstructured":"Sun J, Guan N, Wang Y, et al (2017) Real-time scheduling and analysis of OpenMP task systems with tied tasks. In: 2017 IEEE real-time systems symposium (RTSS), IEEE, pp 92\u2013103","DOI":"10.1109\/RTSS.2017.00016"},{"key":"9397_CR39","doi-asserted-by":"crossref","unstructured":"Sun J, Guan N, Sun J, et al (2019) Calculating response-time bounds for OpenMP task systems with conditional branches. In: 2019 IEEE real-time and embedded technology and applications symposium (RTAS), IEEE, pp 169\u2013181","DOI":"10.1109\/RTAS.2019.00022"},{"key":"9397_CR40","doi-asserted-by":"crossref","unstructured":"Sun J, Li F, Guan N, et al (2020) On computing exact wcrt for DAG tasks. In: 2020 57th ACM\/IEEE design automation conference (DAC), IEEE, pp 1\u20136","DOI":"10.1109\/DAC18072.2020.9218744"},{"key":"9397_CR41","doi-asserted-by":"crossref","unstructured":"Sun J, Guan N, Guo Z, et al (2021) Calculating worst-case response time bounds for OpenMP programs with loop structures. In: 2021 IEEE real-time systems symposium (RTSS), IEEE, pp 123\u2013135","DOI":"10.1109\/RTSS52674.2021.00022"},{"key":"9397_CR42","doi-asserted-by":"crossref","unstructured":"Tang Y, Guan N, Yi W (2022) Real-time task models. Handbook of real-time computing, p 469","DOI":"10.1007\/978-981-287-251-7_29"},{"key":"9397_CR43","doi-asserted-by":"crossref","unstructured":"Ueter N, Von Der Br\u00fcggen G, Chen JJ, et al (2018) Reservation-based federated scheduling for parallel real-time tasks. In: 2018 IEEE Real-time systems symposium (RTSS), IEEE, pp 482\u2013494","DOI":"10.1109\/RTSS.2018.00061"},{"key":"9397_CR44","doi-asserted-by":"crossref","unstructured":"Voudouris P, Stenstr\u00f6m P, Pathan R (2017) Timing-anomaly free dynamic scheduling of task-based parallel applications. In: real-time and embedded technology and applications symposium (RTAS), 2017 IEEE, IEEE, pp 365\u2013376","DOI":"10.1109\/RTAS.2017.2"},{"key":"9397_CR45","doi-asserted-by":"crossref","unstructured":"Voudouris P, Stenstr\u00f6m P, Pathan R (2021) Bounding the execution time of parallel applications on unrelated multiprocessors. Real-time systems pp 1\u201344","DOI":"10.1145\/3477018"},{"key":"9397_CR46","doi-asserted-by":"crossref","unstructured":"Wang Y, Guan N, Sun J, et al (2017) Benchmarking OpenMP programs for real-time scheduling. In: 2017 IEEE 23rd international conference on embedded and real-time computing systems and applications (RTCSA), IEEE, pp 1\u201310","DOI":"10.1109\/RTCSA.2017.8046322"},{"key":"9397_CR47","doi-asserted-by":"crossref","unstructured":"Wang Y, Jiang X, Guan N, et al (2022) Scheduling and analysis of real-time tasks with parallel critical sections. In: Proceedings of the 59th ACM\/IEEE design automation conference, pp 1255\u20131260","DOI":"10.1145\/3489517.3530611"},{"key":"9397_CR48","doi-asserted-by":"crossref","unstructured":"Wu Y, Zhang W, Guan N, et al (2021) Improving interference analysis for real-time DAG tasks under partitioned scheduling. IEEE transactions on computers","DOI":"10.1109\/TC.2021.3092181"},{"key":"9397_CR49","doi-asserted-by":"crossref","unstructured":"Zhao S, Dai X, Bate I, et al (2020) DAG scheduling and analysis on multiprocessor systems: Exploitation of parallelism and dependency. In: 2020 IEEE real-time systems symposium (RTSS), IEEE, pp 128\u2013140","DOI":"10.1109\/RTSS49844.2020.00022"},{"key":"9397_CR50","doi-asserted-by":"crossref","unstructured":"Zhao S, Dai X, Bate I (2022) DAG scheduling and analysis on multi-core systems by modelling parallelism and dependency. IEEE transactions on parallel and distributed systems","DOI":"10.1109\/TPDS.2022.3177046"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-023-09397-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11241-023-09397-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-023-09397-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,13]],"date-time":"2024-07-13T16:13:06Z","timestamp":1720887186000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11241-023-09397-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,25]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["9397"],"URL":"https:\/\/doi.org\/10.1007\/s11241-023-09397-y","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"type":"print","value":"0922-6443"},{"type":"electronic","value":"1573-1383"}],"subject":[],"published":{"date-parts":[[2023,5,25]]},"assertion":[{"value":"24 April 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}