Proceedings of International Conference on Applied Innovation in IT
2017/03/16, Volume 1, Issue 5, 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

    PARTICIPATION

       - Call for Papers!!!
       - Paper Submission
       - Important Dates
       - Committee
       - Guest registration


    PROCEEDINGS

       - Issue 1 (ICAIIT 2013)
       - Issue 2 (ICAIIT 2014)
       - Issue 3 (ICAIIT 2015)
       - Issue 4 (ICAIIT 2016)
       - Issue 5 (ICAIIT 2017)

    ETHICS IN PUBLICATIONS

    ACCOMODATION

    CONTACT US

 


           ISSN 2199-8876
           Copyright © 2013-2017 Leonid Mylnikov. All rights reserved.