{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T21:08:15Z","timestamp":1776373695780,"version":"3.51.2"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","funder":[{"name":"National Science Foundation","award":["#CNS-2233769"],"award-info":[{"award-number":["#CNS-2233769"]}]},{"name":"German Federal Ministry of Research, Technology and Space of Germany","award":["16KISK001K"],"award-info":[{"award-number":["16KISK001K"]}]},{"name":"German Research Council (DFG) through the InterMCore project","award":["505744711"],"award-info":[{"award-number":["505744711"]}]},{"name":"European Research Council","award":["865170"],"award-info":[{"award-number":["865170"]}]},{"name":"EU Horizon Europe Programme","award":["101135183"],"award-info":[{"award-number":["101135183"]}]},{"name":"Chair for CPSs in Production Engineering at TUM"},{"name":"NSF","award":["CNS-2111688 and CCF-2326606"],"award-info":[{"award-number":["CNS-2111688 and CCF-2326606"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2025,11,30]]},"abstract":"<jats:p>\n            To design performant, expressive, and reliable cyber-physical systems (CPSs), researchers extensively perform quasi-static scheduling for concurrent models of computation (MoCs) on multi-core hardware. However, these quasi-static scheduling approaches are developed independently for their corresponding MoCs, despite commonality in the approaches. To help generalize the use of quasi-static scheduling to new and emerging MoCs, this article proposes a\n            <jats:italic toggle=\"yes\">unified<\/jats:italic>\n            approach for a class of deterministic timed concurrent models (DTCMs), including prominent models such as synchronous dataflow (SDF), Boolean-controlled dataflow (BDF), scenario-aware dataflow (SADF), and Logical Execution Time (LET). In contrast to scheduling techniques tailored exclusively to specific MoCs, our unified approach leverages a common\n            <jats:italic toggle=\"yes\">intermediate<\/jats:italic>\n            formalism called state space finite automata (SSFA), bridging the gap between high-level MoCs and executable schedules. Once identified as DTCMs, new MoCs can directly adopt SSFA-based scheduling, significantly easing adoption. We show that quasi-static schedules facilitated by SSFA are provably free from timing anomalies and enable straightforward worst-case makespan analysis. We demonstrate the approach using the reactor model\u2014an emerging discrete-event MoC\u2014programmed using the Lingua Franca (\n            <jats:sc>LF<\/jats:sc>\n            ) language. Experiments show that quasi-statically scheduled\n            <jats:sc>LF<\/jats:sc>\n            programs exhibit lower runtime overhead compared to the dynamically scheduled\n            <jats:sc>LF<\/jats:sc>\n            programs, and that the analyzable worst-case makespans enable compile-time deadline checking.\n          <\/jats:p>","DOI":"10.1145\/3762653","type":"journal-article","created":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T11:24:33Z","timestamp":1756725873000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Quasi-Static Scheduling for Deterministic Timed Concurrent Models on Multi-Core Hardware"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6885-5572","authenticated-orcid":false,"given":"Shaokai","family":"Lin","sequence":"first","affiliation":[{"name":"University of California, Berkeley","place":["Berkeley, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2396-6284","authenticated-orcid":false,"given":"Erling","family":"Jellum","sequence":"additional","affiliation":[{"name":"University of California, Berkeley","place":["Berkeley, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1574-8858","authenticated-orcid":false,"given":"Mirco","family":"Theile","sequence":"additional","affiliation":[{"name":"Technical University of Munich","place":["Munich, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3196-7869","authenticated-orcid":false,"given":"Tassilo","family":"Tanneberger","sequence":"additional","affiliation":[{"name":"TU Dresden","place":["Dresden, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9764-6259","authenticated-orcid":false,"given":"Binqi","family":"Sun","sequence":"additional","affiliation":[{"name":"Technical University of Munich","place":["Munich, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5442-3098","authenticated-orcid":false,"given":"Chadlia","family":"Jerad","sequence":"additional","affiliation":[{"name":"University of Manouba","place":["Manouba, Tunisia"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-6862-5989","authenticated-orcid":false,"given":"Yimo","family":"Xu","sequence":"additional","affiliation":[{"name":"University of California, Berkeley","place":["Berkeley, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-8213-0704","authenticated-orcid":false,"given":"Guangyu","family":"Feng","sequence":"additional","affiliation":[{"name":"University of California, Berkeley","place":["Berkeley, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-9438-6400","authenticated-orcid":false,"given":"Magnus","family":"M\u00e6hlum","sequence":"additional","affiliation":[{"name":"Norwegian University of Science and Technology","place":["Trondheim, Norway"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8114-9760","authenticated-orcid":false,"given":"Jian-Jia","family":"Chen","sequence":"additional","affiliation":[{"name":"Technical University of Dortmund","place":["Dortmund, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2366-382X","authenticated-orcid":false,"given":"Martin","family":"Schoeberl","sequence":"additional","affiliation":[{"name":"Technical University of Denmark","place":["Lyngby, Denmark"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3458-7511","authenticated-orcid":false,"given":"Linh Thi Xuan","family":"Phan","sequence":"additional","affiliation":[{"name":"University of Pennsylvania","place":["Philadelphia, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5007-445X","authenticated-orcid":false,"given":"Jeronimo","family":"Castrillon","sequence":"additional","affiliation":[{"name":"TU Dresden","place":["Dresden, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6190-8707","authenticated-orcid":false,"given":"Sanjit A.","family":"Seshia","sequence":"additional","affiliation":[{"name":"University of California, Berkeley","place":["Berkeley, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5663-0584","authenticated-orcid":false,"given":"Edward A.","family":"Lee","sequence":"additional","affiliation":[{"name":"University of California, Berkeley","place":["Berkeley, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,26]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"System Design, Modeling, and Simulation using Ptolemy II","year":"2014","unstructured":"2014. System Design, Modeling, and Simulation using Ptolemy II."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.1993.319147"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/921086"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5626\/JCSE.2008.2.1.074"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/EFTA.2007.4416926"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","unstructured":"Marc C. W. Geilen Mladen Skelin J. Reinier van Kampenhout Hadi Alizadeh Ara Twan Basten Sander Stuijk and Kees G. W. Goossens. 2020. Scenarios in dataflow modeling and analysis. In System-Scenario-based Design Principles and Applications. Springer International Publishing Cham 145\u2013180. DOI:10.1007\/978-3-030-20343-6_8","DOI":"10.1007\/978-3-030-20343-6_8"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3381847"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2006.33"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45449-7_12"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512567"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45212-6_16"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3472-0_6"},{"key":"e_1_3_2_14_2","unstructured":"Benjamin Horowitz. 2003. Single-Mode Single-Processor Giotto Scheduling. Computer Science Division University of California."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3104255"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2687357.2687368"},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","unstructured":"Axel Jantsch. 2003. Modeling Embedded Systems and SoCs - Concurrency and Time in Models of Computation. Morgan Kaufmann.","DOI":"10.1016\/B978-155860925-9\/50005-6"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3576914.3587497"},{"key":"e_1_3_2_19_2","first-page":"3:1\u20133:13","volume-title":"Proceedings of the 4th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023)","volume":"108","author":"Jellum Erling Rennemo","year":"2023","unstructured":"Erling Rennemo Jellum, Shaokai Lin, Peter Donovan, Efsane Soyer, Fuzail Shakir, Torleiv Bryne, Milica Orlandic, Marten Lohstroh, and Edward A. Lee. 2023. Beyond the threaded programming model on real-time operating systems. In Proceedings of the 4th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023), Vol. 108. 3:1\u20133:13."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","unstructured":"Christoph M. Kirsch and Ana Sokolova. 2012. The logical execution time paradigm. In Advances in Real-Time Systems Samarjit Chakraborty and J\u00f6rg Ebersp\u00e4cher (Eds.). Springer Berlin Heidelberg Berlin Heidelberg 103\u2013120. DOI:10.1007\/978-3-642-24349-3_5","DOI":"10.1007\/978-3-642-24349-3_5"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2006.180"},{"key":"e_1_3_2_23_2","unstructured":"Edward A Lee. 1988. Recurrences iteration and conditionals in statically scheduled block diagram languages. VLSI Signal Processing 3 (1988) 330\u2013340."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.5009446"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1450095.1450117"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","unstructured":"Shaokai Lin Yatin A. Manerkar Marten Lohstroh Elizabeth Polgreen Sheng-Jung Yu Chadlia Jerad Edward A. Lee and Sanjit A. Seshia. 2023. Towards building verifiable CPS using lingua franca. ACM Trans. Embed. Comput. Syst. 22 5s (September 2023) 1\u201324. DOI:10.1145\/3609134","DOI":"10.1145\/3609134"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","unstructured":"Marten Lohstroh Christian Menard Soroush Bateni and Edward A. Lee. 2021. Toward a lingua franca for deterministic concurrent systems. ACM Transactions on Embedded Computing Systems (TECS) Special Issue on FDL\u201919 20 4 (May 2021) 1\u201327. DOI:10.1145\/3448128","DOI":"10.1145\/3448128"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-41131-2_4"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.1999.818824"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","unstructured":"Claire Maiza Hamza Rihani Juan M. Rivas Jo\u00ebl Goossens Sebastian Altmeyer and Robert I. Davis. 2019. A survey of timing verification techniques for multi-xore real-time Systems. ACM Comput. Surv. 52 3 (June 2019) 1\u201338. DOI:10.1145\/3323212","DOI":"10.1145\/3323212"},{"key":"e_1_3_2_32_2","volume-title":"Proceedings of the 22th International Workshop on Worst-Case Execution Time Analysis (WCET 2024)","author":"Maroun Emad Jacob","year":"2024","unstructured":"Emad Jacob Maroun, Eva Dengler, Stefan Dietrich, Chistian Hepp, Benedikt Herzog, Henriette Huber, Jens Knoop, Daniel Prokesch, Peter Puschner, Phillip Raffeck, Martin Schoeberl, Simon Schuster, and Peter W\u00e4gemann. 2024. The platin multi-target worst-case analysis tool. In Proceedings of the 22th International Workshop on Worst-Case Execution Time Analysis (WCET 2024)."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","unstructured":"Christian Menard Marten Lohstroh Soroush Bateni Matthew Chorlian Arthur Deng Peter Donovan Cl\u00e9ment Fournier Shaokai Lin Felix Suchert Tassilo Tanneberger Hokeun Kim Jeronimo Castrillon and Edward A. Lee. 2023. High-performance deterministic concurrency using lingua franca. ACM Trans. Archit. Code Optim. 20 4 (October 2023) 1\u201329. DOI:10.1145\/3617687","DOI":"10.1145\/3617687"},{"key":"e_1_3_2_34_2","unstructured":"Giovanni De Micheli. 1994. Synthesis and optimization of digital circuits. McGraw-Hill Higher Education."},{"key":"e_1_3_2_35_2","unstructured":"Guillaume Roumage Selma Azaiez Cyril Faure and St\u00e9phane Louise. 2025. An extended survey and a comparison framework for dataflow models of computation and communication. Retrieved from https:\/\/arxiv.org\/abs\/2501.07273"},{"key":"e_1_3_2_36_2","first-page":"4:1\u20134:13","volume-title":"Proceedings of the 22nd International Workshop on Worst-Case Execution Time Analysis (WCET 2024)","volume":"121","author":"Schoeberl Martin","year":"2024","unstructured":"Martin Schoeberl, Ehsan Khodadad, Shaokai Lin, Emad Jacob Maroun, Luca Pezzarossa, and Edward A. Lee. 2024. Invited paper: Worst-case execution time analysis of lingua franca applications. In Proceedings of the 22nd International Workshop on Worst-Case Execution Time Analysis (WCET 2024), Vol. 121. 4:1\u20134:13."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-018-9300-4"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2331147.2331165"},{"key":"e_1_3_2_39_2","volume-title":"Multiprocessor Scheduling to Account for Interprocessor Communication","author":"Sih Gilbert C.","year":"1991","unstructured":"Gilbert C. Sih. 1991. Multiprocessor Scheduling to Account for Interprocessor Communication. Ph. D. Dissertation. EECS Department, University of California, Berkeley."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/SAMOS.2011.6045491"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2024.3350243"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.23919\/DATE.2017.7927110"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-023-09403-3"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS48715.2020.000-4"},{"key":"e_1_3_2_45_2","doi-asserted-by":"crossref","unstructured":"Andrew Waterman Yunsup Lee David A. Patterson and Krste Asanovic. 2014. The RISC-V instruction set manual volume I: User-level ISA version 2.0. EECS Department University of California Berkeley Tech. Rep. UCB\/EECS-2014-54 (2014) 4.","DOI":"10.21236\/ADA605735"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2014.6925994"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3762653","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T17:13:18Z","timestamp":1759338798000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3762653"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,26]]},"references-count":45,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2025,11,30]]}},"alternative-id":["10.1145\/3762653"],"URL":"https:\/\/doi.org\/10.1145\/3762653","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,26]]},"assertion":[{"value":"2025-08-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}