New Challenges in Scheduling Theory

October 21 - 27, 2012 --- Centre CNRS "La Villa Clythia", Frejus, France

A 4/3-Approximation Algorithm for a Scheduling Problem on Multi-Cores with GPUs

SpeakerFlorence Monna

Coauthors: Safia Kedad-Sidhoum, Gregory Mounié, and Denis Trystram

There are more and more multi-core architectures using accelerators like GPUs (Graphics Processing Units). We propose here a new method for scheduling efficiently any parallel application using mixed CPU-GPU architectures where some tasks can be processed either on a core (CPU) or a GPU. This problem of scheduling with GPUs is NP-hard, thus, we are looking for efficient algorithms with small approximation ratio. We introduce this method for the relaxed problem of a computing platform with only one GPU. We provide a dynamic programming scheme which achieves an approximation ratio of 4/3. Then, the analysis is extended for any number of GPUs (denoted by k) whose guarantee is 4/3 + 1/(3k). Finally, we run simulations based on the benchmark suite Rodinia. They emphasize the good behaviour of the proposed method in regard to a classical list scheduling algorithm.