Mapping Filtering Streaming Applications with Communication Costs

Abstract : In this paper, we explore the problem of mapping filtering streaming applications on large-scale homogeneous platforms, with a particular emphasis on communication models and their impact. Filtering application are streaming applications where each node also has a selectivity which either increases or decreases the size of its input data set. This selectivity makes the problem of scheduling these applications more challenging than the more studied problem of scheduling "non-filtering" streaming workflows. We identify three significant realistic communication models. For each of them, we address the complexity of the following important problems: Given an execution graph, how can one compute the period and latency? A solution to this problem is an operation list which provides the time-steps at which each computation and each communication occurs in the system. Given a filtering workflow problem, how can one compute the schedule that minimizes the period or latency? A solution to this problem requires generating both the execution graph and the associated operation list. Altogether, with three models, two problems and two objectives, we present 12 complexity results, thereby providing solid theoretical foundations for the study of filtering streaming applications.
Type de document :
Communication dans un congrès
Proceedings of the Twenty-first Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), 2009, New York, NY, United States. ACM, pp.19--28, 2009, 〈10.1145/1583991.1583997〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01062574
Contributeur : Equipe Roma <>
Soumis le : mercredi 10 septembre 2014 - 09:56:04
Dernière modification le : vendredi 20 avril 2018 - 15:44:27

Lien texte intégral

Identifiants

Collections

Citation

Kunal Agrawal, Anne Benoit, Fanny Dufossé, Yves Robert. Mapping Filtering Streaming Applications with Communication Costs. Proceedings of the Twenty-first Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), 2009, New York, NY, United States. ACM, pp.19--28, 2009, 〈10.1145/1583991.1583997〉. 〈hal-01062574〉

Partager

Métriques

Consultations de la notice

229