TY - GEN

T1 - Scheduling Malleable Jobs under Topological Constraints

AU - Bampis, Evripidis

AU - Dogeas, Konstantinos

AU - Kononov, Alexander

AU - Lucarelli, Giorgio

AU - Pascual, Fanny

PY - 2020/5/1

Y1 - 2020/5/1

N2 - Bleuse et al. (EuroPar 2018) introduced a general model for interference-aware scheduling in large scale parallel platforms. They considered two different types of communications: the flows induced by data exchanges during computations and the flows related to Input/Output operations. Rather than taking into account these communications explicitly, they restrict the possible allocations of a job by external topological constraints. In their work, jobs are considered to be rigid: a job requires a specific number of machines in order to be executed. Here, we first adopt the same framework for the platform and the aforementioned topological constraints. We show that there is no polynomial time approximation algorithm under the rigid setting with ratio smaller than 3/2, unless P = NP. Then, we focus on the malleable setting. We show that in the proportional-malleable setting, where the work of every job remains constant independently of the number of machines on which it is executed, the scheduling problem remains NPhard even in the uniform case, where the maximum number of machines is the same for all the jobs. Then, we propose a 2-approximation algorithm for this case. Furthermore, we present an approximation algorithm solving the more general case where the maximum number of machines is job-dependent and the work of the jobs is increasing with respect to the number of used machines, due to the communication overhead.

AB - Bleuse et al. (EuroPar 2018) introduced a general model for interference-aware scheduling in large scale parallel platforms. They considered two different types of communications: the flows induced by data exchanges during computations and the flows related to Input/Output operations. Rather than taking into account these communications explicitly, they restrict the possible allocations of a job by external topological constraints. In their work, jobs are considered to be rigid: a job requires a specific number of machines in order to be executed. Here, we first adopt the same framework for the platform and the aforementioned topological constraints. We show that there is no polynomial time approximation algorithm under the rigid setting with ratio smaller than 3/2, unless P = NP. Then, we focus on the malleable setting. We show that in the proportional-malleable setting, where the work of every job remains constant independently of the number of machines on which it is executed, the scheduling problem remains NPhard even in the uniform case, where the maximum number of machines is the same for all the jobs. Then, we propose a 2-approximation algorithm for this case. Furthermore, we present an approximation algorithm solving the more general case where the maximum number of machines is job-dependent and the work of the jobs is increasing with respect to the number of used machines, due to the communication overhead.

KW - Approximation algorithms

KW - communications

KW - Input/Output

KW - malleable jobs

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

U2 - 10.1109/IPDPS47924.2020.00041

DO - 10.1109/IPDPS47924.2020.00041

M3 - Conference contribution

AN - SCOPUS:85088898436

T3 - Proceedings - 2020 IEEE 34th International Parallel and Distributed Processing Symposium, IPDPS 2020

SP - 316

EP - 325

BT - Proceedings - 2020 IEEE 34th International Parallel and Distributed Processing Symposium, IPDPS 2020

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 34th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2020

Y2 - 18 May 2020 through 22 May 2020

ER -