{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T16:31:05Z","timestamp":1775665865102,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T00:00:00Z","timestamp":1625788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            Continuous demands for higher performance and reliability within stringent resource budgets is driving a shift from homogeneous to heterogeneous processing platforms for the implementation of today\u2019s cyber-physical systems (CPSs). These CPSs are typically represented as\n            <jats:italic>Directed-acyclic Task Graph<\/jats:italic>\n            (DTG) due to the complex interactions between their functional components that are often distributed in nature. In this article, we consider the problem of scheduling a real-time application modelled as a single DTG, where tasks may have multiple implementations designated as quality-levels, with higher quality-levels producing more accurate results and contributing to higher rewards\/Quality-of-Service for the system. First, we introduce an optimal solution using\n            <jats:italic>Integer Linear Programming (ILP) for a DTG with multiple quality-levels, to be executed on a heterogeneous distributed platform<\/jats:italic>\n            . However, this ILP-based optimal solution exhibits high computational complexity and does not scale for moderately large problem sizes. Hence, we propose two low-overhead heuristic algorithms called\n            <jats:italic>Global Slack Aware Quality-level Allocator<\/jats:italic>\n            (\n            <jats:italic>G-SLAQA<\/jats:italic>\n            ) and\n            <jats:italic>Total Slack Aware Quality-level Allocator<\/jats:italic>\n            (\n            <jats:italic>T-SLAQA<\/jats:italic>\n            ), which are able to produce satisfactorily efficient as well as fast solutions within a reasonable time.\n            <jats:italic>G-SLAQA<\/jats:italic>\n            , the baseline heuristic, is greedier and faster than its counter-part\n            <jats:italic>T-SLAQA<\/jats:italic>\n            , whose performance is at least as efficient as\n            <jats:italic>G-SLAQA<\/jats:italic>\n            . The efficiency of all the proposed schemes have been extensively evaluated through simulation-based experiments using benchmark and randomly generated DTGs. Through the case study of a real-world\n            <jats:italic>automotive traction controller<\/jats:italic>\n            , we generate schedules using our proposed schemes to demonstrate their practical applicability.\n          <\/jats:p>","DOI":"10.1145\/3462776","type":"journal-article","created":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T15:04:44Z","timestamp":1625843084000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["<i>SLAQA<\/i>"],"prefix":"10.1145","volume":"20","author":[{"given":"Sanjit Kumar","family":"Roy","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Guwahati, Guwahati, Assam, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4481-102X","authenticated-orcid":false,"given":"Rajesh","family":"Devaraj","sequence":"additional","affiliation":[{"name":"Nvidia Graphics, Bangalore, Karnataka, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnab","family":"Sarkar","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kharagpur, Kharagpur, West Bengal, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Debabrata","family":"Senapati","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Guwahati, Guwahati, Assam, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 2010 10th IEEE\/ACM International Conference on Cluster, Cloud and Grid Computing. 224\u2013232","author":"Zhu X."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.68"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328755"},{"key":"e_1_2_1_4_1","volume-title":"Article 62 (Mar.","author":"Mittal Sparsh","year":"2016"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISORC.2015.18"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.3390\/s17010033"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCDC.2014.6852285"},{"key":"e_1_2_1_8_1","first-page":"1","article-title":"Minimizing cost of scheduling tasks on heterogeneous multicore embedded systems","volume":"16","author":"Liu Jing","year":"2016","journal-title":"ACM Trans. Embed. Comput. Syst."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.57"},{"key":"e_1_2_1_10_1","volume-title":"Hard Real-time Computing Systems: Predictable Scheduling Algorithms and Applications","author":"Buttazzo Giorgio C"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1176980"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3012278"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.23919\/ACC.2017.7963442"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-020-00669-0"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2019.101706"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2014.2308175"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2021.3059569"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.993206"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2015.04.005"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.23919\/ACC.2019.8815148"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3126496"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 31st Euromicro Conference on Real-Time Systems (ECRTS\u201919)","author":"Rouxel Benjamin","year":"2019"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2018.00056"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2014.23"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA50079.2020.9203660"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2017.00015"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2526682"},{"key":"e_1_2_1_28_1","volume-title":"Garey","author":"Johnson David S.","year":"1979"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80008-0"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SBAC-PAD.2004.1"},{"key":"e_1_2_1_31_1","volume-title":"Computer and Information Science","author":"Jedari Behrouz","year":"2009"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.722221"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.1264795"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.80160"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.9.6.841"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3143043.3143183"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2010.02.005"},{"key":"e_1_2_1_38_1","unstructured":"Guoqi Xie Renfa Li and Keqin Li. Semanticscholar 2016. Distributed Computing for Functional Safety of Automotive Embedded Systems. Semanticscholar.  Guoqi Xie Renfa Li and Keqin Li. Semanticscholar 2016. Distributed Computing for Functional Safety of Automotive Embedded Systems. Semanticscholar."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2012.08.015"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2008.11.001"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2017.2676183"},{"key":"e_1_2_1_42_1","unstructured":"[n.d.]. CPLEX Optimizer. Retrieved from https:\/\/www.ibm.com\/analytics\/data-science\/prescriptive-analytics\/cplex-optimizer.  [n.d.]. CPLEX Optimizer. Retrieved from https:\/\/www.ibm.com\/analytics\/data-science\/prescriptive-analytics\/cplex-optimizer."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ress.2004.08.008"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3462776","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3462776","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:27Z","timestamp":1750195887000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3462776"}},"subtitle":["Quality-level Aware Scheduling of Task Graphs on Heterogeneous Distributed Systems"],"short-title":[],"issued":{"date-parts":[[2021,7,9]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3462776"],"URL":"https:\/\/doi.org\/10.1145\/3462776","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,9]]},"assertion":[{"value":"2020-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}