Low-Cost Approximation Algorithms for Scheduling Independent Tasks on Hybrid Platforms

Résumé : Les plates-formes hybrides utilisant sur des accélérateurs tels que des GPUs ou des Xeon Phis sont de plus en plus utilisées pour le calcul. Lors de l’ordonnancement de tâches sur de telles plates-formes, il est nécessaire de prendre en compte les temps d’exécution des tâches en fonction du type de coeurs utilisé pour l’exécuter. Nous traitons le problème consistant à minimiser le temps total d’exécution (ou makespan) lors de l’ordonnancement de tâches indépendantes sur deux types de processeurs, problème noté (Pm, Pk)||Cmax. Nous proposons BalancedEstimate et BalancedMakespan, deux nouveaux algorithmes d’approximation de facteur 2 avec de faibles complexités. Leur facteur d’approximation est à la fois similaire à celui des meilleurs algorithmes d’approximation reposant sur des techniques d’approximation duale (et qui ont donc de grandes complexités) et significativement meilleur que ceux des algorithmes d’approximation existants de faible coût. Nous avons comparé ces deux algorithmes aux stratégies existantes avec des simulations dans différents scénarios. Ces simulations ont montré que leurs performances sont parmi les meilleures dans tous les cas.
Type de document :
Rapport
[Research Report] RR-9029, Inria - Research Centre Grenoble – Rhône-Alpes. 2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01475884
Contributeur : Equipe Roma <>
Soumis le : vendredi 23 juin 2017 - 15:08:38
Dernière modification le : vendredi 6 juillet 2018 - 15:06:09
Document(s) archivé(s) le : mercredi 10 janvier 2018 - 22:20:54

Fichier

INRIA-9029v2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01475884, version 2

Citation

Loris Marchal, Louis-Claude Canon, Frédéric Vivien. Low-Cost Approximation Algorithms for Scheduling Independent Tasks on Hybrid Platforms. [Research Report] RR-9029, Inria - Research Centre Grenoble – Rhône-Alpes. 2017. 〈hal-01475884v2〉

Partager

Métriques

Consultations de la notice

320

Téléchargements de fichiers

117