#  PretVM: Predictable, Efficient Virtual Machine for Real-Time Concurrency
††thanks: The work in this paper was supported in part by the National Science
Foundation (NSF), award #CNS-2233769 (Consistency vs. Availability in Cyber-
Physical Systems), by DARPA grant FA8750-20-C-0156, by Intel, and by the
iCyPhy Research Center (Industrial Cyber-Physical Systems), supported by
Denso, Siemens, and Toyota. This work was also supported, in part, by the
German Federal Ministry of Education and Research (BMBF) as part of the
program “Souverän. Digital. Vernetzt.”, joint project 6G-life (16KISK001K),
and by the German Research Council (DFG) through the InterMCore project
(505744711).Mirco Theile and Binqi Sun were supported by the Chair for Cyber-
Physical Systems in Production Engineering at TUM.

Shaokai Lin  UC Berkeley
Berkeley, USA  Erling Jellum  NTNU
Trondheim, Norway  Mirco Theile  TU Munich
Munich, Germany  Tassilo Tanneberger  TU Dresden
Dresden, Germany  Binqi Sun  Chadlia Jerad  TU Munich
Munich, Germany  University of Manouba
Manouba, Tunisia  Ruomu Xu  UC Berkeley
Berkeley, USA  Guangyu Feng  UC Berkeley
Berkeley, USA  Christian Menard  Marten Lohstroh  TU Dresden
Dresden, Germany  UC Berkeley
Berkeley, USA  Jeronimo Castrillon  TU Dresden
Dresden, Germany  Sanjit Seshia  UC Berkeley
Berkeley, USA  Edward Lee  UC Berkeley
Berkeley, USA

###### Abstract

This paper introduces the Precision-Timed Virtual Machine (PretVM), an
intermediate platform facilitating the execution of quasi-static schedules
compiled from a subset of programs written in the Lingua Franca (LF)
coordination language. The subset consists of those programs that in principle
should have statically verifiable and predictable timing behavior. The PretVM
provides a schedule with well-defined worst-case timing bounds. The PretVM
provides a clean separation between _application_ logic and _coordination_
logic, yielding more analyzable program executions. Experiments compare the
PretVM against the default (more dynamic) LF scheduler and show that it
delivers time-accurate deterministic execution.

###### Index Terms:

Cyber-Physical Systems, Real-Time Systems, DAG Scheduling, Virtual Machine,
Concurrency

##  I Introduction

When developing real-time software for Cyber-Physical Systems (CPSs), the
conventional strategy often adopts a bottom-up approach, where the emphasis is
first placed on defining the ”how”—for instance, using a preemptive EDF
scheduler—in hopes of realizing the ”what”, i.e., the desired timing behavior.
This bottom-up process relies heavily on experimental feedback to find out
whether a system is able to meet system-level timing constraints. Iteratively,
code optimizations are carried out until the desired behavior is achieved.
Yet, the bottom-up method complicates code validation and upgrades, and it
renders implementations platform-specific and only works well in systems where
multiple runs of the same code yield very similar timing behavior. Code
obtained through such a process, therefore, tends to not be useable on
different platforms and is challenging to prove safe. As Cyber-Physical
Systems become more software-defined (e.g., in the automotive industry [1])
and increasingly often implemented using multi-core and heterogeneous
hardware, the bottom-up approach becomes less feasible and attractive.

Henzinger and Kirsch [2] observe that a lot of these difficulties are due to
an entanglement of concerns between “reactivity,” which refers to real-time
interaction with a physical environment, “schedulability,” which concerns
real-time execution in a specific execution environment, and “functionality,”
such as control laws and device drivers. The Giotto language and methodology
they developed, which introduced the concept of Logical Execution Time (LET),
meant specifically to help programmers separate these concerns. A Giotto
program explicitly specifies the exact real-time interaction of software
components with the physical world, leaving it to the Giotto compiler (not the
software or control engineer) to generate timing code that ensures the
specified timing behavior on a given platform. The timing code, known as E
code, encodes Giotto’s LET semantics and runs on the Embedded Machine, a
virtual machine that makes E code portable [3].

The recently emerged Lingua Franca (LF) [4, 5] coordination language and its
underlying reactor model [6] can be characterized as a generalization of
Giotto and LET [7]. It takes the separation between reactivity and
schedulability a step further by decoupling the passage of physical time from
logical time, except when interactions with the physical world are involved
(through timers, sensors, and actuators) [8]. In part because LF is not
strictly task-based and allows sporadic events, the scheduling of LF programs
is carried out dynamically, at runtime. While the timing behavior is specified
in the LF code, alignment with physical time is best-effort and without hard
guarantees that could be derived based on a quasi-static schedule.

This paper describes an augmentation of the LF toolchain that generates quasi-
static schedules. We do this through a compiler extension, runtime
integration, and virtual machine abstraction called the Precision-Timed
Virtual Machine, or in short, PretVM. The functionality that PretVM offers to
LF is similar to what the E Machine [3] provides for LET. PretVM enables a
methodology for obtaining predetermined temporal behavior for the subset of LF
programs comprising sequences of periodic task sets. Based on a directed
acyclic graph (DAG) representation of the program, a partitioned quasi-static
schedule can be derived using different schedulers. This quasi-static
schedule, after being translated into our PretVM bytecode for each partition,
can be executed using multiple worker threads. We show that our approach
exhibits predictable timing and can leverage existing work in multi-core
mapping and scheduling, such as Edge Generation Scheduling for DAG Tasks [9].

In this work, we focus on a subset of LF programs whose behavior can be
statically analyzed by our approach. We exclude “dynamic” features of LF, such
as actions and physical connections, and save them for future work.

##### Contributions

In this paper, we present the following key contributions:

  1. 1.

We present the Precision-Timed Virtual Machine, PretVM, as an intermediary
platform supporting a top-down, model-based design flow for real-time software
in Cyber-Physical Systems.

  2. 2.

We provide a methodology to statically schedule and compile a subset of LF
into PretVM bytecode.

  3. 3.

We show that our approach is amenable to predicting the worst-case execution
time (WCET) of systems’ hyperperiods.

  4. 4.

We evaluate our approach using a set of LF benchmarks evaluating our
methodology w.r.t. timing accuracy. Results show that PretVM delivers time-
accurate deterministic execution.

##  II Running Example

###  II-A Reaction Wheel System

Figure 1: A simple reaction wheel system

To informally introduce the reactor model, we present a simplified example of
a reaction wheel system used for satellite attitude control [10]. In this
system, a gyroscope and an angular rate sensor periodically collect data from
the environment and send them to a controller, which performs sensor fusion
and generates a command the motor.

The diagram in Figure 1 represents the simplified reaction wheel system. A
reactor is a stateful concurrent component. In the diagram, reactors are
represented as rectangles with rounded corners, and they are Gyroscope,
AngularRateSensor, Controller, and Motor. A reactor can contain reactions,
timers, ports, and connections.

A reaction is a routine that executes when any of its triggers is present, and
it is rendered as a chevron in the diagram. The body of a reaction is written
in a target language and represents the “business logic” of the application.
In this work, each reaction is further annotated with its worst-case execution
time (WCET) for a given platform. The Controller reactor has four reactions,
each labelled with an integer number. These numbers correspond to the
priorities of the reactions within Controller, which determine the order in
which reactions execute should they be triggered simultaneously. It is
important to note that reaction priorities establish a total order only
_within_ the same reactor.

A reaction can be triggered by a port, a timer, an action, or a built-in
trigger such as startup or shutdown. A port, rendered as a black triangle in
the diagram, is used to communicate with other reactors. A timer, rendered as
a clock in the diagram, is used to generate periodic events. Timers are
characterized by an offset and a period which are shown below the clock. For
example, the timer in AngularRateSensor starts firing at $5s$ with a period of
$75s$.

Around the Controller reactor, a connection is drawn from its output port out0
to its input port in2, with a delay of $100\mu s$, effectively scheduling an
event within itself $100\mu s$ into the future. The delay annotated to
connections is optional. If no delay is specified, the event travels along a
connection logically instantaneously.

The built-in trigger startup, rendered as a white circle, is present at the
beginning of the execution, and the built-in trigger shutdown, rendered as a
white diamond, is present at the last tag of the execution. Besides triggers,
connections can be drawn between two ports using connection statements.

