Optimizing Latency and Reliability of Pipeline Workflow Applications

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 applications onto heterogeneous platforms is a difficult challenge, even for simple application patterns such as pipeline graphs. The problem is even more complex when processors are subject to failure during the execution of the application. In this paper, we study the complexity of a bi-criteria mapping which aims at optimizing the latency (i.e., the response time) and the reliability (i.e., the probability that the computation will be successful) of the application. Latency is minimized by using faster processors, while reliability is increased by replicating computations on a set of processors. However, replication increases latency (additional communications, slower processors). The application fails to be executed only if all the processors fail during execution. While simple polynomial algorithms can be found for fully homogeneous platforms, the problem becomes NP-hard when tackling heterogeneous platforms. This is yet another illustration of the additional complexity added by heterogeneity.
Type de document :
Rapport
[Research Report] RR-6345, INRIA. 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00186152
Contributeur : Veronika Rehn-Sonigo <>
Soumis le : mercredi 26 mars 2008 - 10:28:13
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : vendredi 24 septembre 2010 - 11:09:32

Fichiers

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

Identifiants

  • HAL Id : inria-00186152, version 4
  • ARXIV : 0711.1231

Collections

Citation

Anne Benoit, Veronika Rehn-Sonigo, Yves Robert. Optimizing Latency and Reliability of Pipeline Workflow Applications. [Research Report] RR-6345, INRIA. 2008. 〈inria-00186152v4〉

Partager

Métriques

Consultations de la notice

310

Téléchargements de fichiers

122