# Scheduling Independent Tasks on Multi-cores with GPU Accelerators

1 RO - Recherche Opérationnelle
LIP6 - Laboratoire d'Informatique de Paris 6
2 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
LIG - Laboratoire d'Informatique de Grenoble, Inria Grenoble - Rhône-Alpes
Abstract : More and more computers use hybrid architectures combin-ing multi-core processors and hardware accelerators like GPUs (Graphics Processing Units). We present in this paper a new method for scheduling efficiently parallel applications with $m$ CPUs and $k$ GPUs, where each task of the application can be processed either on a core (CPU) or on a GPU. The objective is to minimize the makespan. The corresponding scheduling problem is NP-hard, we propose an efficient approximation algorithm which achieves an approximation ratio of $\frac{4}{3} + \frac{1}{3k}$ . We first detail and analyze the method, based on a dual approximation scheme, that uses a dynamic programming scheme to balance evenly the load between the heterogeneous resources. Finally, we run some simulations based on realistic benchmarks and compare the solution obtained by a relaxed version of this method to the one provided by a classical greedy algorithm and to lower bounds on the value of the optimal makespan.
Document type :
Conference papers

Cited literature [15 references]

https://hal.inria.fr/hal-00921357
Contributor : Grégory Mounié Connect in order to contact the contributor
Submitted on : Monday, November 10, 2014 - 11:56:18 AM
Last modification on : Tuesday, November 16, 2021 - 4:19:37 AM
Long-term archiving on: : Wednesday, February 11, 2015 - 3:29:18 PM

### File

4tiers.pdf
Files produced by the author(s)

### Citation

Safia Kedad-Sidhoum, Florence Monna, Grégory Mounié, Denis Trystram. Scheduling Independent Tasks on Multi-cores with GPU Accelerators. HeteroPar 2013 - 11th International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms, Aug 2013, Aachen, Germany. pp.228-237, ⟨10.1007/978-3-642-54420-0_23⟩. ⟨hal-00921357⟩

Record views