More Web Proxy on the site http://driver.im/

article

Chronos: A timing analyzer for embedded software

Authors:

Abhik RoychoudhuryAuthors Info & Claims

Science of Computer Programming, Volume 69, Issue 1-3

Pages 56 - 67

Published: 01 December 2007 Publication History

Abstract

Estimating the Worst Case Execution Time (WCET) of real-time embedded software is an important problem. WCET is defined as the upper bound b on the execution time of a program P on a processor X such that for any input the execution time of P on X is guaranteed to not exceed b. Such WCET estimates are crucial for schedulability analysis of real-time systems. In this paper, we present Chronos, a static analysis tool for generating WCET estimates of C programs. It performs detailed micro-architectural modeling to capture the timing effects of the underlying processor platform. Consequently, we can provide safe but tight WCET estimate of a given C program running on a complex modern processor. Chronos is an open-source distribution specifically suited to the needs of the research community. We support processor models captured by the popular SimpleScalar architectural simulator rather than targeting specific commercial processors. This makes the Chronos flexible, extensible and easily accessible to the researcher.

References

[1]

AbsInt, aiT: Worst case execution time analyzer. http://www.absint.com/ait/, 2005

[2]

M. Berkelaar, lp_solve: (Mixed Integer) Linear programming problem solver. Available from: ftp://ftp.es.ele.tue.nl/pub/lp_solve

[3]

D. Burger, T. Austin, The SimpleScalar Tool Set, Version 2.0, Technical Report CS-TR-1997-1342, University of Wisconsin, Madison. http://www.simplescalar.com/docs/users_guide_v2.pdf, Jun. 1997

Digital Library

[4]

P. Cousot, R. Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints, in: ACM Symposium on Principles of Programming Languages, 1977

Digital Library

[5]

CPLEX, The ILOG CPLEX Optimizer v7.5, commercial software. http://www.ilog.com, 2002

[6]

J. Gustafsson, The WCET Tool Challenge 2006, in: B.S. Tiziana Margaris, Anna Philippou (Eds.), 2nd International Symposium on Leveraging Applications of Formal Methods, ISOLA¿06, 2007

[7]

J. Gustafsson, et al., Swedish execution time tool (SWEET), 2006

[8]

C. Healy, M. Sjodin, V. Rustagi, D. Whalley, R. Engelen, Supporting timing analysis by automatic bounding of loop iterations, Real-Time Systems 18 (2-3)

[9]

C. Healy, D. Whalley, Automatic detection and exploitation of branch constraints for timing analysis, IEEE Transactions on Software Engineering 28 (8)

[10]

R. Heckmann, M. Langenbach, S. Thesing, R. Wilhelm, The influence of processor architecture on the design and the results of WCET tools, Proceedings of the IEEE 91 (7)

[11]

X. Li, T. Mitra, A. Roychoudhury, Modeling control speculation for timing analysis, Journal of Real-Time Systems 29 (1)

[12]

X. Li, A. Roychoudhury, T. Mitra, Modeling out-of-order processors for WCET analysis, Journal of Real-Time Systems 34 (3)

[13]

Y.-T.S. Li, Cinderella 3.0 WCET analyzer. http://www.princeton.edu/~yauli/cinderella-3.0/, 1996

[14]

Li, Y.-T.S. and Malik, S., Performance Analysis of Real-time Embedded Software. 1999. Kluwer Academic Publishers.

[15]

T. Ltd., Bound-t execution time analyzer. http://www.bound-t.com, 2005

[16]

T. Lundqvist, P. Stenstrom, Timing anomalies in dynamically scheduled microprocessors, in: IEEE Real-Time Systems Symposium, 1999

[17]

Mitra, T. and Roychoudhury, A., Worst case execution time and energy analysis. In: Srikant, Y., Shankar, P. (Eds.), The Compiler Design Handbook, CRC Press.

[18]

T. Mitra, A. Roychoudhury, X. Li, Timing analysis of embedded software for speculative processors, in: ACM SIGDA International Symposium on System Synthesis, ISSS, 2002

[19]

I. Puaut, Heptane static WCET analyzer. http://www.irisa.fr/aces/work/heptane-demo/heptane.html, 2003

[20]

P. Puschner, C. Koza, Calculating the maximum execution time of real-time programs, Journal of Real-time Systems 1 (2)

[21]

M. research group, WCET benchmark programs. http://www.mrtc.mdh.se/projects/wcet/benchmarks.html

[22]

A. Shaw, Reasoning about time in higher level language software, IEEE Transactions on Software Engineering 1 (2)

[23]

J. Souyris, E. Pavec, G. Himbert, V. Jegu, G. Borios, R. Heckmann, Computing the worst case execution time of an avionics program by abstract interpretation. http://www.absint.com/aiT_airbus.pdf

[24]

J. Staschulat, Symta/p: Symbolic timing analysis for processes. http://www.ida.ing.tu-bs.de/research/projects/symta/home.e.shtml, 2005

