Proceedings of International Conference on Applied Innovation in IT
2017/03/16, Volume 5, Issue 1, pp.71-80

Applicability of Extreme Value Theory to the Execution Time Prediction of Programs on SoCs


Irina Fedotova, Bernd Krause, Eduard Siemens


Abstract: This paper describes in detail the estimation algorithm of upper bound prediction of the time acquisition task. We use the specific hardware from ARM Cortex-A series and empirical approach of time values retrieval from the timer counter. The robust Measurement-Based Probabilistic Timing Analysis (MBPTA) method based on the Extreme Value Theory (EVT) has been used for experimental verification of the algorithm. The MBPTA method allows deriving a reliable and safe worst-case execution time (WCET) estimation based on the limited number of measurements on the target platform. However, it requires an appropriate complete set of statistical tests for verifying EVT applicability. In ongoing work, we intend to outline challenges behind EVT assumptions and parameter tuning for timing analysis, and provide more coherent approach for safe probabilistic WCET estimations in order to increase the confidence that timing constraints will be met.

Keywords: Extreme Value Theory, Worst-Case Execution Time, Probabilistic Timing Analysis, Timing Verification

DOI: 10.13142/KT10005.32

Download: PDF

References:

  1. Wilhelm, R., Engblom, J., Ermedahl, A., Holsti, N., Thesing, S., Whalley, D., Bernat, G., Ferdinand, C., Heckmann R., Mitra, T., Mueller, F., Puaut, I., Puschner, P., Staschulat, J., Stenström, P., 2007, ‘The Worst-Case Execution Time Problem — Overview of Methods and Survey of Tools’, ACM Trans. Embed. Comput. Syst., pp. 36–53.
  2. Abella, J., Hardy, D., Puaut, I., Quinones, E., Cazorla, FJ., 2014, ‘On the Comparison of Deterministic and Probabilistic WCET Estimation Techniques’, Proc. of the 26th Euromicro Conference on Real-Time Systems (ECRTS’14), Madrid, pp. 266–275.
  3. Fedotova, I., Krause, B., Siemens E., 2017, ‘Upper Bounds Prediction of the Execution Time of Programs Running on ARM Cortex-A Systems’, Submitted at IFIP AICT (Advances in Information and Communication Technology) in press.
  4. Altmeyer, S., Cucu-Grosjean, L., Davis, RI., 2015, ‘Static probabilistic timing analysis for real-time systems using random replacement caches’, Real-Time Syst., vol. 51, no. 1, pp. 77–123.
  5. Radojković, P., Carpenter, PM., Moretó, M., Čakarević, V., Verdú, J., Pajuelo, A., Cazorla, FJ., Nemirovsky, M., Valero, M., 2016, ‘Thread Assignment in Multicore/Multithreaded Processors: A Statistical Approach’, IEEE Trans. Comput., vol. 65, no. 1, pp. 256–269.
  6. Guet, F., Morio, J., Santinelli, L., 2016, ‘On the Reliability of the Probabilistic Worst-Case Execution Time Estimates’, the 8th European Congress on Embedded Real Time Software and Systems (ERTS 2016), Toulouse, pp. 758–767.
  7. Cazorla, F., Vardanega, T., Quinones, E., Abella, J., 2013, ‘Upper-bounding Program Execution Time with Extreme Value Theory’, Proc. WCET workshop, Paris, pp. 64-76.
  8. Berezovskyi, K., Santinelli, L., Bletsas, K., Tovar, E., 2014, ‘WCET Measurement-based and Extreme Value Theory Characterisation of CUDA Kernels’, Proc. of the 22nd International Conference on Real-Time Networks and Systems, New York, , pp. 279-288.
  9. Berezovskyi, K., Guet, F., Santinelli, L., Bletsas, K., Tovar, E., 2016, ‘Measurement-Based Probabilistic Timing Analysis for Graphics Processor Units’, Proc. Of 29th International Conference Architecture of Computing Systems – ARCS 2016, Nuremberg, pp. 223-236.
  10. Coles, S., 2001 ed, An Introduction to Statistical Modeling of Extreme Values. Springer. Figure 6: Estimate of upper bounds for the Gumbel and Frechet distribution.
  11. Cucu-Grosjean, L., Santinelli, L., Houston, M., Lo, C., Vardanega, T., Kosmidis, L., Abella, J., Mezzetti, E., Quinones, E., Cazorla, JF., 2012, ‘Measurement-Based Probabilistic Timing Analysis for Multi-path Programs’, Proc. of the 24nd Euromicro Conference on Real-Time Systems (ECRTS), pp. 91-101.
  12. Hansen, J., Hissam, SA., Moreno, GA., 2009, ‘Statistical-Based WCET Estimation and Validation’, Proc. of the 9th Intl. Workshop on Worst-Case Execution Time Analysis (WCET), pp. 123-133.
  13. Embrechts, P., Klueuppelberg, C., Mikosch, T., 1996, Modelling Extremal Events for Insurance and Finance, Springer, Berlin.
  14. Balkema A., Haan L., 1974, ‘Residual Life Time at Great Age’, Annals of Probability, vol. 2, no. 5, pp-749-791.
  15. Fedotova I., Siemens E., Hu H., 2013, ‘A High-precision Time Handling Library’, Journal of Communication and Computer, vol. 10, pp. 1076–1086.
  16. Scarrott, C., MacDonald A., 2012, ‘A Review of Extreme Value Threshold Estimation and Uncertainty Quantification’, REVSTAT - Statistical Journal, vol. 10, no. 1, pp. 33–60.
  17. Burnham, KP., Anderson, DR., 2004, ‘Multimodel Inference: Understanding AIC and BIC in Model Selection’, Sociological Methods & Research, vol. 33, no. 2, pp. 261–304.
  18. Wald, A., Wolfowitz, J., 1940, ‘On a Test Whether Two Samples are from the Same Population’, Annals of Mathematical Statistics, vol. 11, no. 2, pp. 147–162.
  19. Hsing, T., 1991, ‘On Tail Index Estimation Using Dependent Data’, Annals of Statistics, vol. 19, no. 3, pp. 1547–1569.
  20. ARP4761, 2001, ‘Guidelines and methods for conducting the safety assessment process on civil airborne systems and equipment’.


    HOME

       - Call for Papers
       - Paper Submission
       - For authors
       - Important Dates
       - Conference Committee
       - Editorial Board
       - Reviewers
       - Last Proceedings


    PROCEEDINGS

       - Volume 12, Issue 1 (ICAIIT 2024)        - Volume 11, Issue 2 (ICAIIT 2023)
       - Volume 11, Issue 1 (ICAIIT 2023)
       - Volume 10, Issue 1 (ICAIIT 2022)
       - Volume 9, Issue 1 (ICAIIT 2021)
       - Volume 8, Issue 1 (ICAIIT 2020)
       - Volume 7, Issue 1 (ICAIIT 2019)
       - Volume 7, Issue 2 (ICAIIT 2019)
       - Volume 6, Issue 1 (ICAIIT 2018)
       - Volume 5, Issue 1 (ICAIIT 2017)
       - Volume 4, Issue 1 (ICAIIT 2016)
       - Volume 3, Issue 1 (ICAIIT 2015)
       - Volume 2, Issue 1 (ICAIIT 2014)
       - Volume 1, Issue 1 (ICAIIT 2013)


    PAST CONFERENCES

       ICAIIT 2024
         - Photos
         - Reports

       ICAIIT 2023
         - Photos
         - Reports

       ICAIIT 2021
         - Photos
         - Reports

       ICAIIT 2020
         - Photos
         - Reports

       ICAIIT 2019
         - Photos
         - Reports

       ICAIIT 2018
         - Photos
         - Reports

    ETHICS IN PUBLICATIONS

    ACCOMODATION

    CONTACT US

 

DOI: http://dx.doi.org/10.25673/115729


        

         Proceedings of the International Conference on Applied Innovations in IT by Anhalt University of Applied Sciences is licensed under CC BY-SA 4.0


                                                   This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License


           ISSN 2199-8876
           Publisher: Edition Hochschule Anhalt
           Location: Anhalt University of Applied Sciences
           Email: leiterin.hsb@hs-anhalt.de
           Phone: +49 (0) 3496 67 5611
           Address: Building 01 - Red Building, Top floor, Room 425, Bernburger Str. 55, D-06366 Köthen, Germany

        site traffic counter

Creative Commons License
Except where otherwise noted, all works and proceedings on this site is licensed under Creative Commons Attribution-ShareAlike 4.0 International License.