Quasi-Static Scheduling for Deterministic Timed Concurrent Models on Multi-Core Hardware
ACM Transactions on Embedded Computing Systems · 30.11.2025 · 24 (5s) · 1-25
DOI: 10.1145/3762653 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Embedded Computing Systems, online erschienen am 26.09.2025. Verfasst von Shaokai Lin und 14 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 45 Literaturangaben. Gefördert von: National Science Foundation, German Federal Ministry of Research, Technology and Space of Germany, German Research Council (DFG) through the InterMCore project.
Abstract (Originalsprache)
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 unified 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 intermediate 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—an emerging discrete-event MoC—programmed using the Lingua Franca ( LF ) language. Experiments show that quasi-statically scheduled LF programs exhibit lower runtime overhead compared to the dynamically scheduled LF programs, and that the analyzable worst-case makespans enable compile-time deadline checking.
Förderung
- National Science Foundation
- German Federal Ministry of Research, Technology and Space of Germany
- German Research Council (DFG) through the InterMCore project
- European Research Council
- EU Horizon Europe Programme
- Chair for CPSs in Production Engineering at TUM
- NSF
Zitieren
APA
Lin, S., Jellum, E., Theile, M., Tanneberger, T., Sun, B., Jerad, C., Xu, Y., Feng, G., Mæhlum, M., Chen, J., Schoeberl, M., Phan, L. T. X., Castrillon, J., Seshia, S. A., & Lee, E. A. (2025). Quasi-Static Scheduling for Deterministic Timed Concurrent Models on Multi-Core Hardware. ACM Transactions on Embedded Computing Systems, 24(5s), 1-25. https://doi.org/10.1145/3762653
Vancouver
Lin S, Jellum E, Theile M, Tanneberger T, Sun B, Jerad C, et al. Quasi-Static Scheduling for Deterministic Timed Concurrent Models on Multi-Core Hardware. ACM Transactions on Embedded Computing Systems. 2025;24(5s):1-25. doi:10.1145/3762653
BibTeX
@article{Lin2025,
author = {Lin, Shaokai and Jellum, Erling and Theile, Mirco and Tanneberger, Tassilo and Sun, Binqi and Jerad, Chadlia and Xu, Yimo and Feng, Guangyu and Mæhlum, Magnus and Chen, Jian-Jia and Schoeberl, Martin and Phan, Linh Thi Xuan and Castrillon, Jeronimo and Seshia, Sanjit A. and Lee, Edward A.},
title = {Quasi-Static Scheduling for Deterministic Timed Concurrent Models on Multi-Core Hardware},
journal = {ACM Transactions on Embedded Computing Systems},
year = {2025},
volume = {24},
number = {5s},
pages = {1--25},
doi = {10.1145/3762653}
}
EUVIMED