Co-Scheduling Algorithms for High-Throughput Workload Execution

Résumé : Nous étudions des algorithmes d'ordonnancement par lots pour un ensemble de tâches parallélisables. Plutôt que d'ordonnancer les tâches séquentiellement en utilisant le degré maximum de parallélisme pour chacune d'entre elles, nous cherchons à ordonnancer plusieurs tâches de manière concurrente. L'idée est de partitionner l'ensemble des tâches en une série de lots, qui seront exécutés les uns après les autres. Un lot est composé de plusieurs tâches, et un certain nombre de processeurs est alloué à chacune de ces tâches, sous la contrainte que le nombre total de processeurs alloués à un lot ne dépasse pas le nombre maximum de processeurs disponibles. L'objectif est de trouver une partition de l'ensemble des tâches en lots, et une allocation de processeurs optimale pour la minimisation de la somme des temps d'exécution de chaque lot. Nous étudions la complexité de ce problème d'optimisation, et proposons plusieurs heuristiques qui obtiennent d'excellentes performances sur plusieurs ensembles de tâches représentatifs des calculs parallèles scientifiques. Notre technique d'ordon\-nancement par lots permet non seulement d'obtenir un gain sur le temps d'exécution total, mais obtient également d'excellents résultats pour le temps de réponse moyen.
Type de document :
Rapport
[Research Report] RR-8293, INRIA. 2013, pp.21
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00819036
Contributeur : Guillaume Aupy <>
Soumis le : mercredi 8 mai 2013 - 10:32:47
Dernière modification le : jeudi 4 octobre 2018 - 16:24:05
Document(s) archivé(s) le : mardi 4 avril 2017 - 01:44:15

Fichier

RR-8293.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00819036, version 1

Collections

Citation

Guillaume Aupy, Manu Shantharam, Anne Benoit, Yves Robert, Padma Raghavan. Co-Scheduling Algorithms for High-Throughput Workload Execution. [Research Report] RR-8293, INRIA. 2013, pp.21. 〈hal-00819036〉

Partager

Métriques

Consultations de la notice

507

Téléchargements de fichiers

166