Abstract
Knowledge about the Worst-Case Execution-Time (WCET) is of primordial importance in the validation of real-time systems. A WCET estimation must be safe and tight. Tightness in WCET estimation is highly desirable for an efficient utilisation of resources. In order to obtain accurate WCET values, more program execution-history must be accounted for. In this thesis we propose the use of Predicated WCET Analysis which uses constraint-logic programming to model context-sensitive execution-times of program segments. We prove that our predicated analysis is safe and very tight compared to contemporary analysis techniques. The execution-time constraints are collected automatically through static analysis. The hardware that we consider is moderately complex which causes considerable execution time variations and we show that we can analyse these dependencies statistically and incorporate all of them in a single calculation model. We show that by using constraint-logic programming, the execution time dependencies between program segments are expressed transparently using direct logical implications; and efficiently as the constraint-model implicitly enforces path-sensitivity during calculation. We also show that we can use a hybrid measurement-based approach to derive the execution time dependencies needed by the predicted analysis. This can be employed to perform predicated WCET analysis on more complex hardware where static analysis encounters serious limitations. A typical application domain in this case is soft real-time systems. We show that our method achieves considerable tightness in comparison to traditional calculation methods. The use of constraint-logic programming in our calculations proves to be the right choice when compared to the exponential behaviour recorded by the use of integer-linear programming. Furthermore, the evaluation of our measurement-based predicated WCET-analysis reveals that the obtained WCET estimations are close to those found by static analysis, and safe in many cases.