On the Complexity of Mapping Pipelined Filtering Services on Heterogeneous Platforms - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 2008

On the Complexity of Mapping Pipelined Filtering Services on Heterogeneous Platforms

Résumé

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 [1]; we derive an algorithm to solve the latency minimization problem in the general case with service precedence constraints; for independent services 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-hard, and that these problems cannot be approximated by any constant factor (unless P=NP). The latter results hold true even for independent services. We provide an integer linear program to solve both problems in the heterogeneous case with independent services. For period minimization on heterogeneous platforms, we design some efficient polynomial time heuristics and we assess their relative and absolute performance through a set of experiments. For small problem instances, the results are very close to the optimal solution returned by the integer linear program.
Fichier principal
Vignette du fichier
LIP-RR_2008-30.pdf (322.82 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02127143 , version 1 (13-05-2019)

Identifiants

  • HAL Id : hal-02127143 , version 1

Citer

Anne Benoit, Fanny Dufossé, Yves Robert. On the Complexity of Mapping Pipelined Filtering Services on Heterogeneous Platforms. [Research Report] LIP RR 2008-30, LIP - Laboratoire de l’Informatique du Parallélisme. 2008. ⟨hal-02127143⟩
65 Consultations
125 Téléchargements

Partager

More