TY - JOUR

T1 - Analytical and numerical evaluation of co-scheduling strategies and their application

AU - Kuchumov, Ruslan

AU - Korkhov, Vladimir

N1 - Publisher Copyright: © 2021 by the authors. Licensee MDPI, Basel, Switzerland.

PY - 2021/10/2

Y1 - 2021/10/2

N2 - 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.

AB - 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.

KW - Co-scheduling

KW - HPC

KW - Scheduling theory

KW - Stochastic optimization

KW - co-scheduling

KW - scheduling theory

KW - stochastic optimization

UR - http://www.scopus.com/inward/record.url?scp=85117132689&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/8f156d88-ab37-3052-a209-5d0d94836745/

U2 - 10.3390/computers10100122

DO - 10.3390/computers10100122

M3 - Article

AN - SCOPUS:85117132689

VL - 10

JO - Computers

JF - Computers

SN - 2073-431X

IS - 10

M1 - 122

ER -