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
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
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.
Type de document :
Communication dans un congrès
HeteroPar 2013 - 11th International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms, Aug 2013, Aachen, Germany. Springer, Euro-Par 2013: Parallel Processing Workshops, 8374, pp.228-237, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-642-54420-0_23〉

Littérature citée [15 références]

https://hal.inria.fr/hal-00921357
Contributeur : Grégory Mounié <>
Soumis le : lundi 10 novembre 2014 - 11:56:18
Dernière modification le : vendredi 21 décembre 2018 - 10:46:07
Document(s) archivé(s) le : mercredi 11 février 2015 - 15:29:18

Fichier

4tiers.pdf
Fichiers produits par l'(les) auteur(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. Springer, Euro-Par 2013: Parallel Processing Workshops, 8374, pp.228-237, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-642-54420-0_23〉. 〈hal-00921357〉

Métriques

Consultations de la notice

532

Téléchargements de fichiers