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

research-article

WCET analysis in shared resources real-time systems with TDMA buses

Authors:

Sebastian AltmeyerAuthors Info & Claims

RTNS '15: Proceedings of the 23rd International Conference on Real Time and Networks Systems

Pages 183 - 192

https://doi.org/10.1145/2834848.2834871

Published: 04 November 2015 Publication History

Abstract

Predictability is an important aspect in real-time and safety-critical systems, where non-functional properties -- such as the timing behavior -- have high impact on the system correctness. As many safety-critical systems have a growing performance demand, simple, but outdated architectures are not sufficient anymore. Instead, multi-core systems are more and more popular, even in the real-time domain. To combine the performance benefits of a multi-core architecture with the required predictability, Time Division Multiple Access (TDMA) buses are often advocated. In this paper, we are interested in accesses to shared resources in such environments. Our approach uses SMT (Satisfiability Modulo Theory) to encode the semantics and execution time of the analyzed program in an environment with shared resources. We use an SMT-solver to find a solution that corresponds to the execution path with correct semantics and maximal execution time. We propose to model a shared bus with TDMA arbitration policy. Using examples, we show how the WCET estimation is enhanced by combining the semantics and the shared bus analysis in SMT.

References

[1]

M. Alt, C. Ferdin, F. Martin, and R. Wilhelm. Cache behavior prediction by abstract interpretation. In Science of Computer Programming, pages 52--66. Springer, 1996.

Digital Library

[2]

C. Ballabriga, H. Cassé, C. Rochange, and P. Sainrat. OTAWA: An open toolbox for adaptive WCET analysis. In S. Min, R. Pettit, P. Puschner, and T. Ungerer, editors, Software Technologies for Embedded and Ubiquitous Systems, pages 35--46. Springer Berlin Heidelberg, 2010.

Digital Library

[3]

G. Behrmann, A. David, and K. G. Larsen. A tutorial on uppaal. In M. Bernardo and F. Corradini, editors, SFM-RT 2004, number 3185 in LNCS, pages 200--236. Springer-Verlag, September 2004.

[4]

A. Biere, J. Knoop, L. Kovács, and J. Zwirchmayr. The auspicious couple: Symbolic execution and WCET analysis. WCET, 30:53--63, 2013.

[5]

S. Chattopadhyay, A. Roychoudhury, and T. Mitra. Modeling shared cache and bus in multi-cores for timing analysis. In Proceedings of the 13th International Workshop on Software and Compilers for Embedded Systems, SCOPES '10, pages 6:1--6:10, New York, USA, 2010. ACM.

Digital Library

[6]

R. C. David. The SMT-LIBv2 Language and Tools: A Tutorial, March 2013.

[7]

L. De Moura and N. Bjorner. Z3: An efficient smt solver. In Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS'08/ETAPS'08, pages 337--340, Berlin, Heidelberg, 2008. Springer-Verlag.

Digital Library

[8]

A. Gustavsson, A. Ermedahl, B. Lisper, and P. Pettersson. Towards WCET Analysis of Multicore Architectures Using UPPAAL. In B. Lisper, editor, WCET 2010, volume 15 of OpenAccess Series in Informatics (OASIcs), pages 101--112. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010.

[9]

J. Henry, M. Asavoae, D. Monniaux, and C. Maïza. How to compute worst-case execution time by optimization modulo theory and a clever encoding of program semantics. In Proceedings of the 2014 SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems, LCTES '14, pages 43--52, New York, NY, USA, 2014. ACM.

Digital Library

[10]

J. Henry, D. Monniaux, and M. Moy. Pagai: A path sensitive static analyser. Electron. Notes Theor. Comput. Sci., 289:15--25, Dec. 2012.

Digital Library

[11]

T. Kelter, H. Falk, P. Marwedel, S. Chattopadhyay, and A. Roychoudhury. Static analysis of multi-core tdma resource arbitration delays. Real-Time Syst., 50(2):185--229, Mar. 2014.

Digital Library

[12]

H. Li, I. Puaut, and E. Rohou. Traceability of flow information: Reconciling compiler optimizations and wcet estimation. In Proceedings of the 22nd International Conference on Real-Time Networks and Systems, page 97. ACM, 2014.

Digital Library

[13]

M. Lv, W. Yi, N. Guan, and G. Yu. Combining abstract interpretation with model checking for timing analysis of multicore software. In Proceedings of the 2010 31st IEEE Real-Time Systems Symposium, RTSS '10, pages 339--349, Washington, DC, USA, 2010. IEEE Computer Society.

Digital Library

[14]

P. Raymond. A general approach for expressing infeasibility in implicit path enumeration technique. In International Conference on Embedded Software (EMSOFT 2014), New Dehli, India, oct 2014.

Digital Library

[15]

P. Raymond, C. Maiza, C. Parent-Vigouroux, F. Carrier, and M. Asavoae. Timing analysis enhancement for synchronous program. Real-Time Systems, pages 1--29, 2015.

Digital Library

[16]

J. Reineke and R. Sen. Sound and efficient WCET analysis in the presence of timing anomalies. In WCET 2009, page 101, 2009.

[17]

J. Reineke, B. Wachter, S. Thesing, R. Wilhelm, I. Polian, J. Eisinger, and B. Becker. A definition and classification of timing anomalies. WCET, 4, 2006.

[18]

A. Schranzhofer, J.-J. Chen, and L. Thiele. Timing analysis for tdma arbitration in resource sharing systems. RTAS '10, pages 215--224, Washington, DC, USA, 2010. IEEE Computer Society.

Digital Library

Cited By

Ghosh PKarsai G(2023)Distributed Cyber Physical Systems Software Model Checking using Timed Automata2023 IEEE 26th International Symposium on Real-Time Distributed Computing (ISORC)10.1109/ISORC58943.2023.00030(164-169)Online publication date: May-2023
https://doi.org/10.1109/ISORC58943.2023.00030
Krishna C(2022)Global Voltage Scaling Across Multiple Cores for Real-Time WorkloadsIEEE Embedded Systems Letters10.1109/LES.2022.314371914:3(159-162)Online publication date: Sep-2022
https://doi.org/10.1109/LES.2022.3143719
Krishna C(2021)Task Sequencing in Frame-Based CPSIEEE Embedded Systems Letters10.1109/LES.2021.305907313:4(154-157)Online publication date: Dec-2021
https://doi.org/10.1109/LES.2021.3059073
Show More Cited By

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. ...
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 ...
Hardware support for WCET analysis of hard real-time multicore systems

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 '15: Proceedings of the 23rd International Conference on Real Time and Networks Systems

November 2015

320 pages

ISBN:9781450335911

DOI:10.1145/2834848

General Chair:
Julien Forget
Université de Lille, France

Copyright © 2015 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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

RTNS '15

RTNS '15: 23rd International Conference on Real-Time Networks and Systems

November 4 - 6, 2015

Lille, France

Acceptance Rates

RTNS '15 Paper Acceptance Rate 31 of 66 submissions, 47%;

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
83
Total Downloads

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

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghosh PKarsai G(2023)Distributed Cyber Physical Systems Software Model Checking using Timed Automata2023 IEEE 26th International Symposium on Real-Time Distributed Computing (ISORC)10.1109/ISORC58943.2023.00030(164-169)Online publication date: May-2023
https://doi.org/10.1109/ISORC58943.2023.00030
Krishna C(2022)Global Voltage Scaling Across Multiple Cores for Real-Time WorkloadsIEEE Embedded Systems Letters10.1109/LES.2022.314371914:3(159-162)Online publication date: Sep-2022
https://doi.org/10.1109/LES.2022.3143719
Krishna C(2021)Task Sequencing in Frame-Based CPSIEEE Embedded Systems Letters10.1109/LES.2021.305907313:4(154-157)Online publication date: Dec-2021
https://doi.org/10.1109/LES.2021.3059073
Huybrechts TMercelis SHellinckx P(2020)A Survey on the Software and Hardware-Based Influences on the Worst-Case Execution TimeAdvances on P2P, Parallel, Grid, Cloud and Internet Computing10.1007/978-3-030-61105-7_27(271-281)Online publication date: 9-Oct-2020
https://doi.org/10.1007/978-3-030-61105-7_27
Patil SScholten STao MAl-Asaad H(2019)Survey of Memory, Timing, and Power Management Verification Methods for Multi-core Processors2019 IEEE 10th Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON)10.1109/IEMCON.2019.8936198(0110-0119)Online publication date: Oct-2019
https://doi.org/10.1109/IEMCON.2019.8936198
Hebbache FBrandner FJan MPautet L(2019)Work-conserving dynamic time-division multiplexing for multi-criticality systemsReal-Time Systems10.1007/s11241-019-09336-wOnline publication date: 26-Jul-2019
https://doi.org/10.1007/s11241-019-09336-w

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.

Media

Figures

Other

Tables

View Table of Contents