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
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102771
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 4:06:50 PM
Last modification on : Friday, April 19, 2019 - 1:38:15 AM

File

LIP-RR_08-19.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102771, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

8

Files downloads

12