Existing results for cyber-physical systems have been proposed to merge the requirements associated to the stability of the physical components and the schedulability of the cyber components. Nevertheless, none of the existing results has studied these requirements for multiple real-time cascade control tasks where their periods choice are dependent and affect stability. In this paper, we propose a methodology to evaluate the periods of the real-time cascade control tasks that ensures stability of the physical components, then we present a co-design problem for the period choice that guarantees good performance of the physical components and schedulability of the cyber components under fixed-priority scheduling. We then evaluate this methodology on a real use-case of a drone system. Results show the importance of studying these requirements together as their relation has an impact on stable periods range.

Current real-time GPU scheduling methods depend on (non-existent) worst-case execution time estimates of programs due to the absence of a complete model for the GPU functioning. To tackle this absence, we conduct a sensitivity analysis on programs suited for execution on embedded GPU hardware. This analysis is a starting point towards the understanding of factors causing execution time variations on GPUs. Our initial conclusions pinpoint significant sources of variation and identify various execution modes.

In this paper, we provide first results introducing the impact of both software and hardware events on the estimation of worst-case energy consumption of programs on embedded processors. We build a framework to better understand the representativeness of measurements with respect to both software and hardware events. We test this framework on execution times and energy consumption data for 5 existing benchmarks as a step towards a statistical worst-case energy consumption model.

In this paper, we prove that a mean system utilization smaller than one is a necessary condition for the feasibility of real-time systems. Such systems are defined asstable. Stable systems have two distinct states: a transient state, followed by a steady-state where the same distribution of response times is repeated infinitely for each task. We prove that the Liu and Layland theorem holds for stable probabilistic real-time systems with implicit deadlines, we provide an analytical approximation of response times for each of those two states and a bound of the instant when a real-time system becomes steady.

The real-time systems community is facing the lack of benchmarks adapted to measurement-based worst-case execution time (WCET) estimators. We provide in this paper first steps towards such benchmarks by proposing them for single core microcontrollers, while we leave as future work the migration to multicore microcontrollers. The considered benchmarks are the programs of an open source drone autopilot. We conclude the paper by underlining the main difficulties of such migration.

This paper presents the design and analysis of a data science competition on a problem of time series regression from aeronautics data. For the purpose of performing predictive maintenance, aviation companies seek to create aircraft “numerical twins”, which are programs capable of accurately predicting strains at strategic positions in various body parts of the aircraft. Given a number of input parameters (sensor data) recorded in sequence during the flight, the competition participants had to predict output values (gauges), also recorded sequentially during test flights, but not recorded during regular flights. The competition data included hundreds of complete flights. It was a code submission competition with complete blind testing of algorithms. The results indicate that such a problem can be effectively solved with gradient boosted trees, after preprocessing and feature engineering. Deep learning methods did not prove as efficient.

Designers of embedded real-time systems derive, in general, their time parameters such as activation periods from those of sensors or actuators. By designers, we mean the team in charge of conceiving embedded real-time systems. This team includes Control Theory designers and Computer Science designers. Within this paper we present the point of view of Computer Science designers, while the periods proposed by Control Theory designers are supposed robust with respect to the physical behavior of the system. The execution times are, then, estimated by studying statically the programs structure or dynamically the programs execution. In some cases, both activation periods and execution times depend on a sensor information. For instance, they depend on the angular speed of wheels within an automotive embedded real-time system and such systems follow a rate-dependent model. Elastic tasks is another model, where one may consider execution time variation depending on the selected period. Within this paper, we are interested in describing statistically the relationship between activation periods and execution times of programs. More precisely, we study the impact of the period variation on the distributions of the execution times. To illustrate our preliminary results, we consider, as case study, the set of programs executing the autopilot of an open-source PX4 drone.

The increased complexity of programs and processors is an important challenge that the embedded real-time systems community faces today, as it implies substancial timing variability. Processor features like pipelines or communication buses are not always completely described, while black-box programs integrated by third parties are hidden for IP reasons. This situation explains the use of statistical approaches to study the timing variability of programs. Most existing work is concentrated on the guarantees provided by positive answers to statistical tests, while our current work concerns potential algorithms based on the negative answers to these tests and their impact on the timing analysis. We introduce here one such algorithm, the Walking Kolmogorov-Smirnov test (WKS).

The design of cyber-physical systems (CPSs) is facing the explosion of new functionalities requiring increased computation capacities and, thus, the introduction of multi-core processors. Moreover, some functionalities may impose precedence constraints between the programs implementing these new functionalities. While important effort has been dedicated to the scheduling of precedence constraints tasks on multi-core processors, existing work considers either partitioned scheduling for a single precedence graph defining precedence constraints between tasks, or global scheduling policies.In this paper, we consider partitioned scheduling for multiple precedence graphs defining precedence constraints between tasks. The variability of execution times and of communication times is described by probability distributions. We propose a new response time analysis over-performing existing ILP-based results. Thanks to its scalability, our solution is extendable to a probabilistic version and we validate it on a PX4 drone autopilot. Beside this autopilot for our experiments, we implemented a probabilistic extension of a multi-core processor simulator, SimSo. A priority assignment heuristic allowing parallel executions is also proposed. Thanks to its adaptation to partitioned scheduling, our heuristic has better performances than existing solutions and its performances are, also, compared against a genetic-based heuristic.

Estimating bounds for the execution or response times of a task is a central concern for real-time designers. Several solutions exist, and probabilistic approaches estimate such bounds by building appropriate probability distributions. Those methods are safe, but they may be pessimistic and rely on strong hypothesis such as independence between tasks.The worst case execution times of tasks are hard to estimate because their measurements are usually disturbed by the system itelf. In general measures are done in isolation, however dependencies between tasks are rarely modeled in that case. By isolation, we mean that a task (or program) is executed without any type of interference coming from other executed tasks.In this paper we propose a statistical analysis of measured response times based on clustering analysis, i.e., building classes of response times that may identify executing modes for a given set of tasks. This work is a first step towards a multivariate analysis that may explicitly identify dependence structures.

The design of embedded systems is facing the explosion of new functionalities requiring increased computation capacities and, thus, the introduction of multi-core processors. Moreover, some functionalities may impose precedence constraints between the programs implementing them. In this paper, we consider partitioned scheduling of tasks with precedence constraints defined by multiple Directed Acyclic Graphs (DAGs). The variability of execution and communication times is taken into account by describing them with probability distributions. Our probabilistic response time analysis is validated on random generated task sets and on a PX4 drone autopilot.

The increased use of statistical libraries within the real-time community is facing today the lack of appropriate libraries. Many of them exist in R, but existing Python statistical libraries are lacking, particularily with respect to Extreme Value Theory and probabilistic worst-case execution time estimation, which are indispensable tools for the analysis of real-time systems. This short paper attempts to describe and bridge this gap.

Measurement-based Worst Case Execution Time (WCET) estimations require appropriate benchmarks that are composed both by programs and representative measurement protocols. The representativeness is defined with respect to both the programs and processors executing them. In this paper we consider the representativeness with respect to a multicore processor and we provide preliminary conclusions on how appropriate benchmarks could be proposed.

The continuous integration of new functionality increases the complexity of embedded systems, while each functionality might impose precedence constraints between the programs fulfilling it. In addition, the prevalence of several processors may create the illusion of higher computation capacity easing the associated scheduling problem. However, this capacity is not exploitable in critical real time systems because of the increased variability of the execution times due to processor features designed to provide excellent average time behaviour and not necessarily ensuring small worst case bounds. This difficulty is added to the existence of scheduling anomalies when the systems are built on top of several processors. In this paper, we study the feasibility of independent tasks scheduled according to a given preemptive fixed-priority partitioned policy on identical processors. Each task is composed of several dependent subtasks related between them according to a directed acyclic graph (DAG). We provide a worst case response time analysis for DAG tasks when each sub-tasks have an individual priority level. This assumption allows to decrease the number of possible execution scenarios, making our analysis easier and less pessimistic.

Nowadays, real-time embedded systems are facing concerns like power consumption and increased functionalities demand. Approaches based on Dynamic Voltage and Frequency Scaling (DVFS) reduce the energy consumed by processors while guaranteeing real-time constraints. In this paper, we present short-comings on existing models reducing energy consumption. Our experimental results clearly show that the execution time of tasks is not exclusively proportional to the processor speed. Thus, we believe that DVFS techniques could also be applied to other components like buses and memory. We discuss the applicability of a probabilistic Worst Case Execution Time (WCET) combined with DVFS techniques, and argue that by adopting a probabilistic frequency-aware model, we can (i) capture more detailed behaviors of tasks w.r.t. hardware frequencies and (ii) apply DVFS techniques to gain in energy consumption.

Probabilistic hard real-time systems, based on hardware architectures that use a random replacement cache, provide a potential means of reducing the hardware over-provision required to accommodate pathological scenarios and the associated extremely rare, but excessively long, worst-case execution times that can occur in deterministic systems. Timing analysis for probabilistic hard real-time systems requires the provision of probabilistic worst-case execution time (pWCET) estimates. The pWCET distribution can be described as an exceedance function which gives an upper bound on the probability that the execution time of a task will exceed any given execution time budget on any particular run. This paper introduces a more effective static probabilistic timing analysis (SPTA) for multi-path programs. The analysis estimates the temporal contribution of an evict-on-miss, random replacement cache to the pWCET distribution of multi-path programs. The analysis uses a conservative join function that provides a proper over-approximation of the possible cache contents and the pWCET distribution on path convergence, irrespective of the actual path followed during execution. Simple program transformations are introduced that reduce the impact of path indeterminism while ensuring sound pWCET estimates. Evaluation shows that the proposed method is efficient at capturing locality in the cache, and substantially outperforms the only prior approach to SPTA for multi-path programs based on path merging. The evaluation results show incomparability with analysis for an equivalent deterministic system using an LRU cache. For some benchmarks the performance of LRU is better, while for others, the new analysis techniques show that random replacement has provably better performance.

The use of increasingly complex hardware and software platforms in response to the ever rising performance demands of modern real-time systems complicates the verification and validation of their timing behaviour, which form a time-and-effort-intensive step of system qualification or certification. In this paper we relate the current state of practice in measurement-based timing analysis, the predominant choice for industrial developers, to the proceedings of the PROXIMA (Probabilistic real-time control of mixed-criticality multicore systems) project in that very field. We recall the difficulties that the shift towards more complex computing platforms causes in that regard. Then we discuss the probabilistic approach proposed by PROXIMA to overcome some of those limitations. We present the main principles behind the PROXIMA approach as well as the changes it requires at hardware or software level underneath the application. We also present the current status of the project against its overall goals, and highlight some of the principal confidence-building results achieved so far.

The authors propose to study the average response time distribution of tasks owing to the pessimism introduced by the analysis of the synchronous case and unsafe response time obtained by simulation. In this regard, the problem we address is twofold. First, we need to determine a relevant and safe probabilistic feasibility interval that is representative of the systems behaviour over its entire lifetime. Second, we need to compute the response time distribution of any job of a task within this feasibility interval in order to combine them into an average distribution. This is a complex problem due to the fact that job arrivals are variable as well as their execution times.

Challenges within real-time research are mostly in terms of modeling and analyzing the complexity of actual real-time embedded systems. Probabilities are effective in both modeling and analyzing embedded systems by increasing the amount of information for the description of elements composing the system. Elements are tasks and applications that need resources, schedulers that execute tasks, and resource provisioning that satisfies the resource demand. In this work, we present a model that considers component-based real-time systems with component interfaces able to abstract both the functional and nonfunctional requirements of components and the system. Our model faces probabilities and probabilistic real-time systems unifying in the same framework probabilistic scheduling techniques and compositional guarantees varying from soft to hard real time. We provide an algebra to work with the probabilistic notation developed and form an analysis in terms of sufficient probabilistic schedulability conditions for task systems with either preemptive fixed-priority or earliest deadline first scheduling paradigms.

This paper integrates analysis of probabilistic cache related pre-emption delays (pCRPD) and static probabilistic timing analysis (SPTA) for multipath programs running on a hardware platform that uses an evict-on-miss random cache replacement policy. The SPTA computes an upper bound on the probabilistic worst-case execution time (pWCET) of the program, which is an exceedance function giving the probability that the execution time of the program will exceed any given value on any particular run. The pCRPD analysis determines the maximum effect of a pre-emption on the pWCET. The integration between SPTA and pCRPD updates the pWCET to account for the effects of one or more pre-emptions at any arbitrary points in the program. This integration is a necessary step enabling effective schedulability analysis for probabilistic hard real-time systems that use pre-emptive or co-operative scheduling. The analysis is illustrated via a number of benchmark programs.

