أعرض في EDS

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
ResultId 1
Header edsair
OpenAIRE
edsair.doi.dedup.....30978986ab7585d4d9c003b0d924e540
767
3

unknown
766.994323730469
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsair&AN=edsair.doi.dedup.....30978986ab7585d4d9c003b0d924e540&custid=s6537998&authtype=sso
FullText Array ( [Availability] => 0 )
Array ( [0] => Array ( [Url] => https://explore.openaire.eu/search/publication?articleId=doi_dedup___::30978986ab7585d4d9c003b0d924e540# [Name] => EDS - OpenAIRE [Category] => fullText [Text] => View record in OpenAIRE [MouseOverText] => View record in OpenAIRE ) )
Items Array ( [Name] => Title [Label] => Title [Group] => Ti [Data] => Resource Allocation for Multiple Concurrent In-Network Stream-Processing Applications )
Array ( [Name] => Author [Label] => Authors [Group] => Au [Data] => <searchLink fieldCode="AR" term="%22Henri+Casanova%22">Henri Casanova</searchLink><br /><searchLink fieldCode="AR" term="%22Veronika+Rehn-Sonigo%22">Veronika Rehn-Sonigo</searchLink><br /><searchLink fieldCode="AR" term="%22Anne+Benoit%22">Anne Benoit</searchLink><br /><searchLink fieldCode="AR" term="%22Yves+Robert%22">Yves Robert</searchLink> )
Array ( [Name] => Author [Label] => Contributors [Group] => Au [Data] => Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL)<br />Inria Grenoble - Rhône-Alpes<br />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)<br />École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)<br />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)<br />Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)<br />University of Hawai‘i [Mānoa] (UHM)<br />INRIA<br />Laboratoire de l'Informatique du Parallélisme (LIP)<br />Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)<br />École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)<br />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)<br />Information and Computer Sciences [Hawaii] (ICS)<br />Sonigo, Veronika )
Array ( [Name] => TitleSource [Label] => Source [Group] => Src [Data] => Lecture Notes in Computer Science ISBN: 9783642141218<br />Euro-Par Workshops<br />[Research Report] RR-6864, INRIA. 2009<br />Seventh International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms<br />Seventh International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms, Aug 2009, Delft, Netherlands )
Array ( [Name] => Publisher [Label] => Publisher Information [Group] => PubInfo [Data] => arXiv, 2009. )
Array ( [Name] => DatePubCY [Label] => Publication Year [Group] => Date [Data] => 2009 )
Array ( [Name] => Subject [Label] => Subject Terms [Group] => Su [Data] => <searchLink fieldCode="DE" term="%22FOS%3A+Computer+and+information+sciences%22">FOS: Computer and information sciences</searchLink><br /><searchLink fieldCode="DE" term="%22Theoretical+computer+science%22">Theoretical computer science</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Networks+and+Communications%22">Computer Networks and Communications</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+science%22">Computer science</searchLink><br /><searchLink fieldCode="DE" term="%22Computation%22">Computation</searchLink><br /><searchLink fieldCode="DE" term="%22Distributed+computing%22">Distributed computing</searchLink><br /><searchLink fieldCode="DE" term="%2202+engineering+and+technology%22">02 engineering and technology</searchLink><br /><searchLink fieldCode="DE" term="%22Theoretical+Computer+Science%22">Theoretical Computer Science</searchLink><br /><searchLink fieldCode="DE" term="%22Stream+processing%22">Stream processing</searchLink><br /><searchLink fieldCode="DE" term="%22polynomial+heuristics%22">polynomial heuristics</searchLink><br /><searchLink fieldCode="DE" term="%22Operator+%28computer+programming%29%22">Operator (computer programming)</searchLink><br /><searchLink fieldCode="DE" term="%22Artificial+Intelligence%22">Artificial Intelligence</searchLink><br /><searchLink fieldCode="DE" term="%22Server%22">Server</searchLink><br /><searchLink fieldCode="DE" term="%22020204+information+systems%22">020204 information systems</searchLink><br /><searchLink fieldCode="DE" term="%22[INFO%2EINFO-DC]+Computer+Science+[cs]%2FDistributed%2C+Parallel%2C+and+Cluster+Computing+[cs%2EDC]%22">[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]</searchLink><br /><searchLink fieldCode="DE" term="%220202+electrical+engineering%2C+electronic+engineering%2C+information+engineering%22">0202 electrical engineering, electronic engineering, information engineering</searchLink><br /><searchLink fieldCode="DE" term="%22Resource+allocation+%28computer%29%22">Resource allocation (computer)</searchLink><br /><searchLink fieldCode="DE" term="%22operator+mapping%22">operator mapping</searchLink><br /><searchLink fieldCode="DE" term="%22in-network+stream-processing%22">in-network stream-processing</searchLink><br /><searchLink fieldCode="DE" term="%22020203+distributed+computing%22">020203 distributed computing</searchLink><br /><searchLink fieldCode="DE" term="%22Heuristic%22">Heuristic</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Graphics+and+Computer-Aided+Design%22">Computer Graphics and Computer-Aided Design</searchLink><br /><searchLink fieldCode="DE" term="%22Tree+%28data+structure%29%22">Tree (data structure)</searchLink><br /><searchLink fieldCode="DE" term="%22trees+of+operators%22">trees of operators</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Distributed%2C+Parallel%2C+and+Cluster+Computing%22">Computer Science - Distributed, Parallel, and Cluster Computing</searchLink><br /><searchLink fieldCode="DE" term="%22Hardware+and+Architecture%22">Hardware and Architecture</searchLink><br /><searchLink fieldCode="DE" term="%22multiple+concurrent+applications%22">multiple concurrent applications</searchLink><br /><searchLink fieldCode="DE" term="%22Resource+allocation%22">Resource allocation</searchLink><br /><searchLink fieldCode="DE" term="%22020201+artificial+intelligence+%26+image+processing%22">020201 artificial intelligence & image processing</searchLink><br /><searchLink fieldCode="DE" term="%22Distributed%2C+Parallel%2C+and+Cluster+Computing+%28cs%2EDC%29%22">Distributed, Parallel, and Cluster Computing (cs.DC)</searchLink><br /><searchLink fieldCode="DE" term="%22[INFO%2EINFO-DC]Computer+Science+[cs]%2FDistributed%2C+Parallel%2C+and+Cluster+Computing+[cs%2EDC]%22">[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]</searchLink><br /><searchLink fieldCode="DE" term="%22Heuristics%22">Heuristics</searchLink><br /><searchLink fieldCode="DE" term="%22Software%22">Software</searchLink><br /><searchLink fieldCode="DE" term="%22Integer+%28computer+science%29%22">Integer (computer science)</searchLink> )
Array ( [Name] => Abstract [Label] => Description [Group] => Ab [Data] => 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. )
Array ( [Name] => Format [Label] => File Description [Group] => SrcInfo [Data] => application/pdf )
Array ( [Name] => ISBN [Label] => ISBN [Group] => ISBN [Data] => 978-3-642-14121-8 )
Array ( [Name] => DOI [Label] => DOI [Group] => ID [Data] => 10.48550/arxiv.0903.0710 )
Array ( [Name] => URL [Label] => Access URL [Group] => URL [Data] => <link linkTarget="URL" linkTerm="https://explore.openaire.eu/search/publication?articleId=doi_dedup___::30978986ab7585d4d9c003b0d924e540" linkWindow="_blank">https://explore.openaire.eu/search/publication?articleId=doi_dedup___::30978986ab7585d4d9c003b0d924e540</link> )
Array ( [Name] => Copyright [Label] => Rights [Group] => Cpyrght [Data] => OPEN )
Array ( [Name] => AN [Label] => Accession Number [Group] => ID [Data] => edsair.doi.dedup.....30978986ab7585d4d9c003b0d924e540 )
RecordInfo Array ( [BibEntity] => Array ( [Identifiers] => Array ( [0] => Array ( [Type] => doi [Value] => 10.48550/arxiv.0903.0710 ) ) [Languages] => Array ( [0] => Array ( [Text] => Undetermined ) ) [Subjects] => Array ( [0] => Array ( [SubjectFull] => FOS: Computer and information sciences [Type] => general ) [1] => Array ( [SubjectFull] => Theoretical computer science [Type] => general ) [2] => Array ( [SubjectFull] => Computer Networks and Communications [Type] => general ) [3] => Array ( [SubjectFull] => Computer science [Type] => general ) [4] => Array ( [SubjectFull] => Computation [Type] => general ) [5] => Array ( [SubjectFull] => Distributed computing [Type] => general ) [6] => Array ( [SubjectFull] => 02 engineering and technology [Type] => general ) [7] => Array ( [SubjectFull] => Theoretical Computer Science [Type] => general ) [8] => Array ( [SubjectFull] => Stream processing [Type] => general ) [9] => Array ( [SubjectFull] => polynomial heuristics [Type] => general ) [10] => Array ( [SubjectFull] => Operator (computer programming) [Type] => general ) [11] => Array ( [SubjectFull] => Artificial Intelligence [Type] => general ) [12] => Array ( [SubjectFull] => Server [Type] => general ) [13] => Array ( [SubjectFull] => 020204 information systems [Type] => general ) [14] => Array ( [SubjectFull] => [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] [Type] => general ) [15] => Array ( [SubjectFull] => 0202 electrical engineering, electronic engineering, information engineering [Type] => general ) [16] => Array ( [SubjectFull] => Resource allocation (computer) [Type] => general ) [17] => Array ( [SubjectFull] => operator mapping [Type] => general ) [18] => Array ( [SubjectFull] => in-network stream-processing [Type] => general ) [19] => Array ( [SubjectFull] => 020203 distributed computing [Type] => general ) [20] => Array ( [SubjectFull] => Heuristic [Type] => general ) [21] => Array ( [SubjectFull] => Computer Graphics and Computer-Aided Design [Type] => general ) [22] => Array ( [SubjectFull] => Tree (data structure) [Type] => general ) [23] => Array ( [SubjectFull] => trees of operators [Type] => general ) [24] => Array ( [SubjectFull] => Computer Science - Distributed, Parallel, and Cluster Computing [Type] => general ) [25] => Array ( [SubjectFull] => Hardware and Architecture [Type] => general ) [26] => Array ( [SubjectFull] => multiple concurrent applications [Type] => general ) [27] => Array ( [SubjectFull] => Resource allocation [Type] => general ) [28] => Array ( [SubjectFull] => 020201 artificial intelligence & image processing [Type] => general ) [29] => Array ( [SubjectFull] => Distributed, Parallel, and Cluster Computing (cs.DC) [Type] => general ) [30] => Array ( [SubjectFull] => [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] [Type] => general ) [31] => Array ( [SubjectFull] => Heuristics [Type] => general ) [32] => Array ( [SubjectFull] => Software [Type] => general ) [33] => Array ( [SubjectFull] => Integer (computer science) [Type] => general ) ) [Titles] => Array ( [0] => Array ( [TitleFull] => Resource Allocation for Multiple Concurrent In-Network Stream-Processing Applications [Type] => main ) ) ) [BibRelationships] => Array ( [HasContributorRelationships] => Array ( [0] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => Henri Casanova ) ) ) [1] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => Veronika Rehn-Sonigo ) ) ) [2] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => Anne Benoit ) ) ) [3] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => Yves Robert ) ) ) [4] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL) ) ) ) [5] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => Inria Grenoble - Rhône-Alpes ) ) ) [6] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => 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) ) ) ) [7] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL) ) ) ) [8] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => 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) ) ) ) [9] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS) ) ) ) [10] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => University of Hawai‘i [Mānoa] (UHM) ) ) ) [11] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => INRIA ) ) ) [12] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => Laboratoire de l'Informatique du Parallélisme (LIP) ) ) ) [13] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS) ) ) ) [14] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL) ) ) ) [15] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => 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) ) ) ) [16] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => Information and Computer Sciences [Hawaii] (ICS) ) ) ) [17] => Array ( [PersonEntity] => Array ( [Name] => Array ( [NameFull] => Sonigo, Veronika ) ) ) ) [IsPartOfRelationships] => Array ( [0] => Array ( [BibEntity] => Array ( [Dates] => Array ( [0] => Array ( [D] => 01 [M] => 01 [Type] => published [Y] => 2009 ) ) [Identifiers] => Array ( [0] => Array ( [Type] => isbn-print [Value] => 9783642141218 ) [1] => Array ( [Type] => issn-locals [Value] => edsair ) [2] => Array ( [Type] => issn-locals [Value] => edsairFT ) ) ) ) ) ) )
IllustrationInfo