CSC News

August 29, 2007

Mueller Receives NSF Award to Study Hybrid Timing Analysis via Multi-Mode Execution

Dr. Frank Mueller has been awarded $140,000 by the National Science Foundation to fund his research proposal titled “CSR--EHS: Collaborative Research: Hybrid Timing Analysis via Multi-Mode Execution.” 

The award will run from August 1, 2007 through July 31, 2009.

Research Abstract - Current software design for safety-critical embedded systems requires stringent compliance with coding standards to ensure safety and reliability.  Safety standards typically require coverage testing for such systems. A key additional requirement for real-time embedded systems is predictable timing behavior of software components. In particular, hard real-time systems have timing constraints that must be met or the system is considered incorrect.  Hence, safety requirements in avionics and in the automotive industry are being extended to require verifiable bounds on execution times.

Determining bounds on the worst-case execution time (WCET) of embedded software is a critically important problem for next-generation embedded real-time systems.  Currently, practitioners resort to testing methods to determine execution times of real-time tasks.  However, testing alone cannot provide a verifiable (safe) upper bound on WCET.  Static timing analysis provides a safer and more efficient alternative to testing.  It yields verifiable bounds on the WCET of tasks regardless of program input by simulating execution along the control-flow paths within the program structure while considering architectural details.  However, static timing analysis cannot keep pace with architectural innovations, e.g., out-of-order execution, speculation and dynamic branch prediction.  Simulation of hardware components is also prone to inaccuracy due to lack of information about subtle details of processors.

We propose a fundamentally new approach to bounding the WCET with three major contributions, presented as management tasks, to overcome the gap between the capabilities of static timing analysis and the advances in hardware.

1) Instead of simulating execution, we promote actual execution in hardware to assess the WCET of a task. Such an approach not only renders tedious hardware modeling unnecessary, but it also guarantees correct behavior regardless of architectural complexity. This provides a means to verify bounds on WCET.

2) Our approach will be evaluated and its complexity (time/space) will be assessed by synthesis on an FPGA platform. This task assesses the feasibility of the design, validates a prototype implementation.

3) We will study the impact of advanced architectural features (dynamic branch prediction, out-of-order/speculative execution etc.) in a co-design space exploration to advance science in providing predictability and tight WCET bounds.

Return To News Homepage