{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:36Z","timestamp":1750220256330,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2021,9,22]],"date-time":"2021-09-22T00:00:00Z","timestamp":1632268800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["ERC-2013-AdG 340328-MECCA"],"award-info":[{"award-number":["ERC-2013-AdG 340328-MECCA"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            This paper presents a federated scheduling algorithm for implicit-deadline sporadic DAGs that execute on an unrelated heterogeneous multiprocessor platform. We consider a global work-conserving scheduler to execute a single DAG exclusively on a subset of the unrelated processors. Formal schedulability analysis to find the makespan of a DAG on its dedicated subset of the processors is proposed. The problem of determining each subset of dedicated unrelated processors for each DAG such that the DAG meets its deadline (i.e., designing the federated scheduling algorithm) is tackled by proposing a novel processors-to-task assignment heuristic using a new concept called\n            <jats:italic>processor value<\/jats:italic>\n            . Empirical evaluation is presented to show the effectiveness of our approach.\n          <\/jats:p>","DOI":"10.1145\/3477018","type":"journal-article","created":{"date-parts":[[2021,9,22]],"date-time":"2021-09-22T20:48:40Z","timestamp":1632343720000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Federated Scheduling of Sporadic DAGs on Unrelated Multiprocessors"],"prefix":"10.1145","volume":"20","author":[{"given":"Petros","family":"Voudouris","sequence":"first","affiliation":[{"name":"Chalmers University of Technology, G\u00f6teborg, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Per","family":"Stenstr\u00f6m","sequence":"additional","affiliation":[{"name":"Chalmers University of Technology, G\u00f6teborg, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Risat","family":"Pathan","sequence":"additional","affiliation":[{"name":"Chalmers University of Technology, G\u00f6teborg, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,9,22]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1007\/s11241-013-9195-z"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/2997465.2997482"},{"unstructured":"ARM. 2011. big.LITTLE technology: The future of mobile. White paper https:\/\/www.arm.com\/files\/pdf\/big_LITTLE_Technology_the_Futue_of_Mobile.pdf.  ARM. 2011. big.LITTLE technology: The future of mobile. White paper https:\/\/www.arm.com\/files\/pdf\/big_LITTLE_Technology_the_Futue_of_Mobile.pdf.","key":"e_1_2_1_3_1"},{"unstructured":"ARM. 2017. The future of compute re-imagined. https:\/\/www.arm.com\/why-arm\/technologies\/dynamiq.  ARM. 2017. The future of compute re-imagined. https:\/\/www.arm.com\/why-arm\/technologies\/dynamiq.","key":"e_1_2_1_4_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1007\/s10766-010-0135-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1109\/IPDPS.2015.33"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.5555\/2738468"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1007\/s10951-018-0593-x"},{"key":"e_1_2_1_9_1","volume-title":"Rosier","author":"Baruah Sanjoy K.","year":"1990","unstructured":"Sanjoy K. Baruah , Aloysius K. Mok , and Louis E . Rosier . 1990 . Preemptively scheduling hard-real-time sporadic tasks on one processor. In [1990] Proceedings 11th Real-time Systems Symposium. IEEE, IEEE, Lake Buena Vista, Florida, USA , 182\u2013190. Sanjoy K. Baruah, Aloysius K. Mok, and Louis E. Rosier. 1990. Preemptively scheduling hard-real-time sporadic tasks on one processor. In [1990] Proceedings 11th Real-time Systems Symposium. IEEE, IEEE, Lake Buena Vista, Florida, USA, 182\u2013190."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of OSPERT","author":"Bastoni Andrea","year":"2010","unstructured":"Andrea Bastoni , Bj\u00f6rn Brandenburg , and James Anderson . 2010 . Cache-related preemption and migration delays: Empirical approximation and impact on schedulability . Proceedings of OSPERT (2010). Andrea Bastoni, Bj\u00f6rn Brandenburg, and James Anderson. 2010. Cache-related preemption and migration delays: Empirical approximation and impact on schedulability. Proceedings of OSPERT (2010)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/341800.341803"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/3394810.3394823"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/3241049"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.5555\/1009383.1009838"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/324133.324234"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1006\/jpdc.2000.1714"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/3358236"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/2751205.2751235"},{"doi-asserted-by":"crossref","unstructured":"Kallia Chronaki Miquel Moret\u00f3 Marc Casas Alejandro Rico Rosa M. Badia Eduard Ayguad\u00e9 and Mateo Valero. 2019. On the maturity of parallel applications for asymmetric multi-core processors. J. Parallel and Distrib. Comput. (2019).  Kallia Chronaki Miquel Moret\u00f3 Marc Casas Alejandro Rico Rosa M. Badia Eduard Ayguad\u00e9 and Mateo Valero. 2019. On the maturity of parallel applications for asymmetric multi-core processors. J. Parallel and Distrib. Comput. (2019).","key":"e_1_2_1_19_1","DOI":"10.1016\/j.jpdc.2019.01.007"},{"key":"e_1_2_1_20_1","volume-title":"Guillaume Lager, Cl\u00e9ment L\u00e9ger, Benjamin Orgogozo, J\u00e9r\u00f4me Reybert, and Thierry Strudel.","author":"de Dinechin Beno\u00eet Dupont","year":"2013","unstructured":"Beno\u00eet Dupont de Dinechin , Pierre Guironnet de Massas , Guillaume Lager, Cl\u00e9ment L\u00e9ger, Benjamin Orgogozo, J\u00e9r\u00f4me Reybert, and Thierry Strudel. 2013 . A distributed run-time environment for the kalray mppa\u00ae-256 integrated manycore processor. Procedia Computer Science ( 2013). Beno\u00eet Dupont de Dinechin, Pierre Guironnet de Massas, Guillaume Lager, Cl\u00e9ment L\u00e9ger, Benjamin Orgogozo, J\u00e9r\u00f4me Reybert, and Thierry Strudel. 2013. A distributed run-time environment for the kalray mppa\u00ae-256 integrated manycore processor. Procedia Computer Science (2013)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/2248487.2151004"},{"volume-title":"Rtcsa","author":"Dinh Son","unstructured":"Son Dinh , Christopher Gill , and Kunal Agrawal . 2020. Efficient deterministic federated scheduling for parallel real-time tasks . In Rtcsa . IEEE. Son Dinh, Christopher Gill, and Kunal Agrawal. 2020. Efficient deterministic federated scheduling for parallel real-time tasks. In Rtcsa. IEEE.","key":"e_1_2_1_22_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1109\/ICPP.2009.64"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/2024723.2000108"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1007\/s11241-018-09325-5"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.5555\/578533"},{"key":"e_1_2_1_27_1","volume-title":"Bounds for certain multiprocessing anomalies. Bell System Technical Journal","author":"Graham Ronald L.","year":"1966","unstructured":"Ronald L. Graham . 1966. Bounds for certain multiprocessing anomalies. Bell System Technical Journal ( 1966 ). Ronald L. Graham. 1966. Bounds for certain multiprocessing anomalies. Bell System Technical Journal (1966)."},{"key":"e_1_2_1_28_1","series-title":"SIAM Journal on Applied Mathematics","volume-title":"Bounds on multiprocessing timing anomalies","author":"Graham Ronald L.","year":"1969","unstructured":"Ronald L. Graham . 1969. Bounds on multiprocessing timing anomalies . SIAM Journal on Applied Mathematics ( 1969 ). Ronald L. Graham. 1969. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics (1969)."},{"key":"e_1_2_1_29_1","volume-title":"Response time bounds for typed DAG parallel tasks on heterogeneous multi-cores. Ieee Tpds","author":"Han Meiling","year":"2019","unstructured":"Meiling Han , Nan Guan , Jinghao Sun , Qingqiang He , Qingxu Deng , and Weichen Liu . 2019. Response time bounds for typed DAG parallel tasks on heterogeneous multi-cores. Ieee Tpds ( 2019 ). Meiling Han, Nan Guan, Jinghao Sun, Qingqiang He, Qingxu Deng, and Weichen Liu. 2019. Response time bounds for typed DAG parallel tasks on heterogeneous multi-cores. Ieee Tpds (2019)."},{"key":"e_1_2_1_30_1","volume-title":"Federated scheduling for typed DAG tasks scheduling analysis on heterogeneous multi-cores. Journal of Systems Architecture","author":"Han Meiling","year":"2020","unstructured":"Meiling Han , Tianyu Zhang , Yuhan Lin , and Qingxu Deng . 2020. Federated scheduling for typed DAG tasks scheduling analysis on heterogeneous multi-cores. Journal of Systems Architecture ( 2020 ). Meiling Han, Tianyu Zhang, Yuhan Lin, and Qingxu Deng. 2020. Federated scheduling for typed DAG tasks scheduling analysis on heterogeneous multi-cores. Journal of Systems Architecture (2020)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.5555\/3207796"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/3282307"},{"key":"e_1_2_1_33_1","volume-title":"Semi-federated scheduling of parallel real-time tasks on multiprocessors. Ieee Rtss","author":"Jiang Xu","year":"2017","unstructured":"Xu Jiang , Nan Guan , Xiang Long , and Wang Yi. 2017. Semi-federated scheduling of parallel real-time tasks on multiprocessors. Ieee Rtss ( 2017 ). Xu Jiang, Nan Guan, Xiang Long, and Wang Yi. 2017. Semi-federated scheduling of parallel real-time tasks on multiprocessors. Ieee Rtss (2017)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1145\/322092.322101"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1109\/ECRTS.2014.23"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1007\/s10107-014-0786-9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1109\/ECRTS.2015.26"},{"doi-asserted-by":"crossref","unstructured":"Alba Melo Jesus Carretero Per Stenstrom Sanjay Ranka and Eduard Ayguade. 2019. Trends on heterogeneous and innovative hardware and software systems.  Alba Melo Jesus Carretero Per Stenstrom Sanjay Ranka and Eduard Ayguade. 2019. Trends on heterogeneous and innovative hardware and software systems.","key":"e_1_2_1_38_1","DOI":"10.1016\/j.jpdc.2019.08.001"},{"unstructured":"NVIDIA. 2018. Nvidia jetson AGX xavier and the new era of autonomous machines. Nvidia presentation http:\/\/info.nvidia.com\/rs\/156-OFN-742\/images\/Jetson_AGX_Xavier_New_Era_Autonomous_Machines.pdf.  NVIDIA. 2018. Nvidia jetson AGX xavier and the new era of autonomous machines. Nvidia presentation http:\/\/info.nvidia.com\/rs\/156-OFN-742\/images\/Jetson_AGX_Xavier_New_Era_Autonomous_Machines.pdf.","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","volume-title":"Scheduling parallel real-time recurrent tasks on multicore platforms. Ieee Tpds","author":"Pathan Risat","year":"2018","unstructured":"Risat Pathan , Petros Voudouris , and Per Stenstr\u00f6m . 2018. Scheduling parallel real-time recurrent tasks on multicore platforms. Ieee Tpds ( 2018 ). Risat Pathan, Petros Voudouris, and Per Stenstr\u00f6m. 2018. Scheduling parallel real-time recurrent tasks on multicore platforms. Ieee Tpds (2018)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1007\/978-3-030-35540-1_4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1109\/71.207593"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1109\/RTAS48715.2020.00-17"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1109\/71.993206"},{"doi-asserted-by":"crossref","unstructured":"Niklas Ueter Georg von der Br\u00fcggen Jian-Jia Chen Jing Li and Kunal Agrawal. 2018. Reservation-based federated scheduling for parallel real-time tasks. In Ieee Rtss.  Niklas Ueter Georg von der Br\u00fcggen Jian-Jia Chen Jing Li and Kunal Agrawal. 2018. Reservation-based federated scheduling for parallel real-time tasks. In Ieee Rtss.","key":"e_1_2_1_45_1","DOI":"10.1109\/RTSS.2018.00061"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.1145\/2678373.2665692"},{"key":"e_1_2_1_47_1","volume-title":"Anderson","author":"Yang Kecheng","year":"2014","unstructured":"Kecheng Yang and James H . Anderson . 2014 . Optimal GEDF-based schedulers that allow intra-task parallelism on heterogeneous multiprocessors. In Ieee Estimedia . Kecheng Yang and James H. Anderson. 2014. Optimal GEDF-based schedulers that allow intra-task parallelism on heterogeneous multiprocessors. In Ieee Estimedia."},{"doi-asserted-by":"publisher","key":"e_1_2_1_48_1","DOI":"10.1145\/2997465.2997486"},{"key":"e_1_2_1_49_1","volume-title":"The HPC-DAG task model for heterogeneous real-time systems","author":"Zahaf Houssam-Eddine","year":"2020","unstructured":"Houssam-Eddine Zahaf , Zahaf Houssam-Eddine , Nicola Capodieci , Roberto Cavicchioli , Giuseppe Lipari , and Marko Bertogna . 2020. The HPC-DAG task model for heterogeneous real-time systems . IEEE Trans. Comput . ( 2020 ). Houssam-Eddine Zahaf, Zahaf Houssam-Eddine, Nicola Capodieci, Roberto Cavicchioli, Giuseppe Lipari, and Marko Bertogna. 2020. The HPC-DAG task model for heterogeneous real-time systems. IEEE Trans. Comput. (2020)."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477018","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3477018","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:46Z","timestamp":1750188646000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477018"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,22]]},"references-count":49,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3477018"],"URL":"https:\/\/doi.org\/10.1145\/3477018","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2021,9,22]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}