Document Open Access Logo

Using Markov’s Inequality with Power-Of-k Function for Probabilistic WCET Estimation

Authors Sergi Vilardell , Isabel Serra , Enrico Mezzetti , Jaume Abella , Francisco J. Cazorla , Joan del Castillo

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2022.20.pdf
  • Filesize: 2.22 MB
  • 24 pages

Document Identifiers

Author Details

Sergi Vilardell
  • Polytechnic University of Catalonia, Barcelona, Spain
  • Barcelona Supercomputing Center (BSC), Spain
Isabel Serra
  • Barcelona Supercomputing Center (BSC), Spain
  • Centre de Recerca Matemàtica, Barcelona, Spain
Enrico Mezzetti
  • Barcelona Supercomputing Center (BSC), Spain
  • Maspatechnologies S.L, Barcelona, Spain
Jaume Abella
  • Barcelona Supercomputing Center (BSC), Spain
Francisco J. Cazorla
  • Barcelona Supercomputing Center (BSC), Spain
  • Maspatechnologies S.L, Barcelona, Spain
Joan del Castillo
  • Autonomous University of Barcelona, Spain

Funding

This work has been partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) under grant PID2019-110854RB-I00 / AEI / 10.13039/501100011033 and the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 772773).

Cite AsGet BibTex

Sergi Vilardell, Isabel Serra, Enrico Mezzetti, Jaume Abella, Francisco J. Cazorla, and Joan del Castillo. Using Markov’s Inequality with Power-Of-k Function for Probabilistic WCET Estimation. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 20:1-20:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ECRTS.2022.20

Abstract

Deriving WCET estimates for software programs with probabilistic means (a.k.a. pWCET estimation) has received significant attention during last years as a way to deal with the increased complexity of the processors used in real-time systems. Many works build on Extreme Value Theory (EVT) that is fed with a sample of the collected data (execution times). In its application, EVT carries two sources of uncertainty: the first one that is intrinsic to the EVT model and relates to determining the subset of the sample that belongs to the (upper) tail, and hence, is actually used by EVT for prediction; and the second one that is induced by the sampling process and hence is inherent to all sample-based methods. In this work, we show that Markov’s inequality can be used to obtain provable trustworthy probabilistic bounds to the tail of a distribution without incurring any model-intrinsic uncertainty. Yet, it produces pessimistic estimates that we shave substantially by proposing the use of a power-of-k function instead of the default identity function used by Markov’s inequality. Lastly, we propose a method to deal with sampling uncertainty for Markov’s inequality that consistently improves EVT estimates on synthetic and real data obtained from a railway application.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time system architecture
Keywords
  • Markov’s inequality
  • probabilistic time estimates
  • probabilistic WCET
  • Extreme Value Theory

Metrics

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

