TY - JOUR

T1 - Online scheduling of mixed CPU-GPU jobs

AU - Chen, Lin

AU - Ye, Deshi

AU - Zhang, Guochuan

N1 - Funding Information:
∗A preliminary version of this paper appeared in Proceedings of the 10th International Conference on Theory and Applications of Models of Computation (TAMC’13 1-9). Research was supported in part by NSFC(11071215,11271325). ‡Corresponding author.
Publisher Copyright:
© World Scientific Publishing Company.

PY - 2014/11/8

Y1 - 2014/11/8

N2 - We consider the online scheduling problem in a CPU-GPU cluster. In this problem there are two sets of processors, the CPU processors and the GPU processors. Each job has two distinct processing times, one for the CPU processor and the other for the GPU processor. Once a job is released, a decision should be made immediately about which processor it should be assigned to. The goal is to minimize the makespan, i.e., the largest completion time among all the processors. Such a problem could be seen as an intermediate model between the scheduling problem on identical machines and unrelated machines. We provide a 3.85-competitive online algorithm for this problem and show that no online algorithm exists with competitive ratio strictly less than 2. We also consider two special cases of this problem, the balanced case where the number of CPU processors equals to that of GPU processors, and the one-sided case where there is only one CPU or GPU processor. For the balanced case, we first provide a simple 3-competitive algorithm, and then a better algorithm with competitive ratio of 2.732 is derived. For the one-sided case, a 3-competitive algorithm is given.

AB - We consider the online scheduling problem in a CPU-GPU cluster. In this problem there are two sets of processors, the CPU processors and the GPU processors. Each job has two distinct processing times, one for the CPU processor and the other for the GPU processor. Once a job is released, a decision should be made immediately about which processor it should be assigned to. The goal is to minimize the makespan, i.e., the largest completion time among all the processors. Such a problem could be seen as an intermediate model between the scheduling problem on identical machines and unrelated machines. We provide a 3.85-competitive online algorithm for this problem and show that no online algorithm exists with competitive ratio strictly less than 2. We also consider two special cases of this problem, the balanced case where the number of CPU processors equals to that of GPU processors, and the one-sided case where there is only one CPU or GPU processor. For the balanced case, we first provide a simple 3-competitive algorithm, and then a better algorithm with competitive ratio of 2.732 is derived. For the one-sided case, a 3-competitive algorithm is given.

KW - CPU-GPU cluster

KW - Competitive ratio

KW - Online scheduling

KW - Unrelated machine scheduling

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

U2 - 10.1142/S0129054114500312

DO - 10.1142/S0129054114500312

M3 - Article

AN - SCOPUS:84908620336

SN - 0129-0541

VL - 25

SP - 745

EP - 761

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 6

ER -