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
T2 - 10th International Conference on Theory and Applications of Models of Computation, TAMC 2013
Y2 - 20 May 2013 through 22 May 2013
ER -