References

  1. Jaume Abella, Maria Padilla, Joan Del Castillo, and Francisco J. Cazorla. Measurement-based worst-case execution time estimation using the coefficient of variation. ACM Trans. Des. Autom. Electron. Syst., 22(4), June 2017. URL: https://doi.org/10.1145/3065924.
  2. Jaume Abella, Eduardo Quiñones, Franck Wartel, Tullio Vardanega, and Francisco J. Cazorla. Heart of gold: Making the improbable happen to increase confidence in MBPTA. In 26th Euromicro Conference on Real-Time Systems, ECRTS 2014, Madrid, Spain, July 8-11, 2014, pages 255-265. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/ECRTS.2014.33.
  3. Charalampos Antoniadis, Dimitrios Garyfallou, Nestor Evmorfopoulos, and Georgios Stamoulis. Evt-based worst case delay estimation under process variation. In 2018 Design, Automation Test in Europe Conference Exhibition (DATE), pages 1333-1338, 2018. URL: https://doi.org/10.23919/DATE.2018.8342220.
  4. Luis Fernando Arcaro, Karila Palma Silva, Rômulo Silva de Oliveira, and Luís Almeida. Reliability test based on a binomial experiment for probabilistic worst-case execution times. In 41st IEEE Real-Time Systems Symposium, RTSS 2020, Houston, TX, USA, December 1-4, 2020, pages 51-62. IEEE, 2020. Google Scholar
  5. August Aimé Balkema and Laurens de Haan. Residual Life Time at Great Age. The Annals of Probability, 2(5):792-804, 1974. URL: https://doi.org/10.1214/aop/1176996548.
  6. Francesco Bartolucci and Luca Scrucca. Point estimation methods with applications to item response theory models. In Penelope Peterson, Eva Baker, and Barry McGaw, editors, International Encyclopedia of Education (Third Edition), pages 366-373. Elsevier, Oxford, third edition edition, 2010. URL: https://doi.org/10.1016/B978-0-08-044894-7.01376-2.
  7. Kostiantyn Berezovskyi, Luca Santinelli, Konstantinos Bletsas, and Eduardo Tovar. WCET Measurement-Based and Extreme Value Theory Characterisation of CUDA Kernels. In Proceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS '14, pages 279-288, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2659787.2659827.
  8. Jose Blanchet, Fei He, and Karthyek Murthy. On distributionally robust extreme value analysis. Extremes, 23:317-347, 2020. URL: https://doi.org/10.1007/s10687-019-00371-1.
  9. Frederico Caeiro and Maria Gomes. Semi-parametric tail inference through probability-weighted moments. Journal of Statistical Planning and Inference, 141(2):937-950, 2011. URL: https://doi.org/10.1016/j.jspi.2010.08.015.
  10. Frederico Caeiro and Maria Gomes. Threshold selection in extreme value analysis. Extremes, September 2014. URL: https://doi.org/10.1007/s10687-021-00405-7.
  11. Enrique Castillo, Ali Hadi, Narayanaswamy Balakrishnan, and José Sarabia. Extreme Value and Related Models With Applications in Engineering and Science. Wiley series in probability and statistics. Whiley, January 2005. Google Scholar
  12. Joan Del Castillo, Jalila Daoudi, and Richard Lockhart. Methods to distinguish between polynomial and exponential tails. Scandinavian Journal of Statistics, 41(2):382-393, 2014. URL: https://doi.org/10.1111/sjos.12037.
  13. Francisco J. Cazorla, Leonidas Kosmidis, Enrico Mezzetti, Carles Hernandez, Jaume Abella, and Tullio Vardanega. Probabilistic worst-case timing analysis: Taxonomy and comprehensive survey. ACM Comput. Surv., 52(1), February 2019. URL: https://doi.org/10.1145/3301283.
  14. Kuan-Hsun Chen and Jian-Jia Chen. Probabilistic schedulability tests for uniprocessor fixed-priority scheduling under soft errors. In 2017 12th IEEE International Symposium on Industrial Embedded Systems (SIES), pages 1-8, 2017. URL: https://doi.org/10.1109/SIES.2017.7993392.
  15. Kuan-Hsun Chen, Niklas Ueter, Georg von der Brüggen, and Jian-Jia Chen. Efficient computation of deadline-miss probability and potential pitfalls. In 2019 Design, Automation Test in Europe Conference Exhibition (DATE), pages 896-901, 2019. URL: https://doi.org/10.23919/DATE.2019.8714908.
  16. Stuart Coles. An Introduction to Statistical Modeling of Extreme Values. Springer, 2001. URL: https://doi.org/10.1007/978-1-4471-3675-0.
  17. Liliana Cucu-Grosjean, Luca Santinelli, Michael Houston, Codé Lo, Tullio Vardanega, Leonidas Kosmidis, Jaume Abella, Enrico Mezzetti, Eduardo Quiñones, and Francisco J. Cazorla. Measurement-based probabilistic timing analysis for multi-path programs. In 2012 24th Euromicro Conference on Real-Time Systems, pages 91-101, July 2012. URL: https://doi.org/10.1109/ECRTS.2012.31.
  18. Robert Davis and Liliana Cucu-Grosjean. A survey of probabilistic schedulability analysis techniques for real-time systems. Leibniz Transactions on Embedded Systems, 6(1):04-1-04:53, 2019. URL: https://doi.org/10.4230/LITES-v006-i001-a004.
  19. Anthony C. Davison and Richard L. Smith. Models for exceedances over high thresholds. Journal of the Royal Statistical Society. Series B (Methodological), 52(3):393-442, 1990. URL: https://doi.org/10.1111/j.2517-6161.1990.tb01796.x.
  20. Deloitte. Semiconductors - the Next Wave Opportunities and winning strategies for semiconductor companies, 2019. URL: https://www2.deloitte.com/content/dam/Deloitte/cn/Documents/technology-media-telecommunications/deloitte-cn-tmt-semiconductors-the-next-wave-en-190422.pdf.
  21. Jose L. Diaz, Daniel F. Garcia, Kanghee Kim, Chang-Gun Lee, Lucia Lo Bello, José M. Lopez, Sang Lyul Min, and Orazio Mirabella. Stochastic analysis of periodic real-time systems. In 23rd IEEE Real-Time Systems Symposium, 2002. RTSS 2002., pages 289-300, 2002. URL: https://doi.org/10.1109/REAL.2002.1181583.
  22. Paul Embrechts, Thomas Mikosch, and Claudia Klüppelberg. Modelling Extremal Events: For Insurance and Finance. Springer-Verlag, Berlin, Heidelberg, 1997. Google Scholar
  23. Ronald A. Fisher. Moments and product moments of sampling distributions. Proceedings of the London Mathematical Society, s2-30(1):199-238, 1930. URL: https://doi.org/10.1112/plms/s2-30.1.199.
  24. Samuel Jimenez Gil, Iain Bate, George Lima, Luca Santinelli, Adriana Gogonel, and Liliana Cucu-Grosjean. Open challenges for probabilistic measurement-based worst-case execution time. IEEE Embedded Systems Letters, 2017. URL: https://doi.org/10.1109/LES.2017.2712858.
  25. Fabrice Guet, Luca Santinelli, and Jérôme Morio. On the representativity of execution time measurements: Studying dependence and multi-mode tasks. In Jan Reineke, editor, 17th International Workshop on Worst-Case Execution Time Analysis, WCET 2017, June 27, 2017, Dubrovnik, Croatia, volume 57 of OASICS, pages 3:1-3:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/OASIcs.WCET.2017.3.
  26. Paul R. Halmos. The Theory of Unbiased Estimation. The Annals of Mathematical Statistics, 17(1):34-43, 1946. URL: https://doi.org/10.1214/aoms/1177731020.
  27. Jeffery Hansen, Scott Hissam, and Gabriel A. Moreno. Statistical-Based WCET Estimation and Validation. In Niklas Holsti, editor, 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09), volume 10 of OpenAccess Series in Informatics (OASIcs), pages 1-11, Dagstuhl, Germany, 2009. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. also published in print by Austrian Computer Society (OCG) with ISBN 978-3-85403-252-6. URL: https://doi.org/10.4230/OASIcs.WCET.2009.2291.
  28. Bruce M. Hill. A Simple General Approach to Inference About the Tail of a Distribution. The Annals of Statistics, 3(5):1163-1174, 1975. URL: https://doi.org/10.1214/aos/1176343247.
  29. Rob Hyndman and Yanan Fan. Sample quantiles in statistical packages. The American Statistician, 50:361-365, November 1996. URL: https://doi.org/10.1080/00031305.1996.10473566.
  30. Norman Lloyd Johnson. Continuous univariate distributions. Vol. 2. Wiley and Sons, New York, 2nd ed. / norman l. johnson, samuel kotz, n. balakrishnan. edition, 1994. Google Scholar
  31. Leonidas Kosmidis, Jaume Abella, Eduardo Quiñones, and Francisco J. Cazorla. A cache design for probabilistically analysable real-time systems. In Enrico Macii, editor, Design, Automation and Test in Europe, DATE 13, Grenoble, France, March 18-22, 2013, pages 513-518. EDA Consortium San Jose, CA, USA / ACM DL, 2013. URL: https://doi.org/10.7873/DATE.2013.116.
  32. Bar Light. Concentration inequalities using higher moments information. arXiv, 2020. URL: https://doi.org/10.48550/ARXIV.2006.05130.
  33. George Lima and Iain Bate. Valid Application of EVT in Timing Analysis by Randomising Execution Time Measurements. In 2017 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 187-198, 2017. URL: https://doi.org/10.1109/RTAS.2017.17.
  34. George Lima, Dário Dias, and Edna Barros. Extreme Value Theory for Estimating Task Execution Time Bounds: A Careful Look. In Euromicro Conference on Real-Time Systems, ECRTS, 2016. URL: https://doi.org/10.1109/ECRTS.2016.20.
  35. Jyh-Charn S. Liu and Sharif M. Shahrier. On predictability of caches for real-time applications. In Proceedings of International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pages 52-56, 1994. URL: https://doi.org/10.1109/MASCOT.1994.284448.
  36. Andrey Markov. On certain applications of algebraic continued fractions. Ph.D. thesis, St. Petersburg, 1884. Google Scholar
  37. Thomas Mikosch. Regular variation, subexponentiality and their applications in probability theory. International Journal of Production Economics - INT J PROD ECON, January 1999. Google Scholar
  38. Suzana Milutinovic, Enrico Mezzetti, Jaume Abella, Tullio Vardanega, and Francisco J. Cazorla. On uses of Extreme Value Theory fit for industrial-quality WCET analysis. In 12th IEEE International Symposium on Industrial Embedded Systems, SIES 2017, Toulouse, France, June 14-16, 2017, pages 1-6. IEEE, 2017. URL: https://doi.org/10.1109/SIES.2017.7993402.
  39. Sims Osborne and James H. Anderson. Simultaneous multithreading and hard real time: Can it be safe? In Marcus Völp, editor, 32nd Euromicro Conference on Real-Time Systems, ECRTS 2020, July 7-10, 2020, Virtual Conference, volume 165 of LIPIcs, pages 14:1-14:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ECRTS.2020.14.
  40. R Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2021. URL: https://www.R-project.org/.
  41. Archana Ravindar and Y. N. Srikant. Estimation of probabilistic bounds on phase CPI and relevance in WCET analysis. In Proceedings of the Tenth ACM International Conference on Embedded Software, EMSOFT '12, pages 165-174, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2380356.2380388.
  42. Federico Reghenzani, Giuseppe Massari, and William Fornaciari. Probabilistic-WCET reliability: Statistical testing of EVT hypotheses. Microprocess. Microsystems, 77:103-135, 2020. URL: https://doi.org/10.1016/j.micpro.2020.103135.
  43. Federico Reghenzani, Luca Santinelli, and William Fornaciari. Dealing with uncertainty in pWCET estimations. ACM Trans. Embed. Comput. Syst., 19(5):33:1-33:23, 2020. URL: https://doi.org/10.1145/3396234.
  44. Luca Santinelli, Jérôme Morio, Guillaume Dufour, and Damien Jacquemart. On the Sustainability of the Extreme Value Theory for WCET Estimation. In Heiko Falk, editor, 14th International Workshop on Worst-Case Execution Time Analysis, volume 39 of OpenAccess Series in Informatics (OASIcs), pages 21-30, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.WCET.2014.21.
  45. Ashwin Satyanarayana. Intelligent sampling for big data using bootstrap sampling and Chebyshev inequality. In 2014 IEEE 27th Canadian Conference on Electrical and Computer Engineering (CCECE), pages 1-6, 2014. URL: https://doi.org/10.1109/CCECE.2014.6901029.
  46. Karila Palma Silva, Luis Fernando Arcaro, and Romulo Silva De Oliveira. On Using GEV or Gumbel Models When Applying EVT for Probabilistic WCET Estimation. In 2017 IEEE Real-Time Systems Symposium (RTSS), pages 220-230, 2017. URL: https://doi.org/10.1109/RTSS.2017.00028.
  47. Didier Sornette. Critical Phenomena in Natural Sciences: Chaos, Fractals, Selforganization and Disorder: Concepts and Tools. Springer, January 2006. URL: https://doi.org/10.1007/3-540-33182-4.
  48. Seth M. Steinberg and Clarence E. Davis. Distribution-free confidence intervals for quantiles in small samples. Communications in Statistics - Theory and Methods, 14(4):979-990, 1985. URL: https://doi.org/10.1080/03610928508805144.
  49. Pafnuti Tchebichef. Des valeurs moyennes. Journal de mathématiques pures et appliquées, 12(2):177-184, 1867. Google Scholar
  50. Vladimir Utkin. Calculating the reliability of machine parts on the basis of the Chebyshev inequality. Russian Engineering Research, 32, January 2012. URL: https://doi.org/10.3103/S1068798X11120264.
  51. Gladimir V.G. Baranoski, Jon G. Rokne, and Guangwu Xu. Applying the exponential Chebyshev inequality to the nondeterministic computation of form factors. Journal of Quantitative Spectroscopy and Radiative Transfer, 69(4):447-467, 2001. URL: https://doi.org/10.1016/S0022-4073(00)00095-9.
  52. Sergi Vilardell, Isabel Serra, Jaume Abella, Joan Del Castillo, and Francisco J. Cazorla. Software timing analysis for complex hardware with survivability and risk analysis. In 2019 IEEE 37th International Conference on Computer Design (ICCD), pages 227-236, 2019. URL: https://doi.org/10.1109/ICCD46524.2019.00036.
  53. Georg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen, and Katharina Morik. Efficiently approximating the probability of deadline misses in real-time systems. In ECRTS, 2018. URL: https://doi.org/10.4230/LIPIcs.ECRTS.2018.6.
  54. Franck Wartel, Leonidas Kosmidis, Adriana Gogonel, Andrea Baldovin, Zoë R. Stephenson, Benoit Triquet, Eduardo Quiñones, Code Lo, Enrico Mezzetti, Ian Broster, Jaume Abella, Liliana Cucu-Grosjean, Tullio Vardanega, and Francisco J. Cazorla. Timing analysis of an avionics case study on complex hardware/software platforms. In Wolfgang Nebel and David Atienza, editors, Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition, DATE 2015, Grenoble, France, March 9-13, 2015, pages 397-402. ACM, 2015. URL: https://doi.org/10.7873/DATE.2015.0189.
  55. Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David B. Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter P. Puschner, Jan Staschulat, and Per Stenström. The worst-case execution-time problem - overview of methods and survey of tools. ACM Trans. Embed. Comput. Syst., 7(3):36:1-36:53, 2008. URL: https://doi.org/10.1145/1347375.1347389.
  56. Julien Worms and Sid Touati. Parametric and Non-Parametric Statistics for Program Performance Analysis and Comparison. [Research Report] RR-8875, INRIA Sophia Antipolis - I3S; Université NiceSophia Antipolis; Université Versailles Saint Quentin en Yvelines; Laboratoire de mathématiques deVersailles, 2017. URL: https://hal.inria.fr/hal-01286112.
  57. Julien Worms and Sid Touati. Modelling program’s performance with gaussian mixtures for parametric statistics. IEEE Transactions on Multi-Scale Computing Systems, 4(3):383-395, 2018. URL: https://doi.org/10.1109/TMSCS.2017.2754251.
  58. Pavel G. Zaykov and Jan Kubalčik. Worst-case measurement-based statistical tool. In 2019 IEEE Aerospace Conference, pages 1-10, 2019. URL: https://doi.org/10.1109/AERO.2019.8741824.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact