During the last twenty years different design solutions have been proposed for time critical embedded systems through pessimistic estimation of performances of the processors (thus increased costs) while using average time behavior processors. A possible solution to decrease the pessimism while designing time critical embedded systems is to enrich existing models with appropriate probabilistic descriptions. time critical embedded systems, probabilistic worst-case reasoning
1. INTRODUCTION An embedded system is a computing system with a dedicated function, embedded within a larger device,e.g., a defibrillator or an airplane. Today 95% of current processors are embedded, making embedded systems central computing systems of our society. Beside constraints like power consumption and weight, embedded systems may have time constraints and such systems are called time critical embedded systems. Time critical embedded systems design is mainly based on commercial processors with a good average time behavior. During the last twenty years different design solutions have been proposed through pessimistic estimation of performances of the processors (thus increased costs) while using average time behavior processors.
The pessimism of all existing solutions comes mainly from the implementation phase where an absolute value is considered for the worst case execution time of a program. The arrival of modern and more complex processors (e.g., use of caches, multiand many-core processors) increases the timing variability of programs, i.e., the absolute worst case execution time is becoming significantly larger. For instance, larger execution times require an increased number of processors or more powerful processors. An intuitive solution to overcome this pessimism is the introduction by Steve Vestal in Vestal (2007) of the notion of mixed criticality for time critical embedded systems. This solution defines several possible values for the worst case execution time of a program on a processor and it has propagated from the original work on scheduling theory Burns and Davis (2015) to synchronous languages Yip and al. (2014), predictable processors Zimmer and al. (2014), model checking Boudjadar and al. (2014), etc. Nevertheless today the mixed criticality solutions are heterogeneous and they are proposed for different phases of design without a common framework.
A possible solution to build such common framework while decreasing the pessimism may be proposed by enriching existing models with appropriate probabilistic descriptions. Probabilistic description of a model provides more information to the designer while allowing several values for a parameter, or several states for a property. Nevertheless, the introduction of probabilities is not trivial as not every probabilistic approach may be used to study time critical embedded systems. First, we prove that the worst case values of the execution times of a program are rare events Cucu-Grosjean and al. (2012). Secondly, the average-case probabilistic reasoning is not useful to guarantee time constraints Maxim and Cucu (2013). We define the probabilistic worst case reasoning as a probabilistic bound on possible values for a parameter or a property of the system Cucu-Grosjean (2013).
In this talk we define probabilistic upper bounds on all possible values or states as the probabilistic worst case reasoning ensuring the migration of probabilistic methods from modelling soft time constraints to analysing hard time constraints. Two common misconceptions concerning probabilistic time critical embedded systems are discussed: independence and the identical distribution. We summarize recent state-of-the-art research into probabilistic approaches, and we conclude with the main open challenges in this area. 2. DESIGN OF TIME CRITICAL EMBEDDED SYSTEMS The design of a time critical embedded system may have basically three main phases: (i) the description of the physical process that should be controlled (control theory), (ii) the description of the functional requirements that should be fulfilled (synchronous and asynchronous models) and (iii) the description of the implementation of the time critical embedded system (scheduling or verification).
Synchronous**
Models* Model* Checking*
Control* Theory* Processor* In order to decrease the pessimism of the design solutions, while ensuring time critical constraints, probabilistic description of parameters may be defined at different levels of design of a time critical embedded system:
Probabilistic approaches for control theory for mixed criticality systems. Solving a control system problem consists in finding the sampling frequency and we identify it as the first property to be described probabilistically.
Probabilistic approaches for synchronous models for mixed criticality systems. The transition between states might be the first property to be described probabilistically by relaxing the synchrony hypothesis.
Probabilistic approaches for asynchronous models taking into account mixed criticality systems. Here the transition between states may be the first to be described probabilistically.
Probabilistic approaches for real-time scheduling analysis for mixed criticality systems.
Probabilistic approaches for verification for mixed criticality systems. The integration of rare events probability distributions in current probabilistic model checking seems to be the first reasonable step. Vestal, S. (2007) Preemptive scheduling of multicriticality systems with varying degrees of execution time assurance the IEEE Real-Time Systems Symposium.
Yip, E. and Kuo, M. and Roop, P. and Broman, D., (2015) Relaxing the synchronous approach for mixed-criticality systems the 20th IEEE RealTime and Embedded Technology and Application Symposium.
Zimmer, M. and Broman, D. and Shaver, C. and Lee, E., (2014) FlexPRET: A processor platform for mixed-criticality systems the 20th IEEE RealTime and Embedded Technology and Application Symposium.
Maxim, D. and Cucu-Grosjean, L., (2014) Response Time Analysis for Fixed-Priority Tasks with Multiple Probabilistic Parameters the 34th IEEE Real-Time Systems Symposium.