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

research-article

Reproducibility and representativity: mandatory properties for the compositionality of measurement-based WCET estimation approaches

Authors:

L. Cucu-GrosjeanAuthors Info & Claims

ACM SIGBED Review, Volume 14, Issue 3

Pages 24 - 31

https://doi.org/10.1145/3166227.3166230

Published: 22 November 2017 Publication History

Abstract

The increased number of systems consisting of multiple interacting components imposes the evolution of timing analyses towards methods able to estimate the timing behavior of an entire system by aggregating timings bounds of its components. In this paper we propose the first discussion on the properties required by measurement-based timing analyses to ensure such compositionality. We identify the properties of reproducibility and representativity as necessary conditions to ensure the convergence of any measurement protocol allowing a compositional measurement-based timing analysis.

References

[1]

J. Reineke, "Caches in WCET analysis: Predictability - competitiveness - sensitivity," Ph.D. dissertation, Saarland University, 2009.

[2]

M. Santos, B. Lisper, G. Lima, and V. Lima, "Sequential composition of execution time distributions by convolution," in Proc. 4th Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS 2011), November 2011, pp. 30--37.

[3]

L. Cucu-Grosjean, "Independence - a misunderstood property of and for (probabilistic) real-time systems," in "Real-Time Systems: the past, the present, and the future", the 60th birthday of Prof. Alan Burns, 2013.

[4]

R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. B. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, F. Mueller, I. Puaut, P. P. Puschner, J. Staschulat, and P. Stenström, "The worst-case execution-time problem - overview of methods and survey of tools," ACM Trans. Embedded Comput. Syst., vol. 7, no. 3, 2008.

Digital Library

[5]

P. Cousot and R. Cousot, "Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints," in Conference Record of the Fourth ACM Symposium on Principles of Programming Languages (POPL), 1977, pp. 238--252.

Digital Library

[6]

P. Cousot and R. Cousot, "Modular static program analysis," in Compiler Construction, 11th International Conference, CC 2002, 2002, pp. 159--178.

Digital Library

[7]

J. Reineke and R. Sen, "Sound and efficient WCET analysis in the presence of timing anomalies," in 9th Intl. Workshop on Worst-Case Execution Time Analysis, WCET, 2009.

[8]

I. Wenzel, R. Kirner, P. P. Puschner, and B. Rieder, "Principles of timing anomalies in superscalar processors," in Fifth International Conference on Quality Software (QSIC), 2005, pp. 295--306.

Digital Library

[9]

P. Cousot and M. Monerau, "Probabilistic abstract interpretation," in Programming Languages and Systems - 21st European Symposium on Programming, ESOP, 2012, pp. 169--193.

Digital Library

[10]

L. David and I. Puaut, "Static determination of probabilistic execution times," in 16th Euromicro Conference on Real-Time Systems (ECRTS), 2004, pp. 223--230.

Digital Library

[11]

A. Adjé, O. Bouissou, J. Goubault-Larrecq, E. Goubault, and S. Putot, "Static analysis of programs with imprecise probabilistic inputs," in Verified Software: Theories, Tools, Experiments - 5th International Conference, VSTTE 2013, 2013, pp. 22--47.

Digital Library

[12]

F. Guet, L. Santinelli, and J. Morio, "On the Reliability of the Probabilistic Worst-Case Execution Time Estimates," in 8th European Congress on Embedded Real Time Software and Systems (ERTS), Jan. 2016.

[13]

S. Edgar and A. Burns, "Statistical analysis of WCET for scheduling," in the 22nd IEEE Real-Time Systems Symposium, 2001.

Digital Library

[14]

G. Lima, D. Dias, and E. Barros, "Extreme value theory for estimating task execution time bounds: A careful look," in 28th Euromicro Conference on Real-Time Systems, 2016, pp. 200--211.

[15]

L. Yue, I. Bate, T. Nolte, and L. Cucu-Grosjean, "A new way about using statistical analysis of worst-case execution times," ACM SIGBED Review, September 2011.

Digital Library

[16]

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

Digital Library

[17]

J. Gustafsson, A. Betts, A. Ermedahl, and B. Lisper, "The Mälardalen WCET benchmarks - past, present and future," in the International Workshop on Worst-case Execution-time Analysis, 2010.

[18]

N. A. Lynch and M. R. Tuttle, "An introduction to input/output automata," CWI Quarterly, vol. 2, pp. 219--246, 1989.

[19]

L. d. Alfaro, T. A. Henzinger, and M. Stoelinga, "Timed interfaces," in Proceedings of the Second International Conference on Embedded Software, ser. EMSOFT '02, 2002, pp. 108--122.

Digital Library

[20]

M. Geilen, S. Tripakis, and M. Wiggers, "The earlier the better: A theory of timed actor interfaces," in Proceedings of the 14th International Conference on Hybrid Systems: Computation and Control, ser. HSCC '11, 2011, pp. 23--32.

Digital Library

[21]

S. Hahn, J. Reineke, and R. Wilhelm, "Towards compositionality in execution time analysis: definition and challenges," SIGBED Review, vol. 12, no. 1, pp. 28--36, 2015.

Digital Library

[22]

S. Altmeyer, R. I. Davis, L. S. Indrusiak, C. Maiza, V. Nélis, and J. Reineke, "A generic and compositional framework for multicore response time analysis," in Proceedings of the 23rd International Conference on Real Time Networks and Systems, RTNS, 2015, pp. 129--138.

