Resource Allocation for Multiple Concurrent In-Network Stream-Processing Applications
| العنوان: | Resource Allocation for Multiple Concurrent In-Network Stream-Processing Applications |
|---|---|
| المؤلفون: | Henri Casanova, Veronika Rehn-Sonigo, Anne Benoit, Yves Robert |
| المساهمون: | Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), University of Hawai‘i [Mānoa] (UHM), INRIA, Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Information and Computer Sciences [Hawaii] (ICS), Sonigo, Veronika |
| المصدر: | Lecture Notes in Computer Science ISBN: 9783642141218 Euro-Par Workshops [Research Report] RR-6864, INRIA. 2009 Seventh International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms Seventh International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms, Aug 2009, Delft, Netherlands |
| بيانات النشر: | arXiv, 2009. |
| سنة النشر: | 2009 |
| مصطلحات موضوعية: | FOS: Computer and information sciences, Theoretical computer science, Computer Networks and Communications, Computer science, Computation, Distributed computing, 02 engineering and technology, Theoretical Computer Science, Stream processing, polynomial heuristics, Operator (computer programming), Artificial Intelligence, Server, 020204 information systems, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, Resource allocation (computer), operator mapping, in-network stream-processing, 020203 distributed computing, Heuristic, Computer Graphics and Computer-Aided Design, Tree (data structure), trees of operators, Computer Science - Distributed, Parallel, and Cluster Computing, Hardware and Architecture, multiple concurrent applications, Resource allocation, 020201 artificial intelligence & image processing, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, Software, Integer (computer science) |
| الوصف: | This work investigates the operator mapping problem for in-network stream-processing. In a stream-processing application, a tree of operators is applied, in steady-state mode, to datasets that are continuously updated at different locations in the network. The goal is to generate updated final results at a desired rate. In in-network stream-processing, dataset updates and operator computations are performed by servers distributed in a network. We consider the problem of mapping operators to these servers in the case of multiple concurrent stream-processing applications. In this case, different operator trees corresponding to different applications may share common subtrees, so that intermediate results can be reused by different applications. This work provides complexity results for different versions of the operator mapping problem, which can be formulated as integer linear programs. Several polynomial-time heuristics are proposed for a particularly relevant version of the problem, which is NP-hard. These heuristics are compared and evaluated via simulation. The results demonstrate the importance of mapping the operators to appropriate processors, and the importance of sharing common sub-trees across operator trees. |
| وصف الملف: | application/pdf |
| ردمك: | 978-3-642-14121-8 |
| DOI: | 10.48550/arxiv.0903.0710 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::30978986ab7585d4d9c003b0d924e540 |
| Rights: | OPEN |
| رقم الانضمام: | edsair.doi.dedup.....30978986ab7585d4d9c003b0d924e540 |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783642141218 |
|---|---|
| DOI: | 10.48550/arxiv.0903.0710 |