ONLINE SCHEDULING OF MIXED CPU-GPU JOBS
Authors:
- 1 September 2014
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 25 (06) , 745-761
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- Partitioned EDF scheduling on a few types of unrelated multiprocessorsReal-Time Systems, 2012
- Scheduling on two identical machines with a speed-up resourceInformation Processing Letters, 2011
- Scheduling parallel dedicated machines with the speeding‐up resourceNaval Research Logistics (NRL), 2008
- On-Line Load Balancing for Related MachinesJournal of Algorithms, 2000
- An On-Line Algorithm for Some Uniform Processor SchedulingSIAM Journal on Computing, 1998
- On-line routing of virtual circuits with applications to load balancing and machine schedulingJournal of the ACM, 1997
- Approximation algorithms for scheduling unrelated parallel machinesMathematical Programming, 1990
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation ApproachSIAM Journal on Computing, 1988
- Bounds for List Schedules on Uniform ProcessorsSIAM Journal on Computing, 1980
- Bounds for Certain Multiprocessing AnomaliesBell System Technical Journal, 1966