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

Irina Fedotova, Bernd Krause, Eduard Siemens

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’.