2311.06788

# Real-Time Probabilistic Programming **Authors**: Lars Hummelgren, Matthias Becker, and David Broman > EECS and Digital Futures, KTH Royal Institute of Technology, Sweden {larshum, mabecker, ## Abstract Complex cyber-physical systems interact in real-time and must consider both timing and uncertainty. Developing software for such systems is expensive and difficult, especially when modeling, inference, and real-time behavior must be developed from scratch. Recently, a new kind of language has emerged—called probabilistic programming languages (PPLs)—that simplify modeling and inference by separating the concerns between probabilistic modeling and inference algorithm implementation. However, these languages have primarily been designed for offline problems, not online real-time systems. In this paper, we combine PPLs and real-time programming primitives by introducing the concept of real-time probabilistic programming languages (RTPPL). We develop an RTPPL called ProbTime and demonstrate its usability on an automotive testbed performing indoor positioning and braking. Moreover, we study fundamental properties and design alternatives for runtime behavior, including a new fairness-guided approach that automatically optimizes the accuracy of a ProbTime system under schedulability constraints. ## I Introduction Probabilistic programming [1, 2] is an emerging programming paradigm that enables simple and expressive probabilistic modeling of complex systems. Specifically, the key motivation for probabilistic programming languages (PPLs) is to separate the concerns between the model (the probabilistic program) and the inference algorithm. Such separation enables the system designer to focus on the modeling problem without the need to have deep knowledge of Bayesian inference algorithms, such as Sequential Monte Carlo (SMC) [3, 4] or Markov chain Monte Carlo (MCMC) [5] methods. There are many research PPLs, including Pyro [6], WebPPL [7], Stan [8], Anglican [9], Turing [10], Gen [11], and Miking CorePPL [12]. These PPLs focus on offline inference problems, such as data cleaning [13], phylogenetics [14], computer vision [15], or cognitive science [16], where time and timing properties are not explicitly part of the programming model. Likewise, many languages and environments exist for programming real-time systems [17, 18, 19] with no built-in support for probabilistic modeling and inference. Although some recent work exists on using probabilistic programming for reactive synchronous systems [20, 21] and for continuous time systems [22], no existing work combines probabilistic programming with real-time programming, where both inference and timing constructs are first-class. Combining probabilistic programming with real-time programming results in several significant research challenges. Specifically, we identify two key challenges: (i) how to incorporate language constructs for both timing and probabilistic reasoning in a sound manner, and (ii) how to fairly distribute resources among systems of tasks while considering real-time constraints and inference accuracy requirements. In this paper, we introduce a new kind of language that we call real-time probabilistic programming languages (RTPPLs). In this paradigm, users can focus on the modeling aspect of inferring unknown parameters of the application’s problem space without knowing details of how timing aspects or inference algorithms are implemented. We motivate the ideas behind this new kind of language and outline the main design challenges. To demonstrate the concepts of RTPPL, we develop an RTPPL called ProbTime, which includes probabilistic programming primitives, timing primitives, and primitives for designing modular task-based real-time systems. We create a compiler toolchain for ProbTime and demonstrate how it can be efficiently implemented in an automotive positioning and braking case study. A key aspect of our design is real-time inference using Sequential Monte-Carlo (SMC) and the automatic configuration built on top of this. We have implemented the compiler within the Miking framework [23] as part of the Miking CorePPL effort [12]. ⬇ 2 let x = assume (Beta 2.0 2.0) in \ label {lst: ppl - code: assume} 3 observe true (Bernoulli x); \ label {lst: ppl - code: observe} 4 ...\ label {lst: ppl - code: dots} 5 x \ label {lst: ppl - code: result} (a) Line LABEL:lst:ppl-code:assume defines the latent variable x and gives the prior Beta(2,2). Line LABEL:lst:ppl-code:observe shows an observation statement (observing a true value), and line LABEL:lst:ppl-code:result states that the posterior for x should be computed. <details> <summary>x1.png Details</summary>  ### Visual Description ## Bar Chart: Distribution Plot ### Overview The image is a bar chart depicting a distribution. The bars are blue and arranged symmetrically, forming a bell-like shape. The y-axis represents a value, and the x-axis represents categories. ### Components/Axes * **Y-axis:** Ranges from 0.00 to 0.08, with increments of 0.01. * **X-axis:** No explicit labels, but the bars represent different categories or values along the x-axis. * **Bars:** All bars are blue. ### Detailed Analysis The bar chart shows a distribution that increases to a peak and then decreases symmetrically. * **Left Side (Ascending):** * The first bar is approximately 0.01. * The second bar is approximately 0.02. * The third bar is approximately 0.035. * The fourth bar is approximately 0.043. * The fifth bar is approximately 0.053. * The sixth bar is approximately 0.06. * The seventh bar is approximately 0.065. * The eighth bar is approximately 0.07. * The ninth bar is approximately 0.073. * **Center (Peak):** * The tenth bar is approximately 0.076. * **Right Side (Descending):** * The eleventh bar is approximately 0.076. * The twelfth bar is approximately 0.07. * The thirteenth bar is approximately 0.065. * The fourteenth bar is approximately 0.07. * The fifteenth bar is approximately 0.053. * The sixteenth bar is approximately 0.043. * The seventeenth bar is approximately 0.035. * The eighteenth bar is approximately 0.02. * The nineteenth bar is approximately 0.008. ### Key Observations * The distribution is symmetrical. * The peak of the distribution is around the tenth and eleventh bars. * The values increase gradually to the peak and then decrease gradually. ### Interpretation The bar chart represents a distribution, likely a probability distribution or a frequency distribution. The symmetrical bell shape suggests a normal distribution or a similar symmetric distribution. The x-axis represents different categories or values, and the y-axis represents the frequency or probability of each category. The peak indicates the most frequent or probable category. The data suggests that values near the center of the distribution are more common than values at the extremes. </details> (b) Prior distribution Beta(2,2) for latent variable x. <details> <summary>x2.png Details</summary>  ### Visual Description ## Bar Chart: Distribution ### Overview The image is a bar chart displaying a distribution. The bars are blue and arranged along an implicit x-axis. The y-axis ranges from 0.00 to 0.09 in increments of 0.01. The bars form a bell-shaped curve, indicating a normal or near-normal distribution. ### Components/Axes * **Y-axis:** Ranges from 0.00 to 0.09, incrementing by 0.01. * 0.00 * 0.01 * 0.02 * 0.03 * 0.04 * 0.05 * 0.06 * 0.07 * 0.08 * 0.09 * **X-axis:** Implicit, represented by the position of the bars. No explicit labels are provided. ### Detailed Analysis The bar heights, read from left to right, are approximately: * Bar 1: 0.003 * Bar 2: 0.009 * Bar 3: 0.015 * Bar 4: 0.024 * Bar 5: 0.032 * Bar 6: 0.042 * Bar 7: 0.052 * Bar 8: 0.061 * Bar 9: 0.071 * Bar 10: 0.079 * Bar 11: 0.083 * Bar 12: 0.085 * Bar 13: 0.088 * Bar 14: 0.084 * Bar 15: 0.079 * Bar 16: 0.070 * Bar 17: 0.059 * Bar 18: 0.040 * Bar 19: 0.018 ### Key Observations * The distribution is unimodal, with a peak around the 13th bar. * The distribution appears roughly symmetrical. * The values increase from left to center, then decrease from center to right. ### Interpretation The bar chart represents a distribution, likely of some variable. The bell shape suggests that the data is normally distributed, or at least approximately so. Without labels on the x-axis, the specific meaning of the distribution is unclear, but it shows the frequency or probability of different values occurring. The peak of the distribution indicates the most common value. The symmetry suggests that values are equally likely to be above or below the mean. </details> (c) Posterior distribution for x, one true observation. <details> <summary>x3.png Details</summary>  ### Visual Description ## Bar Chart: Probability Distribution ### Overview The image is a bar chart representing a probability distribution. The y-axis represents probability values ranging from 0.00 to 0.12. The x-axis is not explicitly labeled, but it represents discrete categories or values. The blue bars indicate the probability associated with each category. The distribution appears to be approximately normal or Gaussian. ### Components/Axes * **Y-axis (Probability):** Ranges from 0.00 to 0.12, with increments of 0.01. * 0.00 * 0.01 * 0.02 * 0.03 * 0.04 * 0.05 * 0.06 * 0.07 * 0.08 * 0.09 * 0.10 * 0.11 * 0.12 * **X-axis:** The x-axis is not labeled, but it represents discrete categories or values. * **Bars:** Blue bars represent the probability associated with each category on the x-axis. ### Detailed Analysis The bar heights, and therefore probabilities, are as follows (approximate due to visual estimation): * Bar 1: ~0.002 * Bar 2: ~0.008 * Bar 3: ~0.016 * Bar 4: ~0.032 * Bar 5: ~0.048 * Bar 6: ~0.068 * Bar 7: ~0.084 * Bar 8: ~0.102 * Bar 9: ~0.112 * Bar 10: ~0.110 * Bar 11: ~0.100 * Bar 12: ~0.088 * Bar 13: ~0.070 * Bar 14: ~0.050 * Bar 15: ~0.035 * Bar 16: ~0.018 * Bar 17: ~0.008 * Bar 18: ~0.002 ### Key Observations * The distribution is centered around the 9th bar, which has the highest probability (~0.112). * The probabilities decrease symmetrically as you move away from the center in either direction. * The distribution is unimodal, with a single peak. * The shape of the distribution resembles a normal distribution. ### Interpretation The bar chart represents a discrete probability distribution, likely an approximation of a continuous distribution. The shape suggests that the underlying data might be normally distributed. The x-axis represents different possible outcomes or categories, and the height of each bar indicates the likelihood of that outcome occurring. The distribution is centered, meaning that outcomes near the center are more probable than those further away. The symmetry suggests that deviations from the center are equally likely in both directions. </details> (d) Posterior distri-bution, observations [T, F, F, T, T] Figure 1: A simple CorePPL program modeling a coin flip. Fig. (1(a)) shows the source code, and Fig. (1(b)) the prior distribution. Fig. (1(c)) gives the posterior distribution after one coin flip, and Fig. (1(d)) the posterior after a sequence of 5 coin flips. In summary, we make the following contributions: - We introduce the new paradigm of real-time probabilistic programming languages (RTPPL), motivate why it is essential, and outline significant design challenges (Sec. II). - We design and implement ProbTime, a language within the domain of RTPPL (Sec. III), and specify its formal behavior (Sec. IV). - We present a novel automated offline configuration approach that maximizes inference accuracy under timing constraints. Specifically, we introduce the concepts of execution-time and particle fairness within the context of real-time probabilistic programming (Sec. V) and study how they can be incorporated in an automated configuration setting (Sec. VI). - We develop an automotive testbed including both hardware and software. As part of our case study, we demonstrate how a non-trivial ProbTime program can perform indoor positioning and braking in a real-time physical environment (Sec. VII). ## II Motivation and Challenges with RTPPL This section introduces the main ideas of probabilistic programming, motivates why it is useful for real-time systems, and outlines some of the key challenges. ### II-A Probabilistic Programming Languages (PPLs) Probabilistic programming is a rather recent programming paradigm that enables probabilistic modeling where the models can be described as Turing complete programs. Specifically, given a probabilistic program $f$ , observed data, and prior knowledge about the distribution of latent variables $\theta$ , a PPL execution environment can automatically approximate the posterior distribution of $\theta$ . Recall Bayes’ rule $$ \displaystyle p(\theta,\textbf{data})=\frac{p(\textbf{data},\theta)p(\theta)}{ p(\textbf{data})} \tag{1} $$ where $p(\theta,\textbf{data})$ is the posterior, $p(\textbf{data},\theta)$ the likelihood, $p(\theta)$ the prior, and $p(\textbf{data})$ the normalizing constant. Using a simple toy probabilistic program, we explain how standard PPL constructs relate to Bayes’ rule. Consider Fig. 1(a), written in CorePPL [12], the core language that our work is based on. We use this coin-flip example to give an intuition of the fundamental constructs in a PPL. The model starts by defining a random variable x (line LABEL:lst:ppl-code:assume) using the assume construct. In this example, random variable x models the probability that a coin flip becomes true (we let true mean heads and false mean tails). For instance, if $p(\texttt{x})=0.5$ , the coin is fair, whereas if, e.g., $p(\texttt{x})=0.7$ , it is unfair and more likely to result in true when flipped. The assume construct on line LABEL:lst:ppl-code:assume defines the random variable and gives its prior; in this case, the Beta distribution with both parameters equal to $2$ . If we sample from this prior, we get the Beta distribution depicted in Fig. 1(b). Note how the sample constructs in a probabilistic program (assume in CorePPL) correspond to the prior $p(\theta)$ in Bayes’ rule (Equation 1). However, the goal of Bayesian inference is to estimate the posterior for a latent variable, given some observations. Line LABEL:lst:ppl-code:observe in the program shows an observe statement, where a coin flip of value true is observed according to the Bernoulli distribution. Note how the Bernoulli distribution’s parameter depends on the random variable x. Consider Fig. 1(c), which depicts the inferred posterior distribution given one observed true coin flip. As expected, the distribution shifts slightly to the right, meaning that given one sample, the coin is estimated to be somewhat biased toward true. Note also how observe statements in a probabilistic program correspond to the likelihood $p(\textbf{data},\theta)$ in Bayes’ rule. That is, the likelihood we observe specific data, given a certain latent variable $\theta$ . If we extend Fig. 1(a) with in total five observations [true, false, false, true, true] in a sequence (illustrated with ... on line LABEL:lst:ppl-code:dots), the resulting posterior looks like Fig. 1(d). We can note the following: (i) the resulting mean is still slightly biased toward true (we have observed one more true value), and (ii) the variance is lower (the peak is slightly thinner). The latter case is a direct consequence of Bayesian inference and one of its key benefits: given the prior and the observed data, the posterior correctly represents the uncertainty of the result, not just a point estimate. There are many inference strategies that can be used for the inference in the toy example, such as sequential Monte Carlo (SMC) or Markov chain Monte Carlo (MCMC). In this work, we focus on SMC and one of its instances, also known as the particle filter [24] algorithm, because of its strength in this kind of application. The intuition of particle filters is that inference is done by executing the probabilistic program (the model) multiple times (potentially in parallel). Each such execution point is called a particle and consists at the end of a weight (how likely the particle is) and the output values, where the set of all particles forms the posterior distribution. Intuitively, the more particles, the better the accuracy of the approximate inference. Many more details of the algorithm (e.g., resampling strategies) are outside this paper’s scope, and an interested reader is referred to this technical overview by Naesseth et al. [25]. Although hiding the details of the inference algorithm is one of the key ideas of PPLs (separating the model from inference), the number of particles is essential for automatic inference and scheduling. Hence, this is a key concept in our work and will be discussed further in this paper. ### II-B Real-Time Probabilistic Programming (RTPPL) ⬇ 46 system { 47 sensor speed1 : Float rate 50 ms ///\label{lst:model:sa1} 48 sensor speed2 : Float rate 100 ms 49 actuator brake : Float rate 500 ms ///\label{lst:model:sa2} 50 task speedEst1 = Speed (250 ms) importance 1 ///\label{lst:model:tasks1} 51 task speedEst2 = Speed (500 ms) importance 1 52 task pos = Position () importance 3 53 task braking = Brake (300 ms) importance 4 ///\label{lst:model:tasks2} 54 speed1 -> speedEst1. in1 ///\label{lst:model:conn1} 55 speed2 -> speedEst2. in1 56 speedEst1. out -> pos. in1 ///\label{lst:model:s1conn1} 57 speedEst1. out -> braking. in1 ///\label{lst:model:s1conn2} 58 speedEst2. out -> pos. in2 59 speedEst2. out -> braking. in2 60 pos. out -> braking. in3 61 braking. out -> brake } ///\label{lst:model:conn2} (a) The system declaration of a ProbTime program. <details> <summary>x4.png Details</summary>  ### Visual Description ## System Diagram: Braking System ### Overview The image is a system diagram illustrating a braking system. It shows the flow of information and control signals between different components, including speed sensors, estimators, a position module, a braking module, and the final brake output. ### Components/Axes * **Nodes:** The diagram contains nodes represented by ovals and rectangles. Ovals represent inputs and outputs (speed sensors and brake), while rectangles represent processing modules (speed estimators, position, and braking). * **Connections:** Arrows indicate the flow of information between the nodes. Each arrow is labeled with an input or output name (e.g., "in1", "out"). ### Detailed Analysis or ### Content Details 1. **speed1 (Oval, top-left):** Represents the first speed sensor input. 2. **speedEst1 (Rectangle, top-center):** Represents the first speed estimator module. * Input: "in1" from "speed1" * Output: "out" to "pos" (input "in1") and "braking" (input "in1") 3. **pos (Rectangle, top-right):** Represents the position module. * Input: "in1" from "speedEst1" * Input: "in2" from "speedEst2" * Output: "out" to "braking" (input "in3") 4. **braking (Rectangle, bottom-right):** Represents the braking module. * Input: "in1" from "speedEst1" * Input: "in2" from "speedEst2" * Input: "in3" from "pos" * Output: "out" to "brake" 5. **brake (Oval, bottom-right):** Represents the final brake output. 6. **speed2 (Oval, bottom-left):** Represents the second speed sensor input. 7. **speedEst2 (Rectangle, bottom-center):** Represents the second speed estimator module. * Input: "in1" from "speed2" * Output: "out" to "pos" (input "in2") and "braking" (input "in2") ### Key Observations * The system uses two speed sensors and estimators. * The position module receives input from both speed estimators. * The braking module receives input from both speed estimators and the position module. ### Interpretation The diagram illustrates a redundant braking system that uses two speed sensors to improve reliability and accuracy. The speed estimators likely process the raw sensor data to filter noise and provide a more accurate speed estimate. The position module uses the speed estimates to determine the vehicle's position, which is then used by the braking module to calculate the appropriate braking force. The braking module integrates information from the speed estimators and the position module to control the final brake output. The redundancy in speed sensing and estimation suggests a safety-critical application where reliable braking is essential. </details> (b) A graphical representation of the system defined in Fig. 2(a). The system consists of two sensors, speed1 and speed2 on the left-hand side, four tasks speedEst1, speedEst2, pos, and braking in the middle, and an actuator brake on the right-hand side. Lines represent connections, where the white box represents the output port and the incoming arrow represents the input port. Figure 2: Example system of a ProbTime program in textual (2(a)) and graphical form (2(b)). The toy example of a coin flip in the previous example gives an intuition of probabilistic programming but does not show its power in large-scale applications. Probabilistic programming is used in several domains today, but surprisingly, little has been done in the context of time-critical applications. Although a rich literature exists on using Bayesian inference and filtering algorithms (e.g., particle filters in aircraft positioning [24]), these algorithms are typically hand-coded where both the probabilistic model and the inference algorithm are combined. This means that a developer needs to have deep insights into three different fields: (i) probabilistic modeling, (ii) Bayesian inference algorithms, and (iii) real-time programming aspects. Standard probabilistic programming is motivated by the appealing argument of separating (i) and (ii), thus enabling probabilistic modeling by developers without deep knowledge of how to implement inference efficiently and correctly. However, so far, probabilistic programming has not been combined with (iii) real-time aspects, such as timing, scheduling, and worst-case execution time estimation. This paper aims to make the first step towards mitigating this gap. We call this approach real-time probabilistic programming (RTPPL). How can an RTPPL be designed? For instance, we can extend an existing PPL with timing semantics, extend an existing real-time language with PPL constructs, or create a new domain-specific language (DSL) including only a minimal number of constructs for reasoning about timing and probabilistic inference. In this research work, we choose the latter to avoid complexity when extending large existing languages. In particular, our purpose is to create this rather small research language to study the fundamentals of this new kind of language category. We identify and examine the following key challenges with RTPPLs: - Challenge A: In an RTPPL, how can we encode real-time properties (deadlines, periodicity, etc.) and probabilistic constructs (sampling, observations, etc.) without forcing the user to specify low-level details such as particle counts and worst-case execution times? - Challenge B: How can a runtime environment be constructed, such that a fair amount of time is spent on different tasks, giving the right number of particles for each task (for accuracy), where the system is still known to be statically schedulable? We first address Challenge A (Sec. III - IV) by designing a new minimalistic research DSL called ProbTime and defining its formal behavior. Using the new DSL, we address Challenge B by studying two new concepts: execution-time fairness and particle fairness (Sec. V), and how particle counts, execution-time measurements, and scheduling can be performed automatically to get a fair and working configuration (Sec. VI). ## III ProbTime - an RTPPL In this section, we introduce a new real-time probabilistic programming language called ProbTime. We present the timing and probabilistic constructs in the language using a small example, followed by an overview of the compiler implementation. ProbTime is open-source and publically available https://github.com/miking-lang/ProbTime. ### III-A System Declaration We present a ProbTime system declaration implementing automated braking for a train in Fig. 2. The system keeps track of the train’s position and uses the automatic brakes before reaching the end of the track. The train provides observation data via two speed sensors with varying frequencies and accuracy (left side of Fig. 2(b)), and the system can activate the brakes via an actuator (right side of Fig. 2(b)). In Fig. 2(a), we first declare the sensors and actuators and associate them with a type to indicate what kind of data they operate on (lines LABEL:lst:model:sa1 - LABEL:lst:model:sa2). We also specify the rate at which data is provided by sensors and consumed by actuators. The squares in the graphical representation correspond to the tasks of our system. We instantiate the tasks on lines LABEL:lst:model:tasks1 - LABEL:lst:model:tasks2. Note that speedEst1 and speedEst2 are instantiated from the same template. The importance construct captures the relative importance of tasks. We use the importance value to indicate how important the quality of inference performed by a task is. It is not to be confused with the task priority. As we saw in the coin flip example (Sec. II), the number of particles used in inference relates to the quality of the estimate. In the train example, we use importance on lines LABEL:lst:model:tasks1 - LABEL:lst:model:tasks2 to indicate that pos and braking should run more particles than speedEst1 and speedEst2. We discuss importance in more detail in Sec. V. On lines LABEL:lst:model:conn1 - LABEL:lst:model:conn2 in Fig. 2(a), we declare the connections using arrow syntax a -> b, specifying that data written to output port a is delivered to input port b. Names of sensors and actuators represent ports and x.y refers to port y of task x. ### III-B Templates and Timing Constructs Continuing with the train braking example, we outline the definitions of the task templates Speed and Position in Listing 1. Consider the definition of the Speed template (lines LABEL:lst:model:speed1 - LABEL:lst:model:speed2). We declare the input port in1 and the output port out on lines LABEL:lst:model:speedin1 - LABEL:lst:model:speedout, and annotate them with types. We control timing in ProbTime using the iterative periodic block statement. A periodic block is a loop where each iteration starts after a statically known delay. Each iteration constitutes a task instance. On lines LABEL:lst:model:speed-periodic - LABEL:lst:model:speed2, we define a periodic block whose period is determined by the period argument of the Speed template. For instance, if period is $1\text{\,}\mathrm{s}$ , the release time is one second after the release time of the previous iteration. Our approach to timing is similar to the logical execution time paradigm [26]. However, while all timestamps are absolute under the hood, we only expose a relative view of the logical time of the current task instance. The read statement retrieves a sequence of inputs available from an input port at the logical time of the task instance. On line LABEL:lst:model:speed-read, we retrieve inputs from port in1 and store them in the variable obs. Similarly, the write statement (line LABEL:lst:model:speed-write) sends a message with a given payload to the specified output port. In Position (lines LABEL:lst:model:pos1 - LABEL:lst:model:pos2), we use our prior belief of the train’s position when estimating its current position. However, variables in ProbTime are immutable by default. We use update d in the periodic block on line LABEL:lst:model:pos-upd to indicate that updates to d (the position distribution) should be visible in subsequent iterations. Also, in the write on line LABEL:lst:model:pos-write, we specify an offset to the timestamp of the message relative to the current logical time of the task (it is zero by default). Listing 1: Definition of the Speed and Position task templates. ⬇ 20 template Speed (period : Int) {///\label{lst:model:speed1} 21 input in1 : Float ///\label{lst:model:speedin1} 22 output out : Dist (Float) ///\label{lst:model:speedout} 23 periodic period {///\label{lst:model:speed-periodic} 24 read in1 to obs ///\label{lst:model:speed-read} 25 infer speedModel (obs) to d ///\label{lst:model:speed-infer} 26 write d to out } } ///\label{lst:model:speed-write} \label{lst:model:speed2} 27 template Position () {///\label{lst:model:pos1} 28 input in1 : Dist (Float) 29 input in2 : Dist (Float) 30 output out : Dist (Float) 31 infer initPos () to d 32 periodic 1 s update d {///\label{lst:model:pos-upd} 33 read in1 to speed1 34 read in2 to speed2 35 infer positionModel (d, speed1, speed2) to d 36 write d to out offset 500 ms } } ///\label{lst:model:pos-write} \label{lst:model:pos2} ### III-C Models and Probabilistic Constructs We define three probabilistic constructs in ProbTime, similar to what is used in other PPLs: sample, observe, and infer. We use sample and observe when defining probabilistic models, and we use the infer construct to produce a distribution from a probabilistic model in task templates. Listing 2: Probabilistic model for estimating the train’s speed. ⬇ 10 model speedModel (obs : [TSV (Float)]) : Float {///\label{lst:model:model1} 11 sample b $\sim$ Uniform (0.0, maxSpeed) ///\label{lst:model:intercept} 12 sample m $\sim$ Gaussian (0.0, 1.0) 13 sample sigma $\sim$ Gamma (1.0, 1.0) ///\label{lst:model:sigma} 14 for o in obs {///\label{lst:model:for1} 15 var ts = timestamp (o) ///\label{lst:model:to-timestamp} 16 var x = intToFloat (ts) / intToFloat (1 s) ///\label{lst:model:tstofloat} 17 var y = m * x + b 18 observe value (o) $\sim$ Gaussian (y, sigma) } ///\label{lst:model:observe} \label{lst:model:for2} 19 return b } ///\label{lst:model:model-ret} \label{lst:model:model2} Consider the probabilistic model defined using the function speedModel in Listing 2. The function models the speed of the train at the current logical time using Bayesian linear regression. The parameter obs is a sequence of speed observations encoded as a sequence of floating-point messages (we use TSV as a short-hand for timestamped values). In this model, we use a sample statement to sample a random slope and intercept of a line, assuming acceleration is constant. There are three latent variables (defined on lines LABEL:lst:model:intercept - LABEL:lst:model:sigma): b (the offset of the line), m (the slope of the line), and sigma (the variance, approximating the uncertainty of the estimate). The estimated line can be seen as a function of the speed over (relative) time, where $0 0$ is the logical time of the task instance. In the for-loop on lines LABEL:lst:model:for1 - LABEL:lst:model:for2, we update our belief based on the speed observations. First, we translate the relative timestamp of the observation o to a floating-point number, representing our x-value (lines LABEL:lst:model:to-timestamp - LABEL:lst:model:tstofloat). We use the observe statement on line LABEL:lst:model:observe to update our belief. The observed value is the data of o (retrieved using value(o)), and we expect observations to be distributed according to a Gaussian distribution centered around the y-value. We return the train’s estimated speed (the intercept of the line) on line LABEL:lst:model:model-ret. Figure 3 presents a sample plot of what this looks like when the train accelerates. As we use relative timestamps in ProbTime, we can define this rather complicated model succinctly. <details> <summary>x5.png Details</summary>  ### Visual Description ## Scatter Plot: Speed vs. Time ### Overview The image is a scatter plot showing the relationship between speed (m/s) and time (s). It includes a primary blue line representing a linear fit, several translucent blue lines representing possible variations, and red data points. A vertical black line marks time = 0. ### Components/Axes * **X-axis:** Time (s), ranging from -0.6 to 0.1, with tick marks at -0.6, -0.5, -0.4, -0.3, -0.2, -0.1, 0.0, and 0.1. * **Y-axis:** Speed (m/s), ranging from 0.0 to 0.6, with tick marks at 0.0, 0.2, 0.4, and 0.6. * **Data Points:** Five red data points are scattered across the plot. * **Linear Fit:** A solid blue line represents the primary linear fit to the data. * **Variations:** Many translucent blue lines show possible variations around the primary linear fit. * **Vertical Line:** A solid black vertical line is positioned at time = 0. ### Detailed Analysis * **Red Data Points:** * Point 1: Approximately at (-0.5, 0.0) * Point 2: Approximately at (-0.4, 0.1) * Point 3: Approximately at (-0.3, 0.2) * Point 4: Approximately at (-0.2, 0.3) * Point 5: Approximately at (-0.1, 0.4) * **Blue Line (Linear Fit):** The blue line slopes upward, indicating a positive correlation between time and speed. It starts at approximately (-0.6, -0.1) and extends to approximately (0.1, 0.6). * **Translucent Blue Lines:** These lines show a range of possible linear fits, with the density of lines decreasing as you move away from the primary blue line. They all generally slope upwards. ### Key Observations * The speed generally increases with time. * The red data points appear to be relatively close to the primary blue line, suggesting a good fit. * The translucent blue lines indicate uncertainty in the linear fit, with more variation at the extremes of the time range. ### Interpretation The plot suggests a linear relationship between time and speed. The red data points support this relationship, and the blue line represents the best linear fit. The translucent blue lines represent the uncertainty in the fit, likely due to limited data or noise. The vertical line at time = 0 serves as a reference point. The data suggests that as time increases, the speed also increases, and the model provides a reasonable approximation of this relationship, although with some uncertainty. </details> Figure 3: Outcome of the speed model for the speedEst2 task on synthetic data. The x-axis represents time in seconds, and the y-axis represents the train’s speed in meters per second (we seek the speed at the current time, $x=0.0$ ). The red dots represent speed observations, and the blue lines are estimates from the model (slope and intercept), where the opacity of a line indicates its likelihood. <details> <summary>x6.png Details</summary>  ### Visual Description ## Diagram: ProbTime Compilation Process ### Overview The image is a diagram illustrating the compilation process of ProbTime, a programming language. It shows the flow of data and transformations from the initial ProbTime Program to the final CorePPL Executables, highlighting key components like Parser, Validator, Extractor, Backend Compiler, and CorePPL Compiler. ### Components/Axes * **Nodes:** The diagram consists of rectangular nodes representing different stages or components in the compilation process. These nodes are labeled with the names of the components and their associated data structures. Some nodes are colored blue, while others are gray. * **Arrows:** Arrows indicate the flow of data and control between the components. * **Numbers:** Each blue node has a number in a circle next to it, indicating the order of operations. ### Detailed Analysis 1. **ProbTime Program:** The process begins with a "ProbTime Program" represented by a gray rectangle on the left. 2. **Parser (1):** The "ProbTime Program" is fed into the "Parser," a blue rectangle. The number "1" in a circle is next to the Parser. 3. **ProbTime AST:** The Parser outputs "ProbTime AST" (Abstract Syntax Tree), represented by a gray rectangle. 4. **Validator (2):** The "ProbTime AST" is fed into the "Validator," a blue rectangle. The number "2" in a circle is next to the Validator. 5. **ProbTime Runtime:** A "ProbTime Runtime" gray rectangle is positioned above the "Extractor" and feeds into it. 6. **System Declaration:** A "System Declaration" gray rectangle is positioned above the "ProbTime Task ASTs" and feeds into the "Extractor". 7. **Extractor (3):** The "ProbTime AST," "ProbTime Runtime," and "System Declaration" are fed into the "Extractor," a blue rectangle. The number "3" in a circle is next to the Extractor. 8. **ProbTime Task ASTs:** The Extractor outputs "ProbTime Task ASTs," represented by a stack of gray rectangles. 9. **Backend Compiler (4):** The "ProbTime Task ASTs" are fed into the "Backend Compiler," a blue rectangle. The number "4" in a circle is next to the Backend Compiler. 10. **CorePPL ASTs:** The Backend Compiler outputs "CorePPL ASTs," represented by a stack of gray rectangles enclosed in a dashed rectangle. 11. **CorePPL Compiler (5):** The "CorePPL ASTs" are fed into the "CorePPL Compiler," a blue rectangle. The number "5" in a circle is next to the CorePPL Compiler. 12. **ProbTime Executables:** The CorePPL Compiler outputs "ProbTime Executables," represented by a stack of gray rectangles. ### Key Observations * The diagram illustrates a sequential process, with data flowing from left to right. * The blue rectangles represent active components (Parser, Validator, Extractor, Backend Compiler, CorePPL Compiler) that perform transformations on the data. * The gray rectangles represent data structures (ProbTime Program, ProbTime AST, ProbTime Task ASTs, CorePPL ASTs, ProbTime Executables) that are passed between the components. * The Validator, ProbTime Runtime, and System Declaration feed into the Extractor. * The CorePPL ASTs and CorePPL Compiler are enclosed in a dashed rectangle, possibly indicating a related subsystem. ### Interpretation The diagram depicts the compilation pipeline for ProbTime. The ProbTime Program is parsed and validated, then transformed into a series of Abstract Syntax Trees (ASTs). The Extractor combines the AST with runtime information and system declarations. The Backend Compiler then translates these ASTs into CorePPL ASTs, which are then compiled into ProbTime Executables by the CorePPL Compiler. The use of CorePPL as an intermediate representation suggests that ProbTime leverages CorePPL's capabilities for execution or further processing. The Validator step indicates a focus on ensuring the correctness and consistency of the ProbTime program before further compilation. </details> Figure 4: An overview of the ProbTime compiler. Gray square boxes represent artifacts, and rounded blue squares represent compiler transformations (numbered by the order in which they run). We use the pre-existing CorePPL compiler to produce executable code in the dashed area. Finally, recall Listing 1 at line LABEL:lst:model:speed-infer, where we use the infer statement to infer the posterior using the probabilistic model (in this case speedModel). ### III-D Compiler Implementation Fig. 4 depicts the key steps of the ProbTime compiler. The compiler is implemented within the Miking framework [23] because of its good support for defining domain-specific languages and the possibility of extending the Miking CorePPL [12] framework with real-time constructs. A key step of the compilation is the extractor (3 in Fig. 4), which produces one abstract syntax tree (AST) for each task declared in the ProbTime AST. We combine this AST with a runtime AST, which, for instance, implements infer and delay. We individually pass the task ASTs to the backend compiler (4), translating them to CorePPL ASTs, which are compiled into executables using the existing CorePPL compiler (5). Our implementation consists of 4400 lines of code. ## IV System Model and Formal Specification This section presents a formal specification of ProbTime on a system level (Sec. IV-A), including a system model. We also consider ProbTime on a task level (Sec. IV-B), focusing on communication and the probabilistic constructs. ### IV-A System-Level Specification We define a ProbTime system as a tuple $(\mathcal{T},\mathcal{S},\mathcal{A},\mathcal{C})$ , where $\mathcal{T}$ is a set of tasks, $\mathcal{S}$ is a set of sensors, $\mathcal{A}$ is a set of actuators, and $\mathcal{C}$ is a set of connections. A task $\tau$ is represented by the tuple $(C,T,\pi,n,v)$ , where $C$ is its worst-case execution time (WCET), $T$ its period, $\pi$ its static priority, $n$ the number of particles, and $v$ its assigned importance value. Tasks are subject to an implicit deadline $D=T$ . We assume the periodic block of each task $\tau$ contains at most one use of infer, for which we set the number of particles $n_{\tau}$ . We assume the tasks of $\mathcal{T}$ are ordered by increasing period. The tasks execute on an exclusive subset of the cores available on a platform. Specifically, if the platform has $m$ cores, we schedule our tasks on a subset $\mathcal{U}$ of cores, where $k<m$ (we reserve one core for the platform). Each task $\tau$ is statically assigned a core $c\in\mathcal{U}$ . We use partitioned fixed-priority scheduling on the cores $\mathcal{U}$ . Priorities are assigned on the rate monotonic principle [27], where the task $\tau$ with the lowest period $T_{\tau}$ has the highest priority $\pi_{\tau}$ . The tasks are preemptive. Each task $\tau$ has a set of input ports $I_{\tau}$ from which it can receive data and a set of output ports $O_{\tau}$ to which it can send data. Sensors act as output ports, and actuators as input ports. A ProbTime system has a set of input ports $I=\mathcal{A}\cup\bigcup_{\tau\in\mathcal{T}}I_{\tau}$ and a set of output ports $O=\mathcal{S}\cup\bigcup_{\tau\in\mathcal{T}}O_{\tau}$ . The set $\mathcal{C}$ contains connections $c_{i}=(o_{j},i_{k}),o_{j}\in O\land i_{k}\in I$ . We say that a task $\tau$ is a predecessor of $\tau^{\prime}$ if $\exists(o,i)\in\mathcal{C}.o\in O_{\tau}\land i\in I_{\tau^{\prime}}$ . Every port $p\in I\cup O$ of a task has an associated buffer $B_{p}$ storing incoming or outgoing messages. Given the particle counts $n_{\tau}$ of all tasks $\tau$ , we can determine the message size. The compiler counts the number of times a task writes to each port when this can be determined at compile-time (otherwise, the compiler produces a warning). Based on these counts and the declared rate of sensors and actuators, the automatic configuration (Sec. VI) verifies that a given (fixed) buffer size is sufficient for the messages passing through all ports. ### IV-B Task-Level Specification We present the behavior of a task $\tau$ in Algorithm 1. The RunTaskInstance function (lines 1 - 6) is called at the start of the periodic block. It starts with an absolute delay until the next period, increasing the logical time [28] of the task by $T_{\tau}$ (line 3). The task $\tau$ reads all data from input ports $i\in I_{\tau}$ to buffers $B_{i}$ (using ReadNonBlocking on line 4), runs an iteration of the periodic block (such as lines LABEL:lst:model:speed-read - LABEL:lst:model:speed-write in Listing 1) in RunIteration (line 5), and writes messages stored in output buffers $B_{o}$ to their output ports $o\in O_{\tau}$ (using WriteNonBlocking on line 6). Reads and writes in a ProbTime task operate on the buffers rather than directly on the ports. The statement read i to x results in $\texttt{x}\leftarrow\textsc{ReadInputPort}(\texttt{i})$ . Similarly, write v to o offset d results in $\textsc{WriteOutputPort}(\texttt{v},\texttt{o},\texttt{d})$ , which concatenates a message with payload v and timestamp equal to the current logical time of the task ( $t_{0}$ ) plus an offset (d) to the buffer $B_{o}$ . The reads from and writes to the ports are non-blocking, so we have no precedence relationships between tasks, and communication has no impact on scheduling. Algorithm 1 Definition of the behavior of the task runtime. 1: function RunTaskInstance τ () 2: while true do 3: $\textsc{DelayUntil}(T_{\tau})$ 4: for $i\in I_{\tau}$ do $B_{i}\leftarrow\textsc{ReadNonBlocking}(i)$ 5: $\textsc{RunIteration}(\tau)$ 6: for $o\in O_{\tau}$ do $\textsc{WriteNonBlocking}(o,B_{o})$ 7: function ReadInputPort ( $i$ ) 8: return $B_{i}$ 9: function WriteOutputPort ( $v,o,d$ ) 10: $B_{o}\leftarrow B_{o},(v,t_{0}+d)$ Algorithm 2 Algorithmic definition of the formal behavior of probabilistic constructs within a task. 1: function Infer τ ( $m,x_{1},\ldots,x_{n}$ ) 2: for $i\in 1\ldots n_{\tau}$ do 3: $v_{i},w_{i}\leftarrow\textsc{RunParticle}(m,x_{1},\ldots,x_{n})$ 4: return $(v_{1},w_{1}),\ldots,(v_{n_{\tau}},w_{n_{\tau}})$ 5: function RunParticle ( $m,x_{1},\ldots,x_{n}$ ) 6: $w\leftarrow 0$ 7: $v\leftarrow m_{w}(x_{1},\ldots,x_{n})$ 8: return $v,w$ 9: function UpdateWeight ( $w,o,d$ ) 10: return $w+\textsc{LogObserve}(o,d)$ 11: function LogObserve ( $o,d$ ) 12: if $\textsc{Elementary}(d)$ then return $\text{logPdf}_{d}(o)$ 13: else error 14: function Sample ( $d$ ) 15: if $\textsc{Elementary}(d)$ then return $\text{sample}_{d}()$ 16: else 17: $r\leftarrow\textsc{SampleUniform}(0,c_{|d|})$ 18: $j\leftarrow\textsc{LowerBound}(r,c)$ 19: return $v_{j}$ We present the formal behavior of the probabilistic constructs infer, observe, and sample in Algorithm 2. Consider the definition of inference for a task $\tau$ in the Infer τ function (lines 1 - 4). We perform inference by running a fixed number of particles $n_{\tau}$ , as determined by the automatic configuration (Sec. VI). Each particle $(v_{j},w_{j})$ consists of a value $v_{j}$ returned by the probabilistic model function $m$ and a weight $w_{j}$ determined by use of observe within the model. The sequence of particles returned by Infer τ (line 4) is the resulting distribution. The statement infer m (x, y) to d corresponds to $\texttt{d}\leftarrow$ Infer ${}_{\tau}(\texttt{m},\texttt{x},\texttt{y})$ in our pseudocode. When we run a particle in the RunParticle function (lines 5 - 8), we use a weight $w$ , representing the accumulated log-likelihood of a particle having a particular value $v$ . Every statement observe o $\sim$ d modifies the weight as $w\leftarrow\textsc{UpdateWeight}(w,\texttt{o},\texttt{d})$ . We denote the model function as $m_{w}$ on line 7 to indicate that the model $m$ mutates the weight $w$ . For instance, if the model $m_{w}$ is speedModel of Listing 2, we run lines LABEL:lst:model:intercept - LABEL:lst:model:model-ret, and update $w$ for each use of observe on line LABEL:lst:model:observe. The LogObserve function (lines 11 - 13 in Algorithm 2) represents the computation of the logarithmic weight for an observe statement. ProbTime supports observations on elementary distributions (e.g., Gaussian) but not empirical distributions (produced by an infer). For an elementary distribution, we compute the weight using its logarithmic probability distribution function (line 12). When we sample a random value as in sample x $\sim$ d, we assign a random value to the variable x from the distribution d. We define this in the Sample function (lines 14 - 19). For an elementary distribution, we use a known sampling function (line 15). For empirical distributions, we use the cumulative weights $c_{j}=\sum_{i=1}^{j}w_{i}$ to pick a random particle through a binary search (lines 17 - 19). Therefore, the time complexity of sampling is $O(\log n)$ for an empirical distribution of $n$ particles. As ProbTime supports sending empirical distributions between tasks, this complexity results in a dependency. A task $\tau_{i}$ that samples from a distribution sent by a predecessor $\tau_{j}$ has an increased execution time if we increase $n_{\tau_{j}}$ . ## V Fairness In this section, we present new perspectives on fairness that emerge when combining real-time and probabilistic inference. ### V-A Execution-Time and Particle Fairness We know that more particles improve the accuracy of the inference, but it is not obvious how the result of one task $\tau$ impacts the whole system’s behavior. As we concluded in Sec. IV, increasing the execution time or particle count of a task may affect the performance of other tasks. ProbTime allows the user to specify how important each task is. Specifically, we use the importance values $v_{\tau}$ associated with each task $\tau$ as a measure to guide fairness. But what is the right approach to fairness? We define and study fairness in two ways: (i) execution-time fairness, where we allocate execution time budgets $B_{\tau}$ (which the WCETs $C_{\tau}$ of each task $\tau$ must not exceed) to tasks proportional to their importance values, and (ii) particle fairness, where fairness between tasks is given in terms of the number of particles used in the inference. Consider Fig. 5, where we present three scenarios to exemplify the differences between execution-time and particle fairness. Assume we have two tasks $\tau_{A}$ and $\tau_{B}$ such that $T_{\tau_{A}}=T_{\tau_{B}}$ and $v_{\tau_{A}}=2\cdot v_{\tau_{B}}$ , running on one core. The tasks are independent and they have the same execution time per particle. We present the outcome of the three scenarios (labeled 1, 2, and 3, respectively) for $\tau_{A}$ and $\tau_{B}$ concerning their relative ratios of execution time and particle count. <details> <summary>x7.png Details</summary>  ### Visual Description ## Bar Chart: Execution Time and Particle Count for Different Scenarios ### Overview The image presents a bar chart comparing the execution time of two components, A and B, across six different scenarios. It also shows the particle count for each component in each scenario. The execution time is represented by the length of the colored bars, with orange representing component A and blue representing component B. The particle count is listed numerically to the right of the bars. ### Components/Axes * **Title:** Execution time (top-center), Particle count (top-right) * **Y-axis Labels:** Scenario 1E, Scenario 1P, Scenario 2E, Scenario 2P, Scenario 3E, Scenario 3P * **Bar Colors:** Orange (Component A), Blue (Component B) * **Particle Count Labels:** A, B ### Detailed Analysis **Scenario 1E:** * Execution Time: Component A (orange) and Component B (blue) have approximately equal execution times. * Particle Count: A: 2000, B: 1000 **Scenario 1P:** * Execution Time: Component A (orange) and Component B (blue) have approximately equal execution times. * Particle Count: A: 2000, B: 1000 **Scenario 2E:** * Execution Time: Component A (orange) has a significantly longer execution time than Component B (blue). * Particle Count: A: 2000, B: 250 **Scenario 2P:** * Execution Time: Component A (orange) has a shorter execution time than Component B (blue). * Particle Count: A: 1000, B: 500 **Scenario 3E:** * Execution Time: Component A (orange) has a longer execution time than Component B (blue). * Particle Count: A: 500, B: 1000 **Scenario 3P:** * Execution Time: Component A (orange) has a longer execution time than Component B (blue). * Particle Count: A: 1200, B: 600 ### Key Observations * Scenarios 1E and 1P have identical execution time distributions and particle counts. * The execution time ratio between components A and B varies significantly across the different scenarios. * The particle count of component A varies from 500 to 2000, while the particle count of component B varies from 250 to 1000. * There is no clear correlation between execution time and particle count. ### Interpretation The chart illustrates the performance characteristics of two components (A and B) under different scenarios. The execution time and particle count are independent variables, and their relationship is not immediately obvious from the data presented. The "E" and "P" suffixes in the scenario names likely represent different configurations or parameters within each scenario, leading to variations in execution time and particle count. The data suggests that the optimal configuration for each scenario may depend on the specific requirements of the application, as the relative performance of components A and B varies significantly. </details> Figure 5: Illustration of execution time and particle counts for tasks $\tau_{A}$ and $\tau_{B}$ ( $\tau_{A}$ is twice as important as $\tau_{B}$ and both have the same period) for three scenarios when considering execution-time fairness (E) and particle fairness (P). In scenario 1, we find in both cases that, because the tasks have the same execution time per particle, they both end up with the same ratio of execution time and particles. In scenario 2, we assume task $\tau_{B}$ requires four times as much execution time as $\tau_{A}$ per particle. If we use execution-time fairness, the execution time ratio of the tasks remains the same, but $\tau_{B}$ only has time to produce $250$ particles. For particle fairness, the slowdown of $\tau_{B}$ results in both tasks running fewer particles to maintain a fair allocation of particle counts, skewing the execution time in favor of $\tau_{B}$ . In scenario 3, we instead assume $\tau_{A}$ samples from a distribution sent from $\tau_{B}$ , meaning the execution time of $\tau_{A}$ depends on the particle count of $\tau_{B}$ . The exact outcome depends on the ratio of time $\tau_{A}$ spends on sampling. Using execution-time fairness, we find that $\tau_{A}$ only has time to produce $500$ particles. Task $\tau_{B}$ produces the same number of particles as in scenario 1 because it is independent of $\tau_{A}$ . In contrast, when using particle fairness, $\tau_{A}$ produces more particles, and $\tau_{B}$ produces fewer. Which kind of fairness is preferred in a real-time probabilistic inference setting? Although execution-time fairness may seem natural from a real-time perspective, we will see (surprisingly) in the evaluation (Sec. VII-D) that particle fairness works better in practice. Fairness is applicable in scenarios where the output quality is proportional to the time spent producing it. This paper focuses explicitly on SMC inference, where the number of particles controls the quality. However, we foresee no issues extending this to, e.g., MCMC inference algorithms by considering the number of runs instead of the particle count. ### V-B Computation Maximization So far, we only considered the case where tasks run on one core. What if we want to apply fairness to tasks running on multiple cores? We consider two extremes: prioritizing fairness or prioritizing utilization. If we prioritize fairness, we allocate a fixed amount of resources (execution time or particles) to a task instance proportional to its importance value, regardless of which core the task is mapped to. We refer to this as fair utilization. If we prioritize utilization, we maximize the utilization on each core individually, ignoring the importance of tasks running on other cores. We refer to this as maximum utilization. In both cases, the resulting system is schedulable. Assume we allocate the tasks listed on the left-hand side of Fig. 6 on a dual-core system (where $T_{i}$ is the period, $v_{i}$ is the importance, and $c$ is the core of task $\tau_{i}$ ). On the right-hand side, we present the result of applying the two alternatives using execution-time fairness (this also applies to particle fairness). Each box corresponds to a task instance ( $\tau_{D}$ has four times the frequency of $\tau_{A}$ ; hence, it has four boxes), and we consider importance values to apply per task instance. We see that $\tau_{A}$ and $\tau_{B}$ are allocated the same execution time, as $\tau_{A}$ is twice as important as $\tau_{B}$ , but $\tau_{B}$ runs twice as frequently. The main takeaway from Fig. 6 is that, when prioritizing fair utilization, all cores are not always fully utilized. Recall that the tasks of the system may depend on each other. Increasing the execution times of $\tau_{C}$ and $\tau_{D}$ may negatively impact the performance of $\tau_{A}$ and $\tau_{B}$ . This is unfair, considering that $\tau_{A}$ and $\tau_{B}$ have higher importance. On the other hand, if the tasks are independent (which they are in this example), we are wasting computational resources. As an alternative, we also propose the concept of fair utilization maximization, where we start from fair utilization and gradually increase the resources (execution time or particles) allocated to tasks on cores that are not fully utilized as long as the system remains schedulable. If $\tau_{A}$ and $\tau_{B}$ do not depend on $\tau_{C}$ and $\tau_{D}$ , we get the same result as when prioritizing maximum utilization. | $A$ $B$ $C$ | $1\text{\,}\mathrm{s}$ $0.5\text{\,}\mathrm{s}$ $1\text{\,}\mathrm{s}$ | 8 4 4 | 1 1 2 | | --- | --- | --- | --- | | $D$ | $0.25\text{\,}\mathrm{s}$ | 2 | 2 | <details> <summary>x8.png Details</summary>  ### Visual Description ## Core Utilization Diagram: Fair vs. Maximum Utilization ### Overview The image presents a diagram illustrating the utilization of two CPU cores under two different scenarios: "Fair utilization" and "Maximum utilization." Each scenario shows the allocation of core time to four different processes or tasks, labeled A, B, C, and D. The diagram uses color-coding to distinguish between the processes. ### Components/Axes * **Title:** "Fair utilization" (top) and "Maximum utilization" (bottom) * **Cores:** "Core #1" and "Core #2" are labeled to the right of each core's utilization bar. * **Processes/Tasks:** Four processes are represented: A (orange), B (light blue), C (black), and D (green). * **Utilization Bars:** Each core has a bar representing its utilization, segmented into blocks corresponding to the processes running on that core. ### Detailed Analysis **Fair Utilization:** * **Core #1:** * Process A (orange) occupies approximately 50% of the core's time. * Process B (light blue) occupies the remaining 50%, split into two equal blocks of 25% each. * **Core #2:** * Process C (black) occupies approximately 20% of the core's time. * Process D (green) occupies the remaining 80%, split into four equal blocks of 20% each. **Maximum Utilization:** * **Core #1:** * Process A (orange) occupies approximately 50% of the core's time. * Process B (light blue) occupies the remaining 50%, split into two equal blocks of 25% each. * **Core #2:** * Process C (black) occupies approximately 20% of the core's time. * Process D (green) occupies the remaining 80%, represented by four blocks of 20% each. ### Key Observations * Under both "Fair utilization" and "Maximum utilization," Core #1's allocation between processes A and B remains constant. * Similarly, Core #2's allocation between processes C and D remains constant under both scenarios. * The diagram does not show any difference in core utilization between the "Fair utilization" and "Maximum utilization" scenarios. ### Interpretation The diagram suggests that the "Fair utilization" and "Maximum utilization" scenarios, as depicted, result in the same allocation of processes to cores. This could imply that the system is already operating at maximum utilization even under the "Fair utilization" setting, or that the criteria for "fairness" and "maximum" happen to align in this specific case. It's also possible that the diagram is a simplified representation and doesn't capture the nuances of how these utilization strategies differ in practice. The diagram does not provide enough information to determine the specific algorithms or policies used to achieve these utilization levels. </details> Figure 6: The resulting utilization of the tasks (left) allocated on two cores when prioritizing fairness (top right) or maximizing the utilization (bottom right) in terms of execution time. ## VI Automatic Configuration In this section, we present two approaches to automatic configuration that we apply to a compiled ProbTime system to maximize inference accuracy while preserving schedulability. Automatic configuration is performed before running the system so it does not introduce runtime overheads. ### VI-A Configuration Overview We define two key phases needed to configure a ProbTime system: (i) the collection phase, where we record sensor inputs, and (ii) the configuration phase, where we determine the particle counts of all tasks. During phase (i), we collect input data from the sensors of the actual system, which we replay repeatedly during (ii) in a hardware-in-the-loop simulation. The configuration phase runs on the target system. This paper focuses on the configuration phase (ii). We present two alternative approaches to automatic configuration based on execution-time fairness (Sec. VI-B) and particle fairness (Sec. VI-C). In both cases, we seek a particle count $n_{\tau}$ to use in the inference of each task $\tau$ based on its importance value $v_{\tau}$ , using fair utilization. For simplicity, we assume the user provides a task-to-core mapping $\mathcal{M}$ specifying on which core each task runs (such that $\mathcal{M}_{\tau}\in\mathcal{U}$ ). Also, we assume the existence of a function RunTasks that runs the tasks with pre-recorded sensor data to measure the WCET $W_{\tau}$ of each task $\tau$ . Finally, we use a configurable safety margin factor $\delta$ to protect against outliers in the WCET observations. ### VI-B Execution-Time Fairness We perform two steps to achieve execution-time fairness. First, we compute fair execution time budgets $B_{\tau}$ for each task $\tau$ based on its importance $v_{\tau}$ , such that all tasks remain schedulable. Second, we maximize the particle counts while ensuring the WCET of each task $\tau$ is within its budget. We define the ComputeBudgets function in Algorithm 3 (lines 1 - 6) to compute the execution time budgets of tasks with fair utilization. Our approach assumes partitioned scheduling, which means we can examine tasks assigned to different cores independently. For each core $c_{i}$ , we use the sensitivity analysis in the C-space of Bini et al. [29] to compute a maximum change $\lambda_{i}$ to the execution times of tasks for which they remain schedulable, given a direction vector $\mathbf{d}$ (initially, we assume all execution times are zero). We define $\mathbf{d}$ based on the importance values of the tasks (line 3) and pass it to the SensitivityAnalysis function to compute $\lambda_{i}$ (line 4). Then, we pick the minimum lambda among all cores (line 5) and use this to get fair execution time budgets for all tasks (line 6). Algorithm 3 Function to determine the number of particles to use for execution-time fairness. 1: function ComputeBudgets ( $\mathcal{M},\mathcal{T}$ ) 2: for $c_{i}\in\mathcal{U}$ do 3: $\mathbf{d}\leftarrow\{v_{\tau}\ |\ \tau\in\mathcal{T}\land\mathcal{M}_{\tau}=c _{i}\}$ 4: $\lambda_{i}\leftarrow\textsc{SensitivityAnalysis}(\mathbf{d})$ 5: $\lambda\leftarrow\min_{i}\lambda_{i}$ 6: $\mathbf{return}\ \{(\tau,v_{\tau}\cdot\lambda)\ |\ \tau\in\mathcal{T}\}$ 7: function Configure EF ( $\mathcal{M},\mathcal{T}$ ) 8: $L,U\leftarrow\{(\tau,1)\ |\ \tau\in\mathcal{T}\},\{(\tau,\infty)\ |\ \tau\in \mathcal{T}\}$ 9: $N\leftarrow\{(\tau,1)\ |\ \tau\in\mathcal{T}\}$ 10: $A\leftarrow\{\tau\ |\ \tau\in\mathcal{T}\land P_{\tau}=\emptyset\}$ 11: $B\leftarrow\textsc{ComputeBudgets}(\mathcal{M},\mathcal{T})$ 12: $F\leftarrow\{\tau\ |\ \tau\in\mathcal{T}\land v_{\tau}=0\}$ 13: while $A\neq\emptyset$ do 14: $W\leftarrow\textsc{RunTasks}(\mathcal{M},\mathcal{T})$ 15: for $\tau\in A$ do 16: if $L_{\tau}+1<U_{\tau}$ then 17: $L_{\tau},U_{\tau}\leftarrow\begin{cases}L_{\tau},N_{\tau}&\text{if }\frac{W_{ \tau}}{\delta}>B_{\tau}\\ N_{\tau},U_{\tau}&\text{otherwise}\end{cases}$ 18: $N_{\tau}\leftarrow\begin{cases}2\cdot L_{\tau}&\text{if }U_{\tau}=\infty\\ \lfloor\frac{L_{\tau}+U_{\tau}}{2}\rfloor&\text{otherwise}\end{cases}$ 19: else $N_{\tau},F\leftarrow L_{\tau},F\cup\{\tau\}$ 20: $A\leftarrow\{\tau\ |\ \tau\in\mathcal{T}\land P_{\tau}\subseteq F\}\setminus F$ 21: $\mathbf{return}\ N$ Algorithm 4 Computing the number of particles to use for particle fairness. 1: function Schedulable ( $\mathcal{M},\mathcal{T},k$ ) 2: for $\tau\in\mathcal{T}$ do $n_{\tau}\leftarrow\lfloor k\cdot\overline{v}_{\tau}\rfloor$ 3: $W\leftarrow\textsc{RunTasks}(\mathcal{M},\mathcal{T})$ 4: for $(\tau,W_{\tau})\in W$ do $C_{\tau}\leftarrow\frac{W_{\tau}}{\delta}$ 5: $\textbf{return}\ \textsc{RTA}(\mathcal{M},\mathcal{T})$ 6: function Configure PF ( $\mathcal{M},\mathcal{T}$ ) 7: $L,U\leftarrow 1,\infty$ 8: while $L+1<U$ do 9: $k\leftarrow\begin{cases}2\cdot L&\text{if }U=\infty\\ \lfloor\frac{L+U}{2}\rfloor&\text{otherwise}\end{cases}$ 10: $L,U\leftarrow\begin{cases}k,U&\text{if }\textsc{Schedulable}(\mathcal{M}, \mathcal{T},k)\\ L,k&\text{otherwise}\end{cases}$ 11: $\textbf{return}\ \{(\tau,\lfloor L\cdot\overline{v}_{\tau}\rfloor)\ |\ \tau\in \mathcal{T}\}$ We use the execution time budget $B_{\tau}$ as an upper bound for the WCET of the task $\tau$ while trying to maximize its particle count $n_{\tau}$ . We need to carefully adjust the particle counts of tasks, as they may depend on each other. Assume we have a maximum particle count $n_{\tau}$ for a task $\tau$ . Increasing the particle count of a predecessor task $\tau^{\prime}$ of $\tau$ causes the execution time of $\tau$ to increase. However, if we keep the particle count of all predecessors fixed, the WCET $C_{\tau}$ of a task $\tau$ is proportional to its particle count $n_{\tau}$ . This enables using binary search to find the maximum $n_{\tau}$ . We use these observations in the Configure EF function of Algorithm 3, which returns the particle count $N_{\tau}$ to use for each task $\tau$ . We keep track of a set of active tasks $A$ with no active predecessors (initialized on line 10). We use $P_{\tau}$ to denote the set of predecessors of a task $\tau$ . Note on line 12 that the finished set $F$ is initialized to contain all tasks with importance zero (tasks $\tau$ that perform no inference are assumed to have $v_{\tau}=0$ ). While we have active tasks, we use the RunTasks function to measure the WCETs of all tasks (line 14). We keep track of lower and upper bounds, $L_{\tau}$ and $U_{\tau}$ , of the particle count for each task $\tau$ . For each active task $\tau$ , we compare its measured WCET $W_{\tau}$ to its budget $B_{\tau}$ and update the bounds accordingly (lines 16 - 19). When the binary search concludes, we set the particle count $N_{\tau}$ to the lower bound and add the task $\tau$ to the set of finished tasks $F$ (line 19). At the end of each iteration, we update the set of active tasks (line 20). When the active set $A$ is empty, the resulting particle counts $N$ are returned. Note that the algorithm assumes that the task dependency graph is acyclic. ### VI-C Particle Fairness To achieve particle fairness, we seek a multiple $k$ such that $n_{\tau}=\lfloor k\cdot\overline{v}_{\tau}\rfloor$ for all tasks $\tau$ , where $\overline{v}_{\tau}$ is the normalized importance value . When we increase the value of $k$ , the execution time of all tasks increases, meaning we can binary search to find the maximum $k$ . For a given $k$ , we need to determine whether the tasks are schedulable. We do this in the Schedulable function on lines 1 - 5 of Algorithm 4. We set the number of particles for each task (line 2) and run them (line 3). Then, we set the WCET $C_{\tau}$ of the tasks based on their measured WCETs (line 4) and perform a response time analysis [29] to ensure the tasks are schedulable (line 5). We use the Schedulable function in the particle fairness function Configure PF (lines 6 - 11). We define the lower and upper bounds $L$ and $U$ on line 7, and we binary search in this interval on lines 8 - 10. After the loop, the maximum multiple for which the system is schedulable is stored in $L$ . Based on this, we compute the particle count of each $\tau$ on line 11. ## VII Automotive Case Study To demonstrate the applicability of ProbTime to program time-critical embedded systems, we develop a case study for a localization pipeline in an automotive testbed. This section first introduces the testbed, followed by an evaluation of ProbTime. ### VII-A Automotive Testbed The automotive industry is undergoing a paradigm shift to face the challenges that emerge through the advent of autonomous driving [30]. These challenges require higher computational capacities and larger communication bandwidth than traditional automotive systems. This transition leads to a software-defined vehicle where almost all functions of the car will be enabled by software [31]. To demonstrate the applicability of our proposed methods in this context, we have developed an automotive testbed. #### VII-A 1 Hardware The testbed is designed around a 1:10 scale RC car. The E/E architecture consists of several distributed compute nodes of different characteristics connected via bus- and network-based interconnects (see Fig. 7). <details> <summary>x9.png Details</summary>  ### Visual Description ## Diagram: Autonomous Vehicle Sensor Placement ### Overview The image shows a diagram of an autonomous vehicle with sensor placements, alongside a photograph of the actual vehicle. The diagram illustrates the positioning of Time-of-Flight sensors and Speed sensors on the vehicle. The photograph provides a view of the vehicle's hardware components. ### Components/Axes * **Legend (Top-Left)**: * Green Triangle: Time-of-Flight Sensor * Red Rectangle: Speed Sensor * **Vehicle Diagram**: * Direction: Indicated by a white arrow pointing forward. * Front: Labeled on the left side of the vehicle diagram. * Right: Labeled above the right side Time-of-Flight sensor. * Left: Labeled below the left side Time-of-Flight sensor. * **Measurements**: * Distance between front Time-of-Flight sensor and the front of the vehicle: 1.25m * Angle of the right Time-of-Flight sensor: 15 degrees. ### Detailed Analysis or ### Content Details * **Time-of-Flight Sensors**: * Front: One green triangle indicating a Time-of-Flight sensor pointing forward. * Right: One green triangle indicating a Time-of-Flight sensor pointing to the right at a 15-degree angle. * Left: One green triangle indicating a Time-of-Flight sensor pointing to the left. * **Speed Sensors**: * Two red rectangles on the rear of the vehicle, indicating the placement of speed sensors. * **Vehicle Photograph**: * Shows the physical construction of the autonomous vehicle, including the chassis, wheels, and electronic components (Raspberry Pi boards, etc.). ### Key Observations * The diagram provides a clear overview of the sensor placement strategy on the autonomous vehicle. * The photograph gives a realistic view of the vehicle's hardware setup. * The Time-of-Flight sensors are positioned to provide distance measurements in the front, left, and right directions. * The Speed sensors are located at the rear of the vehicle. ### Interpretation The image illustrates the sensor configuration of an autonomous vehicle, combining a schematic diagram with a real-world photograph. The Time-of-Flight sensors enable the vehicle to perceive its surroundings by measuring distances, while the Speed sensors provide information about the vehicle's movement. The 15-degree angle of the right Time-of-Flight sensor suggests a specific design choice for obstacle detection or navigation. The combination of these sensors allows the vehicle to navigate autonomously by perceiving its environment and controlling its movement. </details> Figure 7: Overview of the sensors on the car (left) and a picture of the RC-Car testbed (right). Two microcontroller-based compute nodes act as the interface to most actuators and sensors of the car. High-performance compute nodes provide the required performance to host computation required for Advanced Driving Assistance (ADAS) or Autonomous Driving (AD) workloads. We use a Raspberry Pi 4B (4 Cortex-A72 cores at 1.5GHz). These compute nodes are connected by a local Ethernet network. We use three Time-of-Flight (TOF) sensors installed on the car, as indicated in Fig. 7. These sensors have high accuracy but can only measure distances up to $1.25~{}\text{m}$ . The front wheel sensors report the current speed of the car. #### VII-A 2 Software <details> <summary>x10.png Details</summary>  ### Visual Description ## Diagram: Software Compilation Process ### Overview The image is a diagram illustrating a software compilation process. It shows the flow of data and transformations from initial specifications to final executable files. The process involves several stages, including system declaration, platform specification, mapping, code generation, and compilation. ### Components/Axes The diagram consists of rectangular blocks representing different stages or data types, connected by arrows indicating the flow of information. * **Blocks (Grey):** * System Declaration * Platform Specification * Mapping * Platform .c/.h (multiple instances) * ProbTime Interface .c/.h * Platform Executables (multiple instances) * **Blocks (Blue):** * Code Generation * Compiler * **Arrows:** Indicate the direction of data flow between the blocks. ### Detailed Analysis or ### Content Details 1. **System Declaration:** Located at the top-left. 2. **Platform Specification:** Located at the top-center. 3. **Mapping:** Located at the bottom-left, below "System Declaration". 4. **Code Generation:** Located at the bottom-center, below "Platform Specification" and to the right of "Mapping". This block is blue. 5. **Platform .c/.h:** Located at the top-right, multiple instances stacked. 6. **ProbTime Interface .c/.h:** Located at the bottom-right, to the right of "Code Generation". 7. **Compiler:** Located in the center-right, to the right of "Platform .c/.h" and "ProbTime Interface .c/.h". This block is blue. 8. **Platform Executables:** Located at the far-right, multiple instances stacked. The arrows indicate the following flow: * System Declaration -> Code Generation * Platform Specification -> Code Generation * Mapping -> Code Generation * Code Generation -> Compiler * Platform .c/.h -> Compiler * ProbTime Interface .c/.h -> Compiler * Compiler -> Platform Executables ### Key Observations * The diagram illustrates a sequential process, with data flowing from left to right. * The "Code Generation" and "Compiler" stages are highlighted in blue, possibly indicating key processing steps. * The diagram shows multiple instances of "Platform .c/.h" and "Platform Executables", suggesting that these are collections of files. ### Interpretation The diagram represents a typical software compilation process. It starts with high-level specifications (System Declaration, Platform Specification) and mapping information. These inputs are used to generate code, which is then compiled along with platform-specific and interface files to produce executable files. The use of blue for "Code Generation" and "Compiler" suggests these are the core transformation steps in the process. The multiple instances of "Platform .c/.h" and "Platform Executables" indicate that the compilation process may generate multiple output files for different platforms or components. </details> Figure 8: Code generation and compilation of the platform code, including a ProbTime interface. The operating system on the Raspberry Pi 4B compute node is Linux-based with kernel 5.15.55-rt48-v8+ SMP PREEMPT_RT. The platform software is responsible for reading sensor data and controlling actuators. This is realized by dedicated periodic tasks distributed on different compute nodes. Each task is assigned a static priority and is mapped to a CPU core. Platform software realizes communication between ProbTime tasks by communication buffers located in shared memory. Additionally, sensor data is written to ProbTime communication buffers and from buffers to actuators. We use code generation to produce the files that constitute the interface to a specific ProbTime program (see Fig. 8). Input to the code generation is the system declaration describing the ProbTime program. The remaining platform software is not affected by code generation. The compiler produces an executable for each compute node in the final step. ### VII-B Evaluation Questions To evaluate ProbTime and our automatic configuration, we pose the following evaluation questions: 1. To what extent can ProbTime’s timing and probabilistic constructs be used to implement a realistic application? 1. What is the trade-off between the number of particles, execution time, and inference accuracy? 1. How does execution-time fairness compare to particle fairness concerning allocation of particles and inference time when varying the importance of tasks? 1. To what extent and accuracy can the case study—when executed on the physical car—determine the position and avoid collision? ### VII-C Positioning and Braking in ProbTime (Q1) We implement a positioning and braking system in ProbTime as a case study. The system estimates the position of the RC car while it is moving using sensor inputs. Further, the system reacts by braking to prevent collisions with obstacles. We present an overview of our positioning and braking system in Fig. 9. The figure shows the sensor inputs on the left-hand side. The steering angle is an input signal from the controller, while the other five sensors are directly related to sensors on the car (as shown in Fig. 7). We use the brake actuator (right-hand side) to activate the emergency brakes. <details> <summary>x11.png Details</summary>  ### Visual Description ## Diagram: Braking System Logic ### Overview The image is a block diagram illustrating the logic flow of a braking system. It shows how various sensor inputs (speed, distance, steering angle) are processed to determine the braking force. ### Components/Axes * **Input Sensors (Left Side):** These are represented by ovals. * `speedLeft`: Left wheel speed. * `speedRight`: Right wheel speed. * `sideLeft`: Distance to an object on the left side. * `sideRight`: Distance to an object on the right side. * `frontCenter`: Distance to an object in front. * `steeringAngle`: Steering wheel angle. * **Processing Blocks (Center):** These are represented by rectangles. * `speed`: Processes `speedLeft` and `speedRight`. * `distance_SL`: Processes `sideLeft`. * `distance_SR`: Processes `sideRight`. * `distance_FC`: Processes `frontCenter`. * `pos`: Processes the outputs of `speed`, `distance_SL`, `distance_SR`, and `distance_FC`. * `braking`: Processes the output of `pos`. * **Output (Right Side):** * `brake`: Represented by an oval, indicating the final braking output. * **Connections:** Lines with arrowheads indicate the flow of information between the components. ### Detailed Analysis * `speedLeft` and `speedRight` feed into the `speed` processing block. * `sideLeft` feeds into the `distance_SL` processing block. * `sideRight` feeds into the `distance_SR` processing block. * `frontCenter` feeds into the `distance_FC` processing block. * The outputs of `speed`, `distance_SL`, `distance_SR`, and `distance_FC` are inputs to the `pos` processing block. * The output of `pos` is the input to the `braking` processing block. * The output of `braking` is the final `brake` output. * There is a feedback loop from the output of the `speed` block to the input of the `pos` block. * There is a feedback loop from the output of the `distance_FC` block to the input of the `pos` block. ### Key Observations * The diagram illustrates a closed-loop control system for braking. * Multiple sensor inputs are used to determine the braking force. * The `pos` block appears to be a central processing unit that integrates the sensor data. * The `braking` block likely implements the braking control algorithm. ### Interpretation The diagram represents a simplified model of an advanced braking system, potentially an anti-lock braking system (ABS) or an autonomous emergency braking (AEB) system. The system uses various sensors to monitor the vehicle's speed, proximity to obstacles, and steering angle. This information is then processed to determine the appropriate braking force, which is applied to the wheels. The feedback loops suggest that the system continuously adjusts the braking force based on the vehicle's response. The system aims to optimize braking performance and prevent skidding or collisions. </details> Figure 9: A graphical representation of the positioning and braking system. The squares of Fig. 9 represent the tasks. We instantiate all distance estimation tasks (distance_SL, distance_SR, and distance_FC) from the same template. All tasks have a period of $500\text{\,}\mathrm{ms}$ except pos, which has a period of $1\text{\,}\mathrm{s}$ . We use the speed task to estimate the car’s average speed since the last estimation based on speed observations from the wheels. Preliminary experiments show that the speed sensors are inaccurate at low speeds and that the top speed is reached almost instantaneously when accelerating. Due to the predictable behavior of the speed, we model it as being in one of three states: stationary, max speed, or transitioning (either accelerating or decelerating). This is simpler than using Bayesian linear regression (as we did in the speed model in Listing 2) and computationally cheaper. Our positioning task estimates the x- and y-coordinates of the car’s center. It also estimates the direction the car faces relative to an encoded map of the environment (provided by the user). The model starts from a prior belief of the position (initially, a known starting position) and estimates a trajectory along which the car moved until the current logical time of the task based on steering angle observations and speed estimations. We update our belief by comparing each input distance estimation with what the sensor would have observed at that timestamp, given that the car followed the estimated trajectory. We implement this using Bayesian linear regression. The braking task uses a probabilistic model to estimate the distance until a collision occurs, given steering angle observations, an encoded map, and the speed and position estimations. We activate the emergency brakes if the median distance is estimated to be below a fixed threshold. In response to Q1, the current case study demonstrates that a non-trivial application can be efficiently implemented in ProbTime (using 600 lines of code). ### VII-D Experiments and Results To answer evaluation questions Q2, Q3, and Q4, we perform three experiments on the positioning system of Fig. 9. We want to run as many particles per iteration as possible for the first experiment. Therefore, we run this on an Intel(R) Xeon(R) Gold 6148 CPU with 64 GB RAM using Ubuntu 22.04. We use the Raspberry Pi on the car for the second and third experiments. The first two experiments use pre-recorded data in a simulation, while the third uses live data. When discussing results or settings, we only consider the pos and braking tasks, as the other tasks perform no inference. The pos and braking tasks run on separate cores. #### VII-D 1 Positioning Inference Accuracy (Q2) We investigate how the number of particles impacts the inference accuracy and execution times. To be able to run more particles per inference, we perform a slow mode simulation where the replaying of observation data and the ProbTime tasks consider time to pass slower relative to the wall time. We use position estimates as a measure of inference accuracy because they are easily compared to a known final position from pre-recorded data. In this experiment, we vary the particle count of the pos task while fixing the particle count of braking. In Fig. 10, we present the average position error along the x- and y-axis (left) and the WCETs (right) for the two tasks over $100$ runs with varying particle counts in the positioning task. Note that the positioning model often fails to track the car when using $10^{2}$ particles. The estimation error along both axes decreases drastically as we increase the number of particles, mainly when increasing from $10^{2}$ to $10^{3}$ particles. The increased variance going from $10^{4}$ to $10^{5}$ particles is likely due to inaccuracies in our model. The WCET of the pos task scales linearly with the number of particles (note the logarithmic axes), while the braking task becomes noticeably slower when we increase the number of particles to $10^{5}$ . This is because it processes a position distribution sent from the pos task (i.e., braking depends on pos). In connection to Q2, we have seen the impact of particle count on the inference accuracy. Few particles lead to a big uncertainty, and the benefit of increasing the particle count is negligible past a certain point. We also see that the number of particles is linearly connected to the WCET and that the particle count of a task may impact the WCET of other tasks. <details> <summary>x12.png Details</summary>  ### Visual Description ## Combined Chart: Error vs. #particles and WCET vs. #particles ### Overview The image presents two charts side-by-side. The left chart is a violin plot showing the distribution of x-error and y-error as a function of the number of particles. The right chart is a bar plot showing the Worst-Case Execution Time (WCET) for 'pos' and 'braking' as a function of the number of particles. Both charts share the same x-axis: '#particles'. Both charts use a log scale for both axes. ### Components/Axes **Left Chart (Error vs. #particles):** * **Y-axis:** "Error (m)" - Logarithmic scale with markers at 10^-2, 10⁰, and 10². * **X-axis:** "#particles" - Logarithmic scale with markers at 10², 10³, 10⁴, and 10⁵. * **Legend (Top-Right):** * "x-error" - Light Blue * "y-error" - Light Orange **Right Chart (WCET vs. #particles):** * **Y-axis:** "WCET (s)" - Logarithmic scale with markers at 10^-1 and 10⁰. * **X-axis:** "#particles" - Logarithmic scale with markers at 10², 10³, 10⁴, and 10⁵. * **Legend (Top-Left):** * "pos" - Dark Blue * "braking" - Orange ### Detailed Analysis **Left Chart (Error vs. #particles):** * **x-error (Light Blue):** * At 10² particles: The distribution is centered around 10¹ m, with a wide spread. * At 10³ particles: The distribution is centered around 10^-1 m, with a smaller spread. * At 10⁴ particles: The distribution is centered around 10^-1 m, with a smaller spread. * At 10⁵ particles: The distribution is centered around 10^-1 m, with a smaller spread. * Trend: The x-error decreases significantly as the number of particles increases from 10² to 10³, then plateaus. * **y-error (Light Orange):** * At 10² particles: The distribution is centered around 10^-2 m, with a wide spread. * At 10³ particles: The distribution is centered around 10^-2 m, with a smaller spread. * At 10⁴ particles: The distribution is centered around 10^-1 m, with a smaller spread. * At 10⁵ particles: The distribution is centered around 10^-1 m, with a smaller spread. * Trend: The y-error remains relatively constant as the number of particles increases, with a slight increase between 10³ and 10⁴. **Right Chart (WCET vs. #particles):** * **pos (Dark Blue):** * At 10² particles: WCET is approximately 0.02 s. * At 10³ particles: WCET is approximately 0.2 s. * At 10⁴ particles: WCET is approximately 0.6 s. * At 10⁵ particles: WCET is approximately 2 s. * Trend: The WCET for 'pos' increases significantly as the number of particles increases. * **braking (Orange):** * At 10² particles: WCET is approximately 0.08 s. * At 10³ particles: WCET is approximately 0.15 s. * At 10⁴ particles: WCET is approximately 0.2 s. * At 10⁵ particles: WCET is approximately 0.4 s. * Trend: The WCET for 'braking' increases as the number of particles increases, but not as dramatically as 'pos'. ### Key Observations * Increasing the number of particles significantly reduces the x-error, especially between 10² and 10³ particles. * The y-error is less sensitive to the number of particles. * The WCET for both 'pos' and 'braking' increases with the number of particles, but 'pos' is more affected. * At 10^5 particles, the WCET for 'pos' is significantly higher than 'braking'. ### Interpretation The data suggests that increasing the number of particles improves the accuracy of the 'x' position estimate, with diminishing returns beyond 10³ particles. The 'y' position estimate is less affected by the number of particles. However, increasing the number of particles increases the computational cost, as reflected in the WCET. The 'pos' operation is more computationally expensive than 'braking' and its cost increases more rapidly with the number of particles. This information is useful for optimizing the particle filter algorithm, balancing accuracy and computational cost. </details> Figure 10: Results showing the estimation error along the x- and y-axis of the car (left) and the WCETs (right) over ten runs, varying the number of particles in the positioning model. Both figures have a logarithmic x- and y-axis. #### VII-D 2 Automatic Configuration (Q3) To compare the automatic configuration using execution-time and particle fairness, we vary the ratio of importance between the pos and braking tasks. For each ratio, we measure the particle count and WCET of the configured tasks and the number of iterations needed to configure the system. The resulting ratio of particle count and execution time is presented in Fig. 11. In our experiment, we vary the importance ratio between tasks by powers of two until the starting state cannot be scheduled. As expected, both approaches to fairness have one property scaling at the same rate as the importance ratio (WCET ratio for execution-time fairness and particle count ratio for particle fairness). The WCET ratio for particle fairness peaks when the ratio imbalance is too large (e.g., when the ratio is $2^{8}$ ) as the more important task fully utilizes its core. Increasing the ratio imbalance past this point only causes the less important task to run fewer particles. For execution-time fairness, this imbalance results in the less important task being allocated an insufficient budget due to fair utilization. Execution-time fairness needs $48.8\pm 11.8$ iterations (mean and standard deviation) to configure all tasks compared to $16.5\pm 2.8$ for particle fairness. Recall from Sec. VI that execution-time fairness considers task dependencies while particle fairness runs independently of them. For our model, the problem of task dependencies is hardly noticeable. However, what if the speed task also performed inference? To investigate this, we configure a variant of the positioning and braking model where speed performs inference, with it running on a separate core from pos and braking, and all three tasks have the same importance. We find that the tasks all get $385$ particles using particle fairness, whereas using execution-time fairness, pos gets $21$ particles, braking gets $95$ particles, and speed gets $24199$ particles. For execution-time fairness, the speed task has time to run many particles, which slows down the other tasks that depend on its output. This issue could be mitigated by setting an upper bound on the particle count (machine-specific) or by giving pos and braking higher importance. <details> <summary>x13.png Details</summary>  ### Visual Description ## Log-Log Plot: Ratio of Particles or WCET vs. Importance Ratio ### Overview The image is a log-log plot comparing the ratio of particles or Worst-Case Execution Time (WCET) against the importance ratio (positive / braking). Four different data series are plotted: EF_P, EF_W, PF_P, and PF_W. The plot shows how these ratios change with varying importance ratios. ### Components/Axes * **X-axis:** Importance Ratio (pos / braking). The x-axis is scaled logarithmically with base 2, ranging from 2^-10 to 2¹⁰. The x-axis markers are: 2^-10, 2^-8, 2^-6, 2^-4, 2^-2, 2⁰, 2², 2⁴, 2⁶, 2⁸, 2¹⁰. * **Y-axis:** Ratio of particles or WCET. The y-axis is scaled logarithmically with base 2, ranging from 2^-10 to 2¹⁰. The y-axis markers are: 2^-10, 2^-8, 2^-6, 2^-4, 2^-2, 2⁰, 2², 2⁴, 2⁶, 2⁸, 2¹⁰. * **Legend:** Located in the top-left corner of the plot. * **EF_P:** Orange line with '+' markers. * **EF_W:** Yellow-orange line with triangle markers. * **PF_P:** Light blue line with 'x' markers. * **PF_W:** Blue line with square markers. ### Detailed Analysis * **EF_P (Orange, '+'):** Initially, the line is at approximately 2^-6 at x=2^-8. The line generally slopes upward, increasing more rapidly after x=2⁰. At x=2⁶, the value is approximately 2⁹. At x=2¹⁰, the value is approximately 2¹⁰. * **EF_W (Yellow-Orange, Triangle):** Starts at approximately 2^-6 at x=2^-8. The line generally slopes upward, increasing more rapidly after x=2⁰. At x=2⁶, the value is approximately 2⁶. At x=2¹⁰, the value is approximately 2⁹. * **PF_P (Light Blue, 'x'):** Starts at approximately 2^-10 at x=2^-10. The line generally slopes upward. At x=2⁶, the value is approximately 2⁵. At x=2¹⁰, the value is approximately 2⁹. * **PF_W (Blue, Square):** Starts at approximately 2^-5 at x=2^-10. The line is relatively flat until x=2^-4, then slopes upward. The line plateaus again after x=2⁴. At x=2⁶, the value is approximately 2⁵. At x=2¹⁰, the value is approximately 2⁶. ### Key Observations * For lower importance ratios (left side of the plot), PF_P has the lowest ratio of particles or WCET, while EF_P and EF_W have similar values. PF_W starts higher than PF_P, but remains relatively flat for a while. * As the importance ratio increases (right side of the plot), all lines generally increase, but at different rates. EF_P shows the most rapid increase, followed by EF_W and PF_P. PF_W increases the least and plateaus. * The lines for EF_P and EF_W are very close to each other, suggesting a similar relationship between importance ratio and the ratio of particles or WCET. * The lines for PF_P and PF_W diverge significantly as the importance ratio increases, indicating different behaviors. ### Interpretation The plot illustrates the relationship between the importance ratio (positive / braking) and the ratio of particles or WCET for four different configurations (EF_P, EF_W, PF_P, PF_W). The data suggests that: * The "EF" configurations (EF_P, EF_W) are more sensitive to changes in the importance ratio than the "PF" configurations (PF_P, PF_W), especially at higher importance ratios. This is evident from the steeper slopes of the EF_P and EF_W lines. * The "PF_W" configuration appears to be less affected by the importance ratio, as its line plateaus at higher importance ratios. This could indicate a saturation effect or a different underlying mechanism. * The "PF_P" configuration shows a more gradual increase with the importance ratio compared to "EF_P" and "EF_W", suggesting a more stable or predictable behavior. * The initial differences at low importance ratios suggest that the configurations have different baseline performance characteristics. The plot highlights the trade-offs between different configurations and how their performance varies with the importance ratio. This information can be used to select the most appropriate configuration for a given application or scenario. </details> Figure 11: The ratio of particles (using suffix P) and worst-case execution time (suffix W) when varying the importance ratio. We use prefix EF for execution-time fairness results and PF for particle fairness. Note the logarithmic x- and y-axes. <details> <summary>extracted/5716520/figures/corridor.png Details</summary>  ### Visual Description ## Heatmap: Room Occupancy ### Overview The image is a heatmap representing occupancy within a room. The room layout is depicted with walls and open spaces. The heatmap uses color intensity to indicate the level of occupancy, with brighter colors (yellow/green) indicating higher occupancy and darker colors (purple/black) indicating lower or no occupancy. ### Components/Axes * **Room Layout:** The image shows the floor plan of a room, including walls and openings. The central area is a large, open space. * **Heatmap Overlay:** A color gradient is overlaid on the room layout to represent occupancy levels. * **Color Gradient:** The color gradient ranges from dark purple/black (low occupancy) to green/yellow (high occupancy). There is no explicit legend provided, so the exact occupancy values associated with each color are unknown. ### Detailed Analysis * **High Occupancy Area:** There is a distinct area of high occupancy in the top-right corner of the room. This area is represented by a bright yellow/green color, indicating a concentration of people or activity. * **Low Occupancy Areas:** The central area of the room and most of the surrounding space show low occupancy, indicated by the dark purple/black color. * **Other Occupancy Points:** There is a small area of slightly elevated occupancy near the bottom-left of the room. ### Key Observations * The heatmap suggests that the top-right corner of the room is the most frequently used or occupied area. * The central area of the room is largely unoccupied. * There is a minor occupancy point in the bottom-left. ### Interpretation The heatmap provides a visual representation of how space is utilized within the room. The concentration of occupancy in the top-right corner could be due to the placement of furniture, equipment, or a specific activity that attracts people to that area. The low occupancy in the central area suggests that it may be used for circulation or is simply not a desirable location for people to congregate. The small occupancy point in the bottom-left could be due to a doorway or another point of interest. Without additional context, it is difficult to determine the exact reasons for the observed occupancy patterns. </details> Figure 12: The encoded map ( $18.6\text{\,}\mathrm{m}$ x $9.5\text{\,}\mathrm{m}$ ) of the corridor in which we drive the car. The overlay shows particles spreading when less information is available (top-right) and gathering when close to distinguishable obstacles (bottom-left). In connection to Q3, we argue that particle fairness is preferable. First, the problems above only apply to execution-time fairness. Second, there is a direct connection between particle count and inference accuracy. Therefore, we argue that reasoning about the allocation of particles directly seems more natural than doing it in terms of execution time. #### VII-D 3 Positioning and Braking (Q4) For this experiment, we run the tasks on the physical car. To evaluate the positioning model, we drive the car around in a corridor (Fig. 12). As we measure the car’s position by hand, we can only make measurements when the car is stationary. Therefore, we drive it from a known starting position and compare the actual final position to the last position estimated by the model. We drive the car in a clockwise direction for a full lap ten times using two distinct scenarios to illustrate how environmental details impact the accuracy of the position estimates. In scenario 1, we start at the bottom-left corner and drive past the starting point. In scenario 2, we begin in the top-right corner and stop along the long corridor at the top. During preliminary evaluations, we found that using importance $4$ for pos and $1$ for braking yields good results. The configured system runs inference using $1312$ particles in pos and $328$ in braking. We evaluate the automated braking by driving the car around in the corridor. We find that the emergency brakes are conservative—while they prevent collisions, they often activate in situations where it is unnecessary. This is due to uncertainty in the position estimations. Due to the conservative nature of the braking task, we turn off the brake actuator when evaluating the positioning model. We present the positioning results in Table I. The error along the y-axis is small in scenario 2 because both side sensors are in range in the narrow corridor where the car stops, while the x-axis error is large because the front distance sensor is outside of its range in the corridor. Despite the short range of our sensors, the lack of distinguishing details in the environment, and the limited computational power of the car testbed, our model successfully tracks the car for a full lap in the corridor. Tracking the car in itself is not a novelty, but it shows that the methodology works in practice for a non-trivial application. TABLE I: Results showing the average error in the x- and y-direction (in meters) and the Euclidean distance for our two scenarios, with standard deviations. | 1 2 | $0.50\pm 0.58$ $1.19\pm 0.79$ | $0.28\pm 0.23$ $0.24\pm 0.14$ | $0.63\pm 0.56$ $1.21\pm 0.80$ | | --- | --- | --- | --- | ## VIII Related Work Although surprisingly little has been done in the intersection of probabilistic programming and languages for real-time systems, there is a large body of work in each category. This section gives a summary of the closest related work. Probabilistic programming languages. Languages for performing Bayesian inference date back to the early 1990s, where BUGS [32] is one of the earliest languages for Bayesian networks. The term probabilistic programming was coined much later but is now generally used for all languages performing Bayesian inference. Starting with the Church language [33], a new, more general form of probabilistic programming languages emerged, called universal PPLs. In such languages, the probabilistic model is encoded in a Turing complete language, which enables stochastic branching and possibly an infinite number of random variables. There exist many experimental PPLs in this category, e.g., Gen [11], Anglican [9], Turing [10], WebPPL [7], Pyro [6], and CorePPL [12]. Other state-of-the-art PPL environments are, e.g., Stan [8] and Infer.NET. Similar to many of these environments, ProbTime also makes use of the standard core constructs (sample, observe, and infer), where the key difference is that time and timeliness are also taken into consideration in ProbTime. Real-time programming languages. There exists a quite large body of literature on programming languages that incorporate time and timing as part of the language semantics. Ada [19] has explicit support for timed language constructs, and the real-time extension to Java [34] supports time and event handling. Recently, Timed C was proposed in the research literature to incorporate timing constructs directly in the language. The Timed C work was later extended to support sensitivity analysis [35]. Our work has been inspired by Timed C; the semantics for periodic is loosely based on sdelay in Timed C, although the implementation is different. As in Timed C, ProbTime introduces tagging with timestamps. There are several other languages and environments that have timestamped and tagged values as central semantic concepts. For instance, PTIDES [36] extends the discrete-event (DE) model. Lingua Franca [18] is another recent effort that introduces deterministic actors called reactors, whose only means of communication is through an ordered set of reactions. Synchronous programming. There are also other approaches to programming real-time systems where time is abstracted as ticks. Specifically, the synchronous programming paradigm [37] implements such an approach, where ProbZelus [20] is a recent programming language extending synchronous reactive programming with probabilistic constructs. The ProbZelus work is based on the delayed sampling concept [38] to automatically make inference efficient when conjugate priors can be exposed in the model. A key difference between ProbZelus and ProbTime is our concept of fairness, where the number of particles used in inference is automatically adjusted based on user-provided importance values. Reward-based scheduling. Our automatic configuration is related to reward-based scheduling [39], where tasks consist of a mandatory and an optional part. A non-decreasing reward function maps the time spent running the optional part to a real value. This approach aims to find a schedule for maximizing the reward while all tasks remain schedulable. In ProbTime, inference is the optional part of tasks as we can vary how many particles we use. The importance values assigned to tasks implicitly encode a reward function. ## IX Conclusion In this paper, we introduce a new kind of language called real-time probabilistic programming language (RTPPL). To demonstrate this new kind of language, we develop and analyze a domain-specific RTPPL called ProbTime. We also introduce the concepts of fairness in RTPPLs and illustrate the strength of particle fairness. ## Acknowledgment We would like to thank John Wikman, Linnea Stjerna, Gizem Çaylak, Viktor Palmkvist, Anders Ågren Thuné, Thilanka Thilakasiri, and Rodolfo Jordão for their valuable feedback. This project is financially supported by the Swedish Foundation for Strategic Research (FFL15-0032 and RIT15-0012). The research has also been carried out as part of the Vinnova Competence Center for Trustworthy Edge Computing Systems and Applications (TECoSA) at the KTH Royal Institute of Technology. ## References - [1] A. D. Gordon, T. A. Henzinger, A. V. Nori, and S. K. Rajamani, “Probabilistic programming,” in Proceedings of the on Future of Software Engineering. ACM, 2014, pp. 167–181. - [2] J.-W. van de Meent, B. Paige, H. Yang, and F. Wood, “An introduction to probabilistic programming,” arXiv preprint arXiv:1809.10756, 2018. - [3] A. Doucet, N. De Freitas, and N. Gordon, “An introductiona to sequential Monte Carlo methods,” Sequential Monte Carlo methods in practice, pp. 3–14, 2001. - [4] Lundén, Daniel and Borgström, Johannes and Broman, David, “Correctness of Sequential Monte Carlo Inference for Probabilistic Programming Languages,” in Proceedings of 30th European Symposium on Programming (ESOP), ser. LNCS, vol. 12648. Springer, 2021, pp. 404–431. - [5] S. Brooks, “Markov chain Monte Carlo method and its application,” Journal of the royal statistical society: series D (the Statistician), vol. 47, no. 1, pp. 69–100, 1998. - [6] E. Bingham, J. P. Chen, M. Jankowiak, F. Obermeyer, N. Pradhan, T. Karaletsos, R. Singh, P. Szerlip, P. Horsfall, and N. D. Goodman, “Pyro: Deep Universal Probabilistic Programming,” Journal of Machine Learning Research, vol. 20, no. 28, pp. 1–6, 2019. - [7] N. D. Goodman and A. Stuhlmüller, “The Design and Implementation of Probabilistic Programming Languages,” http://dippl.org/ [Last accessed: May 17, 2023]. - [8] B. Carpenter, A. Gelman, M. D. Hoffman, D. Lee, B. Goodrich, M. Betancourt, M. Brubaker, J. Guo, P. Li, and A. Riddell, “Stan: A probabilistic programming language,” Journal of Statistical Software, vol. 76, no. 1, 2017. - [9] D. Tolpin, J.-W. van de Meent, H. Yang, and F. Wood, “Design and implementation of probabilistic programming language anglican,” in Proceedings of the 28th Symposium on the Implementation and Application of Functional Programming Languages, ser. IFL 2016. New York, NY, USA: ACM, 2016, pp. 6:1–6:12. - [10] H. Ge, K. Xu, and Z. Ghahramani, “Turing: a language for flexible probabilistic inference,” in International conference on artificial intelligence and statistics (AISTATS). PMLR, 2018, pp. 1682–1690. - [11] M. F. Cusumano-Towner, F. A. Saad, A. K. Lew, and V. K. Mansinghka, “Gen: a general-purpose probabilistic programming system with programmable inference,” in Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). ACM, 2019, pp. 221–236. - [12] Lundén, Daniel and Öhman, Joey and Kudlicka, Jan and Senderov, Viktor and Ronquist, Fredrik and Broman, David, “Compiling Universal Probabilistic Programming Languages with Efficient Parallel Sequential Monte Carlo Inference,” in Proceedings of 31th European Symposium on Programming (ESOP), 2022, pp. 29–56. - [13] A. Lew, M. Agrawal, D. Sontag, and V. Mansinghka, “PClean: Bayesian data cleaning at scale with domain-specific probabilistic programming,” in International Conference on Artificial Intelligence and Statistics (AISTATS). PMLR, 2021, pp. 1927–1935. - [14] F. Ronquist, J. Kudlicka, V. Senderov, J. Borgström, N. Lartillot, D. Lundén, L. Murray, T. B. Schön, and D. Broman, “Universal probabilistic programming offers a powerful approach to statistical phylogenetics,” Communications Biology, vol. 4, no. 1, pp. 1–10, 2021. - [15] N. Gothoskar, M. Cusumano-Towner, B. Zinberg, M. Ghavamizadeh, F. Pollok, A. Garrett, J. Tenenbaum, D. Gutfreund, and V. Mansinghka, “3DP3: 3D Scene Perception via Probabilistic Programming,” Advances in Neural Information Processing Systems (NeurIPS), vol. 34, pp. 9600–9612, 2021. - [16] N. D. Goodman, J. B. Tenenbaum, and T. P. Contributors, “Probabilistic Models of Cognition,” 2016, (2nd ed.) https://probmods.org/ [Last accessed: May 17, 2023]. - [17] S. Natarajan and D. Broman, “Timed C: An Extension to the C Programming Language for Real-Time Systems,” in Proceedings of IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2018. - [18] 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), vol. 20, no. 4, pp. 1–27, 2021. - [19] A. Burns and A. Wellings, Concurrent and real-time programming in Ada. Cambridge University Press, 2007. - [20] G. Baudart, L. Mandel, E. Atkinson, B. Sherman, M. Pouzet, and M. Carbin, “Reactive Probabilistic Programming,” in Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2020, pp. 898–912. - [21] G. Baudart, L. Mandel, and R. Tekin, “Jax based parallel inference for reactive probabilistic programming,” in Proceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems, 2022, pp. 26–36. - [22] A. Pfeffer, “Ctppl: A continuous time probabilistic programming language.” in IJCAI, 2009, pp. 1943–1950. - [23] D. Broman, “A Vision of Miking: Interactive Programmatic Modeling, Sound Language Composition, and Self-Learning Compilation,” in Proceedings of the 12th ACM SIGPLAN International Conference on Software Language Engineering, ser. SLE ’19. ACM, 2019, pp. 55–60. - [24] F. Gustafsson, F. Gunnarsson, N. Bergman, U. Forssell, J. Jansson, R. Karlsson, and P.-J. Nordlund, “Particle filters for positioning, navigation, and tracking,” IEEE Transactions on signal processing, vol. 50, no. 2, pp. 425–437, 2002. - [25] C. A. Naesseth, F. Lindsten, T. B. Schön et al., “Elements of sequential monte carlo,” Foundations and Trends® in Machine Learning, vol. 12, no. 3, pp. 307–392, 2019. - [26] C. M. Kirsch and A. Sokolova, “The logical execution time paradigm,” in Advances in Real-Time Systems (to Georg Färber on the occasion of his appointment as Professor Emeritus at TU München after leading the Lehrstuhl für Realzeit-Computersysteme for 34 illustrious years), S. Chakraborty and J. Eberspächer, Eds. Springer, 2012, pp. 103–120. - [27] C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” Journal of the ACM (JACM), vol. 20, no. 1, pp. 46–61, 1973. - [28] M. Lohstroh, E. A. Lee, S. A. Edwards, and D. Broman, “Logical Time for Reactive Software,” in Proceedings of Cyber-Physical Systems and Internet of Things Week, 2023, pp. 313–318. - [29] E. Bini, M. Di Natale, and G. Buttazzo, “Sensitivity analysis for fixed-priority real-time systems,” Real-Time Systems, vol. 39, pp. 5–30, 2008. - [30] D. Zerfowski and D. Buttle, “Paradigm shift in the market for automotive software,” ATZ worldwide, vol. 121, no. 9, pp. 28–33, 2019. - [31] H. Windpassinger, “On the way to a software-defined vehicle,” ATZelectronics worldwide, vol. 17, no. 7, pp. 48–51, 2022. - [32] W. R. Gilks, A. Thomas, and D. J. Spiegelhalter, “A language and program for complex Bayesian modelling,” The Statistician, vol. 43, no. 1, pp. 169–177, 1994. - [33] N. D. Goodman, V. K. Mansinghka, D. Roy, K. Bonawitz, and J. B. Tenenbaum, “Church: A language for generative models,” in Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence, ser. UAI’08. Arlington, Virginia, United States: AUAI Press, 2008, pp. 220–229. - [34] G. Bollella and J. Gosling, “The real-time specification for java,” Computer, vol. 33, no. 6, pp. 47–54, 2000. - [35] S. Natarajan, M. Nasri, D. Broman, B. B. Brandenburg, and G. Nelissen, “From code to weakly hard constraints: A pragmatic end-to-end toolchain for Timed C,” in Proccedings of the IEEE Real-Time Systems Symposium (RTSS). IEEE, 2019, pp. 167–180. - [36] J. C. Eidson, E. A. Lee, S. Matic, S. A. Seshia, and J. Zou, “Distributed real-time software for cyber–physical systems,” Proceedings of the IEEE, vol. 100, no. 1, pp. 45–59, 2011. - [37] A. Benveniste and G. Berry, “The Synchronous Approach to Reactive and Real-Time Systems,” Proc. of the IEEE, vol. 79, no. 9, pp. 1270–1282, 1991. - [38] L. Murray, D. Lundén, J. Kudlicka, D. Broman, and T. Schön, “Delayed Sampling and Automatic Rao-Blackwellization of Probabilistic Programs,” in Proceedings of Machine Learning Research : International Conference on Artificial Intelligence and Statistics (AISTATS). PMLR, 2018. - [39] H. Aydin, R. Melhem, D. Mossé, and P. Mejia-Alvarez, “Optimal reward-based scheduling for periodic real-time tasks,” IEEE Transactions on Computers, vol. 50, no. 2, pp. 111–130, 2001.