All events in the system are handled in the order of tags, which use a super-
dense representation of time [11], encoded as tuples of the form $g=(t,m)$,
where $t\in\mathbb{T}$ is the time value and $m\in\mathbb{N}$ is a microstep
index. Reactions are logically instantaneous; logical time does not elapse
during the execution of a reaction (physical time, denoted as $T$, on the
other hand, does elapse). If a reaction produces an output that triggers
another reaction, then the two reactions execute logically simultaneously
(i.e., at the same tag).

##  III Background

###  III-A Reactor Model and Lingua Franca

The reactor model [6] is a deterministic model of concurrent computation for
reactive systems. It is an adaptation of the actor model [12] in which
messages flow through ports, and delivery is not address-based but connection-
based, like in dataflow [13, 14] and Kahn process networks [15]. Messages are
tagged with a timestamp and delivered in order, assigning a discrete-event
semantics to the operation of reactors. Unlike LET [16], in which logical
execution time is synonymous with physical time, reactions to events are
logically instantaneous, following the synchronous hypothesis that is central
to the synchronous languages [17]. Still, a LET can be assigned to a reaction,
simply by adding a logical delay to its output. The execution semantics of
reactors ensure that at any tag, no reaction executes before all events that
it depends on are known. This invariant is independent of the physical time
that elapses during the execution of a reactor program, and it ensures that
reactors behave deterministically. The proximity between the tag at which an
event is scheduled and the physical time at which it is reacted to, _does_
depend on execution times, and requires further analysis in order to provide
any assurances in that regard.

LF is a polyglot coordination language that allows for the definition and
composition of reactors. Event-triggered reactions, which constitute the
functionality of reactors, have an interface specified in LF syntax, but an
implementation specified in plain target code. Currently, LF supports C, C++,
Python, Rust, and TypeScript. LF code gets compiled down to target code that
is executable using a runtime environment that coordinates the scheduling of
events and reactions to events. For most targets, the runtime transparently
exploits available parallelism and utilizes multiple cores. LF has support for
multiple platforms, including POSIX, Arduino, Zephyr, and several bare-iron
microcontrollers. LF programs can also be federated, meaning that the reactor
semantics get preserved in a distributed system, across separate processes
that communicate over a network. Such federated execution is outside the scope
of this paper.

###  III-B Directed Acyclic Graphs (DAGs)

DAGs are widely used in real-time applications, such as automotive and
avionics, to model real-time computing tasks and their precedence constraints.
This subsection introduces basic concepts and notations for real-time DAG task
modeling.

####  III-B1 Task Model

A DAG task is characterized by $(\mathcal{G},P)$, in which $\mathcal{G}$ is a
graph defining the set of sub-tasks and $P$ denotes the DAG task period. The
graph $\mathcal{G}$ comprises of $(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{v_{i}\\}$ is a set of $n$ nodes representing $n$ sub-tasks,
and $\mathcal{E}=\\{e_{ij}\\}$ is a set of directed edges representing the
precedence relation between the sub-tasks. For any two nodes $v_{i}$ and
$v_{j}$ connected by a directed edge $e_{ij}$, $v_{j}$ can start execution
only if $v_{i}$ has finished its execution. Given the edge $e_{ij}$, $v_{i}$
is the predecessor of $v_{j}$. Each sub-task $v_{i}$ is a non-preemptable
sequential computing workload, with its worst-case execution time (WCET)
denoted as $C_{i}$.

####  III-B2 Node-level Timing Attributes

The timing constraints of each node can be defined through four attributes:
earliest starting time (EST), earliest finishing time (EFT), latest starting
time (LST), and latest finishing time (LFT). The EST is the earliest time a
node can start executing, equalling the maximum of its predecessors’ EFTs.
Similarly, the LFT defines the latest time a node is allowed to finish its
execution to meet the deadline, which is equal to the minimum of its
successors’ LST. The relationship between the timing attributes is

$\displaystyle t^{\text{EST}}_{i}$
$\displaystyle=\max\\{t^{\text{EFT}}_{j}~{}|~{}e_{ji}\in\mathcal{E}\\}$ (1)
$\displaystyle t^{\text{LFT}}_{i}$
$\displaystyle=\min\\{t^{\text{LST}}_{j}~{}|~{}e_{ij}\in\mathcal{E}\\}$

and $t^{\text{EFT}}_{i}=t^{\text{EST}}_{i}+C_{i}$ and
$t^{\text{LST}}_{i}=t^{\text{LFT}}_{i}-C_{i}$. The $t^{\text{LFT}}$ of all
nodes without a successor is set to the DAG task period $P$.

###  III-C DAG Modeling for LF Programs

When constructing the DAG task for DAG scheduling it is necessary that all
externally defined constraints are represented through the DAG topology and
the scalar node values. A real-time LF program releases a task $v_{i}$ (i.e.,
a reaction invocation) at a time offset $O_{i}$ and expects it to complete by
a deadline $D_{i}$, where $D_{i}$ could be the release time of the reaction’s
next invocation or the end of the hyperperiod. The DAG needs to be adapted to
reflect these constraints, which are translated to constraints on node-level
timing attributes as

$O_{i}\leq t^{\text{EST}}_{i}\quad\text{and}\quad t^{\text{LFT}}_{i}\leq
D_{i},$ (2)

i.e., the earliest starting time needs to be larger than the offset and the
last finishing time needs to be less than the deadline. To constrain the
timing attributes accordingly, we borrow the concept of virtual nodes from
[18]. There are two types of virtual nodes, dummy nodes $d_{l}$ that have a
predefined execution time and sync nodes $s_{l}$ with zero execution time.
Using the virtual nodes, a virtual path can be constructed, alternating $S$
sync and $S-1$ dummy nodes. The total execution time of the virtual path is
equal to the period of the DAG task. Through the defined execution time of the
dummy nodes, it follows that for each sync node $s_{l}$,

$t^{\text{EST}}_{s_{l}}=t^{\text{EFT}}_{s_{l}}=t^{\text{LST}}_{s_{l}}=t^{\text{LFT}}_{s_{l}}=\sum_{i=1}^{l-1}C_{d_{i}}=P-\sum_{j=l}^{S-1}C_{d_{j}}.$
(3)

The nodes in the virtual path can be designed such that all unique offset and
deadline values are represented by a sync node. Adding an edge from the
appropriate sync node $s_{l}$ to a sub-task $v_{k}$, or vice-versa,
respectively, results in the relation

$O_{k}=t^{\text{EFT}}_{s_{l}}\leq t^{\text{EST}}_{k}\quad\text{or}\quad
t^{\text{LFT}}_{k}\leq t^{\text{LST}}_{s_{l}}=D_{k},$ (4)

which enforces (2) within the DAG task. As a concrete example, Figure 4 shows
the DAG encoding of the running example.

Lingua Franca CompilerLFParserASTBuilderCGeneratorDAGGeneratorState
SpaceExplorerBytecodeGeneratorLoadBalancedEdgeGenerationQuasi-
StaticSchedulersSelectSchedulerLF
w/WCETsInst.CodePretVMRuntimePretVMBytecodeCompiled by GCC into
executableDAGsEGLBSSDs w/GuardedTransitionsStaticSchedules Figure 2:
Methodology overview. Colored boxes are our work. Brown boxes denote external
tools we build interface for. Blue and brown boxes are described in Sec. IV.
Green boxes are described in Sec. V.

##  IV From LF to Quasi-Static Schedules

Let us now dive into our methodology, as shown in Figure 2. At a high level,
our methodology consists of two parts: first, compiling an LF program into
quasi-static schedules (Sec. IV), and second, generating and executing
bytecode on PretVM implementations (Sec. V). In this section, we focus on the
first part, which covers the blue and brown boxes in Figure 2.

###  IV-A State Space Diagrams with Guarded Transitions

The input of our approach is an LF program with WCET annotations. Each
reaction is labeled by the user with a WCET annotation, indicating the maximum
amount of time this reaction is expected to require to complete execution on a
certain execution platform along with the associated overhead. We explain
further in Sec. VI how a user could derive the WCETs. Given an annotated LF
program, the LF compiler parses the program and builds an abstract syntax tree
(AST). Once an AST is built, the compiler invokes a built-in C Generator for
generating program-specific instrumentation code, including custom C structs
for reactor definitions in the specific program, user-specified reaction
bodies written in C, memory allocation and deallocation functions, etc.

From the AST, the State Space Explorer generates State Space Diagrams (SSDs)
[19], which capture the logical behavior of an LF program. Lin et al. [19]
identified a subset of LF programs whose logical behavior can be represented
using a single SSD. In this work, we expand this subset of LF programs by
combining multiple SSDs with guarded transition relations between each pair of
SSDs.

An SSD is a directed graph $(V,E)$, where each node consists of a timestamp, a
set of reactions invoked at this timestamp, and a set of future events known
at this timestamp. Formally,
$V=(t,r,e)\subseteq\textit{tags}\times\mathcal{P}(\textit{rxns})\times\mathcal{P}(\textit{events})$
and $E\subseteq V\times V$, where $\mathcal{P}$ denotes a power set, tags
denotes the set of timestamps, rxns denotes the set of reactions in an LF
program, and events denotes the set of events. To construct an SSD, the State
Space Explorer performs a light-weight simulation by unrolling a worst-case
execution until either

  1. 1.

there are no more pending events, i.e., $e=\varnothing$,

  2. 2.

or the simulation completes a user-specified time horizon $h$, i.e., $t=h$,

  3. 3.

or a hyperperiod (i.e., a cycle) is found.

The simulation approach is similar to [20].

Figure 3: Three separate SSDs connected by guarded transitions from the
running example. Pending events are not rendered here to save space.

In this work, we combine multiple SSDs to represent more dynamic behaviors of
LF programs. Figure 3 shows the SSDs for the running example in Sec. II. The
logical behavior of the reaction wheel system can be divided into three
phases: an initialization phase, a periodic phase, and a shutdown phase. Each
phase can be represented by an individual SSD, respectively. The
initialization phase consists of one state space node with timestamp $0$, the
very first timestamp of an execution, and a single reaction invocation,
reaction 1 from the Motor reactor, due to the startup trigger (rendered as a
white circle in Figure 1). Similarly, the shutdown phase of the execution also
consists of a single state space node with the last tag of the execution—a
user-specified timeout—and five possible reaction invocations due to the
shutdown trigger and the last firings of the timers. The periodic phase
contains three state space nodes: the first node starts at $t=5s$, the second
starts $75\mu s$ later, and the third node starts $25\mu s$ after the second.
The reaction invocations occur due to the timer firings and the production of
outputs from the reactions in the AngularRateSensor and Gyroscope.

The three phases of execution are connected using guarded transitions. Here,
we use the arrow notations from [21], where the solid arrows represent regular
guarded transitions, and dashed arrows represent default transitions, which
are taken when none of the guarded transitions are taken. In Figure 3, the
initialization phase has a default transition to the periodic phase, meaning
that when the task set in the initialization phase is done, the execution can
move onto the task set in the periodic phase. As part of the transition, the
current time $t$ is incremented by $5\text{sec}$ due to the five-second timer
offset specified in the program (Figure 1). The periodic phase has two
outgoing transitions. The first is a guarded transition to the shutdown phase,
with a guard $t\succeq\text{LAST TAG}$, where $t$ denotes the current time.
This transition is taken when the current time $t$ reaches LAST TAG, which is
a user-specified timeout value. While LAST TAG is not reached, the execution
does not take this guarded transition, but instead takes the default
transition of the periodic phase and executes the periodic task set for
another hyperperiod.

0$s_{1}$75$d_{1}$0$s_{2}$25$d_{2}$0$s_{3}$50$d_{3}$0$s_{4}$$20$$a_{1,1}$$80$$g_{1}$$15$$c_{1,1}$$15$$c_{2}$$20$$a_{1,2}$$15$$c_{1,2}$$15$$m_{2}$$25$$c_{3}$
(a) DAG representation after conversion from the state space diagram in Figure
3, showing timing edges in blue, trigger edges in red, and reactor
sequentialization edges in green, with the virtual path above the dashed line.

0$s_{1}$75$d_{1}$0$s_{2}$25$d_{2}$0$s_{3}$50$d_{3}$0$s_{4}$$20$$a_{1,1}$$80$$g_{1}$$15$$c_{1,1}$$15$$c_{2}$$20$$a_{1,2}$$15$$c_{1,2}$$15$$m_{2}$$25$$c_{3}$
(b) Sample output from the Edge Generation scheduler, which is a transitive
reduction of the DAG in Figure 4(a) with width $M=2+1$, with $+1$ for the
virtual path. The colors of the nodes show a valid partitioning to 2 available
cores.

Figure 4: DAG generation and partitioned scheduling. The node names are the
initial of the reactor name with the reaction number and optionally the
invocation count as subscript. For example, $a_{1,1}$ is the first invocation
of reaction 1 in AngularRateSensor. The numbers in the nodes indicated the
WCET of each reaction and the nodes above the dashed line are the virtual
path.

###  IV-B Converting SSDs to DAGs

In Figure 2, after the SSDs with guarded transitions are generated by the
State Space Explorer, the SSDs enter the DAG Generator and are converted to
DAGs. The conversion starts by generating nodes corresponding to the reaction
invocations, and then connects these nodes through edges based on timing and
precedence constraints.

When iterating over the state space diagram, for each reaction invocation a
node is generated, taking the current logical time as offset, and adopting the
execution time of the reaction. In this work, we assume implicit deadlines for
all nodes, meaning their deadline is equal to their period. As such, every
node has a deadline according to the logical tag of its next invocation. The
period of the DAG task is extracted from the length of the loop in the state
space diagram. After generating all nodes, the virtual nodes are generated
according to the unique offset and deadline values.

The edges added are the following:

  1. 1.

Edges connecting the virtual nodes to form the virtual path;

  2. 2.

Timing edges from and to the virtual path for offset and deadline values of
the nodes, respectively;

  3. 3.

Dependency edges between nodes corresponding to reactions where the second is
triggered by the first;

  4. 4.

Sequentialization edges between nodes belonging to the same reactor, ordering
them by logical time, with the reaction number as tiebreaker.

Figure 4(a) shows the DAG generated from the periodic phase of Figure 3.

As an example for all the added edges, we focus on the node $c_{2}$, which is
the second reaction of the controller reactor. It received the attributes
$O_{c_{2}}=0$, $D_{c_{2}}=150$, and $C_{c_{2}}=15$ from the LF program. The
blue edges from $s_{1}$ and to $s_{4}$ set the bounds for the timing
attributes. The red edge from $g_{1}$ is added because the first reaction of
the gyroscope triggers this reaction. The green edge from $c_{1,1}$ is added
because the first instance of the first reaction of the controller reactor has
the same logical tag but lower number. The outgoing green edge to $c_{1,2}$ is
set because it has a higher logical tag. Lastly, the red outgoing edge to
$c_{3}$ is added because $c_{3}$ is triggered by $c_{2}$ through the logical
action. An example for the need of the virtual path can be seen when
inspecting the node $c_{3}$. Due to the logical action with a minimum delay of
100 the offset of the reaction should be $O_{c_{3}}=100$, necessitating the
constraint $t^{\text{EST}}_{c_{3}}\geq 100$. By adding the edge from the sync
node $s_{3}$, $c_{3}$ cannot start before 100 due to the total time required
by $d_{1}$ and $d_{2}$.

###  IV-C Scheduling by Graph Partitioning

After the conversion to DAGs, the LF compiler selects a user-specified quasi-
static scheduler and feed the generated DAGs to it. At a high level, a quasi-
static scheduler takes a set of graphs as input, partitions the graphs based
on the number of workers available, and outputs graph partitions, which are
considered as quasi-static schedules–a spatial mapping between tasks and
execution platforms with timing and inter-task dependencies. The schedules are
quasi-static because they statically encode tasks that _could_ be triggered,
but whether they are actually triggered is determined during execution using
virtual instructions facilitating control flow. More details on these
instructions are explained in Sec. V.

Given an unparititioned DAG, a quasi-static scheduler is free to designate DAG
nodes to any partition it deems fit. The scheduler can modify edges as long as
the output partitioned DAG satisfies all dependencies in the input
unpartitioned DAG. In addition, the quasi-static scheduler must linearize each
parition by adding edges such that there exists a path in the output DAG
passing through all nodes within the same partition.

In this work, we support two different types of schedulers: Load Balanced and
Edge Generation [9]. The Load Balanced scheduler is a complete scheduler
implemented in Java, embedded inside the LF compiler. It directly takes the
generated DAGs as input and produces graph partitions that aim to assign each
worker the same amount of work measured in execution times.

The Edge Generation scheduler, on the other hand, is an external static
scheduler implemented in Python by Sun et al. [9]. Instead of distributing
workloads fairly across workers, EGS focuses on satisfying timing constraints.
Given a DAG task with a deadline, EGS checks whether the DAG task is trivially
schedulable on the given number of processors. A DAG task $(\mathcal{G},P)$ is
trivially schedulable on $M$ processors if its length is less than or equal to
the period $P$ and its width is less than or equal to the number of processors
$M$. If it is not trivially schedulable by construction, EGS adds edges trying
to make it trivially schedulable. A trivially schedulable DAG can easily be
partitioned using paths that cover the DAG, with an example shown in Figure
4(b).

##  V From Quasi-Static Schedules to PretVM

Once quasi-static schedules are generated in the form of graph partitions,
they will then be compiled into bytecode and executed by the PretVM runtime.
This section walks through the green boxes in Figure 2 in detail. The main
challenges we address here include composing virtual instructions to deliver
correct LF semantics (i.e., deterministic concurrency) and accounting for LF’s
generality over LET (i.e., encoding the logical timeline and detecting whether
a reaction should be invoked during execution), while maintaining low
overhead.

###  V-A Virtual Instruction Set

We begin by defining a virtual instruction set for PretVM, which is used to
encode the quasi-static schedules. The full instruction set is shown in Table
I.

TABLE I: PretVM Virtual Instruction Set Instruction |  Description
---|---
ADD op1, op2, op3 |  Add to an integer variable (op2) by an integer variable (op3) and store to a destination register (op1).
ADDI op1, op2, op3 |  Add to an integer variable (op2) by an immediate (op3) and store to a destination register (op1).
ADV op1, op2, op3 |  Advance the logical time of a reactor (op1) to a base time register (op2) + a time increment variable (op3).
ADVI op1, op2, op3 |  Advance the logical time of a reactor (op1) to a base time register (op2) + an immediate value (op3).
BEQ op1, op2, op3 |  Take the branch (op3) if the op1 register value is equal to the op2 register value.
BGE op1, op2, op3 |  Take the branch (op3) if the op1 register value is greater than or equal to the op2 register value.
BLT op1, op2, op3 |  Take the branch (op3) if the op1 register value is less than the op2 register value.
BNE op1, op2, op3 |  Take the branch (op3) if the op1 register value is not equal to the op2 register value.
DU op1, op2 |  Delay until the physical clock reaches a base timepoint (op1) plus an offset (op2).
EXE op1, op2 |  Execute a function (op1) with argument (op2).
JAL op1 op2 |  Store the return address to op1 and jump to a label (op2).
JALR op1, op2, op3 |  Store the return address to op1 and jump to a base address (op2) + an immediate offset (op3).
STP |  Stop the execution.
WLT op1, op2 |  Wait until a register value (op1) to be less than a desired value (op2).
WU op1, op2 |  Wait until a register value (op1) to be greater than or equal to a desired value (op2).

The PretVM is a register-based virtual machine. The virtual instruction set
borrows inspiration from the RISC-V instruction set [22] and the timing
instructions from the PRET Machines [23, 24, 25]. The virtual instruction set
contains standard RISC-V-like instructions such as ADD, ADDI, BEQ, BGE, BLT,
BNE, JAL, and JALR. These instructions are useful for encoding control flow
and manipulating auxiliary registers (further explained in Sec. V-B) that
keeps track of the progress of a quasi-static schedule.

Besides the standard instructions, the virtual instruction set also contains
timing instructions, including DU, WU, and WLT. The use of timing instructions
adopts the PRET philosophy of making timing a _semantic_ property of the
instruction set. The DU instruction helps align an execution with real time,
and the WU and WLT instructions are useful for implementing synchronization
among workers.

Lastly, we introduce reactor-inspired instructions: ADV, ADVI, EXE, and STP.
The ADV and ADVI instructions advance the timestamp of a reactor’s state. EXE
executes a C function pointer, which could be a user-written reaction body or
any functions required by the runtime to deliver the LF semantics. STP
terminates the LF program execution.

###  V-B Generating Bytecode from Quasi-Static Schedules

With a virtual instruction set defined, we are almost ready to encode the
quasi-static schedules, i.e., partitioned graphs, into bytecode, which
consists of sequences of virtual instructions, one for each worker thread.
Before we dive into the main instruction generation algorithm, let us walk
through a few prerequisites for encoding the quasi-static schedules using the
virtual instruction set.

##### Auxiliary Registers

Encoding the semantics of quasi-static schedules requires storing certain
information at runtime in registers. Certain types of registers are worker-
specific, meaning that they duplicated for each worker, while others are
global, meaning that they are unique and read by all workers. The progress of
a worker during the execution of its schedule is tracked using a worker-
specific counter register. A global start_time register keeps track of the
timestamp at which the execution starts, while a global timeout register
stores the last timestamp (i.e., the timestamp in the shutdown phase in Figure
3) of the execution, as specified by the user. We use a global time_offset
register to keep track of the timestamp at the beginning of the current
hyperperiod. To increment time_offset by a variable amount, as the execution
goes through different phases, a global offset_inc register is used to store
these variable increments at different points during the execution. To store
the return address of a worker before a jump, we use a worker-specific
return_addr register. Moreover, for the purpose of global synchronization at
the boundary of a hyperperiod (explained later), each a worker uses a
binary_sema register as a binary semaphore. Lastly, there is a global constant
zero register, which always holds a value of 0.

##### Synchronization

In our execution strategy, we support two types of synchronization: (i) local
synchronization between a pair of workers, and (ii) global synchronization
across all workers. Local synchronization is achieved using the WU and the
counter registers. Without loss of generality, assume that worker $B$ needs to
wait until worker $A$ completes some upstream task. To implement this, in
worker $A$’s bytecode, we use an ADDI to increment worker $A$’s counter after
it completes the upstream task, and in worker $B$’s bytecode, we use a WU to
let it block until worker $A$’s counter reaches the incremented value. On the
other hand, global synchronization across all workers is achieved by inserting
a synchronization code block into each worker’s bytecode. One worker is
designated as the coordinator, denoted as $c$, facilitating the global
synchronization, while the other workers are participants. Each participant is
denoted as $p$. The coordinator executes the following code block:

  1. 1.

WU $\texttt{binary\\_sema}_{p},1$

  2. 2.

(… Repeat WU for each participant $p$ …)

  3. 3.

ADD $\texttt{time\\_offset},\texttt{time\\_offset},\texttt{offset\\_inc}$

  4. 4.

ADDI $\texttt{counter}_{c},\texttt{zero},0$

  5. 5.

ADDI $\texttt{counter}_{p},\texttt{zero},0$

  6. 6.

(… Repeat ADDI for each participant $p$ …)

  7. 7.

ADVI $\textit{reactor},\texttt{time\\_offset},0$

  8. 8.

(… Repeat ADVI for each reactor in the LF program …)

  9. 9.

ADDI $\texttt{binary\\_sema}_{p},\texttt{zero},0$

  10. 10.

(… Repeat ADDI for each participant $p$ …)

  11. 11.

JALR $\texttt{zero},\texttt{return\\_addr}_{c},0$

Conversely, each participant executes this shorter code block:

  1. 1.

ADDI $\texttt{binary\\_sema}_{p},\texttt{zero},1$

  2. 2.

WLT $\texttt{binary\\_sema}_{p},1$

  3. 3.

JALR $\texttt{zero},\texttt{return\\_addr}_{p},0$

During global synchronization, the coordinator first waits until all
participants have entered their own sync. blocks (line 1-2). A participant
enters the sync block and notifies the coordinator by setting its binary_sema
to 1 (line 1 in the participant code below). Once they have entered and get
blocked by the WLT (line 2 below), the coordinator then updates the global
hyperperiod offset (line 3 above), resets all workers’ counter registers (line
4-6), and advances the timestamp of all reactors’ states (line 7-8). Once
these “bookkeeping” procedures are done, the coordinator resets the
binary_sema registers to 0 (line 9-10 above), at which point the participants
are unblocked by WLT and jump back to the return addresses specified in their
return_addr registers (line 3 below).

##### Connections

LF allows the user to specify connections with optional fixed logical delays.
When the delays are greater than the rate at which output ports are written, a
storage layer is required to store the in-flight events. In this work, we
implement a connection buffer for each delayed connection using a fixed-size
circular buffer. Since the LF semantics guarantees that events sent along a
connection have monotonically increasing timestamps, there is no need to
reorder events and hence circular buffers suffice.

For each connection, we code-generate two connection helper functions: a pre-
connection helper function pushes an event into the circular buffer, and a
post-connection helper function pops an event from the circular buffer. The
quasi-static schedule executes connection helper functions using the EXE
instruction. Since the LF semantics allows an output port to be written to by
multiple reactions triggered at the same timestamp, with the last reaction
taking precedence, a pre-connection helper is inserted after invoking the last
reaction that could modify this port to push the latest written value into the
connection buffer. If a reaction is triggered by a port, a post-connection
helper is inserted to pop the stale value read by the reaction from the
connection buffer.

If a connection has no delay, we optimize the connection helper functions away
and let the downstream receiving reaction read value directly from the pointer
to the sending reactor’s output port.

##### Trigger Detection

The LF semantics requires a reaction to be invoked when any of its triggers
becomes present. Since it is unknown at compile time whether an input-
triggered reaction does get triggered during execution, the quasi-static
schedule must encode logic for checking the presence of triggers at runtime.
We implement the trigger detection mechanism using a combination of BEQ, JAL,
and EXE. For every trigger a reaction has that is an input port, a BEQ is
generated. If the input port is connected to a delayed connection, the BEQ
checks if the head event of the connection buffer has the same timestamp as
the current timestamp of the reaction’s parent reactor. Otherwise if the input
port is connected to a zero-delay connection, the BEQ checks if the sending
output port’s is_present field is true. In both cases, when the condition
evaluates to true, the BEQ branches to the location of an EXE instruction
invoking the reaction body. After a list of BEQ is generated, a JAL
instruction is generated, which branches to the instruction after the
reaction-invoking EXE, when all triggers are absent, in which case the
reaction-invoking EXE is bypassed. A concrete example of this mechanism is
shown in Figure 5 (line 4-6).

##### Instruction Generation

Having discussed the above prerequisites for generating bytecode that encodes
quasi-static schedules, we are now ready to dive into Algorithm 1, which shows
the procedure for generating virtual instructions from a partitioned graph.

Algorithm 1 Generate Instructions from a Partitioned Graph

1:procedure generateInstructions(graphParitioned)

2: Let $B_{i}$ be the set of instructions for worker $i$

3: Let $W$ be the total number of workers

4: Topologically sort the DAG nodes by dependencies

5: for all $\text{currentNode}\in\text{topologicalSort}$ do

6: $w\leftarrow\text{currentNode.assignedWorker}$

7: if $\text{currentNode.type}=\textit{reaction}$ then

8: for all upstream reactions of currentNode do

9: $B_{w}\leftarrow B_{w}\cup\\{\texttt{WU}\\}$ $\triangleright$ Wait for
upstream

10: end for

11: if currentNode depends on sync node then

12: GeneratePreConnectionHelpers()

13: $B_{w}\leftarrow B_{w}\cup\\{\texttt{ADVI},\texttt{DU}\\}$

14: end if

15: for all input port triggers of currentNode do

16: $B_{w}\leftarrow B_{w}\cup\\{\texttt{BEQ}\\}$ $\triangleright$ Test
trigger presence

17: end for

18: $B_{w}\leftarrow B_{w}\cup\\{\texttt{JAL}\\}$ $\triangleright$ Absent
triggers, skip EXE

19: $B_{w}\leftarrow B_{w}\cup\\{\texttt{EXE}\\}$ $\triangleright$ Execute
reaction

20: GeneratePostConnectionHelpers()

21: $B_{w}\leftarrow B_{w}\cup\\{\texttt{ADDI}\\}$ $\triangleright$ Update
counter

22: else if $\text{currentNode.type}=\text{{sync}}$ and currentNode is tail
node of DAG then

23: GeneratePreConnectionHelpers()

24: if currentNode.time is not $\infty$ then

25: for $i=0$ to number of workers - 1 do

26: $B_{i}\leftarrow B_{i}\cup\\{\texttt{DU}\\}$ $\triangleright$ End of
hyperperiod

27: if $i=0$ then

28: $B_{i}\leftarrow B_{i}\cup\\{\texttt{ADDI}\\}$ $\triangleright$ Iterate
again

29: end if

30: $B_{i}\leftarrow B_{i}\cup\\{\texttt{JAL}\\}$ $\triangleright$ Synchronize

31: end for

32: end if

33: end if

34: end for

35: return $\bigcup_{i=0}^{W-1}B_{i}$

36:end procedure

The algorithm first topologically sorts the nodes of the partitioned graph and
traverses the graph in the sorted order, ensuring that before visiting a node,
all of its dependencies have been already visited. If the current node is a
reaction node, then a WU is generated for each of its upstream tasks.
Moreover, if the reaction node depends on a sync node, pre-connection helper
functions are first generated for earlier reactions that write to output
ports; then, ADVI and DU instructions are generated to advance the timestamps
of the parent reactor and delay the execution until the physical release time
of the reaction node. Then, instructions for trigger detection are generated,
which start with a sequence of BEQ instructions and a JAL instruction. This is
then followed by an EXE instruction for executing the reaction body. Once the
reaction is executed, a sequence of EXE instructions execute the post-
connection helper functions. An ADDI instruction is then used to increment a
worker counter, effectively updating the current progress of the worker. If
the current node is an sync node and is the tail node of the partitioned
graph, then pre-connection helper functions are generated for all the
remaining reactions invoked in the current hyperperiod, which can write to
output ports. A DU is also added to each worker’s bytecode. Each worker
further uses an ADDI to increment the hyperperiod register. Once that is done,
each worker executes a JAL to the synchronization block.

##### Linking

Once a sequence of instructions is generated for each partitioned graph for
each worker, the Bytecode Generator links multiple sequences together into a
single piece of output bytecode. The linking process proceeds by phases. It
starts with the first phase the execution enters into, such as the
initialization phase, and places the generated instructions from this phase
into the output bytecode. Then, the process follows the guarded transitions
and places the generated instructions from downstream phases one-by-one, until
there are no more unlinked phases with incoming transitions. At the end of the
instructions generated by each phase, the Bytecode Generator places
instructions generated from guarded transitions using JAL and branch
instructions. In the running example (Figure 3), the default transition
between the initialization phase and the periodic phase is encoded as a JAL
instructions between two code blocks corresponding to the two phases,
similarly for the default self transition in the periodic phase. The guarded
transition with the guard $t\succeq\text{LAST TAG}$ is encoded as
$\texttt{BGE}\;t,\text{LAST TAG},\text{SHUTDOWN}$.

Finally, as a concrete example, the generated bytecode for the worker assigned
to the blue partition in Figure 4(b) is shown in Figure 5.

  1. 1.

EXE $g_{1}$ (This line is labeled $\text{PERIODIC}_{\text{blue}}$.)

  2. 2.

ADDI $\texttt{counter}_{\text{blue}}$, $\texttt{counter}_{\text{blue}}$, $1$

  3. 3.

WU $\texttt{counter}_{\text{green}}$, $2$

  4. 4.

BEQ in1_is_present, true, line_6

  5. 5.

JAL line_9

  6. 6.

EXE $c_{2}$

  7. 7.

EXE out0_pre_connection_helper

  8. 8.

EXE in1_post_connection_helper

  9. 9.

ADDI $\texttt{counter}_{\text{blue}},\texttt{counter}_{\text{blue}},1$

  10. 10.

DU $\texttt{time\\_offset},150\mu s$

  11. 11.

ADDI $\texttt{offset\\_inc},150\mu s$

  12. 12.

JAL $\texttt{return\\_addr}_{\text{blue}},\text{SYNC\\_BLOCK}$

  13. 13.

BGE $\texttt{time\\_offset},\texttt{timeout},\text{SHUTDOWN}_{\text{blue}}$

  14. 14.

JAL $\texttt{return\\_addr}_{\text{blue}},\text{PERIODIC}_{\text{blue}}$

Figure 5: Generated bytecode for the blue worker in Figure 4(b)

###  V-C Executing Bytecode on PretVM

At this point in the workflow (Figure 2), we have finished generating the
PretVM bytecode. To execute the bytecode, we implement a PretVM Runtime, which
implements the virtual instruction set and interprets the bytecode during
execution. To make the PretVM Runtime compatible with the LF instrumentation
code, we embed the runtime under the scheduler API of the LF runtime library.
The PretVM runtime, the instrumentation code, and the PretVM bytecode is
further compiled by a C compiler, such as GCC, into an executable.

##  VI Predictable Timing

Predictability is a central concern in real-time system design. In the
literature, however, predictability is often subject to different
interpretations. We argue that whether a system is predictable depends on the
prediction one aims to make. Prior works have focused on finding the worst-
case execution times (WCETs) of individual tasks on various platforms.
However, finding a WCET at the system level, where tasks coordinate and
execute concurrently on multicore platforms, remains an open problem.

An LF runtime based on PretVM cleanly separates application logic (i.e.,
reaction bodies) from coordination logic (i.e., quasi-static schedules),
presenting a practical way of writing real-time software that is amenable to
timing analysis. On the one hand, LF reactions are run-to-completion at the
time of writing, removing the need to account for preemption and thus
simplifying timing analysis. On the other hand, PretVM instructions’
straightforward semantics simplifies the WCET analysis of each instruction.

Here we make a key assumption that the user can derive WCET values for each
reaction body and every PretVM instruction on a given platform, e.g., using
timing analysis tools or direct measurements. We treat these WCET values as
estimates—they do not need to be ground truth, but violations of them are
considered fault conditions handled at runtime. Assuming that the individual
WCET estimates are not violated during execution, we can now predict the WCET
of an LF program’s hyperperiod, represented as a DAG and implemented in PretVM
bytecode.

We denote a time domain as $\mathbb{T}$. In practice, this domain is defined
as $\mathbb{T}=\mathbb{Z}$, where the unit is nanosecond. Based on the
previous assumption, the user can obtain WCETs for individual reaction bodies
and PretVM instructions, i.e., there exists a function
$w_{r}:\mathcal{R}\rightarrow\mathbb{T}$ and a function
$w_{i}:\mathcal{I}\rightarrow\mathbb{T}$, where $\mathcal{R}$ denotes the set
of reactions and the $\mathcal{I}$ denotes the set of PretVM instructions. For
the WCETs of DU, WU, and WLT, their wait time does not count toward the WCETs,
only the overhead of calling these instructions does. Similarly for EXE, the
WCET of the function its first operand points to does not count toward the
WCET of the EXE instruction itself.

######  Definition VI.1 (WCET of a node).

The WCET of a node $n$ is a function $w:\mathcal{V}\rightarrow\mathbb{T}$
defined as

$w(n)=\begin{cases}0&\text{if }$n$\text{ is {sync}},\\\ d&\text{if $n$ is
{dummy} with interval $d$},\\\ {\sum}_{i\in I(n)}w_{i}(i)+w_{r}(r)&\text{if
$n$ is for reaction $r$}.\end{cases}$

where $I:\mathcal{V}\rightarrow\mathcal{P}(\mathcal{I})$ returns the set of
PretVM instructions generated by a given node $n$.

Referring back to the running example, node $g_{1}$ in Figure 4(b) generates
line 1-2 in Figure 5, so when the user provides a WCET annotation for the
reaction in Gyroscope, the annotated WCET estimate should account for EXE,
ADDI, and the reaction body in Gyroscope.

######  Lemma VI.1 (WCET up to node $n$).

The WCET up to a node $n$, denoted recursively as $\bar{w}(n)$, is defined as

$\bar{w}(n)=\begin{cases}w(n)&\text{if }U(n)=\varnothing,\\\ \max_{u\in
U(n)}\bar{w}(u)+w(n)&\text{otherwise}.\end{cases}$

where $U:\mathcal{V}\rightarrow\mathcal{P}(\mathcal{V})$ maps a DAG node $n$
to a set of its immediately upstream DAG nodes, and if $n$ is the tail node,
$U(n)$ excludes virtual nodes from the returned set.

###### Proof.

We prove this theorem by induction. In the base case, the DAG has a single
sync node $n$, which is also the tail node, and so its WCET, which is by
construction 0, equals $w(n)=\bar{w}(n)$ since the tail node has no upstream.
The base case therefore holds. In the inductive step, the DAG has more than
one nodes and the tail node necessarily has upstream nodes, i.e.,
$U(n)\neq\varnothing$. By the induction hypothesis, for each upstream node
$u\in U(n)$, $\bar{w}(u)$ is the WCET up to node $u$. Since all upstream nodes
point to the tail, a maximum of $\bar{w}(u)$ needs to be taken over all $u\in
U(n)$. Given that the tail node $n$ has a WCET of 0, the WCET up to the tail
node equals $\max_{u\in U(n)}\bar{w}(u)+0=\max_{u\in
U(n)}\bar{w}(u)+w(n)=\bar{w}(n).$ Therefore, the induction step holds. ∎

######  Theorem VI.2 (WCET of a DAG task set).

The WCET of a DAG with the tail node $n_{t}$ is $\bar{w}(n_{t})$.

###### Proof.

The proof follows from Lemma VI.1. ∎

######  Example 1.

The WCET of the DAG in Figure 4(b) can be captured by $\bar{w}(s_{4})$, where

$\displaystyle\bar{w}(s_{4})$
$\displaystyle=\max(\bar{w}(a_{1,2}),\bar{w}(m_{2}))+w(s4)$
$\displaystyle=\max(\bar{w}(s_{2})+20,\bar{w}(c_{3})+15)+0$
$\displaystyle=\max(\max(75,\bar{w}(c_{1,1}))+20,$ $\displaystyle\ \ \
\max(\bar{w}(s_{3}),\bar{w}(c_{1,2}))+40)$ $\displaystyle=...=150$

##  VII Evaluation

|  | Average (us) | Maximum (us) | Standard Deviation (us)
---|---|---|---|---
Program | LoC (LF) | DY | LB | EG | DY | LB | EG | DY | LB | EG
Philosophers | 314 | 18.4 | 12.1 | 11.9 | 355 | 99.2 | 510 | 9.99 | 5.65 | 9.33
LongShort | 31 | 1.49e+06 | 3.11 | 3.17 | 2.91e+06 | 5.22 | 4.32 | 8.11e+05 | 0.781 | 0.571
CoopSchedule | 54 | 18.5 | 10.9 | 12.3 | 50.4 | 32.2 | 69 | 7.64 | 4.69 | 6.4
Counting | 179 | 14.6 | 6.81 | 6.74 | 76.8 | 42.4 | 51.5 | 5.95 | 2.74 | 2.99
ThreadRing | 217 | 19.5 | 14.8 | 12.3 | 44.2 | 58.3 | 36.2 | 7.18 | 8.05 | 6.28
ADASModel | 91 | 12.9 | 5.49 | 1.81e+03 | 41.6 | 19.4 | 1.2e+04 | 5.5 | 3.35 | 3.58e+03
PingPong | 124 | 13.6 | 8.02 | 7.96 | 64.4 | 59.9 | 56.8 | 4.14 | 3.95 | 3.87
Throughput | 166 | 16.2 | 13.6 | 14.1 | 29.1 | 33.4 | 30.5 | 5.18 | 6.87 | 7.04
TABLE II: Average, maximum, and standard deviation of the lags in microseconds
of the dynamic scheduler (DY), the static Load Balanced scheduler (LB), and
the static Edge Generation scheduler (EG).

We evaluate the timing accuracy of PretVM by running a set of real-time LF
benchmarks on Raspberry Pi 4 Model B running Linux. In this experiment,
accuracy is measured in terms of the lag of reaction invocations. For a
reaction invocation $i$, its lag, $l_{i}$, is defined as

$l_{i}=T_{i}-t_{i},$

where $T_{i}$ is the physical time at which the reaction invocation occurs and
$t_{i}$ the logical timestamp. Intuitively, the smaller the difference between
the physical invocation time and the ideal logical invocation time, the more
time-accurate an execution is. We run the same set of benchmarks using two
static schedulers, Load Balanced and Edge Generation, and we compare their
performance against LF’s default Dynamic Scheduler.

The eight benchmarks are selected from [26, 19] with a focus on concurrent
actor design patterns [27], which can be found in modern Cyber-Physical
Systems. For each benchmark program, we annotate each reaction’s WCET estimate
using an @wcet attribute. Syntax elements which are currently not supported by
our implementation include nested reactors, logical and physical actions, and
multiports. A logical action is replaced by adding a connection that links two
newly created output and input ports. The reactor hierarchy is flattened
manually and multiports were expanded by hand.

We collect performance data using LF’s tracing utility, which embeds trace
points throughout the codebase to inspect notable events in the runtime
system. Each event contains an event type, a logical timestamp, and a physical
timestamp. In this experiment, we only collect events for the starting points
of reactions. This choice ensures that the overhead of tracing stays uniform
for all three schedulers under test. To avoid distortions in our measurements,
we have also increased the size of the trace buffer to minimize data being
written to disk during execution.

LF schedulers need to wait for the physical time to surpass the next reaction
invocation’s logical timestamp before processing the invocation. To ensure a
fair comparison between the schedulers, we implement the wait mechanism in all
three schedulers under test using busy wait, replacing the sleep mechanism
found in the default dynamic scheduler. By doing this, we remove timing
variation from operating system’s sleep mechanism and attribute the difference
in performance to scheduler designs.

(a) ADASModel

(b) CoopSchedule

(c) Counting

(d) LongShort

(e) PingPong

(f) ThreadRing

(g) Throughput

(h) Philosophers

Figure 6: Timing accuracy benchmark results. X-axis shows reaction names. Each
reaction contains three distributions, DY, LB, and EG, respectively. Y-axis is
lag in nanoseconds.

Table II shows an overview of the timing accuracy results. Compared to the
dynamic scheduler, the static Load Balanced scheduler has smaller average and
maximum lags on all benchmarks, and it has a smaller standard deviation on all
benchmarks except ThreadRing.

Figure 6 shows strip plots of lags during the periodic phase of each program.
For most reactions, Load Balanced and Edge Generation have smaller lags than
the dynamic scheduler. The occasional outliers shown in the strip plots can be
due to several reasons, including interrupts from the underlying OS and the
flushing of trace buffers to disk.

In ADASModel, Edge Generation shows three clusters of outliers. This is due to
Edge Generation’s scheduling strategy involving adding edges to the DAG, which
tends to delay the releasing of tasks in exchange for schedulability
guarantees. We note that the goal of using Edge Generation is not to minimize
lags, but to use its analysis capability to ensure that a DAG is schedulable.
In this case, larger lags from Edge Generation seem tolerable. In general,
Load Balanced is better at miniming lags than Edge Generation and the dynamic
scheduler.

Notably, for the LongShort benchmark, Load Balanced and Edge Generation
significantly outperform the dynamic scheduler. This performance gain can be
explained by the fact that the quasi-static schedulers keep track of the
current logical time for each reactor, meaning that every reactor can advance
its logical time independently as long as the core LF semantics is respected,
i.e., each reactor processes events in timestamp order. The dynamic scheduler,
on the other hand, uses a single variable to track logical time for all
reactors, ensuring that all reactors advance time together. The LongShort
benchmark has a design pattern that combines infrequent, long-running
reactions with frequent, short-running reactions. The dynamic scheduler
struggles because it performs a global barrier synchronization at the end of
each tag. The barrier makes reactions that are to occur at the next tag wait
on the long-running reactions, even if there are no more actual data
dependencies to fulfill. In the quasi-static schedulers, the capability to
advance time individually for each reactor effectively prevent waiting
unnecessarily, resulting in significantly reduced lags. We plan to compare our
PretVM approach with ongoing research on easing global barrier synchronization
in dynamic schedulers in the future.

##  VIII Related Work

Our work is largely inspired by the Embedded Machine [3], which serves as an
execution backend for the Giotto language [16, 2], implementing the LET model
[28]. An emerging extension of LET is the System-level LET (SL LET) model,
which scales LET to distributed settings by introducing a notion of “time
zones” [29]. The reactors model [6] in Lingua Franca generalizes LET by
distinguishing logical time from physical time [7]. Another emerging model
offering similar generalization is the Sparse Synchronous Model (SSM) [30],
the semantics of which can be facilitated using RP2040’s PIO instruction set
[31], sharing similarity with our approach. The difference here is that it
seems challenging to generate quasi-static schedules for SSM, while we show
that it is feasible for a subset of LF.

In the real-time scheduling literature, various hardware and software
complexities have been considered in real-time systems, leading to a range of
Directed Acyclic Graph (DAG) representations. One of the earliest
contributions to DAG scheduling introduced what is now known as Graham’s
bound. It provides an upper bound on the response time of a task based on the
longest path within the DAG and the DAG’s volume [32]. In recent years, He et
al.[33] proposed a method of prioritizing subtasks within the longest paths to
reduce response times and enhance schedulability. Subsequently, Zhao et
al.[34] improved the priority assignment strategy at the subtask level by
considering subtask dependencies. Different from the above approaches, Sun et.
al [9] proposed a new DAG scheduler named Edge Generation Scheduling (EGS).

##  IX Conclusion

In this paper, we present the Precision-Timed Virtual Machine, PretVM, which
facilitates the execution of quasi-static schedules compiled from a subset of
LF programs, supporting a top-down, model-based design flow for real-time
software in Cyber-Physical Systems. Our approach is amenable to predicting the
WCETs of LF programs’ hyperperiods given assumptions on the WCETs of
individual reactions and virtual instructions. We evaluate our approach using
design patterns found in modern CPSs, implemented in LF. The results show that
PretVM delivers time-accurate deterministic execution.

## Acknowledgment

The work in this paper was supported in part by the National Science
Foundation (NSF), award #CNS-2233769 (Consistency vs. Availability in Cyber-
Physical Systems), by DARPA grant FA8750-20-C-0156, by Intel, and by the
iCyPhy Research Center (Industrial Cyber-Physical Systems), supported by
Denso, Siemens, and Toyota.

