Timing Analysis and Timing Predictability

Date: Thursday, October 13, 2011
Speaker: Reinhard Wilhelm
Venue: TU Vienna

Hard real-time systems are subject to stringent timing constraints, which are dictated by the surrounding physical environment. A schedulability analysis has to be performed in order to guarantee that all timing constraints will be met. Existing techniques for schedulability analysis require upper bounds for the execution times of all the system’s tasks to be known. These upper bounds are commonly called worst-case execution times (WCETs). The WCET-determination problem has become non-trivial due to the advent of processor features such as caches, pipelines, and all kinds of speculation, which make the execution time of an individual instruction locally unpredictable. Such execution times may vary between a few cycles and several hundred cycles.A combination of Abstract Interpretation (AI) with Integer Linear Programming (ILP) has been successfully used to determine precise upper bounds on the execution times of real-time programs. The task solved by abstract interpretation is to compute invariants about the processor’s execution states at all program points. These invariants describe the contents of caches, of the pipeline, of prediction units etc. They allow to verify local safety properties, safety properties who correspond to the absence of “timing accidents”. Timing accidents, e.g. cache misses, pipeline stalls are reasons for the increase of the execution time of an individual instruction in an execution state.The technology and tools have been used in the certification of several time-critical subsystems of the Airbus A380. The AbsInt tool, aiT, is the only tool worldwide, validated for these avionics applications.I will give an introduction to our timing-analysis method, present results about the predictability of cache architectures, and give an overview of current work and open problems.

Prof. Reinhard Wilhelm is a full Professor of Computer Science at the Saarland University, Saarbruecken and the Scientific Director of the International Conference and Research Center for Computer Science, Schloss Dagstuhl, Germany. He is the cofounder of AbsInt, a company developing software tools for embedded systems.The research activities of Prof. Reinhard Wilhelm cover a wide range of topics, including compiler generation, program analysis, and software visualisation. His contributions to research have been honored by several awards and prizes. To name a few, Prof. Wilhelm is an ACM Fellow, and he received the European IST Prize with the spin-off company AbsInt, the Alwin Walther Medal, the Konrad-Zuse Medal and the ACM Distinguished Service Award.

Posted in RiSE Seminar