On the Sustainability of the Extreme Value Theory for WCET Estimation

Authors Luca Santinelli, Jérôme Morio, Guillaume Dufour, Damien Jacquemart



PDF
Thumbnail PDF

File

OASIcs.WCET.2014.21.pdf
  • Filesize: 0.6 MB
  • 10 pages

Document Identifiers

Author Details

Luca Santinelli
Jérôme Morio
Guillaume Dufour
Damien Jacquemart

Cite AsGet BibTex

Luca Santinelli, Jérôme Morio, Guillaume Dufour, and Damien Jacquemart. On the Sustainability of the Extreme Value Theory for WCET Estimation. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 21-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/OASIcs.WCET.2014.21

Abstract

Measurement-based approaches with extreme value worst-case estimations are beginning to be proficiently considered for timing analyses. In this paper, we intend to make more formal extreme value theory applicability to safe worst-case execution time estimations. We outline complexities and challenges behind extreme value theory assumptions and parameter tuning. Including the knowledge requirements, we are able to conclude about safety of the probabilistic worst-case execution estimations from the extreme value theory, and execution time measurements.
Keywords
  • Extreme Value Theory
  • Worst-Case Execution Time
  • Probabilistic Worst-Case Execution Time
  • Dependence
  • Stationarity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Francisco J. Cazorla, Tullio Vardanega, Eduardo Quinones, and Jaume Abella. Upper-bounding program execution time with extreme value theory. In WCET, 2013. Google Scholar
  2. L. Cucu-Grosjean, L. Santinelli, M. Houston, C. Lo, T. Vardanega, L. Kosmidis, J. Abella, E. Mezzeti, E. Quinones, and F. J. Cazorla. Measurement-Based Probabilistic Timing Analysis for Multi-path Programs. In 23nd Euromicro Conference on Real-Time Systems (ECRTS). IEEE, 2012. Google Scholar
  3. R. A. Davis and T. Mikosch. The extremogram: A correlogram for extreme events. Bernoulli, 2009. Google Scholar
  4. B. Efron and R. J. Tibshirani. An Introduction to the Bootstrap. Chapman &Hall, New York, NY, 1993. Google Scholar
  5. P. Embrechts, C. Kluppelberg, and T. Mikosch. Modelling extremal events for insurance and finance. ZOR Zeitschrift for Operations Research Mathematical Methods of Operations Research, 97(1):1-34, 1994. Google Scholar
  6. Christopher A. T. Ferro and Johan Segers. Automatic declustering of extreme values via an estimators. EURANDOM report, Eindhoven University of Technology, 2002. Google Scholar
  7. Mark K. Gardner. Probabilistic analysis and scheduling of critical soft real-time systems. PhD thesis, University of Illinois at Urbana-Champaign, Champaign, IL, USA, 1999. AAI9953022. Google Scholar
  8. E. J. Gumbel. Statistics of Extremes. Columbia University Press, 1958. Google Scholar
  9. J. Hansen, S. Hissam, and G. A. Moreno. Statistical-based wcet estimation and validation. In the 9th International Workshop on Worst-Case Execution Time (WCET) Analysis, 2009. Google Scholar
  10. T. Hsing. On tail index estimation using dependent data. The Annals of Statistics, 1991. Google Scholar
  11. M. R. Leadbetter, G. Lindgren, and H. Rootzén. Extremes and Related Properties of Random Sequences and Processes. Springer-Verlag, 1983. Google Scholar
  12. D. Mejzler. On the problem of the limit distribution for the maximal term of a variational series. Lvov. Politehn. Inst. Naucn Zap. Ser. Fiz.-Mat., 1956. Google Scholar
  13. J. Pickands. Statistical inference using extreme order statistics. Annals of Statistics, 3(1):119-131, 1975. Google Scholar
  14. R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. B. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, T. 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., 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail