{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T22:58:48Z","timestamp":1778626728582,"version":"3.51.4"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,1,10]],"date-time":"2024-01-10T00:00:00Z","timestamp":1704844800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EU H2020 project AMPERE","award":["871669"],"award-info":[{"award-number":["871669"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2024,1,31]]},"abstract":"<jats:p>This article tackles the problem of optimal placement of complex real-time embedded applications on heterogeneous platforms. Applications are composed of directed acyclic graphs of tasks, with each directed-acyclic-graph (DAG) having a minimum inter-arrival period for its activation requests and an end-to-end deadline within which all of the computations need to terminate since each activation. The platforms of interest are heterogeneous power-aware multi-core platforms with Dynamic Voltage and Frequency Scaling (DVFS) capabilities, including big.LITTLE Arm architectures and platforms with GPU or FPGA hardware accelerators with Dynamic Partial Reconfiguration capabilities. Tasks can be deployed on CPUs using partitioned EDF-based scheduling. Additionally, some of the tasks may have an alternate implementation available for one of the accelerators on the target platform, which are assumed to serve requests in non-preemptive FIFO order. The system can be optimized by minimizing power consumption, respecting precise timing constraints, maximizing the applications\u2019 slack, respecting given power consumption constraints, or even a combination of these, in a multi-objective formulation.<\/jats:p>\n          <jats:p>We propose an off-line optimization of the mentioned problem based on mixed-integer quadratic constraint programming (MIQCP). The optimization provides the DVFS configuration of all the CPUs (or accelerators) capable of frequency switching and the placement to be followed by each task in the DAGs, including the software-vs.-hardware implementation choice for tasks that can be hardware accelerated. For relatively big problems, we developed heuristic solvers capable of providing suboptimal solutions in a significantly reduced time compared to the MIQCP strategy, thus widening the applicability of the proposed framework.<\/jats:p>\n          <jats:p>We validate the approach by running a set of randomly generated DAGs on Linux under SCHED_DEADLINE, deployed onto two real boards, one with Arm big.LITTLE architecture, the other with FPGA acceleration, verifying that the experimental runs meet the theoretical expectations in terms of timing and power optimization goals.<\/jats:p>","DOI":"10.1145\/3592609","type":"journal-article","created":{"date-parts":[[2023,4,13]],"date-time":"2023-04-13T12:40:38Z","timestamp":1681389638000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Multi-criteria Optimization of Real-time DAGs on Heterogeneous Platforms under P-EDF"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0362-0657","authenticated-orcid":false,"given":"Tommaso","family":"Cucinotta","sequence":"first","affiliation":[{"name":"Scuola Superiore Sant\u2019Anna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8432-3162","authenticated-orcid":false,"given":"Alexandre","family":"Amory","sequence":"additional","affiliation":[{"name":"Scuola Superiore Sant\u2019Anna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5663-4713","authenticated-orcid":false,"given":"Gabriele","family":"Ara","sequence":"additional","affiliation":[{"name":"Scuola Superiore Sant\u2019Anna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-0903-1149","authenticated-orcid":false,"given":"Francesco","family":"Paladino","sequence":"additional","affiliation":[{"name":"Scuola Superiore Sant\u2019Anna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4480-8808","authenticated-orcid":false,"given":"Marco Di","family":"Natale","sequence":"additional","affiliation":[{"name":"Scuola Superiore Sant\u2019Anna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,1,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTTAS.2001.929862"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/827270.829047"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/DFT50435.2020.9250750"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2005.20"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3477314.3507030"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS52030.2021.00013"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TrustCom.2011.132"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2019.03.013"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373400.3373408"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2808231"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2015.27"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021711220939"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2010.23"},{"key":"e_1_3_2_15_2","first-page":"1","volume-title":"Proceedings of the IEEE Real-Time Systems Symposium (RTSS\u201916)","author":"Biondi Alessandro","year":"2016","unstructured":"Alessandro Biondi, Alessio Balsini, Marco Pagani, Enrico Rossi, Mauro Marinoni, and Giorgio Buttazzo. 2016. A framework for supporting real-time applications on dynamic reconfigurable FPGAs. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS\u201916). IEEE, 1\u201312."},{"key":"e_1_3_2_16_2","unstructured":"OpenMP Architecture Review Board. 2021. OpenMP Application Programming Interface version 5.2."},{"key":"e_1_3_2_17_2","volume-title":"Proceedings of the IEEE Conference on Real Time Computing Systems and Applications","author":"Casile Antonino","year":"1998","unstructured":"Antonino Casile, Giorgio Buttazzo, Gerardo Lamastra, and Giuseppe Lipari. 1998. Simulation and tracing of hybrid task sets on distributed systems. In Proceedings of the IEEE Conference on Real Time Computing Systems and Applications."},{"key":"e_1_3_2_18_2","volume-title":"Proceedings of the 25th Euromicro Conference on Digital System Design (DSD\u201922)","author":"Casini Daniel","year":"2022","unstructured":"Daniel Casini and Alessandro Biondi. 2022. Placement of chains of real-time tasks on heterogeneous platforms under EDF scheduling. In Proceedings of the 25th Euromicro Conference on Digital System Design (DSD\u201922)."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3316781.3317771"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECRTS.2019.6"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2022.102416"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2022.102416"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00365326"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS52674.2021.00027"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3550355.3552408"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.11.014"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2362336.2362353"},{"key":"e_1_3_2_28_2","volume-title":"Proceedings of the Linux Audio Conference (LAC\u201911)","author":"Cucinotta Tommaso","unstructured":"Tommaso Cucinotta, Dario Faggioli, and Giacomo Bagnoli. 2011. Low-latency audio on linux by means of real-time scheduling. In Proceedings of the Linux Audio Conference (LAC\u201911)."},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","DOI":"10.1109\/TII.2009.2027013","article-title":"A real-time service-oriented architecture for industrial automation","author":"Cucinotta Tommaso","year":"2009","unstructured":"Tommaso Cucinotta, Antonio Mancina, Gaetano F. Anastasi, Giuseppe Lipari, Leonardo Mangeruca, Roberto Checcozzo, and Fulvio Rusin\u2018a. 2009. A real-time service-oriented architecture for industrial automation. IEEE Trans. Industr. Inf. (2009).","journal-title":"IEEE Trans. Industr. Inf."},{"key":"e_1_3_2_30_2","article-title":"QoS control for pipelines of tasks using multiple resources","author":"Cucinotta Tommaso","year":"2009","unstructured":"Tommaso Cucinotta and Luigi Palopoli. 2009. QoS control for pipelines of tasks using multiple resources. IEEE Trans. Comput. (2009).","journal-title":"IEEE Trans. Comput."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.6334205"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/1978802.1978814"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/tc.2022.3187351"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2020.101729"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2005.39"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2695664.2695808"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCS48598.2019.9188183"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2830555"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-65482-9_1"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2020.3023169"},{"key":"e_1_3_2_41_2","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201911)","author":"Kato Shinpei","year":"2011","unstructured":"Shinpei Kato, Karthik Lakshmanan, Ragunathan Rajkumar, and Yutaka Ishikawa. 2011. TimeGraph: GPU scheduling for real-time multi-tasking environments. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201911). USENIX Association."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2018.00011"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2010.42"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2012.05.048"},{"issue":"1","key":"e_1_3_2_45_2","article-title":"Scheduling alghorithms for multiprogramming in a hard real-time environment","volume":"20","author":"Liu C. L.","year":"1973","unstructured":"C. L. Liu and J. Layland. 1973. Scheduling alghorithms for multiprogramming in a hard real-time environment. J. ACM 20, 1 (1973).","journal-title":"J. ACM"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3323212"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2015.23"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISORC49007.2020.00015"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.637146"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.micpro.2019.102939"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2020.101953"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSD.2011.19"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/384198.384209"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2997465.2997498"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.micpro.2015.06.004"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISORC49007.2020.00042"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1117\/12.298417"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.micpro.2021.104336"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/2997465.2997472"},{"issue":"10","key":"e_1_3_2_60_2","doi-asserted-by":"crossref","first-page":"2671","DOI":"10.1109\/TPDS.2014.2359449","article-title":"Deadline assignment in EDF schedulers for real-time distributed systems","volume":"26","author":"Rivas Juan M.","year":"2014","unstructured":"Juan M. Rivas, J. Javier Guti\u00e9rrez, J. Carlos Palencia, and Michael Gonz\u00e1lez Harbour. 2014. Deadline assignment in EDF schedulers for real-time distributed systems. IEEE Trans. Parallel Distrib. Syst. 26, 10 (2014), 2671\u20132684.","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3412841.3441930"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3464298.3493402"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2021.102210"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/ETFA.2010.5641357"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/242223.242291"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.7873\/DATE.2015.0778"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1109\/CISS.2015.7086884"},{"key":"e_1_3_2_68_2","first-page":"365","volume-title":"Proceedings of the 22nd Euromicro Conference on Digital System Design (DSD\u201919)","author":"Wurst Falk","year":"2019","unstructured":"Falk Wurst, Dakshina Dasari, Arne Hamann, Dirk Ziegenbein, Ignacio Sanudo, Nicola Capodieci, Marko Bertogna, and Paolo Burgio. 2019. System performance modelling of heterogeneous hw platforms: An automated driving case study. In Proceedings of the 22nd Euromicro Conference on Digital System Design (DSD\u201919). IEEE, 365\u2013372."},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPADS.2002.1183422"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA50079.2020.9203643"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2017.123"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4798"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2018.00028"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3592609","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3592609","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:56Z","timestamp":1750183736000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3592609"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,10]]},"references-count":72,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,31]]}},"alternative-id":["10.1145\/3592609"],"URL":"https:\/\/doi.org\/10.1145\/3592609","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,10]]},"assertion":[{"value":"2022-11-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}