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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00073105
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 11:52:24 AM
Last modification on : Wednesday, March 13, 2019 - 3:02:04 PM
Long-term archiving on : Sunday, April 4, 2010 - 11:34:25 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

193

Files downloads

136