Multi-criteria scheduling of pipeline workflows - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

Multi-criteria scheduling of pipeline workflows

Résumé

Mapping workflow applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline graphs. Several antagonist criteria should be optimized, such as throughput and latency (or a combination). In this paper, we study the complexity of the bi-criteria mapping problem for pipeline graphs on communication homogeneous platforms. In particular, we assess the complexity of the well-known chains-to-chains problem for different-speed processors, which turns out to be NP-hard. We provide several efficient polynomial bi-criteria heuristics, and their relative performance is evaluated through extensive simulations.
L’ordonnancement et l’allocation des workflows sur plates-formes parallèles est un problème crucial, même pour des applications simples comme des graphes en pipeline. Plusieurs critères contradictoires doivent être optimisés, tels que le débit et la latence (ou une combinaison des deux). Dans ce rapport, nous étudions la complexité du problème de l’ordonnancement bi-critère pour les graphes pipelinés sur des plate-formes avec communications homogènes. En particulier nous évaluons la complexité du problème bien connu ”chains-on-chains” pour les processeurs hétérogènes, un problème qui s’avère NP-difficile. Nous proposons plusieurs heuristiques bi-critères efficaces en temps polynomial. Leur performance relative est évaluée par des simulations intensives.
Fichier principal
Vignette du fichier
RR-6232.pdf (287.56 Ko) Télécharger le fichier
RR2007-32.pdf (544.18 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00156732 , version 1 (27-06-2007)
inria-00156732 , version 2 (27-06-2007)
inria-00156732 , version 3 (28-06-2007)
inria-00156732 , version 4 (28-06-2007)

Identifiants

  • HAL Id : inria-00156732 , version 4
  • ARXIV : 0706.4009

Citer

Anne Benoit, Veronika Rehn-Sonigo, Yves Robert. Multi-criteria scheduling of pipeline workflows. [Research Report] RR-6232, LIP RR-2007-32, INRIA. 2007, 2+17p. ⟨inria-00156732v4⟩
151 Consultations
174 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More