This work was also supported, in part, by the German Federal Ministry of
Education and Research (BMBF) as part of the program “Souverän. Digital.
Vernetzt.”, joint project 6G-life (16KISK001K), and by the German Research
Council (DFG) through the InterMCore project (505744711).

Mirco Theile and Binqi Sun were supported by the Chair for Cyber-Physical
Systems in Production Engineering at TUM.

The authors thank Linh Thi Xuan Phan and the anonymous reviewers for providing
helpful feedback. Shaokai Lin thanks Zitao Fang and Yang Huang for their
collaboration on a course project for CS267 (Application of Parallel
Computers) at UC Berkeley, which provided early inspiration for this work.

## References

  * [1] Z. Liu, W. Zhang, and F. Zhao, “Impact, challenges and prospect of software-defined vehicles,” _Automotive Innovation_ , vol. 5, no. 2, pp. 180–194, 2022.
  * [2] T. A. Henzinger, B. Horowitz, and C. M. Kirsch, “Giotto: A time-triggered language for embedded programming,” _Proceedings of IEEE_ , vol. 91, no. 1, pp. 84–99, 2003.
  * [3] T. A. Henzinger and C. M. Kirsch, “The embedded machine: Predictable, portable realtime code,” in _International Conference on Programming Language Design and Implementation (PLDI)_. ACM Press, 2002, Conference Proceedings, pp. 315–326.
  * [4] M. Lohstroh, C. Menard, S. Bateni, and E. A. Lee, “Toward a Lingua Franca for deterministic concurrent systems,” _ACM Transactions on Embedded Computing Systems (TECS), Special Issue on FDL’19_ , vol. 20, no. 4, p. Article 36, May 2021.
  * [5] M. Lohstroh, S. Bateni, C. Menard, A. Schulz-Rosengarten, J. Castrillon, and E. A. Lee, “Deterministic coordination across multiple timelines,” _ACM Transactions on Embedded Computing Systems (TECS)_ , Oct. 2023. [Online]. Available: https://doi.org/10.1145/3615357
  * [6] M. Lohstroh, Í. Í. Romero, A. Goens, P. Derler, J. Castrillon, E. A. Lee, and A. Sangiovanni-Vincentelli, “Reactors: A deterministic model for composable reactive systems,” in _Cyber Physical Systems. Model-Based Design – Proceedings of the 9th Workshop on Design, Modeling and Evaluation of Cyber Physical Systems (CyPhy 2019) and the Workshop on Embedded and Cyber-Physical Systems Education (WESE 2019)_ , R. Chamberlain, M. Edin Grimheden, and W. Taha, Eds. Cham: Springer International Publishing, Feb. 2020, pp. 59–85. [Online]. Available: https://link.springer.com/chapter/10.1007/978-3-030-41131-2_4
  * [7] E. A. Lee and M. Lohstroh, _Generalizing Logical Execution Time_. Switzerland: Springer Nature, 2022, vol. LNCS 13660, pp. 1–22.
  * [8] M. Lohstroh, C. Menard, A. Schulz-Rosengarten, M. Weber, J. Castrillon, and E. A. Lee, “A language for deterministic coordination across multiple timelines,” in _Forum for Specification and Design Languages (FDL)_. IEEE, September 15-17 2020, Conference Proceedings.
  * [9] B. Sun, M. Theile, Z. Qin, D. Bernardini, D. Roy, A. Bastoni, and M. Caccamo, “Edge generation scheduling for dag tasks using deep reinforcement learning,” _IEEE Transactions on Computers_ , vol. 73, no. 4, pp. 1034–1047, 2024.
  * [10] J. Cardoso, C. Chanel, P. Chauvin, A. Hostallier, J. Lamaison, A. Mascarenas-Gonzales, E. Metral, and L. Alloza, “Lab on the real-time control of reaction wheel,” 2022, unpublished lab exercise for the course 1MAE803: Real-time Control of Aerospace Systems, M.Sc in Aerospace Engineering, ISAE-SUPAERO.
  * [11] Z. Manna and A. Pnueli, “Verifying hybrid systems,” in _Hybrid Systems_. Springer, 1993, pp. 4–35.
  * [12] C. Hewitt, P. B. Bishop, and R. Steiger, “A universal modular ACTOR formalism for artificial intelligence,” in _Proceedings of the 3rd International Joint Conference on Artificial Intelligence. Standford, CA, USA, August 20-23, 1973_ , 1973, pp. 235–245.
  * [13] J. B. Dennis, “First version data flow procedure language,” MIT Laboratory for Computer Science, Report MAC TM61, 1974.
  * [14] W. A. Najjar, E. A. Lee, and G. R. Gao, “Advances in the dataflow computational model,” _Parallel Computing_ , vol. 25, no. 13-14, pp. 1907–1929, December 1999.
  * [15] G. Kahn, “The semantics of a simple language for parallel programming,” in _Proc. of the IFIP Congress 74_. North-Holland Publishing Co., 1974, Conference Proceedings, pp. 471–475.
  * [16] T. A. Henzinger, B. Horowitz, and C. M. Kirsch, “Giotto: A time-triggered language for embedded programming,” in _EMSOFT 2001_ , vol. LNCS 2211\. Springer-Verlag, 2001, Conference Proceedings, pp. 166–184.
  * [17] A. Benveniste and G. Berry, “The synchronous approach to reactive and real-time systems,” _Proceedings of the IEEE_ , vol. 79, no. 9, pp. 1270–1282, 1991.
  * [18] M. Verucchi, M. Theile, M. Caccamo, and M. Bertogna, “Latency-aware generation of single-rate DAGs from multi-rate task sets,” in _IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)_ , 2020, pp. 226–238.
  * [19] S. Lin, Y. A. Manerkar, M. Lohstroh, E. Polgreen, S.-J. Yu, C. Jerad, E. A. Lee, and S. A. Seshia, “Towards building verifiable CPS using Lingua Franca,” _ACM Trans. Embed. Comput. Syst._ , vol. 22, no. 5s, sep 2023. [Online]. Available: https://doi.org/10.1145/3609134
  * [20] A. H. Ghamarian, M. C. Geilen, T. Basten, and S. Stuijk, “Throughput analysis of synchronous data flow graphs,” _Proceedings - Design, Automation and Test in Europe, DATE_ , pp. 116–121, 2006.
  * [21] E. A. Lee and S. A. Seshia, _Introduction to Embedded Systems - A Cyber-Physical Systems Approach_ , 2nd ed. Cambridge, MA, USA: MIT Press, 2017. [Online]. Available: http://LeeSeshia.org
  * [22] A. Waterman, Y. Lee, D. Patterson, K. Asanovic, V. I. U. level Isa, A. Waterman, Y. Lee, and D. Patterson, “The risc-v instruction set manual,” _Volume I: User-Level ISA’, version_ , vol. 2, 2014.
  * [23] B. Lickly, I. Liu, S. Kim, H. D. Patel, S. A. Edwards, and E. A. Lee, “Predictable programming on a precision timed architecture,” in _Proceedings of the 2008 International Conference on Compilers, Architectures and Synthesis for Embedded Systems_ , ser. CASES ’08. New York, NY, USA: Association for Computing Machinery, 2008, p. 137–146. [Online]. Available: https://doi.org/10.1145/1450095.1450117
  * [24] M. Zimmer, D. Broman, C. Shaver, and E. A. Lee, “Flexpret: A processor platform for mixed-criticality systems,” in _2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS)_ , 2014, pp. 101–110.
  * [25] E. R. Jellum, S. Lin, P. Donovan, C. Jerad, E. Wang, M. Lohstroh, E. A. Lee, and M. Schoeberl, “Interpret: A time-predictable multicore processor,” in _Proceedings of Cyber-Physical Systems and Internet of Things Week 2023_ , ser. CPS-IoT Week ’23. New York, NY, USA: Association for Computing Machinery, 2023, p. 331–336. [Online]. Available: https://doi.org/10.1145/3576914.3587497
  * [26] C. Menard, M. Lohstroh, S. Bateni, M. Chorlian, A. Deng, P. Donovan, C. Fournier, S. Lin, F. Suchert, T. Tanneberger, H. Kim, J. Castrillon, and E. A. Lee, “High-performance deterministic concurrency using Lingua Franca,” _ACM Trans. Archit. Code Optim._ , vol. 20, no. 4, oct 2023. [Online]. Available: https://doi.org/10.1145/3617687
  * [27] S. M. Imam and V. Sarkar, “Savina - an actor benchmark suite: Enabling empirical evaluation of actor libraries,” in _Proceedings of the 4th International Workshop on Programming Based on Actors Agents & Decentralized Control_, ser. AGERE! ’14. New York, NY, USA: Association for Computing Machinery, 2014, p. 67–80. [Online]. Available: https://doi.org/10.1145/2687357.2687368
  * [28] C. M. Kirsch and A. Sokolova, “The logical execution time paradigm,” _Advances in Real-Time Systems_ , pp. 103–120, 2012.
  * [29] R. Ernst, L. Ahrendts, and K.-B. Gemlau, “System level let: Mastering cause-effect chains in distributed systems,” in _IECON 2018-44th Annual Conference of the IEEE Industrial Electronics Society_. IEEE, 2018, pp. 4084–4089.
  * [30] J. Hui and S. A. Edwards, “The sparse synchronous model on real hardware,” _ACM Transactions on Embedded Computing Systems_ , 2022.
  * [31] J. Hui, K. J. Edwards, and S. A. Edwards, “Timestamp peripherals for precise real-time programming,” in _Proceedings of the 21st ACM-IEEE International Conference on Formal Methods and Models for System Design_ , 2023, pp. 137–147.
  * [32] R. L. Graham, “Bounds on multiprocessing timing anomalies,” _SIAM Journal on Applied Mathematics_ , vol. 17, no. 2, pp. 416–429, 1969.
  * [33] Q. He, N. Guan, Z. Guo _et al._ , “Intra-task priority assignment in real-time scheduling of DAG tasks on multi-cores,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 30, no. 10, pp. 2283–2295, 2019.
  * [34] S. Zhao, X. Dai, I. Bate, A. Burns, and W. Chang, “DAG scheduling and analysis on multiprocessor systems: Exploitation of parallelism and dependency,” in _IEEE Real-Time Systems Symposium (RTSS)_ , 2020, pp. 128–140.