Computing the throughput of probabilistic and replicated streaming applications

Anne Benoit 1 Fanny Dufossé 2 Matthieu Gallet 1, 2 Bruno Gaujal 2, 3 Yves Robert 1
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 investigate how to compute the throughput of probabilistic and replicated streaming applications. We are given (i) a streaming application whose dependence graph is a linear chain; (ii) a one- to-many mapping of the application onto a fully heterogeneous target, where a processor is assigned at most one application stage, but where a stage can be replicated onto a set of processors; and (iii) a set of I.I.D. (Indepen- dent and Identically-Distributed) variables to model each computation and communication time in the mapping. How can we compute the throughput of the application, i.e., the rate at which data sets can be processed? We consider two execution models, the Strict model where the actions of each processor are sequentialized, and the Overlap model where a processor can compute and communicate in par- allel. The problem is easy when application stages are not replicated, i.e., assigned to a single processor: in that case the throughput is dictated by the critical hardware resource. However, when stages are replicated, i.e., as- signed to several processors, the problem becomes surprisingly complicated: even in the deterministic case, the optimal throughput may be lower than the smallest internal resource throughput. To the best of our knowledge, the problem has never been considered in the probabilistic case.
Type de document :
[Research Report] RR-7182, INRIA. 2010, pp.34
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Matthieu Gallet <>
Soumis le : mardi 2 février 2010 - 13:29:22
Dernière modification le : jeudi 8 novembre 2018 - 14:26:10
Document(s) archivé(s) le : jeudi 18 octobre 2012 - 14:06:32


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


  • HAL Id : inria-00452424, version 1



Anne Benoit, Fanny Dufossé, Matthieu Gallet, Bruno Gaujal, Yves Robert. Computing the throughput of probabilistic and replicated streaming applications. [Research Report] RR-7182, INRIA. 2010, pp.34. 〈inria-00452424〉



Consultations de la notice


Téléchargements de fichiers