Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Mapping filter services on heterogeneous platforms

Abstract : 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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 4:06:50 PM
Last modification on : Wednesday, October 26, 2022 - 8:15:02 AM


Files produced by the author(s)


  • 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⟩



Record views


Files downloads