{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T10:03:10Z","timestamp":1769248990105,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T00:00:00Z","timestamp":1646006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T00:00:00Z","timestamp":1646006400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>To share limited, large-capacity resources, the high-performance computing field provides services by allocating available resources to jobs through batch job schedulers. Therefore, it is natural that a queue waiting time occurs until the resources are available if resources are not sufficient. The prediction of queue waiting time is very useful to improve overall resource utilization. However, the queue waiting time is very difficult to predict because it is significantly affected by the many factors such as applied scheduling algorithm and characteristics of the executed job. In this study, a method of predicting queue waiting time using only the historical log data created by the batch job scheduler is examined. Specifically, a method of predicting queue waiting time based on a hidden Markov model is proposed. It has the following three stages. First, outliers are removed by applying the outlier detection algorithm using a statistics-based parametric method. Second, the parameters of the hidden state are estimated using the observed queue waiting time sequence based on the historical job log. Third, the queue waiting interval at time<jats:inline-formula><jats:alternatives><jats:tex-math>$$t+1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>t<\/mml:mi><mml:mo>+<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is provided using the estimated parameters at time<jats:italic>t<\/jats:italic>. Comparing the prediction accuracy with those of the other prediction methods, experimental results show that the proposed algorithm improves the prediction accuracy by up to 60%.<\/jats:p>","DOI":"10.1007\/s11227-022-04356-z","type":"journal-article","created":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T13:02:41Z","timestamp":1646053361000},"page":"12202-12223","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Queue congestion prediction for large-scale high performance computing systems using a hidden Markov model"],"prefix":"10.1007","volume":"78","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1388-1583","authenticated-orcid":false,"given":"Ju-Won","family":"Park","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Min-Woo","family":"Kwon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taeyoung","family":"Hong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,28]]},"reference":[{"key":"4356_CR1","doi-asserted-by":"crossref","unstructured":"Yoo AB, Jette MA, Grondona M (2003) Slurm: simple linux utility for resource management. In: Proc. of the Workshop on job scheduling strategies for parallel processing, Springer, pp 44\u201360","DOI":"10.1007\/10968987_3"},{"key":"4356_CR2","doi-asserted-by":"crossref","unstructured":"Henderson RL (1995) Job scheduling under the portable batch system. In: Proc. of the Workshop on Job Scheduling Strategies for Parallel Processing, Springer, pp 279\u2013294","DOI":"10.1007\/3-540-60153-8_34"},{"key":"4356_CR3","doi-asserted-by":"crossref","unstructured":"Qian J, Srisa-An W, Seth S, et\u00a0al (2016) Exploiting Fifo Scheduler to Improve Parallel Garbage Collection Performance. In: Proc. of the12th ACM SIGPLAN\/SIGOPS International Conference on Virtual Execution Environments, pp 109\u2013121","DOI":"10.1145\/2892242.2892248"},{"issue":"1","key":"4356_CR4","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1109\/TC.2020.2984607","volume":"70","author":"B Salami","year":"2020","unstructured":"Salami B, Noori H, Naghibzadeh M (2020) Fairness-aware energy efficient scheduling on heterogeneous multi-core processors. IEEE Trans Comput 70(1):72\u201382","journal-title":"IEEE Trans Comput"},{"issue":"118","key":"4356_CR5","first-page":"420","volume":"209","author":"S Zhou","year":"2020","unstructured":"Zhou S, Jin M, Du N (2020) Energy-efficient scheduling of a single batch processing machine with dynamic job arrival times. Energy 209(118):420","journal-title":"Energy"},{"issue":"1","key":"4356_CR6","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1214\/aoms\/1177697196","volume":"41","author":"LE Baum","year":"1970","unstructured":"Baum LE, Petrie T, Soules G et al (1970) A maximization technique occurring in the statistical analysis of probabilistic functions of markov chains. The Ann Math Stat 41(1):164\u2013171","journal-title":"The Ann Math Stat"},{"key":"4356_CR7","unstructured":"Technologies A (2021) Altair PBS Professional 2021.1 administrator\u2019s guide"},{"key":"4356_CR8","doi-asserted-by":"crossref","unstructured":"Kumar R, Vadhiyar S (2014) Prediction of queue waiting times for metascheduling on parallel batch systems. In: Proc of the Workshop on Job Scheduling Strategies for Parallel Processing, Springer, pp 108\u2013128","DOI":"10.1007\/978-3-319-15789-4_7"},{"key":"4356_CR9","doi-asserted-by":"crossref","unstructured":"Li H, Groep D, Wolters L (2005) Efficient response time predictions by exploiting application and resource state similarities. In: Proc of the 6th IEEE\/ACM International Workshop on Grid Computing, IEEE, pp 8","DOI":"10.1109\/GRID.2005.1542747"},{"key":"4356_CR10","doi-asserted-by":"crossref","unstructured":"Park JW (2019) Queue Witing Time Prediction for Large-Scale High-Performance Computing System. In: Proc of the International Conference on High Performance Computing & Simulation, IEEE, pp 850\u2013855","DOI":"10.1109\/HPCS48598.2019.9188119"},{"key":"4356_CR11","doi-asserted-by":"crossref","unstructured":"Downey AB (1997a) Predicting queue times on space-sharing parallel computers. In: Proc of the 11th International Parallel Processing Symposium, IEEE, pp 209\u2013218","DOI":"10.1109\/IPPS.1997.580894"},{"key":"4356_CR12","doi-asserted-by":"crossref","unstructured":"Downey AB (1997b) Using queue time predictions for processor allocation. In: Proc of the Workshop on Job Scheduling Strategies for Parallel Processing, Springer, pp 35\u201357","DOI":"10.1007\/3-540-63574-2_15"},{"key":"4356_CR13","doi-asserted-by":"crossref","unstructured":"Smith W, Taylor V, Foster I (1999) Using run-time predictions to estimate queue wait times and improve scheduler performance. In: Proc of the Workshop on Job scheduling strategies for Parallel Processing, Springer, pp 202\u2013219","DOI":"10.1007\/3-540-47954-6_11"},{"key":"4356_CR14","doi-asserted-by":"crossref","unstructured":"Nurmi D, Mandal A, Brevik J, et\u00a0al (2006) Evaluation of a Workflow Scheduler Using Integrated Performance Modelling and Batch Queue Wait Time Prediction. In: Proc. of the 2006 ACM\/IEEE conference on Supercomputing, IEEE, pp 29\u201329","DOI":"10.1109\/SC.2006.29"},{"key":"4356_CR15","doi-asserted-by":"crossref","unstructured":"Brevik J, Nurmi D, Wolski R (2004) Automatic methods for predicting machine availability in desktop grid and peer-to-peer systems. In: Proc. of the International Symposium on Cluster Computing and the Grid, IEEE, pp 190\u2013199","DOI":"10.1109\/CCGrid.2004.1336566"},{"key":"4356_CR16","doi-asserted-by":"crossref","unstructured":"Nurmi D, Brevik J, Wolski R (2007) Qbets: queue bounds estimation from time series. In: Proc of the workshop on job scheduling strategies for parallel processing, Springer, pp 76\u2013101","DOI":"10.1007\/978-3-540-78699-3_5"},{"key":"4356_CR17","doi-asserted-by":"crossref","unstructured":"Sonmez O, Yigitbasi N, Iosup A, et\u00a0al (2009) Trace-based evaluation of job runtime and queue wait time predictions in grids. In Proc of the 18th ACM international symposium on High performance distributed computing, ACM, pp 111\u2013120","DOI":"10.1145\/1551609.1551632"},{"key":"4356_CR18","doi-asserted-by":"crossref","unstructured":"Olivares M, Musalem A, Yung D (2020) Balancing Agent Retention and Waiting Time in Service Platforms. In: Proc of the 21st ACM Conference on Economics and Computation, ACM, pp 295\u2013313","DOI":"10.1145\/3391403.3399464"},{"issue":"3","key":"4356_CR19","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1080\/00401706.1991.10484833","volume":"33","author":"BH Juang","year":"1991","unstructured":"Juang BH, Rabiner LR (1991) Hidden markov models for speech recognition. Technometrics 33(3):251\u2013272","journal-title":"Technometrics"},{"issue":"3","key":"4356_CR20","doi-asserted-by":"publisher","first-page":"1429","DOI":"10.1007\/s11831-020-09422-4","volume":"28","author":"B Mor","year":"2020","unstructured":"Mor B, Garhwal S, Kumar A (2020) A systematic review of hidden markov models and their applications. Archiv Comput Methods Eng 28(3):1429\u20131448","journal-title":"Archiv Comput Methods Eng"},{"key":"4356_CR21","doi-asserted-by":"crossref","unstructured":"Li J, Wu B, Sun X, et\u00a0al (2021) Causal Hidden Markov Model for Time Series Disease Forecasting. In: Proc of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition, IEEE, pp 12,105\u201312,114","DOI":"10.1109\/CVPR46437.2021.01193"},{"issue":"5","key":"4356_CR22","doi-asserted-by":"publisher","first-page":"4887","DOI":"10.1007\/s11227-020-03476-8","volume":"77","author":"F Jazayeri","year":"2021","unstructured":"Jazayeri F, Shahidinejad A, Ghobaei-Arani M (2021) A latency-aware and energy-efficient computation offloading in mobile fog computing: a hidden markov model-based approach. The J Supercomput 77(5):4887\u20134916","journal-title":"The J Supercomput"},{"issue":"1","key":"4356_CR23","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1080\/00031305.1988.10475524","volume":"42","author":"J Lee Rodgers","year":"1988","unstructured":"Lee Rodgers J, Nicewander WA (1988) Thirteen ways to look at the correlation coefficient. The Am Stat 42(1):59\u201366","journal-title":"The Am Stat"},{"key":"4356_CR24","doi-asserted-by":"crossref","unstructured":"Benesty J, Chen J, Huang Y et al (2009) Pearson correlation coefficient. Noise Reduction in Speech Processing, vol 2. Springer, Berlin Heidelberg, pp 1\u20134","DOI":"10.1007\/978-3-642-00296-0_5"},{"issue":"346","key":"4356_CR25","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1080\/01621459.1974.10482955","volume":"69","author":"MB Brown","year":"1974","unstructured":"Brown MB, Forsythe AB (1974) Robust tests for the equality of variances. J Am Stat Assoc 69(346):364\u2013367","journal-title":"J Am Stat Assoc"},{"issue":"5","key":"4356_CR26","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 LA (2018) Correlation coefficients: appropriate use and interpretation. Anesth Anal 126(5):1763\u20131768","journal-title":"Anesth Anal"},{"issue":"1\u20133","key":"4356_CR27","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0304-4076(92)90104-Y","volume":"54","author":"D Kwiatkowski","year":"1992","unstructured":"Kwiatkowski D, Phillips PC, Schmidt P et al (1992) Testing the null hypothesis of stationarity against the alternative of a unit root: How sure are we that economic time series have a unit root? J Econ 54(1\u20133):159\u2013178","journal-title":"J Econ"},{"issue":"6","key":"4356_CR28","doi-asserted-by":"publisher","first-page":"1554","DOI":"10.1214\/aoms\/1177699147","volume":"37","author":"LE Baum","year":"1966","unstructured":"Baum LE, Petrie T (1966) Statistical inference for probabilistic functions of finite state markov chains. The Ann Math Stat 37(6):1554\u20131563","journal-title":"The Ann Math Stat"},{"issue":"2","key":"4356_CR29","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1023\/B:AIRE.0000045502.10941.a9","volume":"22","author":"V Hodge","year":"2004","unstructured":"Hodge V, Austin J (2004) A survey of outlier detection methodologies. Artif Intell Rev 22(2):85\u2013126","journal-title":"Artif Intell Rev"},{"key":"4356_CR30","unstructured":"Van\u00a0der Loo MP (2010) Distribution based outlier detection in univariate data. Statistics Netherlands"},{"issue":"1","key":"4356_CR31","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s10115-005-0233-6","volume":"11","author":"J Tang","year":"2007","unstructured":"Tang J, Chen Z, Fu AW et al (2007) Capabilities of outlier detection schemes in large datasets, framework and methodologies. Knowl Inform Syst 11(1):45\u201384","journal-title":"Knowl Inform Syst"},{"issue":"1","key":"4356_CR32","first-page":"1","volume":"3","author":"LE Baum","year":"1972","unstructured":"Baum LE et al (1972) An inequality and associated maximization technique in statistical estimation for probabilistic functions of markov processes. Inequalities 3(1):1\u20138","journal-title":"Inequalities"},{"issue":"6","key":"4356_CR33","doi-asserted-by":"publisher","first-page":"874","DOI":"10.1016\/j.engappai.2007.09.009","volume":"21","author":"A Ben-David","year":"2008","unstructured":"Ben-David A (2008) About the relationship between roc curves and cohen\u2019s kappa. Eng Appl Artif Intell 21(6):874\u2013882","journal-title":"Eng Appl Artif Intell"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04356-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-022-04356-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04356-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T13:02:11Z","timestamp":1726750931000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-022-04356-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,28]]},"references-count":33,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["4356"],"URL":"https:\/\/doi.org\/10.1007\/s11227-022-04356-z","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,28]]},"assertion":[{"value":"3 February 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}