Multi-criteria scheduling of pipeline workflows

Anne Benoit 1, 2 Veronika Rehn-Sonigo 1, 2 Yves Robert 1, 2
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : 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.
Type de document :
Rapport
[Research Report] RR-6232, INRIA. 2007
Liste complète des métadonnées

https://hal.inria.fr/inria-00156732
Contributeur : Rapport de Recherche Inria <>
Soumis le : jeudi 28 juin 2007 - 17:19:56
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : vendredi 24 septembre 2010 - 10:59:59

Fichiers

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

Identifiants

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

Collections

Citation

Anne Benoit, Veronika Rehn-Sonigo, Yves Robert. Multi-criteria scheduling of pipeline workflows. [Research Report] RR-6232, INRIA. 2007. 〈inria-00156732v4〉

Partager

Métriques

Consultations de la notice

305

Téléchargements de fichiers

129