FULL TITLE

Timing Analysis of Real-Time Systems

KEYWORDS

real-time systems, worst-case execution time (WCET), measurement-based analysis, static analysis.

SUMMARY

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.
Industry has, for many years, approached this problem in a brute force manner by testing the program rigorously using data sets generated for functional test purposes.

The obvious problem with this technique is that the WCET might never be captured since exhaustive testing is generally infeasible; furthermore, Tracey [1] 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 [2]. 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 [3] 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 [2]. 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.

KEY REFERENCES

[1] N. Tracey, "A Search-Based Automated Test-Generation Framework for Safety-Critical Software", PhD Thesis, University of York, UK, July 2000.

[2] 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.

[3] A. Betts and G. Bernat, "Instrumentation Point Graphs for WCET Analysis", University of York Technical Report, July 2005.

Author

Adam Betts (York)