Low-Cost Approximation Algorithms for Scheduling Independent Tasks on Hybrid Platforms - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2017

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

Algorithmes d’approximation pour l’ordonnancement de tâches indépendantes sur des plates-formes hybrides

Résumé

Hybrid platforms embedding accelerators such as GPUs or Xeon Phis are increasingly used in computing. When scheduling tasks on such platforms, one has to take into account that a task execution time depends on the type of core used to execute it. We focus on the problem of minimizing the total completion time (or makespan) when scheduling independent tasks on two processor types, also known as the (Pm,Pk)||Cmax problem. We propose BalancedEstimate and BalancedMakespan, two novel 2-approximation algorithms with low complexity. Their approximation ratio is both on par with the best approximation algorithms using dual approximation techniques (which are, thus, of high complexity) and significantly smaller than the approximation ratio of existing low-cost approximation algorithms. We compared both algorithms by simulations to existing strategies in different scenarios. These simulations showed that their performance is among the best ones in all cases.
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.
Fichier principal
Vignette du fichier
RR-9029.pdf (1014.38 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01475884 , version 1 (24-02-2017)
hal-01475884 , version 2 (23-06-2017)

Identifiants

  • HAL Id : hal-01475884 , version 1

Citer

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-01475884v1⟩
492 Consultations
512 Téléchargements

Partager

Gmail Facebook X LinkedIn More