In this paper, we consider a probabilistic model for real-time task systems with probabilistic worst-case execution times, probabilistic minimum inter-arrival times and probabilistic deadlines. We propose an analysis computing response time distributions of the tasks scheduled on one processor under a task-level fixed-priority preemptive scheduling policy. The complexity of our method is analyzed and it is improved by re-sampling techniques on worst-case execution time distributions and/or minimal inter-arrival time distributions. The improvements are shown through experimental results. Also, experiments are conducted in order to investigate the improvement obtained by using a probabilistic model in terms of precision and schedulability gained as opposed to a deterministic worst-case reasoning.

Static timing analysis is the state-of-the-art practice of ascertaining the timing behavior of current-generation real-time embedded systems. The adoption of more complex hardware to respond to the increasing demand for computing power in next-generation systems exacerbates some of the limitations of static timing analysis. In particular, the effort of acquiring (1) detailed information on the hardware to develop an accurate model of its execution latency as well as (2) knowledge of the timing behavior of the program in the presence of varying hardware conditions, such as those dependent on the history of previously executed instructions. We call these problems the timing analysis walls. In this vision-statement article, we present probabilistic timing analysis , a novel approach to the analysis of the timing behavior of next-generation real-time embedded systems. We show how probabilistic timing analysis attacks the timing analysis walls; we then illustrate the mathematical foundations on which this method is based and the challenges we face in the effort of efficiently implementing it. We also present experimental evidence that shows how probabilistic timing analysis reduces the extent of knowledge about the execution platform required to produce probabilistically accurate WCET estimations.

The rigorous application of static timing analysis requires a large and costly amount of detail knowledge on the hardware and software components of the system. Probabilistic Timing Analysis has potential for reducing the weight of that demand. In this paper, we present a sound measurement-based probabilistic timing analysis technique based on Extreme Value Theory. In all the experiments made as part of this work, the timing bounds determined by our technique were less than 15% pessimistic in comparison with the tightest possible bounds obtainable with any probabilistic timing analysis technique. As a point of interest to industrial users, our technique also requires a comparatively low number of measurement runs of the program under analysis, less than 650 runs were needed for the benchmarks presented in this paper.

Real-time embedded systems are becoming ever more complex. We are reaching the stage where even if static Response-Time Analysis (RTA) was feasible from a cost and technical perspective, the results of such an analysis are overly pessimistic. This makes them less useful to the practitioner. In addition, the temporal validation and verification of such systems in some applications, e.g., aeronautics, requires the probability of obtaining a worst-case response time larger than a given value in order to support dependable system functions. All these facts advocate moving toward statistical RTA, which instead of calculating absolute worst-case timing guarantees, computes a probabilistic worst-case response time estimate. The contribution of this paper is to present and evaluate such a statistical RTA technique which uses a black box view of the systems under analysis, by not requiring estimates of parameters such as worst-case execution times of tasks. Furthermore, our analysis is applicable to real systems that are complex, e.g., from a task dependencies perspective.

This paper describes the tool support for a framework for performing statistical WCET analysis of realtime embedded systems by using bootstrapping sampling and Extreme Value Theory (EVT). To be specific, bootstrapping sampling is used to generate timing traces, which not only fulfill the requirements given by statistics and probability theory, but also are robust to use in the context of estimating the WCET of programs. Next, our proposed statistical inference uses EVT to analyze such timing traces, and computes a WCET estimate of the target program, pertaining to a given predictable probability. The evaluation results show that our proposed method could have the potential of being able to provide a tighter upper bound on the WCET estimate of the programs under analysis, when compared to the estimates given by the referenced WCET analysis methods.

A challenging research issue of analyzing a real-time system is to model the tasks composing the system and the resource provided to the system. In this paper, we propose a probabilistic component-based model which abstracts in the interfaces both the functional and non-functional requirements of such systems. This approach allows designers to unify in the same framework probabilistic scheduling techniques and compositional guarantees that go from soft to hard real-time. We provide sufficient schedulability tests for task systems using such framework when the scheduler is either preemptive Fixed-Priority or Earliest Deadline First.

In this paper we study the global scheduling of periodic task systems upon uniform multiprocessor platforms. We first show two very general properties which are well-known for uniprocessor platforms and which remain for multiprocessor one: (i) under few and not so restrictive assumptions, we show that any feasible schedules of periodic task system are periodic from some point and (ii) for the specific case of synchronous periodic task systems, we show that the schedule repeats from the origin. We then present our main result: any feasible schedules of asynchronous periodic task sets using a fixed-priority scheduler are periodic from a specific point. Moreover, we characterize that point and we provide a feasibility interval for those systems.