{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T12:41:45Z","timestamp":1775047305226,"version":"3.50.1"},"reference-count":34,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2021,10,2]],"date-time":"2021-10-02T00:00:00Z","timestamp":1633132800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002261","name":"Russian Foundation for Basic Research","doi-asserted-by":"publisher","award":["19-37-90138"],"award-info":[{"award-number":["19-37-90138"]}],"id":[{"id":"10.13039\/501100002261","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computers"],"abstract":"<jats:p>Applications in high-performance computing (HPC) may not use all available computational resources, leaving some of them underutilized. By co-scheduling, i.e., running more than one application on the same computational node, it is possible to improve resource utilization and overall throughput. Some applications may have conflicting requirements on resources and co-scheduling may cause performance degradation, so it is important to take it into account in scheduling decisions. In this paper, we formalize the co-scheduling problem and propose multiple scheduling strategies to solve it: an optimal strategy, an online strategy and heuristic strategies. These strategies vary in terms of the optimality of the solution they produce and a priori information about the system they require. We show theoretically that the online strategy provides schedules with a competitive ratio that has a constant upper limit. This allows us to solve the co-scheduling problem using heuristic strategies that approximate this online strategy. Numerical simulations show how heuristic strategies compare to the optimal strategy for different input systems. We propose a method for measuring input parameters of the model in practice and evaluate this method on HPC benchmark applications. We show the high accuracy of the measurement method, which allows us to apply the proposed scheduling strategies in the scheduler implementation.<\/jats:p>","DOI":"10.3390\/computers10100122","type":"journal-article","created":{"date-parts":[[2021,10,4]],"date-time":"2021-10-04T09:24:15Z","timestamp":1633339455000},"page":"122","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Analytical and Numerical Evaluation of Co-Scheduling Strategies and Their Application"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8927-2111","authenticated-orcid":false,"given":"Ruslan","family":"Kuchumov","sequence":"first","affiliation":[{"name":"Faculty of Applied Mathematics and Control Processes, Saint Petersburg State University, 7\/9 Universitetskaya Emb., 199034 St. Petersburg, Russia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2458-3194","authenticated-orcid":false,"given":"Vladimir","family":"Korkhov","sequence":"additional","affiliation":[{"name":"Faculty of Applied Mathematics and Control Processes, Saint Petersburg State University, 7\/9 Universitetskaya Emb., 199034 St. Petersburg, Russia"}]}],"member":"1968","published-online":{"date-parts":[[2021,10,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1203","DOI":"10.1021\/acs.chemrev.0c00006","article-title":"Many-Body Quantum Chemistry on Massively Parallel Computers","volume":"121","author":"Calvin","year":"2020","journal-title":"Chem. Rev."},{"key":"ref_2","unstructured":"Sharif, M.B., Ghafoor, S.K., Hines, T.M., Morales-Hern\u00e4ndez, M., Evans, K.J., Kao, S.C., Kalyanapu, A.J., Dullo, T.T., and Gangrade, S. (July, January 29). Performance Evaluation of a Two-Dimensional Flood Model on Heterogeneous High-Performance Computing Architectures. Proceedings of the Platform for Advanced Scientific Computing Conference, Geneva, Switzerland."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Rudy, J., and Rodwald, P. (2020). Job Scheduling with Machine Speeds for Password Cracking Using Hashtopolis. Advances in Intelligent Systems and Computing, Springer International Publishing.","DOI":"10.1007\/978-3-030-48256-5_51"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1177\/1094342015597083","article-title":"A survey of high-performance computing scaling challenges","volume":"31","author":"Geist","year":"2016","journal-title":"Int. J. High Perform. Comput. Appl."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"3373","DOI":"10.1007\/s11227-015-1438-4","article-title":"Workflow scheduling in cloud: A survey","volume":"71","author":"Wu","year":"2015","journal-title":"J. Supercomput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"e4041","DOI":"10.1002\/cpe.4041","article-title":"A taxonomy and survey on scheduling algorithms for scientific workflows in IaaS cloud computing environments","volume":"29","author":"Rodriguez","year":"2016","journal-title":"Concurr. Comput. Pract. Exp."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Yoo, A.B., Jette, M.A., and Grondona, M. (2003, January 24). Slurm: Simple linux utility for resource management. Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, Seattle, WA, USA.","DOI":"10.1007\/10968987_3"},{"key":"ref_8","unstructured":"Gentzsch, W. (2001, January 15\u201318). Sun Grid Engine: Towards creating a compute power grid. Proceedings of the First IEEE\/ACM International Symposium on Cluster Computing and the Grid, Brisbane, QLD, Australia."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Uchro\u0144ski, M., Bo\u017cejko, W., Krajewski, Z., Tykierko, M., and Wodecki, M. (2018). User Estimates Inaccuracy Study in HPC Scheduler. Advances in Intelligent Systems and Computing, Springer International Publishing.","DOI":"10.1007\/978-3-319-91446-6_47"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Gainaru, A., Aupy, G.P., Sun, H., and Raghavan, P. (2019, January 5\u20138). Speculative Scheduling for Stochastic HPC Applications. Proceedings of the 48th International Conference on Parallel Processing, Kyoto, Japan.","DOI":"10.1145\/3337821.3337890"},{"key":"ref_11","unstructured":"Breslow, A.D., Porter, L., Tiwari, A., Laurenzano, M., Carrington, L., Tullsen, D.M., and Snavely, A.E. (2012). The case for colocation of HPC workloads. Concurrency and Computation: Practice and Experience Preprint, John Wiley & Sons."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Breitbart, J., Pickartz, S., Lankes, S., Weidendorfer, J., and Monti, A. (2017, January 5\u20138). Dynamic Co-Scheduling Driven by Main Memory Bandwidth Utilization. Proceedings of the 2017 IEEE International Conference on Cluster Computing (CLUSTER), Honolulu, HI, USA.","DOI":"10.1109\/CLUSTER.2017.59"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Zacarias, F.V., Petrucci, V., Nishtala, R., Carpenter, P., and Moss\u00e9, D. (2019, January 15\u201318). Intelligent Colocation of Workloads for Enhanced Server Efficiency. Proceedings of the 2019 31st International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), Campo Grande, Brazil.","DOI":"10.1109\/SBAC-PAD.2019.00030"},{"key":"ref_14","unstructured":"Pottier, L. (2018). Co-Scheduling for Large-Scale Applications: Memory and Resilience. [Ph.D. Thesis, Universit\u00e9 de Lyon]."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3375714","article-title":"Dynamic colocation policies with reinforcement learning","volume":"17","author":"Li","year":"2020","journal-title":"ACM Trans. Archit. Code Optim. (TACO)"},{"key":"ref_16","unstructured":"Trinitis, C., and Weidendorfer, J. (2017). Co-Scheduling of HPC Applications, IOS Press."},{"key":"ref_17","unstructured":"de Blanche, A., and Lundqvist, T. (2018, January 23). Node Sharing for Increased Throughput and Shorter Runtimes\u2014An Industrial Co-Scheduling Case Study. Proceedings of the 3rd Workshop on Co-Scheduling of HPC Applications (COSH 2018), Manchester, UK."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Xiong, Q., Ates, E., Herbordt, M.C., and Coskun, A.K. (2018, January 25\u201327). Tangram: Colocating HPC Applications with Oversubscription. Proceedings of the 2018 IEEE High Performance extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2018.8547644"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Kuchumov, R., and Korkhov, V. (2021). An Analytical Bound for Choosing Trivial Strategies in Co-scheduling. International Conference on Computational Science and Its Applications, Springer International Publishing. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-030-87010-2_28"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1177\/1094342017710806","article-title":"Co-scheduling Amdahl applications on cache-partitioned systems","volume":"32","author":"Aupy","year":"2018","journal-title":"Int. J. High Perform. Comput. Appl."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1221","DOI":"10.1177\/1094342019846956","article-title":"Co-scheduling HPC workloads on cache-partitioned CMP platforms","volume":"33","author":"Aupy","year":"2019","journal-title":"Int. J. High Perform. Comput. Appl."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/j.jpdc.2021.02.010","article-title":"Intelligent colocation of HPC workloads","volume":"151","author":"Zacarias","year":"2021","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Jokanovic, A., Sancho, J.C., Rodriguez, G., Lucero, A., Minkenberg, C., and Labarta, J. (2015, January 25\u201329). Quiet Neighborhoods: Key to Protect Job Performance Predictability. Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium, Hyderabad, India.","DOI":"10.1109\/IPDPS.2015.87"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Snavely, A., and Tullsen, D.M. (2000). Symbiotic jobscheduling for a simultaneous multithreaded processor. ACM SIGOPS Operating Systems Review, Association for Computing Machinery.","DOI":"10.1145\/378993.379244"},{"key":"ref_25","unstructured":"Parekh, S., Eggers, S., Levy, H., and Lo, J. (2000). Thread-Sensitive Scheduling for SMT Processors, University of Washington. Technical Report 2000-04-02."},{"key":"ref_26","unstructured":"Jain, R., Hughes, C.J., and Adve, S.V. (2002, January 3\u20135). Soft real-time scheduling on simultaneous multithreaded processors. Proceedings of the 23rd IEEE Real-Time Systems Symposium, RTSS 2002, Austin, TX, USA."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Eyerman, S., Michaud, P., and Rogiest, W. (2015, January 29\u201331). Revisiting symbiotic job scheduling. Proceedings of the 2015 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), Philadelphia, PA, USA.","DOI":"10.1109\/ISPASS.2015.7095791"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Gawiejnowicz, S. (2020). Models and Algorithms of Time-Dependent Scheduling, Springer.","DOI":"10.1007\/978-3-662-59362-2"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Pinedo, M.L. (2012). Scheduling. Theory, Algorithms, and Systems, Springer.","DOI":"10.1007\/978-1-4614-2361-4"},{"key":"ref_30","unstructured":"Matousek, J., and Gartner, B. (2006). Understanding and Using Linear Programming, Springer."},{"key":"ref_31","unstructured":"Bailey, D., Harris, T., Saphir, W., Van Der Wijngaart, R., Woo, A., and Yarrow, M. (1995). The NAS Parallel Benchmarks 2.0, Technical Report, Technical Report NAS-95-020."},{"key":"ref_32","unstructured":"Bienia, C. (2011). Benchmarking Modern Multiprocessors. [Ph.D. Thesis, Princeton University]."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Kuchumov, R., and Korkhov, V. (2020, January 1\u20134). Collecting HPC Applications Processing Characteristics to Facilitate Co-scheduling. Proceedings of the International Conference on Computational Science and Its Applications, Cagliari, Italy.","DOI":"10.1007\/978-3-030-58817-5_14"},{"key":"ref_34","unstructured":"Kuchumov, R., and Korkhov, V. (2021, September 30). Co-Scheduling Numerical Simulation Source Code. Available online: https:\/\/gitlab.com\/mildlyparallel\/co-scheduling-simulations."}],"container-title":["Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-431X\/10\/10\/122\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:08:46Z","timestamp":1760166526000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-431X\/10\/10\/122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,2]]},"references-count":34,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2021,10]]}},"alternative-id":["computers10100122"],"URL":"https:\/\/doi.org\/10.3390\/computers10100122","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints202109.0053.v1","asserted-by":"object"}]},"ISSN":["2073-431X"],"issn-type":[{"value":"2073-431X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,2]]}}}