{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,29]],"date-time":"2026-08-29T15:53:42Z","timestamp":1788018822572,"version":"build-2784847793"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,11,6]],"date-time":"2022-11-06T00:00:00Z","timestamp":1667692800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,6]],"date-time":"2022-11-06T00:00:00Z","timestamp":1667692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100013276","name":"Interreg","doi-asserted-by":"publisher","award":["#R075"],"award-info":[{"award-number":["#R075"]}],"id":[{"id":"10.13039\/100013276","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cluster Comput"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This work aims to estimate the execution time of data processing tasks (specific executions of a program or an algorithm) before their execution. The paper focuses on the estimation of the average-case execution time (ACET). This metric can be used to predict the approximate cost of computations, e.g. when resource consumption in a High-Performance Computing system has to be known in advance. The presented approach proposes to create machine learning models using historical data. The models use program metadata (properties of input data) and parameters of the run-time environment as their explanatory variables. Moreover, the set of these variables can be easily expanded with additional parameters of the specific programs. The program code itself is treated as a black box. The response variable of the model is the execution time. The models have been validated within a Large-Scale Computing system that allows for a unified treatment of programs as computation modules. We present the process of training and validation for several different computation modules and discuss the suitability of the proposed models for ACET estimation in various computing environments.<\/jats:p>","DOI":"10.1007\/s10586-022-03774-1","type":"journal-article","created":{"date-parts":[[2022,11,6]],"date-time":"2022-11-06T12:02:45Z","timestamp":1667736165000},"page":"3943-3956","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Estimation of execution time for computing tasks"],"prefix":"10.1007","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5498-1009","authenticated-orcid":false,"given":"Jan","family":"Bielecki","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"\u015amia\u0142ek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,11,6]]},"reference":[{"issue":"4","key":"3774_CR1","doi-asserted-by":"publisher","first-page":"734","DOI":"10.31577\/cai_2021_4_734","volume":"40","author":"K Marek","year":"2021","unstructured":"Marek, K., \u015amia\u0142ek, M., Rybi\u0144ski, K., Roszczyk, R., Wdowiak, M.: BalticLSC: low-code software development platform for large scale computations. Comput. Inform. 40(4), 734\u2013753 (2021)","journal-title":"Comput. Inform."},{"key":"3774_CR2","doi-asserted-by":"crossref","unstructured":"Roszczyk, R., Wdowiak, M., \u015amia\u0142ek, M., Rybi\u0144ski, K., Marek, K.: BalticLSC: a low-code HPC platform for small and medium research teams. In: 2021 IEEE Symposium on Visual Languages and Human-Centric Computing (VL\/HCC), pp. 1\u2013 4. IEEE (2021)","DOI":"10.1109\/VL\/HCC51201.2021.9576305"},{"issue":"3","key":"3774_CR3","doi-asserted-by":"publisher","first-page":"217","DOI":"10.54870\/1551-3440.1375","volume":"13","author":"AA Nasar","year":"2016","unstructured":"Nasar, A.A.: The history of algorithmic complexity. Math. Enthus. 13(3), 217\u2013242 (2016)","journal-title":"Math. Enthus."},{"issue":"1","key":"3774_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1134\/S0361768816010059","volume":"42","author":"V Kozyrev","year":"2016","unstructured":"Kozyrev, V.: Estimation of the execution time in real-time systems. Program. Comput. Softw. 42(1), 41\u201348 (2016)","journal-title":"Program. Comput. Softw."},{"key":"3774_CR5","doi-asserted-by":"crossref","unstructured":"Phinjaroenphan, P., Bevinakoppa, S., Zeephongsekul, P.: A method for estimating the execution time of a parallel task on a grid node. In: European Grid Conference, pp. 226\u2013 236 ( 2005). Springer","DOI":"10.1007\/11508380_24"},{"key":"3774_CR6","doi-asserted-by":"publisher","unstructured":"Taunk, K., De, S., Verma, S., Swetapadma, A.: A brief review of nearest neighbor algorithm for learning and classification. In: 2019 International Conference on Intelligent Computing and Control Systems (ICCS), pp. 1255\u2013 1260 ( 2019). https:\/\/doi.org\/10.1109\/ICCS45141.2019.9065747","DOI":"10.1109\/ICCS45141.2019.9065747"},{"key":"3774_CR7","doi-asserted-by":"crossref","unstructured":"Iverson, M.A., Ozguner, F., Potter, L.C.: Statistical prediction of task execution times through analytic benchmarking for scheduling in a heterogeneous environment. In: Proceedings. Eighth Heterogeneous Computing Workshop (HCW\u201999), pp. 99\u2013111. IEEE (1999)","DOI":"10.1109\/HCW.1999.765115"},{"issue":"3","key":"3774_CR8","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/BF00994018","volume":"20","author":"C Cortes","year":"1995","unstructured":"Cortes, C., Vapnik, V.: Support-vector networks. Mach. Learn. 20(3), 273\u2013297 (1995)","journal-title":"Mach. Learn."},{"key":"3774_CR9","doi-asserted-by":"publisher","DOI":"10.1201\/9781420011746.ch35","author":"A Ermedahl","year":"2007","unstructured":"Ermedahl, A., Engblom, J.: Execution time analysis for embedded real-time systems. Citeseer (2007). https:\/\/doi.org\/10.1201\/9781420011746.ch35","journal-title":"Citeseer"},{"key":"3774_CR10","unstructured":"Haugli, F.B.: Using online worst-case execution time analysis and alternative tasks in real time systems. Master\u2019s Thesis, Institutt for teknisk kybernetikk (2014)"},{"key":"3774_CR11","doi-asserted-by":"crossref","unstructured":"Shah, S.A.B., Rashid, M., Arif, M.: A prediction model for measurement-based timing analysis. In: Proceedings of the 6th International Conference on Software and Computer Applications, pp. 9\u201314 ( 2017)","DOI":"10.1145\/3056662.3056666"},{"key":"3774_CR12","unstructured":"Gem5 website. https:\/\/www.gem5.org\/, last visited 12.07.2021 (2021)"},{"issue":"01","key":"3774_CR13","doi-asserted-by":"publisher","first-page":"2050005","DOI":"10.1142\/S021812662050005X","volume":"29","author":"M Rashid","year":"2020","unstructured":"Rashid, M., Shah, S.A.B., Arif, M., Kashif, M.: Determination of worst-case data using an adaptive surrogate model for real-time system. J. Circuits Syst. Comput. 29(01), 2050005 (2020)","journal-title":"J. Circuits Syst. Comput."},{"issue":"3","key":"3774_CR14","doi-asserted-by":"publisher","first-page":"1449","DOI":"10.1007\/s10586-016-0606-5","volume":"19","author":"F Meng","year":"2016","unstructured":"Meng, F., Su, X., Qu, Z.: Nonlinear approach for estimating WCET during programming phase. Clust. Comput. 19(3), 1449\u20131459 (2016)","journal-title":"Clust. Comput."},{"key":"3774_CR15","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/B978-0-12-416632-5.00007-4","volume-title":"Handbook of Statistical Analysis and Data Mining Applications","author":"R Nisbet","year":"2018","unstructured":"Nisbet, R., Miner, G., Yale, K.: Chapter 7\u2014basic algorithms for data mining: a brief overview. In: Nisbet, R., Miner, G., Yale, K. (eds.) Handbook of Statistical Analysis and Data Mining Applications, 2nd edn., pp. 121\u2013147. Academic Press, Boston (2018). https:\/\/doi.org\/10.1016\/B978-0-12-416632-5.00007-4","edition":"2"},{"issue":"2","key":"3774_CR16","doi-asserted-by":"publisher","first-page":"0229345","DOI":"10.1371\/journal.pone.0229345","volume":"15","author":"DG Jenkins","year":"2020","unstructured":"Jenkins, D.G., Quintana-Ascencio, P.F.: A solution to minimum sample size for regressions. PLoS ONE 15(2), 0229345 (2020)","journal-title":"PLoS ONE"},{"key":"3774_CR17","unstructured":"Huang, L., Jia, J., Yu, B., Chun, B.-G., Maniatis, P., Naik, M.: Predicting execution time of computer programs using sparse polynomial regression, 23, 883\u2013891 (2010). https:\/\/proceedings.neurips.cc\/paper\/2010\/file\/995665640dc319973d3173a74a03860c-Paper.pdf"},{"key":"3774_CR18","doi-asserted-by":"crossref","unstructured":"Chen, T., Guestrin, C.: XGBoost: a scalable tree boosting system. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 785\u2013794 (2016)","DOI":"10.1145\/2939672.2939785"},{"key":"3774_CR19","doi-asserted-by":"publisher","unstructured":"Bielecki, J.: [dataset] Details of the tasks executions. Mendeley Data (2022). https:\/\/doi.org\/10.17632\/sbfmwvw77d.2","DOI":"10.17632\/sbfmwvw77d.2"},{"issue":"5","key":"3774_CR20","doi-asserted-by":"publisher","first-page":"1763","DOI":"10.1213\/ANE.0000000000002864","volume":"126","author":"P Schober","year":"2018","unstructured":"Schober, P., Boer, C., Schwarte, L.A.: Correlation coefficients: appropriate use and interpretation. Anesth. Analg. 126(5), 1763\u20131768 (2018)","journal-title":"Anesth. Analg."},{"issue":"2065","key":"3774_CR21","doi-asserted-by":"publisher","first-page":"20150202","DOI":"10.1098\/rsta.2015.0202","volume":"374","author":"IT Jolliffe","year":"2016","unstructured":"Jolliffe, I.T., Cadima, J.: Principal component analysis: a review and recent developments. Philos. Trans. R. Soc. A 374(2065), 20150202 (2016)","journal-title":"Philos. Trans. R. Soc. A"},{"key":"3774_CR22","doi-asserted-by":"publisher","unstructured":"Awad, M., Khanna, R.: Support vector regression. In: Efficient Learning Machines: Theories, Concepts, and Applications for Engineers and System Designers, pp. 67\u201380. Apress, Berkeley (2015). https:\/\/doi.org\/10.1007\/978-1-4302-5990-9_4","DOI":"10.1007\/978-1-4302-5990-9_4"},{"issue":"1","key":"3774_CR23","first-page":"5741","volume":"18","author":"E Vural","year":"2017","unstructured":"Vural, E., Guillemot, C.: A study of the classification of low-dimensional data with supervised manifold learning. J. Mach. Learn. Res. 18(1), 5741\u20135795 (2017)","journal-title":"J. Mach. Learn. Res."},{"key":"3774_CR24","doi-asserted-by":"publisher","DOI":"10.29333\/iejme\/6293","author":"R Kouki","year":"2020","unstructured":"Kouki, R., Griffiths, B.J.: Introducing Taylor series and local approximations using a historical and semiotic approach. Int. Electron. J. Math. Educ. (2020). https:\/\/doi.org\/10.29333\/iejme\/6293","journal-title":"Int. Electron. J. Math. Educ."},{"key":"3774_CR25","unstructured":"Cournapeau, D., et al.: Support Vector Regression. Scikit-learn version 0.24.2 (visited 10.04.2021). https:\/\/scikit-learn.org\/stable\/modules\/generated sklearn.svm.SVR.html"},{"key":"3774_CR26","unstructured":"Cournapeau, D., et al.: RBF SVM parameters. Scikit-learn version 0.24.2 (visited 10.04.2021). https:\/\/scikit-learn.org\/stable\/auto_examples\/svm\/plot_rbf_parameters.html"},{"key":"3774_CR27","unstructured":"Cournapeau, D., et al.: KNN Regression. Scikit-learn version 0.24.2 (visited 10.04.2021). https:\/\/scikit-learn.org\/stable\/modules\/neighbors.html#regression"},{"key":"3774_CR28","doi-asserted-by":"crossref","unstructured":"Li, Z., Ding, Q., Zhang, W.: A comparative study of different distances for similarity estimation. In: International Conference on Intelligent Computing and Information Science, pp. 483\u2013488. Springer (2011).","DOI":"10.1007\/978-3-642-18129-0_75"},{"key":"3774_CR29","doi-asserted-by":"publisher","DOI":"10.1093\/acref\/9780199235940.001.0001","volume-title":"The Concise Oxford Dictionary of Mathematics","author":"C Clapham","year":"2009","unstructured":"Clapham, C., Nicholson, J.: The Concise Oxford Dictionary of Mathematics. Oxford University Press, Oxford (2009). https:\/\/doi.org\/10.1093\/acref\/9780199235940.001.0001"},{"key":"3774_CR30","unstructured":"Cournapeau, D., et al.: Standard scaler. Scikit-learn version 0.24.2 (visited 18.04.2021).https:\/\/scikit-learn.org\/stable\/modules\/generated\/sklearn.preprocessing.StandardScaler.html"},{"key":"3774_CR31","unstructured":"Cournapeau, D., et al.: Grid search. Scikit-learn version 0.24.2 (visited 18.04.2021). https:\/\/scikit-learn.org\/stable\/modules\/generated\/sklearn.model_selection.GridSearchCV.html"}],"container-title":["Cluster Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-022-03774-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10586-022-03774-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-022-03774-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T10:30:24Z","timestamp":1728297024000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10586-022-03774-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,6]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["3774"],"URL":"https:\/\/doi.org\/10.1007\/s10586-022-03774-1","relation":{},"ISSN":["1386-7857","1573-7543"],"issn-type":[{"value":"1386-7857","type":"print"},{"value":"1573-7543","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,6]]},"assertion":[{"value":"4 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}