=Paper=
{{Paper
|id=Vol-1431/paper4
|storemode=property
|title=Probabilistic Approaches for Time Critical Embedded Systems
|pdfUrl=https://ceur-ws.org/Vol-1431/paper4.pdf
|volume=Vol-1431
|dblpUrl=https://dblp.org/rec/conf/vecos/Cucu-Grosjean15
}}
==Probabilistic Approaches for Time Critical Embedded Systems==
https://ceur-ws.org/Vol-1431/paper4.pdf
Probabilistic approaches for time critical
embedded systems
Liliana Cucu-Grosjean
AOSTE team, INRIA Paris-Rocquencourt
Domaine de Voluceau, BP 105
78153, Le Chesnay
France
liliana.cucu@inria.fr
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 embedded systems. This solution defines several
possible values for the worst case execution time
An embedded system is a computing system with of a program on a processor and it has propagated
a dedicated function, embedded within a larger from the original work on scheduling theory Burns
device,e.g., a defibrillator or an airplane. Today and Davis (2015) to synchronous languages Yip
95% of current processors are embedded, making and al. (2014), predictable processors Zimmer
embedded systems central computing systems and al. (2014), model checking Boudjadar and al.
of our society. Beside constraints like power (2014), etc. Nevertheless today the mixed criticality
consumption and weight, embedded systems may solutions are heterogeneous and they are proposed
have time constraints and such systems are for different phases of design without a common
called time critical embedded systems. Time critical framework.
embedded systems design is mainly based on
commercial processors with a good average time A possible solution to build such common framework
behavior. During the last twenty years different while decreasing the pessimism may be proposed
design solutions have been proposed through by enriching existing models with appropriate
pessimistic estimation of performances of the probabilistic descriptions. Probabilistic description of
processors (thus increased costs) while using a model provides more information to the designer
average time behavior processors. while allowing several values for a parameter, or
several states for a property. Nevertheless, the
The pessimism of all existing solutions comes mainly introduction of probabilities is not trivial as not
from the implementation phase where an absolute every probabilistic approach may be used to study
value is considered for the worst case execution time critical embedded systems. First, we prove
time of a program. The arrival of modern and more that the worst case values of the execution times
complex processors (e.g., use of caches, multi- of a program are rare events Cucu-Grosjean and
and many-core processors) increases the timing al. (2012). Secondly, the average-case probabilistic
variability of programs, i.e., the absolute worst case reasoning is not useful to guarantee time constraints
execution time is becoming significantly larger. For Maxim and Cucu (2013). We define the probabilistic
instance, larger execution times require an increased worst case reasoning as a probabilistic bound on
number of processors or more powerful processors. possible values for a parameter or a property of the
system Cucu-Grosjean (2013).
An intuitive solution to overcome this pessimism is
the introduction by Steve Vestal in Vestal (2007) In this talk we define probabilistic upper bounds
of the notion of mixed criticality for time critical on all possible values or states as the probabilistic
worst case reasoning ensuring the migration of • Probabilistic approaches for asynchronous
probabilistic methods from modelling soft time models taking into account mixed criticality
constraints to analysing hard time constraints. Two systems. Here the transition between states
common misconceptions concerning probabilistic may be the first to be described probabilisti-
time critical embedded systems are discussed: cally.
independence and the identical distribution. We
summarize recent state-of-the-art research into • Probabilistic approaches for real-time schedul-
probabilistic approaches, and we conclude with the ing analysis for mixed criticality systems.
main open challenges in this area. • Probabilistic approaches for verification for
mixed criticality systems. The integration of
2. DESIGN OF TIME CRITICAL EMBEDDED rare events probability distributions in current
SYSTEMS probabilistic model checking seems to be the
first reasonable step.
The design of a time critical embedded system may
have basically three main phases: (i) the description
REFERENCES
of the physical process that should be controlled
(control theory), (ii) the description of the functional Vestal, S. (2007) Preemptive scheduling of multi-
requirements that should be fulfilled (synchronous criticality systems with varying degrees of execu-
and asynchronous models) and (iii) the description tion time assurance the IEEE Real-Time Systems
of the implementation of the time critical embedded Symposium.
system (scheduling or verification).
Burns, A. and Davis, R., (2015) Mixed Criticality
Systems - Review University of York.
Control*
Theory*
Yip, E. and Kuo, M. and Roop, P. and Broman,
requirements*
D., (2015) Relaxing the synchronous approach
Func8onal*
for mixed-criticality systems the 20th IEEE Real-
Time and Embedded Technology and Application
Synchronous** Asynchronous**
Models* Models*
Symposium.
Zimmer, M. and Broman, D. and Shaver, C. and
Lee, E., (2014) FlexPRET: A processor platform
Processor* for mixed-criticality systems the 20th IEEE Real-
Implementa8on*
Time and Embedded Technology and Application
Symposium.
Model* Real78me*
Checking* Scheduling* Boudjadar, A.J. and David, A. and Kim, J. and
Larsen, K.G. and Mikucionis, M. and Nyman, U.
and Skou, A., (2014) Degree of Schedulability
Figure 1: Different phases of the design of a time critical of Mixed-Criticality Real-Time Systems with
embedded system Probabilistic Sporadic Tasks Theoretical Aspects
of Software Engineering Conference.
In order to decrease the pessimism of the design
solutions, while ensuring time critical constraints, Maxim, D. and Cucu-Grosjean, L., (2014) Response
probabilistic description of parameters may be Time Analysis for Fixed-Priority Tasks with Multiple
defined at different levels of design of a time critical Probabilistic Parameters the 34th IEEE Real-Time
embedded system: Systems Symposium.
• Probabilistic approaches for control theory for Cucu-Grosjean, L. and Santinelli, L. and Houston,
mixed criticality systems. Solving a control sys- M. and Lo, C. and Vardanega, T. and Kosmidis,
tem problem consists in finding the sampling L. and Abella, J. and Mezzeti, E. and Quinones,
frequency and we identify it as the first property E. and Cazorla, F., (2012) Measurement-Based
to be described probabilistically. Probabilistic Timing Analysis for Multi-path Pro-
grams the 24th Euromicro Conference on Real-
• Probabilistic approaches for synchronous time Systems.
models for mixed criticality systems. The
transition between states might be the first Cucu-Grosjean, L., (2013) Independence - a
property to be described probabilistically by misunderstood property of and for (probabilistic)
relaxing the synchrony hypothesis. real-time systems Real-Time Systems: the past,
the present, and the future.