{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T10:20:30Z","timestamp":1781173230957,"version":"3.54.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T00:00:00Z","timestamp":1634774400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T00:00:00Z","timestamp":1634774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC-2013-AdG 340328-MECCA"],"award-info":[{"award-number":["ERC-2013-AdG 340328-MECCA"]}],"id":[{"id":"10.13039\/501100000781","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":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Heterogeneous multiprocessors can offer high performance at low energy expenditures. However, to be able to use them in hard real-time systems, timing guarantees need to be provided, and the main challenge is to determine the worst-case schedule length (also known as makespan) of an application. Previous works that estimate the makespan focus mainly on the independent-task application model or the related multiprocessor model that limits the applicability of the makespan. On the other hand, the directed acyclic graph (DAG) application model and the unrelated multiprocessor model are general and can cover most of today\u2019s platforms and applications. In this work, we propose a simple work-conserving scheduling method of the tasks in a DAG and two new approaches to finding the makespan. A set of representative OpenMP task-based parallel applications from the BOTS benchmark suite and synthetic DAGs are used to evaluate the proposed method. Based on the empirical results, the proposed approach calculates the makespan close to the exhaustive method and with low pessimism compared to a lower bound of the actual makespan calculation.<\/jats:p>","DOI":"10.1007\/s11241-021-09375-2","type":"journal-article","created":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T09:02:41Z","timestamp":1634806961000},"page":"189-232","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Bounding the execution time of parallel applications on unrelated multiprocessors"],"prefix":"10.1007","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6664-2028","authenticated-orcid":false,"given":"Petros","family":"Voudouris","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Per","family":"Stenstr\u00f6m","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Risat","family":"Pathan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,10,21]]},"reference":[{"key":"9375_CR1","volume-title":"Real-time scheduling with resource sharing on heterogeneous multiprocessors. Real-time systems","author":"B Andersson","year":"2014","unstructured":"Andersson B, Raravi G (2014) Real-time scheduling with resource sharing on heterogeneous multiprocessors. Real-time systems. Springer, New York"},{"key":"9375_CR2","doi-asserted-by":"crossref","unstructured":"Andersson B, Raravi G (2016) Scheduling constrained-deadline parallel tasks on two-type heterogeneous multiprocessors. In: Proceedings of the 24th International Conference on Real-Time Networks and Systems, ACM","DOI":"10.1145\/2997465.2997482"},{"key":"9375_CR3","doi-asserted-by":"crossref","unstructured":"Andersson B, Raravi G, Bletsas K (2010) Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors. In: IEEE RTSS","DOI":"10.1109\/RTSS.2010.32"},{"key":"9375_CR4","unstructured":"ARM (2011) big.little technology: the future of mobile. White paper"},{"key":"9375_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08696-5","volume-title":"Multiprocessor scheduling for real-time systems","author":"S Baruah","year":"2015","unstructured":"Baruah S, Bertogna M, Buttazzo G (2015a) Multiprocessor scheduling for real-time systems. Springer, New York"},{"key":"9375_CR6","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s10951-018-0593-x","volume":"22","author":"SK Baruah","year":"2019","unstructured":"Baruah SK, Bonifaci V, Bruni R, Marchetti-Spaccamela A (2019) Ilp models for the allocation of recurrent workloads upon heterogeneous multiprocessors. J Scheduling 22:195\u2013209","journal-title":"J Scheduling"},{"key":"9375_CR7","doi-asserted-by":"crossref","unstructured":"Baruah S, Bonifaci V, Marchetti-Spaccamela A (2015b) The global edf scheduling of systems of conditional sporadic dag tasks. In: IEEE ECRTS","DOI":"10.1109\/ECRTS.2015.27"},{"key":"9375_CR8","doi-asserted-by":"crossref","unstructured":"Baruah S, Bonifaci V, Marchetti-Spaccamela A, Stougie L, Wiese A (2012) A generalized parallel task model for recurrent real-time processes. In: IEEE RTSS","DOI":"10.1109\/RTSS.2012.59"},{"key":"9375_CR9","doi-asserted-by":"crossref","unstructured":"Bender MA, Rabin MO (2000) Scheduling cilk multithreaded parallel programs on processors of different speeds. In: ACM SPAA","DOI":"10.1145\/341800.341803"},{"key":"9375_CR10","doi-asserted-by":"crossref","unstructured":"Bhuiyan A, Guo Z, Saifullah A, Guan N, Xiong H (2018) Energy-efficient real-time scheduling of dag tasks. In: ACM TECS","DOI":"10.1145\/3241049"},{"key":"9375_CR11","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1145\/324133.324234","volume":"46","author":"RD Blumofe","year":"1999","unstructured":"Blumofe RD, Leiserson CE (1999) Scheduling multithreaded computations by work stealing. J ACM 46:720\u2013748","journal-title":"J ACM"},{"key":"9375_CR12","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1006\/jpdc.2000.1714","volume":"61","author":"TD Braun","year":"2001","unstructured":"Braun TD et al (2001) A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J Parallel Distrib Comput 61:810\u2013837","journal-title":"J Parallel Distrib Comput"},{"key":"9375_CR13","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"RP Brent","year":"1974","unstructured":"Brent RP (1974) The parallel evaluation of general arithmetic expressions. J ACM 21:201\u2013206","journal-title":"J ACM"},{"key":"9375_CR14","doi-asserted-by":"crossref","unstructured":"Chen P, Liu W, Jiang X, He Q, Guan N (2019) Timing-anomaly free dynamic scheduling of conditional dag tasks on multi-core systems. In: ACM Transactions on Embedded Computing Systems (TECS)","DOI":"10.1145\/3358236"},{"key":"9375_CR15","doi-asserted-by":"crossref","unstructured":"Chronaki K, et\u00a0al. (2015) Criticality-aware dynamic task scheduling for heterogeneous architectures. In: ACM, ICS","DOI":"10.1145\/2751205.2751235"},{"key":"9375_CR16","doi-asserted-by":"crossref","unstructured":"Chwa HS, Seo J, Lee J, Shin I (2015) Optimal real-time scheduling on two-type heterogeneous multicore platforms. In: IEEE RTSS","DOI":"10.1109\/RTSS.2015.19"},{"key":"9375_CR17","unstructured":"Duran A, et\u00a0al. (2002) Barcelona openmp tasks suite: a set of benchmarks targeting the exploitation of task parallelism in openmp. In: ICPP"},{"key":"9375_CR18","doi-asserted-by":"crossref","unstructured":"Esmaeilzadeh H, Blem E, Amant RS, Sankaralingam K, Burger D (2011) Dark silicon and the end of multicore scaling. In: IEEE ISCA","DOI":"10.1145\/2000064.2000108"},{"key":"9375_CR19","unstructured":"Funk S, Goossens J, Baruah S (2001) On-line scheduling on uniform multiprocessors. In: IEEE RTSS"},{"key":"9375_CR20","volume-title":"Computers and intractability","author":"MR Garey","year":"2002","unstructured":"Garey MR, Johnson DS (2002) Computers and intractability. WH Freeman, New York"},{"issue":"2","key":"9375_CR21","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"},{"key":"9375_CR22","doi-asserted-by":"crossref","unstructured":"Gupta A, Im S, Krishnaswamy R, Moseley B, Pruhs K (2012) Scheduling heterogeneous processors isn\u2019t as easy as you think. In: ACM-SIAM SODA","DOI":"10.1137\/1.9781611973099.98"},{"key":"9375_CR23","doi-asserted-by":"crossref","unstructured":"Han M, Guan N, Sun J, He Q, Deng Q, Liu W (2019) Response time bounds for typed dag parallel tasks on heterogeneous multi-cores. In: IEEE TPDS","DOI":"10.1109\/RTSS.2018.00028"},{"key":"9375_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/00949658008810422","volume":"12","author":"JM Jaffe","year":"1980","unstructured":"Jaffe JM (1980) Bounds on the scheduling of typed task systems. SIAM J Comput 12:1\u201317","journal-title":"SIAM J Comput"},{"key":"9375_CR25","doi-asserted-by":"crossref","unstructured":"Jiang X, Guan N, Long X, Yi W (2017) Semi-federated scheduling of parallel real-time tasks on multiprocessors. In: IEEE RTSS","DOI":"10.1109\/RTSS.2017.00015"},{"key":"9375_CR26","volume-title":"Scheduling on unrelated machines under tree-like precedence constraints. Algorithmica","author":"VA Kumar","year":"2009","unstructured":"Kumar VA, Marathe MV, Parthasarathy S, Srinivasan A (2009) Scheduling on unrelated machines under tree-like precedence constraints. Algorithmica. Springer, New York"},{"key":"9375_CR27","doi-asserted-by":"crossref","unstructured":"Lakshmanan K, Kato S, Rajkumar R (2010) Scheduling parallel real-time tasks on multi-core processors. In: IEEE RTSS","DOI":"10.1109\/RTSS.2010.42"},{"key":"9375_CR28","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/322092.322101","volume":"24","author":"EL Lawler","year":"1978","unstructured":"Lawler EL, Labetoulle J (1978) On preemptive scheduling of unrelated parallel processors by linear programming. J ACM (JACM) 24:612\u2013619","journal-title":"J ACM (JACM)"},{"key":"9375_CR29","doi-asserted-by":"crossref","unstructured":"Li J, Chen JJ, Agrawal K, Lu C, Gill C, Saifullah A (2014) Analysis of federated and global scheduling for parallel real-time tasks. In: IEEE ECRTS","DOI":"10.1109\/ECRTS.2014.23"},{"key":"9375_CR30","doi-asserted-by":"crossref","unstructured":"Melani A, Bertogna M, Bonifaci V, Marchetti-Spaccamela A, Buttazzo GC (2015) Response-time analysis of conditional dag tasks in multiprocessor systems. In: ECRTS","DOI":"10.1109\/ECRTS.2015.26"},{"key":"9375_CR31","unstructured":"Page DR (2019) Approximation algorithms for problems in makespan minimization on unrelated parallel machines. The University of Western Ontario (PhD thesis)"},{"key":"9375_CR32","doi-asserted-by":"crossref","unstructured":"Pathan R, Voudouris P, Stenstr\u00f6m P (2018) Scheduling parallel real-time recurrent tasks on multicore platforms. In: IEEE TPDS","DOI":"10.1109\/TPDS.2017.2777449"},{"key":"9375_CR33","unstructured":"Peter\u00a0Greenhalgh A (2011) Big.little processing with arm cortex-a15 and cortex-a7 improving energy efficiency in high-performance mobile platforms. White paper, http:\/\/www.cl.cam.ac.uk\/~rdm34\/big.LITTLE.pdf"},{"key":"9375_CR34","unstructured":"Raravi G (2014) Real-time scheduling on heterogeneous multiprocessors. Faculty of Engineering, University of Porto (PhD thesis)"},{"key":"9375_CR35","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9161-1","volume-title":"Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors","author":"G Raravi","year":"2013","unstructured":"Raravi G, Andersson B, Bletsas K (2013) Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors. Springer, New York"},{"key":"9375_CR36","doi-asserted-by":"crossref","unstructured":"Sih GC, Lee EA (1993) A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. In: IEEE TPDS","DOI":"10.1109\/71.207593"},{"key":"9375_CR37","doi-asserted-by":"crossref","unstructured":"Topcuoglu H, Hariri S, My Wu (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. In: IEEE TPDS","DOI":"10.1109\/71.993206"},{"key":"9375_CR38","doi-asserted-by":"crossref","unstructured":"Ueter N, von\u00a0der Br\u00fcggen G, Chen JJ, Li J, Agrawal K (2018) Reservation-based federated scheduling for parallel real-time tasks. In: IEEE RTSS","DOI":"10.1109\/RTSS.2018.00061"},{"key":"9375_CR39","doi-asserted-by":"crossref","unstructured":"Voudouris P, Stenstr\u00f6m P, Pathan R (2017) Timing-anomaly free dynamic scheduling of task-based parallel applications. In: IEEE RTAS","DOI":"10.1109\/RTAS.2017.2"},{"key":"9375_CR40","volume-title":"Introduction to graph theory","author":"DB West","year":"2001","unstructured":"West DB et al (2001) Introduction to graph theory. Prentice Hall, Upper Saddle River"},{"key":"9375_CR41","doi-asserted-by":"crossref","unstructured":"Yang K, Yang M, Anderson JH (2016) Reducing response-time bounds for dag-based task systems on heterogeneous multicore platforms. In: ACM RTNS","DOI":"10.1145\/2997465.2997486"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-021-09375-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11241-021-09375-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-021-09375-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,21]],"date-time":"2022-05-21T20:09:22Z","timestamp":1653163762000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11241-021-09375-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,21]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["9375"],"URL":"https:\/\/doi.org\/10.1007\/s11241-021-09375-2","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,21]]},"assertion":[{"value":"29 August 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}