Ordonnancement de chaines indépendantes sur processeurs uniformes avec délais de communication

Wieslaw Kubiak 1 Bernard Penz Denis Trystram
1 APACHE - Parallel algorithms and load sharing
ID-IMAG - Informatique et Distribution, Inria Grenoble - Rhône-Alpes, UJF - Université Joseph Fourier - Grenoble 1
Résumé : Nous montrons dans ce rapport que le problème qui consiste à ordonnancer un ensemble de chaines de taches unitaires indépendantes sur une machine parallèle à processeurs uniformes est NP-difficile au sens fort (en tenant compte ou non des délais de communications). Nous présentons un algorithme linéaire qui calcule une solution optimale pour le cas de 2 processeurs avec délai de communication, lorsqu'un processeur est a fois plus rapide que l'autre (avec a entier). Enfin, nous dérivons une heuristique dans le cas d'un nombre fixé de processeurs avec une bonne garantie de performance.
Type de document :
Rapport
RR-3576, INRIA. 1998
Liste complète des métadonnées

https://hal.inria.fr/inria-00073105
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:52:24
Dernière modification le : mercredi 11 avril 2018 - 01:51:34
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:34:25

Fichiers

Identifiants

  • HAL Id : inria-00073105, version 1

Collections

Citation

Wieslaw Kubiak, Bernard Penz, Denis Trystram. Ordonnancement de chaines indépendantes sur processeurs uniformes avec délais de communication. RR-3576, INRIA. 1998. 〈inria-00073105〉

Partager

Métriques

Consultations de la notice

172

Téléchargements de fichiers

118