Scalable Timing Analysis Methods for Embedded Software

Funding and Open Positions

This project is funded by A*STAR Public Sector Funding for three years  2012-2015.

Principal Investigator (PI):  Abhik Roychoudhury,  National University of Singapore.

Research Staff

Research Fellow:   Clement Ballabriga

Research Assistant:  Chong Lee Kee

Aims of the Project

Real-time embedded software are ubiquitious and control the functionality of many devices used in our everyday lives. The focus of the proposed project will be on compositional timing analysis methods which efficiently derive Worst Case Execution Time (WCET) estimates of large real-life embedded software. WCET analysis usually involves program path analysis as well as micro-architectural analysis. We will aim for achieving compositionality both at the program level, as well in the construction of timing models for the underlying micro-architecture.

At the program level, we plan to generate timing summaries of the individual program fragments such as functions / procedures. Consequently, if a library or a small part of a program is changed – we do not need to re-do the entire analysis.

At the micro-architecture level, our focus will be on building timing models to capture the timing effects of multi-cores. Processor manufacturers have increasingly moved towards multi-cores, and this has impacted the embedded processor market as well. However, when we build a software timing analyzer for multi-core platforms, we want the analyzer to be configurable with respect to small changes, such as changes in the number of cores. Such configurability may be achieved by compositional analysis of the timing effects of the individual cores, that is, we want to analyze the timing effects of each processor core individually and compose them to get the timing effects of a multi-core platform. This removes the need to re-do the complete analysis in case of small changes in the platform.

The main deliverable of the project is a scalable WCET analysis tool that can generate tight execution time bounds for software (possibly running via a real-time operating system  RTOS) on multi-core platforms. This will validate the utility of the compositional timing analysis methods proposed in the project.

Publications so far from the project

This project is putting a determined focus on multi-core Chronos --- a worst case execution time (WCET) analyzer tool for multi-core platforms. Originally, the tool has been built upon Chronos --- a WCET analyzer tool for single core platforms. The single core version of Chronos is still actively maintained and distributed.  Chronos for multi-cores extends its single core counterpart through two crucial analyses: (1) shared Level 2 instruction cache and (2) shared TDMA round robin bus. Additionally, multi-core version of Chronos applies innovative analyses techniques, which capture the key interactions of shared cache and shared bus with different other micro-architectural features (e.g. pipeline and branch prediction).

Recent Publications from the project

[LCTES]

Program Performance Spectrum ( pdf )

Sudipta Chattopadhyay, Lee Kee Chong, Abhik Roychoudhury

ACM Conference on Languages, Compilers and Tools for Embedded Systems (LCTES) 2013.

[RTAS]

Precise Micro-architectural modeling for WCET analysis via AI+SAT  ( pdf )

Abhijeet Banerjee, Sudipta Chattopadhyay, Abhik Roychoudhury

19th IEEE Real-time and Embedded Technology and Applications Symposium (RTAS) 2013.

[TECS]

A Unified WCET Analysis Framework for Multi-core Platforms  ( pdf )

Sudipta Chattopadhyay, Lee Kee Chong, Abhik Roychoudhury, Timon Kelter, Peter Marwedel, Heiko Falk

ACM Transactions on Embedded Computing Systems (TECS), To appear.

[RTS-journal]

Scalable and Precise Refinement of Cache Timing Analysis via Path sensitive Verification  ( pdf )

Sudipta Chattopadhyay and Abhik Roychoudhury

Real-time Systems Journal, Springer, To appear. 

[RTAS]

A Unified WCET Analysis Framework for Multi-core Platforms ( PDF ) 
Sudipta Chattopadhyay, Chong Lee Kee, Abhik Roychoudhury, Timon Kelter, Peter Marwedel and Heiko Falk
18th IEEE Real-time and Embedded Technology and Applications Symposium (RTAS) 2012.

[RTS-journal]

Timing Analysis of Concurrent Programs running on Shared Cache Multi-cores ( pdf )
Yun Liang, Huping Ding, Tulika Mitra, Abhik Roychoudhury, Yan Li, Vivy Suhendra
Real-time Systems Journal, 48(6), 638-680, 2012.

Related earlier Publications