{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T08:49:30Z","timestamp":1767862170590,"version":"3.49.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T00:00:00Z","timestamp":1679443200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T00:00:00Z","timestamp":1679443200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62072118"],"award-info":[{"award-number":["62072118"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Huangpu International Sci & Tech Cooperation Foundation of Guangzhou, China","award":["2021GH12"],"award-info":[{"award-number":["2021GH12"]}]},{"DOI":"10.13039\/501100003453","name":"Guangdong Natural Science Foundation","doi-asserted-by":"crossref","award":["2023A1515011230"],"award-info":[{"award-number":["2023A1515011230"]}],"id":[{"id":"10.13039\/501100003453","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2023,8]]},"DOI":"10.1007\/s11227-023-05186-3","type":"journal-article","created":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T10:02:55Z","timestamp":1679479375000},"page":"13210-13240","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Algorithms for tree-shaped task partition and allocation on heterogeneous multiprocessors"],"prefix":"10.1007","volume":"79","author":[{"given":"Suna","family":"He","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jigang","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bing","family":"Wei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiaxin","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,22]]},"reference":[{"issue":"11","key":"5186_CR1","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1016\/j.parco.2013.09.009","volume":"39","author":"H Hussain","year":"2013","unstructured":"Hussain H, Malik SUR, Hameed A, Khan SU, Bickler G, Min-Allah N, Qureshi MB, Zhang L, Yongji W, Ghani N et al (2013) A survey on resource allocation in high performance distributed computing systems. Parall Comput 39(11):709\u2013736","journal-title":"Parall Comput"},{"key":"5186_CR2","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.jpdc.2022.05.011","volume":"168","author":"V Kelefouras","year":"2022","unstructured":"Kelefouras V, Djemame K (2022) Workflow simulation and multi-threading aware task scheduling for heterogeneous computing. J Parall Distrib Comput 168:17\u201332","journal-title":"J Parall Distrib Comput"},{"key":"5186_CR3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718881","volume-title":"Direct methods for sparse linear systems","author":"TA Davis","year":"2006","unstructured":"Davis TA (2006) Direct methods for sparse linear systems. Society for Industrial and Applied Mathematics, Texas"},{"issue":"1","key":"5186_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629641","volume":"41","author":"K Kim","year":"2014","unstructured":"Kim K, Eijkhout V (2014) A parallel sparse direct solver via hierarchical DAG scheduling. ACM Trans Math Softw 41(1):1\u201327","journal-title":"ACM Trans Math Softw"},{"key":"5186_CR5","doi-asserted-by":"crossref","unstructured":"Sao P, Li XS, Vuduc R (2018) A communication-avoiding 3D LU factorization algorithm for sparse matrices. In: IEEE International parallel and distributed processing symposium, pp. 908\u2013919","DOI":"10.1109\/IPDPS.2018.00100"},{"issue":"7","key":"5186_CR6","doi-asserted-by":"publisher","first-page":"1533","DOI":"10.1109\/TPDS.2020.2971200","volume":"31","author":"C Gou","year":"2020","unstructured":"Gou C, Benoit A, Marchal L (2020) Partitioning tree-shaped task graphs for distributed platforms with limited memory. IEEE Trans Parall Distrib Syst 31(7):1533\u20131544","journal-title":"IEEE Trans Parall Distrib Syst"},{"key":"5186_CR7","doi-asserted-by":"crossref","unstructured":"Ozkaya MY, Benoit A, Ucar B, Herrmann J, Catalyurek UV (2019) A scalable clustering-based task scheduler for homogeneous processors using DAG partitioning. In: IEEE International Parallel and Distributed Processing Symposium, pp. 155\u2013165","DOI":"10.1109\/IPDPS.2019.00026"},{"issue":"9","key":"5186_CR8","doi-asserted-by":"publisher","first-page":"2625","DOI":"10.1109\/TPDS.2017.2671868","volume":"28","author":"H Meyerhenke","year":"2017","unstructured":"Meyerhenke H, Sanders P, Schulz C (2017) Parallel graph partitioning for complex networks. IEEE Trans Parall Distrib Syst 28(9):2625\u20132638","journal-title":"IEEE Trans Parall Distrib Syst"},{"issue":"7","key":"5186_CR9","doi-asserted-by":"publisher","first-page":"1707","DOI":"10.1109\/TPDS.2019.2955494","volume":"31","author":"AC Zhou","year":"2019","unstructured":"Zhou AC, Shen B, Xiao Y, Ibrahim S, He B (2019) Cost-aware partitioning for efficient large graph processing in geo-distributed datacenters. IEEE Trans Parall Distrib Syst 31(7):1707\u20131723","journal-title":"IEEE Trans Parall Distrib Syst"},{"key":"5186_CR10","doi-asserted-by":"crossref","unstructured":"Jacquelin M, Marchal L, Robert Y, Ucar B (2011) On optimal tree traversals for sparse matrix factorization. In: IEEE international parallel & distributed processing symposium, pp. 556\u2013567","DOI":"10.1109\/IPDPS.2011.60"},{"issue":"5","key":"5186_CR11","doi-asserted-by":"publisher","first-page":"1057","DOI":"10.1109\/TPDS.2020.3041829","volume":"32","author":"H Djigal","year":"2021","unstructured":"Djigal H, Feng J, Lu J, Ge J (2021) IPPTS: an efficient algorithm for scientific workflow scheduling in heterogeneous computing systems. IEEE Trans Parall Distrib Syst 32(5):1057\u20131071","journal-title":"IEEE Trans Parall Distrib Syst"},{"issue":"5","key":"5186_CR12","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3944","volume":"29","author":"N Zhou","year":"2017","unstructured":"Zhou N, Qi D, Wang X, Zheng Z, Lin W (2017) A list scheduling algorithm for heterogeneous systems based on a critical node cost table and pessimistic cost table. Concurr Comput Pract Exp 29(5):e3944","journal-title":"Concurr Comput Pract Exp"},{"key":"5186_CR13","first-page":"1","volume":"228","author":"C-G Wu","year":"2021","unstructured":"Wu C-G, Wang L, Wang J-J (2021) A path relinking enhanced estimation of distribution algorithm for direct acyclic graph task scheduling problem. Knowl Syst 228:1\u201315","journal-title":"Knowl Syst"},{"issue":"8","key":"5186_CR14","doi-asserted-by":"publisher","first-page":"1736","DOI":"10.1109\/TPDS.2018.2808959","volume":"29","author":"H Wang","year":"2018","unstructured":"Wang H, Sinnen O (2018) List-scheduling versus cluster-scheduling. IEEE Trans Parall Distrib Syst 29(8):1736\u20131749","journal-title":"IEEE Trans Parall Distrib Syst"},{"issue":"10","key":"5186_CR15","doi-asserted-by":"publisher","first-page":"2718","DOI":"10.1109\/TPDS.2017.2703123","volume":"28","author":"A Yoosefi","year":"2017","unstructured":"Yoosefi A, Naji HR (2017) A clustering algorithm for communicationaware scheduling of task graphs on multi-core reconfigurable systems. IEEE Trans Parall Distrib Syst 28(10):2718\u20132732","journal-title":"IEEE Trans Parall Distrib Syst"},{"issue":"1","key":"5186_CR16","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.jpdc.2010.10.004","volume":"71","author":"O Sinnen","year":"2011","unstructured":"Sinnen O, To A, Kaur M (2011) Contention-aware scheduling with task duplication. J Parall Distrib Comput 71(1):77\u201386","journal-title":"J Parall Distrib Comput"},{"issue":"1","key":"5186_CR17","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/TPDS.2018.2851221","volume":"30","author":"K He","year":"2018","unstructured":"He K, Meng X, Pan Z, Yuan L, Zhou P (2018) A novel task-duplication based clustering algorithm for heterogeneous computing environments. IEEE Trans Parall Distrib Syst 30(1):2\u201314","journal-title":"IEEE Trans Parall Distrib Syst"},{"issue":"1","key":"5186_CR18","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s11227-020-03281-3","volume":"77","author":"R Ramezani","year":"2021","unstructured":"Ramezani R (2021) Dynamic scheduling of task graphs in multi-fpga systems using critical path. J Supercomput 77(1):597\u2013618","journal-title":"J Supercomput"},{"key":"5186_CR19","doi-asserted-by":"crossref","unstructured":"Marchal L, Nagy H, Simon B, Vivien F (2018) Parallel scheduling of DAGs under memory constraints. In: IEEE international parallel and distributed processing symposium, pp. 204\u2013213","DOI":"10.1109\/IPDPS.2018.00030"},{"key":"5186_CR20","doi-asserted-by":"crossref","unstructured":"Kitagawa Y, Ishigooka T, Azumi T (2018) Dag scheduling algorithm for a cluster-based many-core architecture. In: IEEE International Conference on Embedded And Ubiquitous Computing, pp. 150\u2013157","DOI":"10.1109\/EUC.2018.00030"},{"issue":"3","key":"5186_CR21","doi-asserted-by":"publisher","first-page":"7539","DOI":"10.1007\/s10586-018-1856-1","volume":"22","author":"X Geng","year":"2019","unstructured":"Geng X, Mao Y, Xiong M, Liu Y (2019) An improved task scheduling algorithm for scientific workflow in cloud computing environment. Cluster Comput 22(3):7539\u20137548","journal-title":"Cluster Comput"},{"key":"5186_CR22","doi-asserted-by":"publisher","first-page":"7637","DOI":"10.1109\/TII.2019.2962531","volume":"16","author":"X Tang","year":"2019","unstructured":"Tang X, Shi W, Wu F (2019) Interconnection network energy-aware workflow scheduling algorithm on heterogeneous systems. IEEE Trans Indust Inform 16:7637\u20137645","journal-title":"IEEE Trans Indust Inform"},{"key":"5186_CR23","doi-asserted-by":"crossref","unstructured":"Guermouche A, Marchal L, Simon B, Vivien F (2015) Scheduling trees of malleable tasks for sparse linear algebra. In: European Conference on Parallel Processing, pp. 479\u2013490","DOI":"10.1007\/978-3-662-48096-0_37"},{"issue":"2","key":"5186_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2779052","volume":"2","author":"L Eyraud-Dubois","year":"2015","unstructured":"Eyraud-Dubois L, Marchal L, Sinnen O, Vivien F (2015) Parallel scheduling of task trees with limited memory. ACM Trans Parall Comput 2(2):1\u201337","journal-title":"ACM Trans Parall Comput"},{"key":"5186_CR25","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/j.parco.2016.06.004","volume":"59","author":"SC Rennich","year":"2016","unstructured":"Rennich SC, Stosic D, Davis TA (2016) Accelerating sparse cholesky factorization on GPUs. Parall Comput 59:140\u2013150","journal-title":"Parall Comput"},{"key":"5186_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.09.037","volume":"707","author":"E Kayaaslan","year":"2018","unstructured":"Kayaaslan E, Lambert T, Marchal L, Ucar B (2018) Scheduling series-parallel task graphs to minimize peak memory. Theor Comput Sci 707:1\u201323","journal-title":"Theor Comput Sci"},{"key":"5186_CR27","doi-asserted-by":"crossref","unstructured":"Gou C, Benoit A, Marchal L (2018) Memory-aware tree partitioning on homogeneous platforms. In: Euromicro International Conference on Parallel, Distributed and Network-Based Processing, pp. 321\u2013324","DOI":"10.1109\/PDP2018.2018.00056"},{"key":"5186_CR28","doi-asserted-by":"crossref","unstructured":"Aupy G, Brasseur C, Marchal L (2017) Dynamic memory-aware task-tree scheduling. In: IEEE international parallel and distributed processing symposium, pp. 758\u2013767","DOI":"10.1109\/IPDPS.2017.58"},{"issue":"1","key":"5186_CR29","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0167-8191(03)00091-7","volume":"30","author":"F Guinand","year":"2004","unstructured":"Guinand F, Moukrim A, Sanlaville E (2004) Sensitivity analysis of tree scheduling on two machines with communication delays. Parall Comput 30(1):103\u2013120","journal-title":"Parall Comput"},{"key":"5186_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1177\/15501477211003830","volume":"17","author":"H Bai","year":"2021","unstructured":"Bai H, Zhang X, Liu Y, Xie Y (2021) Resource scheduling based on routing tree and detection matrix for internet of things. Int J Distrib Sens Netw 17:1\u201313","journal-title":"Int J Distrib Sens Netw"},{"key":"5186_CR31","doi-asserted-by":"crossref","unstructured":"Herrmann J, Marchal L, Robert Y (2014) Memory-aware list scheduling for hybrid platforms. In: IEEE international parallel & distributed processing symposium workshops, pp. 689\u2013698","DOI":"10.1109\/IPDPSW.2014.80"},{"key":"5186_CR32","doi-asserted-by":"crossref","unstructured":"Bak S, Hernandez O, Gates M, Luszczek P, Sarkar V (2021) Task-graph scheduling extensions for efficient synchronization and communication. In: Proceedings of the Acm International Conference on Supercomputing, pp. 88\u2013101","DOI":"10.1145\/3447818.3461616"},{"key":"5186_CR33","doi-asserted-by":"crossref","unstructured":"Herrmann J, Marchal L, Robert Y (2013) Model and complexity results for tree traversals on hybrid platforms. In: EUROPEAN CONFERENCE ON PARALLEL PROCESSING, pp. 647\u2013658","DOI":"10.1007\/978-3-642-40047-6_65"},{"issue":"3","key":"5186_CR34","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1109\/TPDS.2013.57","volume":"25","author":"H Arabnejad","year":"2014","unstructured":"Arabnejad H, Barbosa JG (2014) List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE Trans Parall Distrib Syst 25(3):682\u2013694","journal-title":"IEEE Trans Parall Distrib Syst"},{"key":"5186_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.asoc.2020.106202","volume":"91","author":"G Taheri","year":"2020","unstructured":"Taheri G, Khonsari A, Entezari-Maleki R, Sousa L (2020) A hybrid algorithm for task scheduling on heterogeneous multiprocessor embedded systems. Appl Soft Comput 91:1\u201314","journal-title":"Appl Soft Comput"},{"key":"5186_CR36","doi-asserted-by":"publisher","first-page":"20493","DOI":"10.1109\/ACCESS.2021.3054725","volume":"9","author":"D Jeong","year":"2021","unstructured":"Jeong D, Kim J, Oldja M-L, Ha S (2021) Parallel scheduling of multiple sdf graphs onto heterogeneous processors. IEEE Access 9:20493\u201320507","journal-title":"IEEE Access"},{"key":"5186_CR37","doi-asserted-by":"crossref","unstructured":"Li J, Zheng G, Zhang H, Shi G (2019) Task scheduling algorithm for heterogeneous real-time systems based on deadline constraints. In: IEEE International Conference on Electronics Information And Emergency Communication, pp. 113\u2013116","DOI":"10.1109\/ICEIEC.2019.8784641"},{"key":"5186_CR38","doi-asserted-by":"crossref","unstructured":"He S, Wu J, Wei B, Wu J (2021) Task tree partition and subtree allocation for heterogeneous multiprocessors. In: IEEE International Conference on Parallel Distributed Processing With Applications, Big Data Cloud Computing, Sustainable Computing Communications, Social Computing Networking, pp. 571\u2013577","DOI":"10.1109\/ISPA-BDCloud-SocialCom-SustainCom52081.2021.00084"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-023-05186-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-023-05186-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-023-05186-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T14:07:39Z","timestamp":1687270059000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-023-05186-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,22]]},"references-count":38,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["5186"],"URL":"https:\/\/doi.org\/10.1007\/s11227-023-05186-3","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,22]]},"assertion":[{"value":"9 March 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}