Abstract
This work aims at facilitating the schedulability analysis of non-critical systems, in particular those that have soft real-time constraints, where worst-case execution times (WCETs) can be replaced by less stringent probabilistic bounds, which we call maximal execution times (METs). To this end, it is possible to obtain adequate probabilistic execution time models by separating the non-random dependency on input data from a modeling error that is purely random. The proposed approach first utilizes execution time multivariate measurements for building a multiple regression model and then uses the theory related to confidence bounds of coefficients, in order to estimate the upper bound of execution time. Although certainly our method cannot directly achieve extreme probability levels that are usually expected for WCETs, it is an attractive alternative for MET analysis, since it can arguably guarantee safe probabilistic bounds. The method’s effectiveness is demonstrated on a JPEG decoder running on an industrial SPARC V8 processor.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
Classifying the different methods is beyond of the scope of this paper. A detailed survey of the different approaches and their classifications can found in [13].
For a higher precision, it may be possible to instrument the binary code for the target platform in a separate binary executable used only for the construction of \(P_{pp}\), and still use the non-instrumented version for the end-to-end execution time measurements on the target platform.
In general, this execution time is never 0 due to different reasons e.g., initialization; \(\beta _0\) captures this cost.
Sources are made available at www-verimag.imag.fr/~nouri/met-estimation.
A common practice is to consider \(70\%\) for the training set and \(30\%\) for the test set.
Downloaded from Internet, presumably authored by P. Guerrier and G. Janssen 1998.
We could not obtain more measurements because the FPGA card was available for a limited period of time, and loading data into it required some manual work.
Matching PCA predictors back to the original ones (or to the ones obtained by using stepwise regression) is feasible, but requires some additional work. For simplicity, we choose not to show it here.
The small probability for the same \(\alpha \) in the case of stepwise regression is due to the fact that (6) takes into account the number of predictors p, which is greater in this case.
References
Bernat G, Colin A, Petters SM (2002) WCET analysis of probabilistic hard real-time system. In: Proceedings of RTSS’02, IEEE, pp 279–288
Bernat G, Burns A, Newby M (2005) Probabilistic timing analysis: an approach using copulas. J Embed Comput 1(2):179–194
Betts A, Bernat G (2006) Tree-based WCET analysis on instrumentation point graphs. In: Proceedings of ISORC’06, IEEE, pp 558–565
Cucu-Grosjean L, Santinelli L, Houston M, Lo C, Vardanega T, Kosmidis L, Abella J, Mezzetti E, Quiñones E, Cazorla FJ (2012) Measurement-based probabilistic timing analysis for multi-path programs. In: Proceedings of ECRTS’12, IEEE, pp 91–101
Draper NR, Smith H (1981) Applied regression analysis, 2nd edn. Wiley, Hoboken
Eskenazi EM, Fioukov AV, Hammer DK (2004) Performance prediction for component compositions. In: CBSE’04, Springer, pp 280–293
Hastie T, Tibshirani R, Friedman J (2009) The elements of statistical learning: data mining, inference and prediction, 2nd edn. Springer, Berlin
Huang L, Jia J, Yu B, Chun BG, Maniatis P, Naik M (2010) Predicting execution time of computer programs using sparse polynomial regression. In: Proceedings of NIPS’10, Curran Associates Inc., USA, pp 883–891
Jolliffe I (2002) Principal component analysis. Springer series in statistics. Springer, Berlin
Lisper B, Santos M (2009) Model identification for WCET analysis. In: Proceedings of RTAS’09, IEEE, pp 55–64
Poplavko P, Nouri A, Angelis L, Zerzelidis A, Bensalem S, Katsaros P (2017) Regression-based statistical bounds on software execution time. In: Verification and evaluation of computer and communication systems—11th International conference, VECoS 2017, Montreal, QC, Canada, August 24–25, 2017, Proceedings, pp 48–63. https://doi.org/10.1007/978-3-319-66176-6_4
Rapita Systems Ltd (2018) Rapitime. https://www.rapitasystems.com/products/rapitime. Accessed 4 June 2018
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 (2008) The worst-case execution-time problem - overview of methods and survey of tools. ACM Trans Embed Comput Syst 7(3):36:1–36:53
Author information
Authors and Affiliations
Corresponding author
Additional information
The research leading to these results has received funding from the European Space Agency project MoSaTT-CMP, Contract No. 4000111814/14/NL/MH.
P. Poplavko: The presented research was done while working at UGA/VERIMAG.
Rights and permissions
About this article
Cite this article
Nouri, A., Poplavko, P., Angelis, L. et al. Maximal software execution time: a regression-based approach. Innovations Syst Softw Eng 14, 101–116 (2018). https://doi.org/10.1007/s11334-018-0314-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11334-018-0314-9