Digital Library

[23]

T. Lundqvist and P. Stenström, "Timing anomalies in dynamically scheduled microprocessors," in Proceedings of the 20th IEEE Real-Time Systems Symposium, 1999, 1999, pp. 12--21.

Digital Library

[24]

T. Tia, 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 the 2nd IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS95), 1995, pp. 164--174.

Digital Library

[25]

M. Gardner and J. Lui, "Analyzing stochastic fixed-priority real-time systems," in the 5th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS99), 1999, pp. 44--58.

Digital Library

[26]

L. Abeni and G. Buttazzo, "Integrating multimedia applications in hard real-time systems," in the 19th IEEE Real-Time Systems Symposium (RTSS98), 1998, pp. 4--13.

Digital Library

[27]

J. Díaz, D. Garcia, K. Kim, C. Lee, L. Bello, L. J.M., and O. Mirabella, "Stochastic analysis of periodic real-time systems," in the 23rd IEEE Real-Time Systems Symposium (RTSS02), 2002.

Digital Library

[28]

B. Gnedenko, "Sur la distribution limite du terme maximum d'une seris aleatoire," Annals of Mathematics, vol. 44, pp. 423--453, 1943.

[29]

F. Wartel, L. Kosmidis, C. Lo, B. Triquet, E. Quinones, J. Abella, A. Gogonel, A. Baldovin, E. Mezzetti, L. Cucu, T. Vardanega, and F. Cazorla, "Measurement-based probabilistic timing analysis: Lessons from an integrated-modular avionics case study," in the 8th IEEE International Symposium on Industrial Embedded Systems, 2013.

[30]

F. Wartel, L. Kosmidis, A. Gogonel, A. Baldovin, Z. R. Stephenson, B. Triquet, E. Qui$nTones, C. Lo, E. Mezzetti, I. Broster, J. Abella, L. Cucu-Grosjean, T. Vardanega, and F. J. Cazorla, "Timing analysis of an avionics case study on complex hardware/software platforms," in the 2015 Design, Automation & Test in Europe Conference & Exhibition, DATE, 2015, pp. 397--402.

Digital Library

[31]

K. Berezovskyi, L. Santinelli, K. Bletsas, and E. Tovar, "WCET measurement-based and extreme value theory characterisation of CUDA kernels," in 22nd International Conference on Real-Time Networks and Systems, 2014, p. 279.

Digital Library

[32]

L. Santinelli, J. Morio, G. Dufour, and D. Jacquemart, "On the sustainability of the extreme value theory for WCET estimation," in 14th International Workshop on Worst-Case Execution Time Analysis, 2014, pp. 21--30.

Cited By

Khazen MZagalo KClarke HMezouak MAbdeddaim YBar-Hen AAmor SBennour RGogonel AKougblenou KSorel YCucu-Grosjean L(2022)Work in Progress: KDBench - towards open source benchmarks for measurement-based multicore WCET estimators2022 IEEE 28th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS54340.2022.00035(309-312)Online publication date: May-2022
https://doi.org/10.1109/RTAS54340.2022.00035
Abella JMezzetti ECazorla FHung CPapadopoulos G(2019)On assessing the viability of probabilistic scheduling with dependent tasksProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3297339(625-634)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3297339

Recommendations

Evaluating the productivity and reproducibility of a measurement procedure
CoMoGIS'06: Proceedings of the 2006 international conference on Advances in Conceptual Modeling: theory and practice

This paper reports an empirical study that used computer science major students as experimental subjects to evaluate the productivity and the reproducibility of RmFFP. This is a functional size measurement procedure designed according to the COSMIC-FFP ...
Statistical skew modeling for general clock distribution networks in presence of process variations

Clock skew modeling is important in the performance evaluation and prediction of clock distribution networks. This paper addresses the problem of statistical skew modeling for general clock distribution networks in the presence of process variations. ...
Reproducibility and Replicability of Web Measurement Studies
WWW '22: Proceedings of the ACM Web Conference 2022

Web measurement studies can shed light on not yet fully understood phenomena and thus are essential for analyzing how the modern Web works. This often requires building new and adjusting existing crawling setups, which has led to a wide variety of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGBED Review

ACM SIGBED Review Volume 14, Issue 3

October 2017

55 pages

EISSN:1551-3688

DOI:10.1145/3166227

Editors:
Saad Mubeen
Mälardalen University, Sweden
,
Geoffrey Nelissen
CISTER/INESC-TEC, ISEP, Portugal

Issue’s Table of Contents

Copyright © 2017 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 November 2017

Published in SIGBED Volume 14, Issue 3

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
76
Total Downloads

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

Reflects downloads up to 27 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khazen MZagalo KClarke HMezouak MAbdeddaim YBar-Hen AAmor SBennour RGogonel AKougblenou KSorel YCucu-Grosjean L(2022)Work in Progress: KDBench - towards open source benchmarks for measurement-based multicore WCET estimators2022 IEEE 28th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS54340.2022.00035(309-312)Online publication date: May-2022
https://doi.org/10.1109/RTAS54340.2022.00035
Abella JMezzetti ECazorla FHung CPapadopoulos G(2019)On assessing the viability of probabilistic scheduling with dependent tasksProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3297339(625-634)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3297339

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 Issue’s Table of Contents