{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T07:15:15Z","timestamp":1758438915059,"version":"3.44.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"National Key Research and Development Program of China","award":["2023YFB4503205"],"award-info":[{"award-number":["2023YFB4503205"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62202123"],"award-info":[{"award-number":["62202123"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"Joint Funds of the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U22A2036"],"award-info":[{"award-number":["U22A2036"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>Heterogeneous multi-core architectures are gaining popularity in recent years as they combine the benefits of different processors, resulting in improved execution capacity and energy efficiency. However, analyzing response times and allocating resources for the typed directed acyclic graph (DAG) task, which has complex execution logic, on heterogeneous multi-core systems poses significant challenges. Major approaches may yield overly pessimistic worst-case response time (WCRT) estimates in certain scenarios while failing to adequately address critical structural characteristics inherent to typed DAG tasks. To address these limitations, this article explores the WCRT analysis and core allocations for the typed DAG task under partitioned scheduling. In this work, we first delve into the characteristics of the topology structure of the typed DAG task and propose a novel WCRT upper bound to enhance the accuracy of WCRT analysis. Then, a subtask allocation strategy is presented, which enables an effectively utilization of the resources of multi-cores. Finally, the performance of the proposed analysis algorithm and allocation strategy are tested by implementing a verification system on a real heterogeneous multi-core platform. Experimental results demonstrate that our proposed WCRT analysis algorithm exhibits substantial improvements of 38.7% and 37.43% in the theoretical analysis performance and actual analysis accuracy, respectively. Similarly, our proposed core allocation strategy improves the theoretical and the actual execution efficiency of the system by 10.6% and 7.41%, respectively. These results substantiate the practical value of our enhanced WCRT derivation methodology and allocation scheme in improving system resource utilization efficiency.<\/jats:p>","DOI":"10.1145\/3746232","type":"journal-article","created":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T11:23:34Z","timestamp":1753356214000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Partitioned Scheduling and Analysis for a Typed DAG Task on Heterogeneous Multi-Cores"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5179-163X","authenticated-orcid":false,"given":"Yulong","family":"Wu","sequence":"first","affiliation":[{"name":"School of Computer Science and Technowledge, Harbin Institute of Technology Shenzhen","place":["Shenzhen, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8595-1619","authenticated-orcid":false,"given":"Yehan","family":"Ma","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-4957-5672","authenticated-orcid":false,"given":"Mingdong","family":"Xie","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology","place":["Harbin, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4783-876X","authenticated-orcid":false,"given":"Weizhe","family":"Zhang","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology Shenzhen","place":["Shenzhen, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,19]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICESS.2019.8782446"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/SEAA.2019.00031"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2019.02.016"},{"key":"e_1_3_2_5_2","unstructured":"Tinker Board 2S. Retrieved January 20 2025 from https:\/\/www.arm.com\/zh-TW\/technologies\/big-little. ([n. d.])."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2020.101870"},{"key":"e_1_3_2_7_2","article-title":"Type-aware federated scheduling for typed DAG tasks on heterogeneous multicore platforms","author":"Lin Ching-Chi","year":"2022","unstructured":"Ching-Chi Lin, Junjie Shi, Niklas Ueter, Mario G\u00fcnzel, Jan Reineke, and Jian-Jia Chen. 2022. Type-aware federated scheduling for typed DAG tasks on heterogeneous multicore platforms. IEEE Transactions on Computers 72, 5 (2022), 1286\u20131300.","journal-title":"IEEE Transactions on Computers"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2916696"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209040"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3195970.3196104"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS49844.2020.00022"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2021.3092181"},{"key":"e_1_3_2_13_2","unstructured":"The codes in this paper. 2024. Retrieved January 20 2025 from https:\/\/github.com\/DrWuYulong\/partitioned_scheduling_on_heterogeneous. ([n. d.])."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2023.3241221"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2022.3177046"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2022.3202748"},{"key":"e_1_3_2_17_2","volume-title":"Proceedings of the 31st Conference on Real-Time Systems","author":"Nasri Mitra","year":"2019","unstructured":"Mitra Nasri, Geoffrey Nelissen, and Bj\u00f6rn B. Brandenburg. 2019. Response-time analysis of limited-preemptive parallel DAG tasks under global scheduling. In Proceedings of the 31st Conference on Real-Time Systems. 21\u20131."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/SIES.2016.7509443"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.micpro.2022.104744"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2019.101704"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2020.3000051"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/EUC.2011.41"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2006.30"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2016.020"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3508352.3549409"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2019.00026"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2018.00056"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.23919\/DATE54114.2022.9774647"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3665276"},{"key":"e_1_3_2_30_2","first-page":"129","volume-title":"Proceedings of the IEEE Real-Time Systems Symposium","author":"Jeffay Kevin","year":"1991","unstructured":"Kevin Jeffay, Donald F. Stanat, and Charles U. Martel. 1991. On non-preemptive scheduling of periodic and sporadic tasks. In Proceedings of the IEEE Real-Time Systems Symposium. IEEE, US, 129\u2013139."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:TIME.0000033378.56741.14"},{"key":"e_1_3_2_32_2","first-page":"6","volume-title":"Proceedings of the 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-Time Systems (WATERS 2010)","author":"Emberson Paul","year":"2010","unstructured":"Paul Emberson, Roger Stafford, and Robert I. Davis. 2010. Techniques for the synthesis of multiprocessor tasksets. In Proceedings of the 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-Time Systems (WATERS 2010). 6\u201311."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS59052.2023.00061"},{"issue":"1","key":"e_1_3_2_34_2","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erdos Paul","year":"1960","unstructured":"Paul Erdos and Alfr\u00e9d R\u00e9nyi. 1960. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5, 1 (1960), 17\u201360.","journal-title":"Publications of the Mathematical Institute of the Hungarian Academy of Sciences"},{"key":"e_1_3_2_35_2","unstructured":"Tinker Board 2S. 2018. Retrieved January 20 2025 from https:\/\/tinker-board.asus.com\/product\/tinker-board-2s.html. (2018)."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3746232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T00:48:27Z","timestamp":1758329307000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3746232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,19]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3746232"],"URL":"https:\/\/doi.org\/10.1145\/3746232","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2025,9,19]]},"assertion":[{"value":"2024-11-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}