Models, Methods and Tools for Timing Analysis

Motivation

It is predicted that multicores will be increasingly used in future embedded real-time systems for high performance and low energy consumption. The major obstacle is that we may not predict and provide any guarantee on real-time properties of software on such platforms. Shared resources, such as shared caches and shared memory buses, severely degrade the timing predictability of multicore software due to access contention between cores. Since the number of processor cores on a chip continues to increase, the amount of traffic on the shared resources increases accordingly, and this problem is expected to be even worse in the future.

To ensure useful timing guarantees for multicore real-time systems, we need techniques that can explore the timing behaviors of concurrent programs deployed on multicores with either private or shared resources, and then produce predictions of timing properties, such as Worst-Case Execution Time or Worst-Case Response Time, for all real-time tasks.

Long Term Goal

Discover analysis theories and frameworks that can efficiently obtain precise timing properties for concurrent programs scheduled (by any given scheduling policies) on given multicore architectures (especially with shared resources).

Expected Results

Demonstrate analysis techniques, frameworks and tools for WCET and WCRT estimations, or any form of timing predictability representations for concurrent real-time programs on multicores.

Approaches

  • Investigate techniques to model the behaviors of concurrent programs;
  • Investigate different techniques for timing analysis of both dedicated and shared resources respectively, and effectively combine the techniques into an overall framework;
  • Investigate the interaction between task-level analysis and system-level analysis and how this can affect the precision and efficiency of timing analysis.
  • Modeling interferences on shared resources in multi-cores as real-time scheduling problem of general task models (e.g., digraph task models), and investigate analysis techniques for these scheduling problems.

Achievement

  • A new WCET analysis methodology, combining Abstract Interpretation and Model Checking, to precisely estimate the WCET of multi-core programs.
  • The analysis techniques for general Digraph Real-Time (DRT) model. A new efficient graph traversal technique for deriving task set execution demands that is based on graph traversal abstraction. A direct application of this is an efficient uniprocessor feasibility test.

Publications

  • Nan Guan, Mingsong Lv, Wang Yi and Ge Yu "WCET Analysis with MRU Cache: Challenging LRU for Predictability", The 18th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2012.
  • Martin Stigge, Pontus Ekberg, Nan Guan and Wang Yi. On the Tractability of Digraph-Based Task Models. In the proc of the 23rd Euromicro Conference on Real-Time Systems (ECRTS), 2011.
  • Martin Stigge, Pontus Ekberg, Nan Guan and Wang Yi. The Digraph Real-Time Task Model. In the proceedings of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2011
  • Mingsong Lv, Nan Guan, Wang Yi and Ge Yu. "Combining Abstract Interpretation with Model Checking for Timing Analysis of Multicore Software". In proceedings of the 31st IEEE Real-Time Systems Symposium (RTSS), 2010.

Tool contribution

A timing analysis tool called McAiT has been developed, which is available at http://www.neu-rtes.org/mcait
Currently, the tool support timing analysis of multicores with private caches for each core and a shared memory bus for all cores.

Staff

Senior: Philipp Ruemmer (Contact), Wang Yi
Ph.D. students: Pontus Ekberg, Nan Guan, Martin Stigge
Visitors: Mingsong Lv

Internal page