On the complexity of mapping pipelined filtering services on heterogeneous platforms

Abstract : In this paper, we explore the problem of mapping filtering services on large-scale heterogeneous platforms. Two important optimization criteria should be considered in such a framework. The period, which is the inverse of the throughput, measures the rate at which data sets can enter the system. The latency measures the response time of the system in order to process one single data set entirely. Both criteria are antagonistic. For homogeneous platforms, the complexity of period minimization is already known [12]; we derive an algorithm to solve the latency minimization problem in the general case with service precedence constraints; we also show that the bi-criteria problem (latency minimization without exceeding a prescribed value for the period) is of polynomial complexity. However, when adding heterogeneity to the platform, we prove that minimizing the period or the latency becomes NP-complete, and that these problems cannot be approximated by any constant factor (unless P=NP). The latter results hold true even for services without precedence constraints.
Type de document :
Communication dans un congrès
IPDPS - IEEE International Parallel and Distributed Processing Symposium - 2009, May 2009, Roma, Italy. pp.1-12, 2009, 〈10.1109/IPDPS.2009.5161026〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00787973
Contributeur : Equipe Roma <>
Soumis le : mercredi 13 février 2013 - 14:30:50
Dernière modification le : vendredi 20 avril 2018 - 15:44:24

Lien texte intégral

Identifiants

Collections

Citation

Anne Benoit, Fanny Dufossé, Yves Robert. On the complexity of mapping pipelined filtering services on heterogeneous platforms. IPDPS - IEEE International Parallel and Distributed Processing Symposium - 2009, May 2009, Roma, Italy. pp.1-12, 2009, 〈10.1109/IPDPS.2009.5161026〉. 〈hal-00787973〉

Partager

Métriques

Consultations de la notice

166