Afficher la notice abrégée

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorBEAUMONT, Olivier
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorBONICHON, Nicolas
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorDUCHON, Philippe
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorLARCHEVÊQUE, Hubert
dc.contributor.editorIEEE
dc.date.accessioned2024-04-15T09:47:32Z
dc.date.available2024-04-15T09:47:32Z
dc.date.issued2011
dc.date.conference2011-05
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198104
dc.description.abstractDans cet article nous nous intéressons aux plateformes de grande échelle comme BOINC, qui consistent en un ensemble de ressources hétérogènes qui utilisent Internet comme réseau de communications. Dans ce contexte, nous étudions un problème d'agrégation de ressources dans lequel l'objectif est de construire des groupes de noeuds de telle sorte que chaque groupe ait une capacité totale supérieure à une certaine valeur, et tels qu'au sein d'un même groupe, deux noeuds ne soient pas trop éloignés l'un de l'autre. Dans ce contexte, la distance entre deux participants correspond à la latence d'une communication entre eux. Notre objectif est de fournir des algorithmes assurant des facteurs d'approximations prouvés. Dans de telles plateformes, il n'est pas réaliste de supposer connaître l'intégralité de la matrice des latences (qui donne, pour chaque paire de noeud, la latence les séparant). Il est nécessaire d'avoir recours à des outils de plongements comme Vivaldi ou Sequoia. Ces outils permettent de travailler sur des espaces métriques spécifiques bien décrits, dans lesquels la distance entre deux points peut être obtenue directement à partir d'une petite quantité d'informations disponible à chaque noeud. Nous présentons le problème de Bin Covering avec Contrainte de Distance (BCCD), et proposons pour ce problème des algorithmes dédiés à chacun des espaces métriques induits par chacun des outils de plongement que nous étudions. Ensuite nous proposons une comparaison de ces algorithmes en nous appuyant sur des mesures de latences réelles, qui nous permet de décider quel couple algorithme/outil de plongement offre en pratique, sur des jeux de données réalistes, le meilleur équilibre entre prédictions de distance et facteur d'approximation pour ce problème d'agrégation de ressources.
dc.description.abstractEnIn this paper we are interested in large scale distributed platforms like BOINC, consisting of heterogeneous resources and using Internet as underlying communication network. In this context, we study a resource clustering problem, where the goal is to build clusters having at least a given capacity and such that any two participants to the same cluster are not too far from each other. In this context, the distance between two participants corresponds to the latency of a communication between them. Our goal is to provide algorithms with provable approximation ratios. In such large scale networks, it is not realistic to assume that the whole latency matrix (that gives the latency between any two participants) is known, and we need to rely on embedding tools such as Vivaldi or Sequoia. These tools enable to work on compact descriptions and well described metric spaces in which the distance between two points can be obtained directly from a small amount of information available at each node.We present the Bin Covering under Distance Constraint problem (BCDC for short), and propose dedicated algorithms for this problem for each metric space induced by each of the embedding tools. Then, we propose a comparison of these algorithms based on actual latency measures, that enables to decide which algorithm/embedding tool pair offers in practice for realistic datasets the best balancing between distance prediction and approximation ratios for the resource clustering problem.
dc.description.sponsorshipSimulation extrêmement extensible avec SimGrid - ANR-08-SEGI-0022
dc.language.isoen
dc.title.enUse of Internet Embedding Tools for Heterogeneous Resources Aggregation
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page114-124
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleHeterogeneity in Computing Workshop (HCW) - in IPDPS 2011
bordeaux.countryUS
bordeaux.conference.cityAnchorage
bordeaux.peerReviewedoui
hal.identifierinria-00588650
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00588650v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2011&rft.spage=114-124&rft.epage=114-124&rft.au=BEAUMONT,%20Olivier&BONICHON,%20Nicolas&DUCHON,%20Philippe&LARCHEV%C3%8AQUE,%20Hubert&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée