{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T05:11:33Z","timestamp":1772255493824,"version":"3.50.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2019,10,8]],"date-time":"2019-10-08T00:00:00Z","timestamp":1570492800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>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 \u201csimulating\u201d 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.<\/jats:p>","DOI":"10.1145\/3358236","type":"journal-article","created":{"date-parts":[[2019,10,10]],"date-time":"2019-10-10T13:13:05Z","timestamp":1570713185000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Timing-Anomaly Free Dynamic Scheduling of Conditional DAG Tasks on Multi-Core Systems"],"prefix":"10.1145","volume":"18","author":[{"given":"Peng","family":"Chen","sequence":"first","affiliation":[{"name":"The Hong Kong Polytechnic University, Nanyang Technological University"}]},{"given":"Weichen","family":"Liu","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Nanyang Avenue, Singapore"}]},{"given":"Xu","family":"Jiang","sequence":"additional","affiliation":[{"name":"University of Electronic Science and Technology of China, Chengdu, China"}]},{"given":"Qingqiang","family":"He","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong, China"}]},{"given":"Nan","family":"Guan","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong, China"}]}],"member":"320","published-online":{"date-parts":[[2019,10,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.57"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2013.31"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2830865.2830866"},{"key":"e_1_2_1_4_1","volume-title":"Multiprocessor Scheduling for Real-time Systems","author":"Baruah Sanjoy","unstructured":"Sanjoy Baruah , Marko Bertogna , and Giorgio Buttazzo . 2015. Multiprocessor Scheduling for Real-time Systems . Springer . Sanjoy Baruah, Marko Bertogna, and Giorgio Buttazzo. 2015. Multiprocessor Scheduling for Real-time Systems. Springer."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2015.27"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2012.59"},{"key":"e_1_2_1_7_1","volume-title":"Embedded Real-time Systems","author":"Calvez Jean Paul","unstructured":"Jean Paul Calvez , Alan Wyche , and Charles Edmundson . 1993. Embedded Real-time Systems . Vol. 23 . Wiley New York . Jean Paul Calvez, Alan Wyche, and Charles Edmundson. 1993. Embedded Real-time Systems. Vol. 23. Wiley New York."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2013.14"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4108\/ICST.SIMUTOOLS2010.8667"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.503776"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/344588.344618"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2010.42"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2014.23"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/827271.829103"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2016.2584064"},{"key":"e_1_2_1_17_1","volume-title":"2015 27th Euromicro Conference on Real-Time Systems. IEEE, 211--221","author":"Melani Alessandra","unstructured":"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 . 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."},{"key":"e_1_2_1_18_1","first-page":"1","article-title":"Scheduling parallel real-time recurrent tasks on multicore platforms","volume":"99","author":"Pathan Risat Mahmud","year":"2018","unstructured":"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 . 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.","journal-title":"IEEE Transactions on Parallel Distributed Systems PP"},{"key":"e_1_2_1_19_1","volume-title":"6th International Workshop on Worst-Case Execution Time Analysis (WCET\u201906)","author":"Reineke Jan","year":"2006","unstructured":"Jan Reineke , Bj\u00f6rn 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\u201906) . Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. Jan Reineke, Bj\u00f6rn 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\u201906). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9166-9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2017.2"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3358236","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3358236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:07Z","timestamp":1750202587000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3358236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,8]]},"references-count":21,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3358236"],"URL":"https:\/\/doi.org\/10.1145\/3358236","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,8]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}