Advisors: Claire Maiza, Pascal Raymond
The description of the work to be done will be detailed later. Feel free to contact Claire Maiza for more details if you are interested.
The general context: Critical embedded systems are generally composed of repetitive tasks that must meet drastic timing constraints, such as termination deadlines. Providing an upper bound of the worst-case execution time (WCET) of such tasks at design time is thus necessary to prove the correctness of the system. Dynamic methods based on testing give realistic but unsafe results: they do not guarantee to pinpoint the worst-case execution. On the contrary, static timing analysis methods, compute safe WCET upper bounds, but at the cost of a potentially large over-approximation. Sources of over-estimation stem from the analysis of the hardware platform, but also from the identification of semantic information in programs to detect feasible executions.
We propose to integrate more semantics in timing analysis and it may be integrated to the path analysis step. Current path analysis is generally based on an ILP formulation. The first idea is to integrate more semantics in this path analysis via a semantic model based on automata. This kind of method will eventually require a tradeoff between the gain in precision and the size of the ILP system.
See the following references for an introduction to WCET analysis and a similar approach applied to the case of branch prediction.
Expected Skills and Background:
- Fluency in C programming
- Basic knowledge on assembly languages
- Ability to manipulate automata and other formally-defined programming models
Expected Work:
- Study of existing approaches and proposal of a model that includes interesting semantic properties;
- Proposal of a heuristic to automatically extract semantic information;
- Development and evaluation (proof-of-concept).
References:
- A framework for the timing analysis of dynamic branch predictors. Maiza, Claire and Rochange, Christine (in Proceedings of the 19th International Conference on Real-Time and Network Systems (RTNS2011), 2011).
- The Worst-case Execution Time Problem—Overview of Methods and Survey of Tools. Reinhard Wilhelm et al. (in ACM Transactions on Embedded Computing Systems (TECS), 7 (3), 2008. )
