research-article

Re-sampling for statistical timing analysis of real-time systems

Authors:

Luca Santinelli,

Guillem Bernat,

Robert I. Davis,

Liliana Cucu-GrosjeanAuthors Info & Claims

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

Pages 111 - 120

https://doi.org/10.1145/2392987.2393001

Published: 08 November 2012 Publication History

Abstract

Guaranteeing timing constraints is the main purpose of analyses for real-time systems. The satisfaction of these constraints may be verified with probabilistic methods (relying on statistical estimations of certain task parameters) offering both hard and soft guarantees. In this paper, we address the problem of sampling applied to the distributions of worst-case execution times. The pessimism of presented sampling techniques is then evaluated at the level of response times.

Supplementary Material

JPG File (p111-dorin.jpg)

Re-sampling is way of simplifying distributions in order to decrease the cost and complexity of the analysis. Re-sampling of WCET distribution implies selecting a representative subset of samples to be kept from the original set of values, and, subsequently, redistributing the probability mass of the unselected values amongst the selected ones in such a way that the newly obtained distribution is not optimistic with respect to the original one.

Download
61.87 KB

References

[1]

A. Burns, G. Bernat, and I. Broster, "A probabilistic framework for schedulability analysis," in Third International Embedded Software Conference (EMSOFT 2003), 2003, pp. 1--15.

[2]

M. Gardner and J. Lui, "Analyzing stochastic fixed-priority real-time systems," in 5thInternational Conference on Tools and Algorithms for the Construction and Analysis of Systems, 1999.

Digital Library

[3]

G. A. Kaczynski, L. L. Bello, and T. Nolte, "Towards stochastic response-time of hierarchically scheduled real-time tasks," in Proceedings of 11th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA 2006), 2006, pp. 453--456.

[4]

J. L. Díaz, D. F. García, K. Kim, C.-G. Lee, L. Lo Bello, J. M. López, S. L. Min, and O. Mirabella, "Stochastic analysis of periodic real-time systems," in Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS 2002), 2002, p. 289.

Digital Library

[5]

T. Tia, Z. Z. Deng, M. Shankar, M. Storch, J. Sun, L. Wu, and J. Liu, "Probabilistic performance guarantee for real-time tasks with varying computation times." in IEEE Real-Time and Embedded Technology and Applications Symposium (ETFA 1995), 1995.

Digital Library

[6]

A. Atlas and A. Bestavros, "Statistical rate monotonic scheduling," in 19th IEEE Real-Time Systems Symposium (RTSS 1998), 1998.

Digital Library

[7]

L. Cucu-Grosjean, L. Santinelli, M. Houston, C. Lo, T. Vardanega, L. Kosmidis, J. Abella, E. Mezzeti, Q. E., and F. Cazorla, "Measurement-based probabilistic timing analysis for multi-path programs," in the 24th Euromicro Conference on Real-Time Systems (ECRTS12), 2012.

Digital Library

[8]

D. Khan, N. Navet, B. Bavoux, and J. Migge, "Aperiodic traffic in response time analyses with adjustable safety level," in 14th IEEE International Conference on Emerging Techonologies and Factory Automation (ETFA2009), 2009.

Digital Library

[9]

K. Kim, J. L. Diaz, L. Lo Bello, J. M. Lopez, C.-G. Lee, and S. L. Min, "An exact stochastic analysis of priority-driven periodic real-time systems and its approximations," IEEE Trans. Comput., vol. 54, no. 11, pp. 1460--1466, 2005.

Digital Library

[10]

S. Edgar and A. Burns, "Statistical analysis of WCET for scheduling," in 22nd IEEE International Real-Time Systems Symposium (RTSS 2001), 2001, pp. 215--224.

Digital Library

[11]

J. Hansen, S. Hissam, and G. Moreno, "Statistical-based WCET estimation and validation," in 9th International Workshop on Worst-Case Execution Time (WCET) Analysis, 2009.

[12]

J. Beirlant, J. Teugels, Y. Goegebeur, J. Segers, D. D. Waal, and C. Ferro, Statistics Of Extremes: Theory And Applications, Wiley, Ed. Wiley, 2004.

[13]

I. B. Y. Lu, T. Nolte and L. Cucu, "A new way about using statistical analysis of worst-case execution times," in in the WiP sesion of the Euromicro Conference on Real-Time Systems, 2011.

Digital Library

[14]

J. Diaz, J. Lopez, G. M., A. Campos, K. Kim, and L. Lo Bello, "Pessimism in the stochastic analysis of real-time systems: Concept and applications," in 25th IEEE International Real-Time Systems Symposium (RTSS 2004), 2004, pp. 197--207.

Digital Library

[15]

W. A. Fuller, Sampling Statistics, Wiley, Ed. Wiley, 2009.

[16]

K. S. Refaat and P.-E. Hladik, "Efficient stochastic analysis of real-time systems via random sampling," in IEEE Euromicro Conference on Real-Time Systems (ECRTS 2010), 2010, pp. 175--183.

Digital Library

[17]

F. Cazorla, E. Quinones, T. Vardanega, L. Cucu-Grosjean, B. Triquet, G. Bernat, E. Berger, J. Abella, F. Wartel, M. Houston, L. Santinelli, D. Maxim, L. Kosmidis, and C. Lo, "Proartis: Probabilistically analyzable real-time system," ACM Transactions on Embedded Computing Systems, 2012.

[18]

J. M. López, J. L. Díaz, J. Entrialgo, and D. García, "Stochastic analysis of real-time systems under preemptive priority-driven scheduling," Real-Time Syst., pp. 180--207, 2008.

