Scheduling Independent Tasks on Multi-cores with GPU Accelerators

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〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00921357
Contributeur : Grégory Mounié <>
Soumis le : lundi 10 novembre 2014 - 11:56:18
Dernière modification le : jeudi 11 janvier 2018 - 06:27:16
Document(s) archivé(s) le : mercredi 11 février 2015 - 15:29:18

Fichier

4tiers.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

358

Téléchargements de fichiers

282