Computing the throughput of replicated workflows on heterogeneous platforms

Matthieu Gallet 1, 2 Anne Benoit 1, 2 Yves Robert 1, 2 Bruno Gaujal 2, 3
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : In this paper, we focus on computing the throughput of replicated workflows. Given a streaming application whose dependence graph is a linear chain, and a mapping of this application onto a fully heterogeneous platform, how can we compute the optimal throughput, or equivalently the minimal period? The problem is easy when workflow stages are not replicated, i.e., assigned to a single processor: in that case the period is dictated by the critical hardware resource. But when stages are replicated, i.e., assigned to several processors, the problem gets surprisingly complicated, and we provide examples where the optimal period is larger than the largest cycle-time of any resource. We then show how to model the problem as a timed Petri net to compute the optimal period in the general case, and we provide a polynomial algorithm for the one-port communication model with overlap. Finally, we report comprehensive simulation results on the gap between the optimal period and the largest resource cycle-time.
Type de document :
Pré-publication, Document de travail
RR-2009-08. 20 pages. 2009
Liste complète des métadonnées

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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00365522
Contributeur : Matthieu Gallet <>
Soumis le : mardi 3 mars 2009 - 16:20:46
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : vendredi 12 octobre 2012 - 12:45:31

Fichier

RR-2009-08.lip.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00365522, version 1

Collections

Citation

Matthieu Gallet, Anne Benoit, Yves Robert, Bruno Gaujal. Computing the throughput of replicated workflows on heterogeneous platforms. RR-2009-08. 20 pages. 2009. 〈ensl-00365522〉

Partager

Métriques

Consultations de la notice

501

Téléchargements de fichiers

181