Digital Library

[19]

L. Santinelli, P. M. Yomsi, D. Maxim, and L. Cucu-Grosjean, "A component-based framework for modeling and analyzing probabilistic real-time systems," 16th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA'11), 2007.

[20]

D. Maxim, L. Santinelli, and L. Cucu-Grosjean, Improved sampling for statistical timing analysis of real-time systems, in 4th Junior Researcher Workshop on Real-Time Computing, 2010.

[21]

L. Cucu-Grosjean, "Probabilistic real-time schedulability analysis: from uniprocessor to multiprocessor when the execution times are uncertain," RR-INRIA, May 2009.

[22]

"http://www.rapitasystems.com/."

[23]

E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra, "Dimensionality reduction for fast similarity search in large time series databases," Knowledge and Information Systems, vol. 3, pp. 263--286, 2001, 10.1007/PL00011669. {Online}. Available: http://dx.doi.org/10.1007/PL00011669

[24]

D. Maxim, O. Buffet, L. Santinelli, L. Cucu-Grosjean, and R. Davis, "Optimal priority assignments for probabilistic real-time systems," in the 19th International Conference on Real-Time and Network Systems (RTNS2011), 2011.

Cited By

Zagalo KAbdeddaim YBar-Hen ACucu-Grosjean L(2023)Response Time Stochastic Analysis for Fixed-Priority Stable Real-Time SystemsIEEE Transactions on Computers10.1109/TC.2022.321142172:1(3-14)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TC.2022.3211421
Markovic FNolte TPapadopoulos A(2022)Analytical Approximations in Probabilistic Analysis of Real-Time Systems2022 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS55097.2022.00023(158-171)Online publication date: Dec-2022
https://doi.org/10.1109/RTSS55097.2022.00023
Chen KGunzel Mvon der Bruggen GChen J(2022)Critical Instant for Probabilistic Timing Guarantees: Refuted and Revisited2022 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS55097.2022.00022(145-157)Online publication date: Dec-2022
https://doi.org/10.1109/RTSS55097.2022.00022
Show More Cited By

Index Terms

Re-sampling for statistical timing analysis of real-time systems

Recommendations

Towards an analysis framework for tasks with probabilistic execution times and probabilistic inter-arrival times
Special Issue on the 24th Euromicro Conference on Real-Time Systems

In this paper we investigate the problem of calculating the response time distribution for real-time tasks with probabilistic worst-case execution times, probabilistic inter-arrival times and probabilistic deadlines. We propose a definition for the ...
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. ...
Efficient Stochastic Analysis of Real-Time Systems via Random Sampling
ECRTS '10: Proceedings of the 2010 22nd Euromicro Conference on Real-Time Systems

This paper provides a stochastic approach to the analysis of real-time systems under preemptive priority-driven scheduling. The main idea is to simplify the execution time distributions via random sampling to decrease complexity. This beneficial effect ...

Comments

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

Author Tags

Qualifiers

Research-article

Funding Sources

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

29
Total Citations
View Citations
217
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zagalo KAbdeddaim YBar-Hen ACucu-Grosjean L(2023)Response Time Stochastic Analysis for Fixed-Priority Stable Real-Time SystemsIEEE Transactions on Computers10.1109/TC.2022.321142172:1(3-14)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TC.2022.3211421
Markovic FNolte TPapadopoulos A(2022)Analytical Approximations in Probabilistic Analysis of Real-Time Systems2022 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS55097.2022.00023(158-171)Online publication date: Dec-2022
https://doi.org/10.1109/RTSS55097.2022.00023
Chen KGunzel Mvon der Bruggen GChen J(2022)Critical Instant for Probabilistic Timing Guarantees: Refuted and Revisited2022 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS55097.2022.00022(145-157)Online publication date: Dec-2022
https://doi.org/10.1109/RTSS55097.2022.00022
Bozhko Svon der Bruggen GBrandenburg B(2021)Monte Carlo Response-Time Analysis2021 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS52674.2021.00039(342-355)Online publication date: Dec-2021
https://doi.org/10.1109/RTSS52674.2021.00039
Louise S(2019)A First Step Toward Using Quantum Computing for Low-level WCETs EstimationsACM Transactions on Architecture and Code Optimization10.1145/333554916:3(1-22)Online publication date: 18-Jul-2019
https://dl.acm.org/doi/10.1145/3335549
Cazorla FKosmidis LMezzetti EHernandez CAbella JVardanega T(2019)Probabilistic Worst-Case Timing AnalysisACM Computing Surveys10.1145/330128352:1(1-35)Online publication date: 13-Feb-2019
https://dl.acm.org/doi/10.1145/3301283
Ren JXu ZYu CLin CWu GTan G(2019)Execution allowance based fixed priority scheduling for probabilistic real-time systemsJournal of Systems and Software10.1016/j.jss.2019.03.001152:C(120-133)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1016/j.jss.2019.03.001
Ren JBi RSu XLiu QWu GTan G(2018)Workload-aware harmonic partitioned scheduling for probabilistic real-time systems2018 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE.2018.8342005(213-218)Online publication date: Mar-2018
https://doi.org/10.23919/DATE.2018.8342005
Lesage BGriffin DAltmeyer SCucu-Grosjean LDavis R(2018)On the analysis of random replacement caches using static probabilistic timing methods for multi-path programsReal-Time Systems10.1007/s11241-017-9295-254:2(307-388)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11241-017-9295-2
Abdeddaïm YMaxim D(2017)Probabilistic schedulability analysis for fixed priority mixed criticality real-time systemsProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130514(596-601)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130514
Show More Cited By

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