Research

Scientific objectives

Objective 1: worst case execution time estimation of a program

Modern processors induce an increased variability of the execution time of programs, making difficult (or even impossible) a complete static analysis. Our objective is to propose a solution composing probabilistic and non-probabilistic approaches based on static analyses locally and on statistical analyses globally by answering the following identified scientific challenges:

  1. a classification of the variability of execution times of a program with respect to the processor features. We will use as first measure our statistical estimator based on the Extreme Value Theory  (web). The access to this later page requires a login (aoste) and a password (aoste). The difficulty of this challenge is related to the definition of an element belonging to the set of variability factors and its mapping to the execution time of the program.
  2. a compositional rule of statistical models based on Bayesian approaches. The difficulty of this challenge comes from the fact that a global maximum cannot be obtained by upperbouding the corresponding local maxima. We will use as first rule of composition a Bayesian approach (web) We consider as first statistical model those obtained by any static analysis of the program on a basic processor. Through the Bayesian approach we add iteratively the variability due to each processor feature as a new statistical model. The convergence of the global model is decided once no variability is detected at the level of the statistical estimator providing the bounds on the execution time of the program.
Objective 2: deciding the schedulability of all programs running within the same cyber component

The programs may have different time criticalities, but they share the same processor, possibly multicore. This later case is referred as a mixed criticality approach. Our objective is to propose a solution composing probabilistic and non-probabilistic approaches based on answers to the following identified scientific challenges:

  1. scheduling algorithms taking into account the interaction between different variability factors. The proposed scheduling algorithms are the theoretical bases of a scheduler able to guarantee the time constraints of the cyber component. The existence of time parameters described by probability distributions imposes to answer to the challenge of revisiting scheduling algorithms that lose their optimality even in the case of an unicore processor. Moreover, the multicore partionning problem is recognized difficult for the non-probabilistic case.
  2. schedulability analyses based on the algorithms proposed previously. In the case of predictable processors, the schedulability analyses accounting for operating systems costs increase the dependability of CPSs. Morever, in presence of variability factors, the additivity property of non-probabilistic approaches is lost and new composition principles are required. We will propose new composition principles based on our preliminary results on the propagation of the probabilistic constraints. The definition of these principles form the challenge related to this objective.
Objective 3: deciding the schedulability of all programs communicating through predictable and non-predictable networks

The programs of the same cyber component execute on the same processor and they may communicate with the programs of other cyber components through networks that may be predictable (network on chip) or non-predictable (internet, telecommunications). Our objective is to propose a solution to the challenge of analysing schedulability of programs, for which existing (worst case) probabilistic solutions exist \cite{maxim_rtss2013}, communicating through networks, for which probabilistic worst-case solutions \cite{cucu-wfcs} and average solutions exist \cite{lehoczky96}. Our solution is based on the results obtained for the two first objectives, making this third objective a longer-term one.

Comments are closed.