{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T02:15:08Z","timestamp":1771467308717,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T00:00:00Z","timestamp":1738886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62106202"],"award-info":[{"award-number":["62106202"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004750","name":"Aeronautical Science Foundation of China","doi-asserted-by":"publisher","award":["2023M073053003"],"award-info":[{"award-number":["2023M073053003"]}],"id":[{"id":"10.13039\/501100004750","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100015401","name":"Key Research and Development Projects of Shaanxi Province","doi-asserted-by":"publisher","award":["2024GX-YBXM-118"],"award-info":[{"award-number":["2024GX-YBXM-118"]}],"id":[{"id":"10.13039\/501100015401","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>Heterogeneous multiprocessor architecture is frequently employed as an economical and efficient means of providing excellent parallel processing capabilities while keeping production cost and power consumption under control. Although this architecture achieves significant performance enhancement and cost reduction, it results in a serious task allocation and scheduling problem, especially for periodic tasks with data dependencies, all of which should be reasonably scheduled and executed in a timely manner such that their deadlines and dependence requirements could be satisfied even if the worst happens. In this article, we concentrate on the non-preemptive scheduling problem of periodic tasks with data dependencies upon heterogeneous multiprocessor platforms. First, with models of data-dependent tasks and heterogeneous processors, we analyze the time, space, precedence, and data dependence constraints of tasks and design an exact formulation based on the mixed integer linear programming to completely explore the solution space and produce the optimal solutions. Then, by constructing a directed acyclic graph to depict the dependence relationship of jobs generated by tasks, we propose an efficient off-line list-based scheduling algorithm to provide a reasonable time and processor allocation for each job, with a view to minimizing the completion time of jobs. Experiments with randomly generated tasks are performed to evaluate the effectiveness and efficiency of the proposed algorithm, and the experimental results show that our algorithm can averagely enhance the scheduling success ratio by 28.5%, and, respectively, reduce the task completion time and the deviation ratio by 23.3% and 17.2%, on average.<\/jats:p>","DOI":"10.1145\/3711849","type":"journal-article","created":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T11:40:47Z","timestamp":1736422847000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Non-Preemptive Scheduling of Periodic Tasks with Data Dependencies in Heterogeneous Multiprocessor Embedded Systems"],"prefix":"10.1145","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6234-1001","authenticated-orcid":false,"given":"Jinchao","family":"Chen","sequence":"first","affiliation":[{"name":"Northwestern Polytechnical University, Xi'an, China"}]},{"given":"Yang","family":"Wang","sequence":"additional","affiliation":[{"name":"Northwestern Polytechnical University, Xi'an, China"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"Northwestern Polytechnical University, Xi'an, China"}]},{"given":"Yantao","family":"Lu","sequence":"additional","affiliation":[{"name":"Northwestern Polytechnical University, Xi'an, China"}]},{"given":"Qing","family":"Li","sequence":"additional","affiliation":[{"name":"Northwestern Polytechnical University, Xi'an, China"}]},{"given":"Qiuhao","family":"Shu","sequence":"additional","affiliation":[{"name":"Northwestern Polytechnical University, Xi'an, China"}]}],"member":"320","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"165","volume-title":"IEEE International Conference on Computer Design (ICCD\u201917)","author":"Ishak Suhaimi Abd","year":"2017","unstructured":"Suhaimi Abd Ishak, Hui Wu, and Umair Ullah Tariq. 2017. Energy-aware task scheduling on heterogeneous NoC-based MPSoCs. In IEEE International Conference on Computer Design (ICCD\u201917). 165\u2013168."},{"key":"e_1_3_1_3_2","doi-asserted-by":"crossref","unstructured":"Arezoo Abdollahi-Kalkhoran Shahriar Lotfi and Habib Izadkhah. 2022. TEA-SEA: Tiling and scheduling of non-uniform two-level perfectly nested loops using an evolutionary approach. Expert Syst. Applic. 191 (2022) 116152.","DOI":"10.1016\/j.eswa.2021.116152"},{"key":"e_1_3_1_4_2","doi-asserted-by":"crossref","unstructured":"H. Arabnejad and J. G. Barbosa. 2014. List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE Trans. Parallel Distrib. Syst. 25 3 (2014) 682\u2013694.","DOI":"10.1109\/TPDS.2013.57"},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","unstructured":"Hamid Arabnejad Jorge G. Barbosa and Radu Prodan. 2016. Low-time complexity budget\u2013deadline constrained workflow scheduling on heterogeneous resources. Fut. Gen. Comput. Syst. 55 (2016) 29\u201340.","DOI":"10.1016\/j.future.2015.07.021"},{"key":"e_1_3_1_6_2","doi-asserted-by":"crossref","unstructured":"Paul Antoine Arras Didier Fuin Emmanuel Jeannot Arthur Stoutchinin and Samuel Thibault. 2015. List scheduling in embedded systems under memory constraints. Int. J. Parallel Program. 43 6 (2015) 1103\u20131128.","DOI":"10.1007\/s10766-014-0338-1"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2038642.2038672"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2004.20"},{"key":"e_1_3_1_9_2","doi-asserted-by":"crossref","unstructured":"Sanjoy K. Baruah Vincenzo Bonifaci Renato Bruni and Alberto Marchetti-Spaccamela. 2019. ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors. J. Schedul. 22 (2019) 195\u2013209.","DOI":"10.1007\/s10951-018-0593-x"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/PDP.2010.56"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS46320.2019.00059"},{"key":"e_1_3_1_12_2","doi-asserted-by":"crossref","unstructured":"Jinchao Chen Pengcheng Han Yifan Liu and Xiaoyan Du. 2023. Scheduling independent tasks in cloud environment based on modified differential evolution. Concurr. Computat.: Pract. Exper. 35 13 (2023) e6256.","DOI":"10.1002\/cpe.6256"},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","unstructured":"Jinchao Chen Pengcheng Han Ying Zhang Tao You and Pengyi Zheng. 2023. Scheduling energy consumption-constrained workflows in heterogeneous multi-processor embedded systems. J. Syst. Archit. 142 (2023) 102938.","DOI":"10.1016\/j.sysarc.2023.102938"},{"key":"e_1_3_1_14_2","doi-asserted-by":"crossref","unstructured":"Jinchao Chen Tingyang Li Ying Zhang Tao You Yantao Lu Prayag Tiwari and Neeraj Kumar. 2024. Global-and-local attention-based reinforcement learning for cooperative behaviour control of multiple UAVs. IEEE Trans. Vehic. Technol. 73 3 (2024) 4194\u20134206.","DOI":"10.1109\/TVT.2023.3327571"},{"key":"e_1_3_1_15_2","doi-asserted-by":"crossref","unstructured":"Robert I. Davis and Alan Burns. 2011. Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. Real-time Syst. 47 1 (2011) 1\u201340.","DOI":"10.1007\/s11241-010-9106-5"},{"key":"e_1_3_1_16_2","doi-asserted-by":"crossref","unstructured":"Rajesh Devaraj and Arnab Sarkar. 2023. Comments on \u201cIPPTS: An Efficient Algorithm for Scientific Workflow Scheduling in Heterogeneous Computing Systems.\u201d IEEE Trans. Parallel Distrib. Syst. 34 3 (2023) 810\u2013811.","DOI":"10.1109\/TPDS.2022.3232326"},{"key":"e_1_3_1_17_2","doi-asserted-by":"crossref","unstructured":"Hamza Djigal Jun Feng Jiamin Lu and Jidong Ge. 2021. IPPTS: An efficient algorithm for scientific workflow scheduling in heterogeneous computing systems. IEEE Trans. Parallel Distrib. Syst. 32 5 (2021) 1057\u20131071.","DOI":"10.1109\/TPDS.2020.3041829"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15775-2_2"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS59052.2023.00061"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2010.26"},{"key":"e_1_3_1_21_2","doi-asserted-by":"crossref","unstructured":"Joel Goossens Emmanuel Grolleau and Liliana Cucu-Grosjean. 2016. Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platforms. Real-time Syst. 52 6 (2016) 1\u201325.","DOI":"10.1007\/s11241-016-9256-1"},{"key":"e_1_3_1_22_2","doi-asserted-by":"crossref","unstructured":"J. Huang R. Li J. An D. Ntalasha F. Yang and K. Li. 2017. Energy-efficient resource utilization for heterogeneous embedded computing systems. IEEE Trans. Comput. 66 9 (2017) 1518\u20131531.","DOI":"10.1109\/TC.2017.2693186"},{"key":"e_1_3_1_23_2","unstructured":"IBM Corporation. 2024. IBM ILOG CPLEX Optimization Studio. Retrieved from: https:\/\/www.ibm.com\/products\/ilog-cplex-optimization-studio"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.1991.160366"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2008.44"},{"key":"e_1_3_1_26_2","doi-asserted-by":"crossref","unstructured":"Rakesh Kumar Keith I. Farkas Norman P. Jouppi Parthasarathy Ranganathan and Dean M. Tullsen. 2003. Single-ISA heterogeneous multi-core architectures: The potential for processor power reduction. Proc. 36th Int. Symp. Microarchit. 32 2 (2003) 81\u201392.","DOI":"10.1109\/MICRO.2003.1253185"},{"key":"e_1_3_1_27_2","doi-asserted-by":"crossref","unstructured":"Huifang Li Guanghao Xu Danjing Wang MengChu Zhou Yan Yuan and Ahmed Alabdulwahab. 2022. Chaotic-nondominated-sorting owl search algorithm for energy-aware multi-workflow scheduling in hybrid clouds. IEEE Trans. Sustain. Comput. 7 3 (2022) 595\u2013608.","DOI":"10.1109\/TSUSC.2022.3144357"},{"key":"e_1_3_1_28_2","doi-asserted-by":"crossref","unstructured":"Jia Luo Didier El Baz Rui Xue and Jinglu Hu. 2020. Solving the dynamic energy aware job shop scheduling problem with the heterogeneous parallel genetic algorithm. Fut. Gen. Comput. Syst. 108 (2020) 119\u2013134.","DOI":"10.1016\/j.future.2020.02.019"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/CSE.2013.110"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-28430-5_6"},{"key":"e_1_3_1_31_2","doi-asserted-by":"crossref","unstructured":"Haluk Topcuouglu Salim Hariri and Min You Wu. 2002. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst. 13 3 (2002) 260\u2013274.","DOI":"10.1109\/71.993206"},{"key":"e_1_3_1_32_2","doi-asserted-by":"crossref","unstructured":"H. Wang and O. Sinnen. 2018. List-scheduling versus cluster-scheduling. IEEE Trans. Parallel Distrib. Syst. 29 8 (2018) 1736\u20131749.","DOI":"10.1109\/TPDS.2018.2808959"},{"key":"e_1_3_1_33_2","doi-asserted-by":"crossref","unstructured":"Q. Wu F. Ishikawa Q. Zhu Y. Xia and J. Wen. 2017. Deadline-constrained cost optimization approaches for workflow scheduling in clouds. IEEE Trans. Parallel Distrib. Syst. 28 12 (2017) 3401\u20133412.","DOI":"10.1109\/TPDS.2017.2735400"},{"key":"e_1_3_1_34_2","doi-asserted-by":"crossref","unstructured":"Guoqi Xie Junqiang Jiang Yan Liu Renfa Li and Keqin Li. 2017. Minimizing energy consumption of real-time parallel applications using downward and upward approaches on heterogeneous systems. IEEE Trans. Industr. Inform. 13 3 (2017) 1068\u20131078.","DOI":"10.1109\/TII.2017.2676183"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISAI.2016.0050"},{"key":"e_1_3_1_36_2","first-page":"9","volume-title":"IEEE International Symposium on Embedded Multicore\/Many-core Systems-on-chip","author":"Xuan Khanh Do","year":"2015","unstructured":"Khanh Do Xuan, Stephane Louise, and Albert Cohen. 2015. Managing the latency of data-dependent tasks in embedded streaming applications. In IEEE International Symposium on Embedded Multicore\/Many-core Systems-on-chip. IEEE, 9\u201316."},{"key":"e_1_3_1_37_2","doi-asserted-by":"crossref","unstructured":"Xindong You Dawei Sun Xueqiang Lv Shang Gao and Rajkumar Buyya. 2022. MQDS: An energy saving scheduling strategy with diverse QoS constraints towards reconfigurable cloud storage systems. Fut. Gen. Comput. Syst. 129 (2022) 252\u2013268.","DOI":"10.1016\/j.future.2021.11.025"},{"key":"e_1_3_1_38_2","doi-asserted-by":"crossref","unstructured":"Weizhe Zhang Hucheng Xie Boran Cao and Albert M. K. Cheng. 2014. Energy-aware real-time task scheduling for heterogeneous multiprocessors with particle swarm optimization algorithm. Math. Prob. Eng. 2014 1 (2014) 1\u20139.","DOI":"10.1155\/2014\/287475"},{"key":"e_1_3_1_39_2","doi-asserted-by":"crossref","unstructured":"J. Zhou T. Wei M. Chen J. Yan X. S. Hu and Y. Ma. 2016. Thermal-aware task scheduling for energy minimization in heterogeneous real-time MPSoC systems. IEEE Trans. Comput.-aid. Des. Integ. Circ. Syst. 35 8 (2016) 1269\u20131282.","DOI":"10.1109\/TCAD.2015.2501286"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3711849","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3711849","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:15Z","timestamp":1750295955000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3711849"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,7]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3711849"],"URL":"https:\/\/doi.org\/10.1145\/3711849","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,7]]},"assertion":[{"value":"2024-08-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-26","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}