Timing analysis methods for high-performance real-time systems

o Project description
o Project members
o Publications
o Collaborations
o Funding

Project Description

Many industrial applications require a high and predictable performance. Good examples can be found in vehicles where the trend is to use microprocessors in critical control systems. To achieve 100% predictability is often in conflict with achieving high performance because pessimistic (worst-case) assumptions often outrule the exploitation of instruction-level parallellism and effective caching that are key concepts in high-performance microprocessor-based systems today. Pessimistic worst-case execution time (WCET) estimates then lead to much higher system costs because more computational resources are needed.

In this project, our goal is to provide timing analysis methods that can make tight but safe estimates of the worst-case execution time (WCET) of programs in the context of pipelined microprocessor systems employing multi-level memory hierarchies. An ultimate goal with this project is to integrate these techniques in compilers so that real-time programs with hard deadlines can exploit the performance potential of high-performance microprocessors. A concrete result so far is an automatic method that can make accurate estimates of WCET on superscalar microprocessors with multi-level memory hierarchies. The major innovation is a concept we call cycle-level symbolic execution. This concept makes it possible to (1) exclude program paths from the analysis that can never be executed and (2) modelling the timing of the remaining paths very accurately. The prototype we have designed to test the approach has been used to demonstrate the strength of our method on a suite of programs. We have shown that it in many cases is possible to achieve exact estimates of the WCET of programs on emerging high-performance microprocessors. This method is important in validating real-time systems in mission-critical applications where timing constraints are necessary for the function. In the trend of using microprocessors in critical control applications, such automated test approaches are key.


Project members


Publications

Thomas Lunqvist and Per Stenström: "Integrating Path and Timing Analysis Using Instruction-Level Simulation Techniques." February 1998. Submitted for Publication.

Collaborations

Funding

The project is funded by Swedish Research Council for Engineering Science (TFR).