Mapping filter services on heterogeneous platforms - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2008

Mapping filter services on heterogeneous platforms


In this paper, we explore the problem of mapping filtering web 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, measuresthe rate at which data sets can enter the system. The latency measures the responsetime of the system in order to process one single data set entirely. Both criteria areantagonistic. For homogeneous platforms, the complexity of period minimization isalready known [14]; we derive an algorithm to solve the latency minimization problem,and we provide a bi-criteria algorithm which minimizes latency without exceeding aprescribed value for the period. However, when adding heterogeneity to the platform,we prove that minimizing the period or the latency becomes NP-hard. We provide aninteger linear program to solve both problems in the heterogeneous case.For period minimization on heterogeneous platforms, we design some efficient polynomial time heuristics and we assess their relative and absolute performance througha set of experiments. For small problem instances, the results are very close to theoptimal solution returned by the integer linear program.
Fichier principal
Vignette du fichier
LIP-RR_08-19.pdf (342.07 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02102771 , version 1 (17-04-2019)


  • HAL Id : hal-02102771 , version 1


Anne Benoit, Fanny Dufossé, Yves Robert. Mapping filter services on heterogeneous platforms. [Research Report] LIP RR-2008-19, Laboratoire de l'informatique du parallélisme. 2008, 26p. ⟨hal-02102771⟩
31 Consultations
66 Téléchargements


Gmail Mastodon Facebook X LinkedIn More