Online Allocation of Splitable Clients to Multiple Servers on Large Scale Heterogeneous PlatformsReportar como inadecuado




Online Allocation of Splitable Clients to Multiple Servers on Large Scale Heterogeneous Platforms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique 2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms INRIA Futurs, École Nationale Supérieure d-Électronique, Informatique et Radiocommunications de Bordeaux ENSEIRB, CNRS - Centre National de la Recherche Scientifique : UMR5800 3 INRIA Futurs 4 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d-Électronique, Informatique et Radiocommunications de Bordeaux ENSEIRB, CNRS - Centre National de la Recherche Scientifique : UMR5800

Résumé : Dans cet article, nous considérons l-allocation dynamique online d-un très grand nombre de tâches identiques et indépendantes sur une plate-forme maîtres-esclaves. Initialement, plusieurs nœuds maîtres possèdent ou génèrent les tâches qui sont ensuite transférées et traitées par des nœuds esclaves. L-objectif est de maximiser le débit i.e., le nombre fractionnaire de tâches qui peut être traité en une unité de temps, en régime permanent, par la plate-forme. Nous considérons que les communications se déroulent suivant le modèle multi-port à degré borné, dans lequel plusieurs communications peuvent avoir lieu simultanément sous réserve qu-aucune bande passante ne soit dépassée et qu-aucun serveur n-ouvre simultanément un nombre de connections supérieur à son degré maximal. Sous ce modèle, la maximisation du débit correspond au problème Maximum-Througput- Bounded-Degree MTBD qui a été analysé dans~\cite{beaumont08}. Il a été montré que le problème est NP-Complet au sens fort mais qu-une augmentation de ressources minimale de 1 sur le degré maximal des serveurs permet de le résoudre en temps polynomial. Dans cet article, nous considérons une extension de MTBD à la situation plus réaliste, dans le contexte des plates-formes de calcul à grande échelle, dans laquelle les nœuds esclaves rejoignent et quittent dynamiquement la plate-forme à des instants arbitraires problème online MTBD. Nous montrons tout d-abord qu-aucun algorithme complètement à la volée c.-à.-d. qui n-autorise pas les déconnections ne peut conduire à un facteur d-approximation constant, quelle que soit l-augmentation de ressources utilisée. Ensuite, nous montrons qu-il est en fait possible de maintenir à tout instant la solution optimale avec une augmentation de ressource additive de 1 en ne réalisant à chaque modification de la plate-forme qu-une déconnection et qu-une nouvelle connection par maître.





Autor: Olivier Beaumont - Lionel Eyraud-Dubois - Hejer Rejeb - Christopher Thraves -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados