Complexity results for throughput and latency optimization of replicated and data-parallel workflows

Anne Benoit 1, 2 Yves Robert 1, 2
2 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 parallel platforms is a challenging problem, even for simple application patterns such as pipeline or fork graphs. Several antagonist criteria should be optimized for workflow applications, such as throughput and latency (or a combination). In this paper, we consider a simplified model with no communication cost, and we provide an exhaustive list of complexity results for different problem instances. Pipeline or fork stages can be replicated in order to increase the throughput of the workflow, by sending consecutive data sets onto different processors. In some cases, stages can also be data-parallelized, i.e. the computation of one single data set is shared between several processors. This leads to a decrease of the latency and an increase of the throughput. Some instances of this simple model are shown to be NP-hard, thereby exposing the inherent complexity of the mapping problem. We provide polynomial algorithms for other problem instances. Altogether, we provide solid theoretical foundations for the study of mono-criterion or bi-criteria mapping optimization problems.
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger
Contributeur : Anne Benoit <>
Soumis le : jeudi 27 septembre 2007 - 17:48:52
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 18:09:21


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00175066, version 2



Anne Benoit, Yves Robert. Complexity results for throughput and latency optimization of replicated and data-parallel workflows. [Research Report] RR-6308, INRIA. 2007, pp.33. 〈inria-00175066v2〉



Consultations de la notice


Téléchargements de fichiers