A project at Computer Engineering, Chalmers: High-Performance Computer Architecture Group
Many industrial applications require a high and predictable performance. Examples are vehicles where the trend is to use microprocessors in critical control systems. To achieve 100% predictability often is 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.
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 aggressively pipelined microprocessor systems employing multi-level memory hierarchies. An ultimate goal with this project is to deliver methods that automatically make estimates of WCET for real-time programs with hard deadlines that are tight so that the performance potential of high-performance microprocessors can be exploited.
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) model 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 towards using microprocessors in critical control applications, such automated test approaches are key.
Thomas Lundqvist: ``A Static Timing Analysis Method for Programs on High-Performance Processors,'' Licentiate thesis TR-315L, June 1999. (abstract)
Thomas Lundqvist and Per Stenström: ``A Method to Improve the Estimated Worst-Case Performance of Data Caching,'' in Proceedings of the 6th International Conference on Real-Time Computing Systems and Applications (RTCSA'99), pages 255-262, December 1999. (abstract)
Thomas Lundqvist and Per Stenström: ``Timing Anomalies in Dynamically Scheduled Microprocessors,'' in Proceedings of 20th IEEE Real-Time Systems Symposium (RTSS'99), pages 12-21, December 1999. (abstract)
Thomas Lundqvist and Per Stenström: ``An Integrated Path and Timing Analysis Method based on Cycle-Level Symbolic Execution,'' in Real-Time Systems, 17 (2/3):183-207, November 1999. (abstract)
Thomas Lundqvist and Per Stenström: ``Integrating Path and Timing Analysis using Instruction-Level Simulation Techniques,'' in Proceedings of ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, pages 1-15, June 1998. (abstract)