Quasi-Static Scheduling for Deterministic Timed Concurrent Models on Multi-Core Hardware

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

  • Shaokai Lin - , University of California at Berkeley (Autor:in)
  • Erling Jellum - , University of California at Berkeley (Autor:in)
  • Mirco Theile - , Technische Universität München (Autor:in)
  • Tassilo Tanneberger - , Professur für Compilerbau (cfaed) (Autor:in)
  • Binqi Sun - , Technische Universität München (Autor:in)
  • Chadlia Jerad - , University of Manouba (Autor:in)
  • Yimo Xu - , University of California at Berkeley (Autor:in)
  • Guangyu Feng - , University of California at Berkeley (Autor:in)
  • Magnus Mæhlum - , Norwegian University of Science and Technology (Autor:in)
  • Jian Jia Chen - , Technische Universität (TU) Dortmund (Autor:in)
  • Martin Schoeberl - , Technical University of Denmark (Autor:in)
  • Linh Thi Xuan Phan - , University of Pennsylvania (Autor:in)
  • Jeronimo Castrillon - , Professur für Compilerbau (cfaed) (Autor:in)
  • Sanjit A. Seshia - , University of California at Berkeley (Autor:in)
  • Edward A. Lee - , University of California at Berkeley (Autor:in)

Abstract

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.

Details

OriginalspracheEnglisch
Aufsatznummer150
FachzeitschriftACM transactions on embedded computing systems
Jahrgang24
Ausgabenummer5
PublikationsstatusVeröffentlicht - 1 Okt. 2025
Peer-Review-StatusJa

Externe IDs

ORCID /0000-0002-5007-445X/work/206632719

Schlagworte

ASJC Scopus Sachgebiete

Schlagwörter

  • Concurrency, DAG Scheduling, Predictability, Quasi-Static Scheduling