A Reliable Statistical Analysis of the Best-Fit Distribution for High Execution Times

Extreme Value Theory has been used to model the WCET probabilistically, relying on the assumption that probabilistic WCET (pWCET) estimates can be upper-bounded with exponential distributions, but this is only assessed on execution time samples with pass/fail hypothesis tests. However, the degree of fulfilment of this hypothesis for the execution time sample has a direct impact on the tightness of the pWCET estimate. This paper tackles this limitation of pass/fail tests by applying 3 alternative methods to model the distribution of high execution times through the analysis of the number of finite moments of execution time samples. These methods provide information on the degree of fulfilment of the exponentiality hypothesis, rather than a simple pass/fail response. Hence, whenever the number of finite moments is shown to be low, despite pass/fail tests are passed, these methods indicate that pWCET estimates may be untight. We show that those methods complement each other and the information obtained - number of finite moments proven to exist - can be used to increase the execution time sample size opportunistically to obtain tighter pWCET estimates. This work was partially funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No.772773), the Spanish Ministry of Economy and Competitiveness (MINECO) under grant TIN2015-65316-P and the HiPEAC Network of Excellence. Jaume Abella has been partially funded by MINECO under Ramon y Cajal postdoctoral fellowship number RYC-2013-14717.