TY - GEN

T1 - Online scheduling on a CPU-GPU cluster

AU - Chen, Lin

AU - Ye, Deshi

AU - Zhang, Guochuan

N1 - Funding Information:
Research was supported by in part by NSFC(11071215,11271325).

PY - 2013

Y1 - 2013

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 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. We provide a (1 + v3)-competitive algorithm for the balanced case, and a 3-competitive algorithm for the one-sided case.

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 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. We provide a (1 + v3)-competitive algorithm for the balanced case, and a 3-competitive algorithm for the one-sided case.

KW - CPU-GPU cluster

KW - Competitive ratio

KW - Online scheduling

KW - Unrelated machine scheduling

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

U2 - 10.1007/978-3-642-38236-9_1

DO - 10.1007/978-3-642-38236-9_1

M3 - Conference contribution

AN - SCOPUS:84893465822

SN - 9783642382352

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 9

BT - Theory and Applications of Models of Computation - 10th International Conference, TAMC 2013, Proceedings

PB - Springer-Verlag

Y2 - 20 May 2013 through 22 May 2013

ER -