********************************************************************* * Ecole Normale Supe'rieure * * * * Se'minaire * * SEMANTIQUE ET INTERPRETATION ABSTRAITE * * P. Cousot * * * * Vendredi, 14h00--15h30 * * Salle W, 4e`me e'tage, toits du DMA * * DI ENS 45 rue d'Ulm 75005 Paris * ********************************************************************* *** Vendredi 1 octobre 1999 **** 14h00 **************************** Relache PLI'99 (Paris) : http://pauillac.inria.fr/pli/ *** Vendredi 8 octobre 1999 **** 14h00 **************************** Reinhard WILHELM (Saarland University, Saarbruecken, Allemagne) Run-Time Guarantees for Real-Time Systems Re'sume' : Run-time guarantees play an important role in the area of embedded systems and especially hard real-time systems. These systems are typically subject to stringent timing constraints which often result from the interaction with the surrounding physical environment. Therefore, a schedulability analysis has to be performed which guarantees that all timing constraints will be met. All existing techniques for schedulability analysis require the worst case execution time (WCET) of each task in the system to be known before the task is executed. Since in general the problem of computing WCETs is not decidable, estimations of the WCET have to be calculated. These estimations have to be safe, i.e., they may never underestimate the real execution time. Furthermore, they should be tight, i.e., the overestimation should be as small as possible. In modern microprocessor architectures caches and pipelines are key features for improving performance. Unfortunately, they make the analysis of the execution behaviour of instructions very difficult since this behaviour now depends on the execution history. Therefore, the classical approaches to worst case execution time prediction are not directly applicable or lead to results exceeding the real execution time by orders of magnitude. In the USES approach (Univ. of the Saarland Embedded Systems group) we split the analysis into a set of subtasks: value analysis, cache analysis, pipeline analysis, and path analysis. The value analysis calculates the values of registers for each program point in order to enable the cache analysis to predict the data cache behaviour and to provide the path analysis with automatically derived loop and recursion bounds. The cache analysis predicts the instruction and data cache behaviour of each instruction and the pipeline analysis predicts the pipeline behaviour. These three analyses are all done by Abstract Interpretation. The final step of the run-time prediction is the program path analysis which yields an estimation of the machine cycles needed to execute the program. This is based on Integer Linear Programming (ILP). Our experimental results of prototype implementations of the cache analysis, the pipeline analysis and the program path analysis have shown that very tight bounds can be derived. For a wide range of test programs the microarchitecture behaviour could be predicted with high precision and was usually only slightly overestimated. *** Vendredi 15 octobre 1999 **** 14h00 *************************** relache *** Vendredi 22 octobre 1999 **** 14h00 *************************** relache *** Vendredi 29 octobre 1999 **** 14h00 *************************** relache ********************************************************************* Pour recevoir l'annonce par courrier electronique: cousot@di.ens.fr WWW: http://www.di.ens.fr/~cousot/annonceseminaire.shtml *********************************************************************