Timing Analysis of Real-Time Systems
real-time systems, worst-case execution time (WCET), measurement-based analysis, static analysis.
A myriad of safety-critical systems fall under the
real-time umbrella in which temporal correctness is the differentiating
characteristic. A key step in proving temporal correctness is the elicitation
of execution time profiles for each task that executes in the system;
normally, this equates to determining each task's Worst-Case Execution
Time (WCET), which is loosely defined as the longest possible execution
time when running on a particular hardware configuration.
The obvious problem with this technique is that the WCET might never be captured since exhaustive testing is generally infeasible; furthermore, Tracey  has noted that functional data sets are not necessarily suited in determining WCET estimates. In response, academia has proposed static analysis techniques in which the WCET is derived without ever executing the program . However, the scope of static analysis is increasingly impeded by a proliferation of advanced computer architectures, which include caches, pipelines, and branch prediction units, in the real-time domain. These advancements increase average-case performance, but their complex interactions vastly complicate the determination of worst-case behaviour. As a result, pessimistic assumptions are formalised about these speed-up features behaviour, thus spawning loose WCET estimates.
Our measurement-based framework  combines the best of testing and static analysis techniques to determine WCET estimates. On the one hand, we test the program on its intended hardware in order to extract the WCET of code fragments within a program. The clear advantage of this technique is that complications surrounding processor simulation are avoided. The next step in our analysis combines these data by using traditional static analysis techniques found in the literature . In particular, we use techniques that reason about a program's high-level structure in order to deduce the longest path through a program and hence a WCET estimate, normally within a probabilistic framework.
 N. Tracey, "A Search-Based Automated Test-Generation Framework for Safety-Critical Software", PhD Thesis, University of York, UK, July 2000.
 A.Burns and P. Puschner, "A Review of Worst-Case Execution-Time Analysis", Journal of Real-Time Systems, 18(2/3):115-227, May 2000.
 A. Betts and G. Bernat, "Instrumentation Point Graphs for WCET Analysis", University of York Technical Report, July 2005.
Adam Betts (York)
|Page Maintainer: firstname.lastname@example.org||Credits||Project Members only||Last Modified: 10 August, 2005|