research-article

FFX: a portable WCET annotation language

Authors:

Armelle Bonenfant,

Marianne de Michiel,

Jakob ZwirchmayrAuthors Info & Claims

RTNS '12: Proceedings of the 20th International Conference on Real-Time and Network Systems

Pages 91 - 100

https://doi.org/10.1145/2392987.2392999

Published: 08 November 2012 Publication History

Abstract

In order to ensure safety of critical real-time systems it is crucial to verify their temporal properties. Such a property is the Worst-Case Execution Time (WCET), which is obtained by architecture-dependent timing analysis and architecture-independent flow fact analysis. In this article we present a WCET annotation language which is able to express such information originating from the user or the analysis. The open format, named FFX to stand for Flow Facts in XML, is portable, expandable and easy to write, understand and process.

We argue that FFX allows to reuse and exchange the annotation files among WCET tools. FFX therefore permits to tighten WCET results and decreases the effort to support new architectures. Additionally, FFX flow fact files allow fair comparisons of both flow facts and WCET results. FFX can be used for quality assurance when developing new analysis techniques, using it as a flow fact database to test against. We present a small case study exemplifying the above points. Our case study puts special focus on the aspect of comparability and information exchange among WCET tools. In our experiments with FFX, we use the WCET analysis tool chains Otawa/oRange and r-TuBound/CalcWCET167.

Supplementary Material

JPG File (p91-zwirchmayr.jpg)

FFX in Otawa/oRange and r-TuBound/CalcWcet167

Download
6.89 KB

References

[1]

AbsInt Angewandte Informatik GmbH. aiT. http://www.absint.com, 2007.

[2]

Clément Ballabriga, Hugues Cassé, and Marianne de Michiel. A Generic Framework for Blackbox Components in WCET Computation (regular paper). In Workshop on Worst-Case Execution Time Analysis, Dublin, 30/06/09, volume 252, pages 118--129, http://www.ocg.at, octobre 2009. Austrian Computer society.

[3]

Clément Ballabriga, Hugues Cassé, Christine Rochange, and Pascal Sainrat. OTAWA: an Open Toolbox for Adaptive WCET Analysis. In Proc. of IFIP Workshop on Software Technologies for Future Embedded and Ubiquitous Systems (SEUS), Austria, October 2010. Springer.

Digital Library

[4]

Hugues Cassé and Marianne De Michiel. FFX: Flow Facts in XML. Rapport de recherche IRIT/RR-2012-5-FR, IRIT, Université Paul Sabatier, Toulouse, April 2012.

[5]

Hugues Cassé, Marianne de Michiel, and Armelle Bonenfant. FFX (Flow Fact in XML) format. Rapport de recherche RR-2012-5-EN, IRIT, Université Paul Sabatier, Toulouse, 2012.

[6]

Melvin E. Conway. Proposal for an uncol. Commun. ACM, 1(10):5--8, October 1958.

Digital Library

[7]

Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Björn Lisper. The Mäalardalen WCET Benchmarks: Past, Present And Future. In Proc. of 10^th Int'l Workshop on Worst-Case Exeuction Time Analysis (WCET 2010), pages 136--146, Brussels, Belgium, July 2010. Österreichische Computer Gesellschaft.

[8]

Jan Gustafsson. SWEET. http://www.mrtc.mdh.se/projects/wcet/sweet.html, 2001.

[9]

Raimund Kirner. Integration of Static Runtime Analysis and Program Compilation. Master's thesis, Vienna University of Technology, Treitlstraße 3/3/182-1, 1040 Vienna, Austria, 2000.

[10]

Raimund Kirner. User's Manual -- WCET-Analysis Framework based on WCETC. Available at http://www.vmars.tuwien.ac.at/~raimund/calc_wcet/, 2001.

[11]

Raimund Kirner. The WCET Analysis Tool CalcWcet167. In Proc. 5^th Int'l Symposium on Leveraging Applications of Formal Methods, Verification and Validation (to appear). Springer Verlag, October 2012.

Digital Library

[12]

Raimund Kirner, Albrecht Kadlec, Adrian Prantl, Markus Schordan, and Jens Knoop. Towards a Common WCET Annotation Language: Essential Ingredients. In Proc. 8^th Intl. Workshop on Worst-Case Execution Time Analysis (WCET 2008, 2008.

[13]

Raimund Kirner, Jens Knoop, Adrian Prantl, Markus Schordan, and Albrecht Kadlec. Beyond Loop Bounds: Comparing Annotation Languages for Worst-Case Execution Time Analysis. Software and System Modeling, 10(3):411--437, 2011.

Digital Library

[14]

Jens Knoop, Laura Kovács, and Jakob Zwirchmayr. Symbolic Loop Bound Computation for WCET Analysis. In Proc. of PSI 11, pages 116--126, Novosibirsk, Akademgorodok, Russia, 2011.

Digital Library

[15]

Jens Knoop, Laura Kovaćs, and Jakob Zwirchmayr. r-TuBound: Loop Bounds for WCET Analysis. In Proc. of 18^th Logic for Programming Artificial Intelligence and Reasoning (LPAR 18), volume 7180 of LNCS, pages 435--444, Mérida, Venezuela, 2012.

Digital Library

[16]

Marianne De Michiel, Armelle Bonenfant, Hugues Cassé, and Pascal Sainrat. Static Loop Bound Analysis of C Programs Based on Flow Analysis and Abstract Interpretation. In Proc. 14^th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, (RTCSA 2008), Taiwan, 2008.

Digital Library

[17]

Adrian Prantl. High-level Compiler Support for Timing-Analysis. PhD thesis, Vienna University of Technology, Argentinierstraße 8/4/185-1, 1040 Vienna, Austria, 2010.

[18]

Adrian Prantl, Jens Knoop, Markus Schordan, and Markus Triska. Constraint Solving for High-Level WCET Analysis. In Proc. of 18^th Logic-based Methods in Programming Environments, pages 77--88, 2008.

[19]

Adrian Prantl, Markus Schordan, and Jens Knoop. TuBound -- A Conceptually New Tool for Worst-Case Execution Time Analysis. In Proc. 8^th International Workshop on Worst-Case Execution Time Analysis (WCET 2008), pages 141--148, Prague, Czech Republic, 2008. Österreichische Computer Gesellschaft. ISBN: 978-3-85403-237-3.

[20]

Peter Puschner and Anton Schedl. A Tool for the Computation of Worst-Case Task Execution Times. In Proc. of 5^th Euromicro Workshop on Real-Time Systems, pages 224--229, June 1993.

[21]

Rapita Systems Ltd. RapiTime Explained -- White Paper. http://www.rapitasystems.com/downloads/rapitime_explained_white_paper.

[22]

Tidorum Ltd. Bound-T. http://www.tidorum.fi/bound-t, 2005.

[23]

R. von Hanxleden, N. Holsti, B. Lisper, E. Ploedereder, R. Wilhelm, A. Bonenfant, H. Casse, S. Bünte, W. Fellger, S. Gepperth, J. Gustafsson, B. Huber, N. M. Islam, D. Kästner, R. Kirner, L. Kovacs, F. Krause, M. de Michiel, M. C. Olesen, A. Prantl, W. Puffitsch, C. Rochange, M. Schoeberl, S. Wegener, M. Zolda, and J. Zwirchmayr. WCET Tool Challenge 2011: Report. In Proc. 11^th International Workshop on Worst-Case Execution Time Analysis (WCET 2011), 2011.

Cited By

Schuster SWägemann PUlbrich PSchröder-Preikschat WHenkel JLiu X(2021)Annotate once – analyze anywhere: context-aware WCET analysis by user-defined abstractionsProceedings of the 22nd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3461648.3463847(54-66)Online publication date: 22-Jun-2021
https://dl.acm.org/doi/10.1145/3461648.3463847
Damschen MBauer LHenkel J(2016)Extending the WCET Problem to Optimize for Runtime-Reconfigurable ProcessorsACM Transactions on Architecture and Code Optimization10.1145/301405913:4(1-24)Online publication date: 12-Dec-2016
https://dl.acm.org/doi/10.1145/3014059
Li HPuaut IRohou EJan MBen Hedia BGoossens JMaiza C(2014)Traceability of Flow InformationProceedings of the 22nd International Conference on Real-Time Networks and Systems10.1145/2659787.2659805(97-106)Online publication date: 8-Oct-2014
https://dl.acm.org/doi/10.1145/2659787.2659805

Index Terms

FFX: a portable WCET annotation language
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems

Recommendations

A Survey of WCET Analysis of Real-Time Operating Systems
ICESS '09: Proceedings of the 2009 International Conference on Embedded Software and Systems

Timing correctness of hard real-time systems is guaranteed by schedulability analysis and worst-case execution time (WCET) analysis of programs. Traditional WCET analysis mainly deals with application programs and has achieved success in industry. ...
WCET Analysis of the mC/OS-II Real-Time Kernel
CSE '09: Proceedings of the 2009 International Conference on Computational Science and Engineering - Volume 02

Worst-case execution time (WCET) analysis is one of the major tasks in timing validation of hard real-time systems. In complex systems with real-time operating systems (RTOS), the timing properties of the system are decided by both the applications and ...
Hardware support for WCET analysis of hard real-time multicore systems
ISCA '09: Proceedings of the 36th annual international symposium on Computer architecture

The increasing demand for new functionalities in current and future hard real-time embedded systems like automotive, avionics and space industries is driving an increase in the performance required in embedded processors. Multicore processors represent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

RTNS '12: Proceedings of the 20th International Conference on Real-Time and Network Systems

November 2012

216 pages

ISBN:9781450314091

DOI:10.1145/2392987

General Chairs:
Liliana Cucu-Grosjean
INRIA Nancy-Grand Est, France
,
Nicolas Navet
University of Luxembourg, Luxembourg
,
Program Chairs:
Christine Rochange
University of Toulouse/IRIT, France
,
James H. Anderson
University of North Carolina

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

University of Lorraine: University of Lorraine
INRIA: Institut Natl de Recherche en Info et en Automatique
GDR ASR: GDR Architecture, Systèmes et Réseaux

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 November 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

RTNS '12

Sponsor:

University of Lorraine
INRIA
GDR ASR

RTNS '12: 20th International Conference on Real-Time and Network Systems

November 8 - 9, 2012

Pont à Mousson, France

Acceptance Rates

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
124
Total Downloads

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

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schuster SWägemann PUlbrich PSchröder-Preikschat WHenkel JLiu X(2021)Annotate once – analyze anywhere: context-aware WCET analysis by user-defined abstractionsProceedings of the 22nd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3461648.3463847(54-66)Online publication date: 22-Jun-2021
https://dl.acm.org/doi/10.1145/3461648.3463847
Damschen MBauer LHenkel J(2016)Extending the WCET Problem to Optimize for Runtime-Reconfigurable ProcessorsACM Transactions on Architecture and Code Optimization10.1145/301405913:4(1-24)Online publication date: 12-Dec-2016
https://dl.acm.org/doi/10.1145/3014059
Li HPuaut IRohou EJan MBen Hedia BGoossens JMaiza C(2014)Traceability of Flow InformationProceedings of the 22nd International Conference on Real-Time Networks and Systems10.1145/2659787.2659805(97-106)Online publication date: 8-Oct-2014
https://dl.acm.org/doi/10.1145/2659787.2659805

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten