Semi-matching algorithms for scheduling parallel tasks under resource constraints

Anne Benoit 1, 2 Johannes Langguth 2 Bora Uçar 1, 2, *
* Auteur correspondant
1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : On étudie le problème d'ordonnancement visant à minimiser le temps d'exécution lorsque les tâches peuvent être exécutées soit sur un seul processeur, soit sur plusieurs processeurs en parallèle, et sont restreintes à cer- tains sous-ensembles de processeurs. Le problème se ramène à devoir trouver un couplage partiel dans un graphe biparti ou dans un hypergraphe. Sur les graphes bipartis, le problème général est NP-complet, mais il est possible de résoudre en temps polynomial les instances de problèmes où toutes les tâches sont de poids unitaire. Nous montrons dans ce rapport que le problème devient NP-complet pour les hypergraphes même dans le cas unitaire. Nous proposons plusieurs algorithmes gloutons pour résoudre deux versions du problème, et nous étudions leur performance à travers des simulations. Bien qu'il n'y ait aucune garantie d'approximation sur ces algorithmes, ils retournent en moyenne des so- lutions proches de l'optimal (ou d'une borne inférieure connue), avec un temps d'exécution très rapide.
Type de document :
Communication dans un congrès
IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, May 2013, Cambridge, MA, United States. IEEE Computer Society, pp.1744-1753, 2013, 〈10.1109/IPDPSW.2013.30〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00738393
Contributeur : Bora Uçar <>
Soumis le : jeudi 2 janvier 2014 - 19:11:01
Dernière modification le : mardi 16 janvier 2018 - 15:33:58
Document(s) archivé(s) le : samedi 8 avril 2017 - 10:35:34

Fichier

revised-hsm-pco.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Anne Benoit, Johannes Langguth, Bora Uçar. Semi-matching algorithms for scheduling parallel tasks under resource constraints. IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, May 2013, Cambridge, MA, United States. IEEE Computer Society, pp.1744-1753, 2013, 〈10.1109/IPDPSW.2013.30〉. 〈hal-00738393v5〉

Partager

Métriques

Consultations de la notice

490

Téléchargements de fichiers

327