Chronos: Software Timing Analysis

Most embedded applications must provide guaranteed responses within a time bound. To satisfy timing guarantees, embedded system designers often perform extensive simulation of the application code. This is to ensure that the execution time lies within a specified budget under all circumstances. However, simulation might miss corner cases and extensive simulation is infeasible for designs with tight time-to-market constraint.

This project takes a two-pronged approach for developing high-assurance embedded systems with strict timing budget. First, we employ static analysis techniques to estimate the worst-case performance bound. This involves a combination of programming language level analysis with micro-architectural modeling of the platform. Our focus here is to study the effect of micro-architectural features with unpredictable dynamic behavior (e.g., caches, speculation etc.) on timing. Secondly, we employ hardware features such as cache locking, cache partitioning, scratchpad memory to make the runtime behavior of embedded code more predictable.

Tool:


People:

  • Tulika Mitra
  • Huping Ding

Collaborator:



Representative Publications:

[RTS-Jnl] Timing analysis of concurrent programs running on shared cache multi-cores
Yun Liang, Huping Ding, Tulika Mitra, Abhik Roychoudhury, Yan Li, Vivy Suhendra
Real-Time Systems Journal (to appear)

[DAC] WCET-Centric Partial Instruction Cache Locking
Huping Ding, Yun Liang, Tulika Mitra
Design Automation Conference, June 2012
Best Paper Candidate

[TOPLAS] Scratchpad Allocation for Concurrent Embedded Software ACM DL Author-ize service
Vivy Suhendra, Abhik Roychoudhury, Tulika Mitra 
ACM Transactions on Programming Languages and Systems, 34(4), April 2010
Much expanded version of CODES+ISSS’08 conference paper

[DAC] Exploring Locking & Partitioning for Predictable Shared Caches on Multi-Cores
Vivy Suhendra, Tulika Mitra
Design Automation Conference, June 2008

The Worst-Case Execution Time Problem - Overview of Methods and Survey of Tools ACM DL Author-ize service
R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckman, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, P. Stenstrom.
ACM Transactions on Embedded Computing Systems, 7(3), April 2008

Chronos: A Timing Analyzer for Embedded Software
Xianfeng Li, Yun Liang, Tulika Mitra, Abhik Roychoudhury
Science of Computer Programming, Special issue on Experimental Software and Toolkit, 69(1-3), December 2007

Worst-Case Execution Time and Energy Analysis
Tulika Mitra, Abhik Roychoudhury
Chapter in The Compiler Design Handbook: Optimizations and Machine Code Generation, 2nd edition, CRC Press.

Modeling Out-of-Order Processors for WCET Analysis,
Xianfeng Li, Abhik Roychoudhury, Tulika Mitra
Real-Time Systems Journal, Kluwer Academic Publishers, 34(3), November 2006

[RTSS] WCET Centric Data Allocation to Scratchpad Memory,
Vivy Suhendra, Tulika Mitra, Abhik Roychoudhury, Ting Chen
Real-time Systems Symposium, December 2005

Modeling Control Speculation for Timing Analysis,
Xianfeng Li, Tulika Mitra, Abhik Roychoudhury
Real-Time Systems Journal, Kluwer Academic Publishers, 29(1), January 2005

[RTSS] WCET Centric Data Allocation to Scratchpad Memory,
Vivy Suhendra, Tulika Mitra, Abhik Roychoudhury, Ting Chen
Real-time Systems Symposium, December 2005