[25]

R. Wilhelm, The worst-case execution time problem¿overview of methods and survey of tools, ACM Transactions on Embedded Computing Systems (in press)

[26]

Wilhelm, R., Why AI + ILP is good for WCET, but MC is not, nor ILP alone. In: LNCS, vol. 2937.

Cited By

Hsu MHetzelt FGens DMaitland MFranz MChandra SBlincoe KTonella P(2023)A Highly Scalable, Hybrid, Cross-Platform Timing Analysis Framework Providing Accurate Differential Throughput Estimation via Instruction-Level TracingProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616246(821-831)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616246
Priya Dharishini PRamana Murthy P(2022)Static Analyzer for Computing WCET of Multithreaded Programs using Hoare's CSPProceedings of the 15th Innovations in Software Engineering Conference10.1145/3511430.3511438(1-12)Online publication date: 24-Feb-2022
https://dl.acm.org/doi/10.1145/3511430.3511438
Chen JChen KDu CLiu Y(2021)Design and implementation of a virtual ARINC 653 simulation platformSimulation10.1177/003754972199601897:6(427-436)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1177/0037549721996018
Show More Cited By

Index Terms

Chronos: A timing analyzer for embedded software

Recommendations

Avoiding Timing Anomalies Using Code Transformations
ISORC '10: Proceedings of the 2010 13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing

Divide-and-conquer approaches to worst-case execution-time analysis (WCET analysis) pose a safety risk when applied to code for complex modern processors: Interferences between the hardware acceleration mechanisms of these processors lead to timing ...
ChronOS Linux: a best-effort real-time multiprocessor Linux kernel
DAC '11: Proceedings of the 48th Design Automation Conference

We present ChronOS Linux, a best-effort real-time Linux kernel for chip multiprocessors (CMPs). ChronOS addresses the intersection of three problem spaces: a) OS-support for obtaining best-effort timing assurances, b) real-time Linux kernel augmented ...
Chronos: predictable low latency for data center applications
SoCC '12: Proceedings of the Third ACM Symposium on Cloud Computing

In data center applications, predictability in service time and controlled latency, especially tail latency, are essential for building performant applications. This is especially true for applications or services built by accessing data across ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Science of Computer Programming

Science of Computer Programming Volume 69, Issue 1-3

December, 2007

88 pages

ISSN:0167-6423

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2007.

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 01 December 2007

Author Tag

Worst Case Execution Time (WCET) analysis

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

59
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hsu MHetzelt FGens DMaitland MFranz MChandra SBlincoe KTonella P(2023)A Highly Scalable, Hybrid, Cross-Platform Timing Analysis Framework Providing Accurate Differential Throughput Estimation via Instruction-Level TracingProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616246(821-831)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616246
Priya Dharishini PRamana Murthy P(2022)Static Analyzer for Computing WCET of Multithreaded Programs using Hoare's CSPProceedings of the 15th Innovations in Software Engineering Conference10.1145/3511430.3511438(1-12)Online publication date: 24-Feb-2022
https://dl.acm.org/doi/10.1145/3511430.3511438
Chen JChen KDu CLiu Y(2021)Design and implementation of a virtual ARINC 653 simulation platformSimulation10.1177/003754972199601897:6(427-436)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1177/0037549721996018
Búr MMarussy KMeyer BVarró D(2021)Worst-case Execution Time Calculation for Query-based Monitors by Witness GenerationACM Transactions on Embedded Computing Systems10.1145/347190420:6(1-36)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3471904
Luppold AOehlert DFalk H(2020)Compiling for the Worst CaseACM Transactions on Embedded Computing Systems10.1145/338175219:2(1-26)Online publication date: 11-Mar-2020
https://dl.acm.org/doi/10.1145/3381752
Venkataramani VKulkarni AMitra TPeh LChen JShrivastava A(2019)SPECTRUM: a software defined predictable many-core architecture for LTE baseband processingProceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3316482.3326352(82-96)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3316482.3326352
Weichslgartner AWildermann SGangadharan DGlaß MTeich J(2018)A Design-Time/Run-Time Application Mapping Methodology for Predictable Execution Time in MPSoCsACM Transactions on Embedded Computing Systems10.1145/327466517:5(1-25)Online publication date: 19-Nov-2018
https://dl.acm.org/doi/10.1145/3274665
Zheng WWu HNie C(2017)Integrating task scheduling and cache locking for multicore real-time embedded systemsACM SIGPLAN Notices10.1145/3140582.308103352:5(71-80)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3140582.3081033
Zheng WWu HNie CNagarajan VShao Z(2017)Integrating task scheduling and cache locking for multicore real-time embedded systemsProceedings of the 18th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3078633.3081033(71-80)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3078633.3081033
Li JZhao MJu LXue CJia Z(2017)Maximizing Forward Progress with Cache-aware Backup for Self-powered Non-volatile ProcessorsProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062282(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062282
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents