Parametric WCET Analysis

In a real-time system, it is crucial to ensure that all tasks of the system hold their deadlines. A missed deadline in a real-time system means that the system has not been able to function correctly. If the system is safety critical, this could potentially lead to disaster. To ensure that all tasks keep their deadlines, the Worst-Case Execution Time (WCET) of these tasks has to be known. Static analysis analyses a safe model of the hardware together with the source or object code of a program to derive an estimate of the WCET. This estimate is guaranteed to be equal to or greater than the real WCET. This is done by making calculations which in all steps make sure that the time is exactly or conservatively estimated. In many cases, however, the execution time of a task or a program is highly dependent on the given input. Thus, the estimated worst case may correspond to some input or configuration which is rarely (or never) used in practice. For such systems, where execution time is highly input dependent, a more accurate timing analysis which take input into consideration is desired. In this thesis we present a method based on abstract interpretation and counting of semantic states of a program that gives a WCET in terms of some input to the program. This means that the WCET is expressed as a formula of the input rather than a constant. This means that once the input is known, the actual WCET may be more accurate than the absolute and global WCET. Our research also investigate how this analysis can be safe when arithmetic operations causes integers to wrap-around, where the common assumption in static analysis is that variables can take the value of any integer. Our method has been implemented as a prototype and as a part of a static WCET analysis tool in order to get experience with the method and to evaluate the different aspects. Our method shows that it is possible to obtain very complex and detailed information about the timing of a program, given its input