Mapping filter services on heterogeneous platforms

Anne Benoit (1) , Fanny Dufossé (1) , Yves Robert (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Mots clés: Period; Mapping; Latency; Scheduling; Complexity results; Filters; Heuristics; Web services

Domaines: Informatique [cs]

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⟩