DYNAMIC LOAD BALANCING FOR ACTIVE OBJECTS ON COMPUTER GRIDS

of 32
8 views
PDF
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
DYNAMIC LOAD BALANCING FOR ACTIVE OBJECTS ON COMPUTER GRIDS Javier Bustos-Jiménez To cite this version: Javier Bustos-Jiménez. DYNAMIC LOAD BALANCING FOR ACTIVE OBJECTS ON COM- PUTER GRIDS. Networking
Document Share
Document Transcript
DYNAMIC LOAD BALANCING FOR ACTIVE OBJECTS ON COMPUTER GRIDS Javier Bustos-Jiménez To cite this version: Javier Bustos-Jiménez. DYNAMIC LOAD BALANCING FOR ACTIVE OBJECTS ON COM- PUTER GRIDS. Networking and Internet Architecture [cs.ni]. Université Nice Sophia Antipolis, English. tel HAL Id: tel https://tel.archives-ouvertes.fr/tel Submitted on 20 Jul 2007 HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. UNIVERSITÉ DE NICE-SOPHIA ANTIPOLIS - UFR Sciences École Doctorale de Sciences et Technologies de l Information et de la Communication THÈSE pour obtenir le titre de Docteur en Sciences de l UNIVERSITE de Nice-Sophia Antipolis Discipline : Informatique présentée et soutenue par Javier BUSTOS-JIMÉNEZ DYNAMIC LOAD BALANCING FOR ACTIVE OBJECTS ON COMPUTER GRIDS Thèse dirigée par Denis CAROMEL et préparée à l INRIA Sophia Antipolis, projet OASIS soutenue le 18 décembre 2006 Jury: Président du Jury Mauricio MARÍN Universidad de Magallanes, Chile Rapporteurs Pierre COINTE École des Mines de Nantes, France Gonzalo NAVARRO Universidad de Chile, Chili Examinateurs Denis CAROMEL Université de Nice Sophia-Antipolis, France Eric MADELAINE INRIA Sophia-Antipolis, France José PIQUER Universidad de Chile, Chili UNIVERSITÉ DE NICE-SOPHIA ANTIPOLIS - UFR Sciences École Doctorale de Sciences et Technologies de l Information et de la Communication THÈSE pour obtenir le titre de Docteur en Sciences de l UNIVERSITE de Nice-Sophia Antipolis Discipline : Informatique présentée et soutenue par Javier BUSTOS-JIMÉNEZ ÉQUILIBRAGE DE CHARGE DYNAMIQUE POUR DES OBJETS ACTIFS DANS LES GRILLES DE CALCUL Thèse dirigée par Denis CAROMEL et préparée à l INRIA Sophia Antipolis, projet OASIS soutenue le 18 décembre 2006 Jury: Président du Jury Mauricio MARÍN Universidad de Magallanes, Chile Rapporteurs Pierre COINTE École des Mines de Nantes, France Gonzalo NAVARRO Universidad de Chile, Chili Examinateurs Denis CAROMEL Université de Nice Sophia-Antipolis, France Eric MADELAINE INRIA Sophia-Antipolis, France José PIQUER Universidad de Chile, Chili to Cristina... and Amelia Contents List of Figures Acknowledgements ix xiii I Résumé étendu en français (Extended french abstract) xv Équilibrage de Charge pour des Objets Actifs dans les Grilles de Calcul xvii 1 Introduction et objectifs xvii 2 État de l art xix 2.1 Les objets actifs et ProActive xix 2.2 Les algorithmes d équilibrage de charge xxi 2.3 Les réseaux à grande échelle xxiii 3 Algorithmes proposés xxvii 4 Modélisation xxviii 4.1 Modélisation d une grille de bureau xxviii 4.2 Modélisation d une grille de projet xxxii 5 Conclusions et travaux futurs xxxvii II Thesis 1 1 Introduction 3 2 Active Objects Active Objects Reflection Reflective Architecture ProActive Distribution model Active Objects implementation for ProActive Message Passing for Actives Objects in ProActive Synchronisation: Wait-by-necessity ProActive: Environment and implementation ProActive Meta-Object Protocol v vi CONTENTS 3 Networks for parallelism History of parallel computing Cluster of computers Computer Grids A model overview for Project Grids Peer-to-Peer Infrastructure of ProActive Bootstrapping: First Contact Discovering and Self-Organising Theory of Networks Generating random graphs Natural Networks State of the Art on Load-Balancing Static Load-Balancing Dynamic Load-Balancing Components of a Load-Balancing Algorithm Load Index Information-Sharing Policy Transfer Policy Location Policy Related Work Condor Legion Cilk Satin Setting foundations for Load-Balancing of Active-Objects Active-Objects and Processing Idleness Location policy for load-balancing of active-objects Information and transfer policies for load-balancing of active-objects Modelling ProActive behaviour to test algorithm policies Implementing the Information-Sharing Policies Hardware and Software Results Analysis Testing the impact of Information-Sharing Policies Exploiting the Peer-to-Peer infrastructure: Information on-demand Robin-Hood Load-Balancing Algorithm Robin-Hood over ProActive s Peer-to-Peer Infrastructure Robin-Hood and the Nottingham Sheriff Testing algorithms in a real environment Models, Simulations and Deployment on Large-Scale Networks Simulating Desktop Grids Characterising nodes of Desktop Grids Modelling Desktop Grids CONTENTS vii Finding the best processor Scaling towards the infinite network Simulating Project Grids Characterising a Project Grid Modelling a Project Grid Environment-aware Algorithms Experimental Setup Simulation Results Results Confidence Where to run parallel applications? Problematic of Applications and Descriptors Clauses in ProActive Descriptors Clauses in ProActive Applications Constraints The real world Conclusions and Future Work 93 A Matrices for Robin-Hood algorithm working alone 107 B Matrices for Robin-Hood + Nottingham-Sheriff algorithm 111 C Expected values for Kolmogorov-Smirnov test statistics 115 viii CONTENTS List of Figures i Exécution d un appel asynchrone et à distance d une méthode xx ii Migration and tensioning xx iii Grilles présentées xxvii iv Distribution des fréquences des Mflops des 200,000 processeurs enregistrés dans et la distribution normale qui fait la modélisation.. xxix v Passage à l échelle xxxi vi Migrations xxxii vii La latence des nœuds de la grille de projet PlugTests xxxiv viii Nombre total des services dans tous les objets actifs, avec synchronisation chaque 10 unités de temps xxxvi ix % de confiance des algorithmes selon le factor de migration M xxxvi 2.1 The reflection process, featuring levels of data, reification and reflection Parallelisation and distribution with active objects Execution of an asynchronous and remote method call Base-level and meta-level of an active object Migration and tensioning Grids divided by objective (a) step two of Watts and Strogatz model with n = 12 and k = 2; (b) step three with small p e A supermarket Examples of information-sharing policies Matchmaking process of Condor Parallel problems solved by Condor Main classes of Legion infrastructure Legion Resource Management Infrastructure Cilk model: each thread is a circle, grouped in procedures. Each downward arrow is a spawned child, and each horizontal arrow is a spawned successor. Dashed arrows represent data dependency (synchronisations). Also, spawn-levels from the original thread are presented ix x LIST OF FIGURES 5.1 Different behaviours for active-objects request (Q) and reply (P): (a) B starts in wait-for-request (WfR) and A made a wait-by-necessity (WfN). (b) Bad utilisation of the active-object pattern: asynchronous calls become almost synchronous. (c) C has a long waiting time because B delayed the answer The supermarket abstraction for load-balancing of enqueued tasks The supermarket abstraction for load-balancing of Active Objects Migration time from the point of view of latency and object size Mean response time for all policies Bandwidth usage of coordination policies during the information-sharing phase Bandwidth usage of coordination policies during all the load-balancing Impact of load-balancing algorithms over Jacobi calculus Frequency distribution of Mflops for 200, 000 processors registered at and the normal function which models it Final distribution for the Robin-Hood algorithm only, for RB = 0.5 and T = Final distribution for the Robin-Hood + Nottingham Sheriff Tuning for RS considering: a) number of active-objects in (9, 9) per total of active-objects; and b) Number of total migrations reaching a stable state Tuning for RS considering: a) number of active-objects in (9, 9) per total of active-objects; and b) Number of total migrations reaching a stable state. Because the results using 3 to 6 acquaintances were similar, only those for 3 are shown Tuning for RS considering: a) mean number of total migrations until each time-step; and b) mean number of overloaded nodes in each timestep. Using RB = 0.7, acquaintances subset size = 3, x y 3, λ = 0.1, 0.2, 0.3 and T = Tuning the value of RS considering: a) mean number of active objects on a node with µ 1 per total number of active objects; and b) mean number of active objects on a node with µ per total number of active 3 objects. Using RB = 0.7, acquaintances subset size = 3, x y 3, λ = 0.1, 0.2, 0.3 and T = Scalability for a network using RS = 0.9, 1.0, 1.1, RB = Scalability in terms of number of processors used, having RS = Scalability in terms of number of migrations, having RS = 1.0. The plot presents, for an active object, the (mean) number of accumulated migrations performed until a time-step t [0; 1, 000] Scalability, having the number of active objects proportional to the number of nodes Latency between nodes from the PlugTest project grid Total number of pending requests in all active-objects using message-size C = 0.1 and object size M = 1, without synchronisation LIST OF FIGURES xi 6.14 Total number of pending requests in all active-objects using message-size C = 1 and object size M = 10, without synchronisation Total number of pending requests in all active-objects using message-size C = 0.1 services, object size M = 1 services and synchronisation each 10 time-steps % of confidence of load-balancing algorithms, increasing object size (M) Example of clauses in descriptor Example of clauses in application Integer Constraint Schema Grammar Institutional clusters on Grid5000: Bordeaux, Grenoble, Lille, Lyon, Nancy, Orsay, Rennes, Sophia-Antipolis and Toulouse Speed of Jacobi parallel application in iterations per milliseconds Mean number of cumulated migrations that an active object performs during the experience A.1 Final distribution for the Robin-Hood algorithm only, for RB = 0.5 and q = A.2 Final distribution for the Robin-Hood algorithm only, for RB = 0.5 and q = A.3 Final distribution for the Robin-Hood algorithm only, for RB = 0.5 and q = A.4 Final distribution for the Robin-Hood algorithm only, for RB = 0.7 and q = B.1 Final distribution for the Robin-Hood + Nottingham Sheriff algorithm, for RB = 0.5, RS = 0.5 and q = B.2 Final distribution for the Robin-Hood + Nottingham Sheriff algorithm, for RB = 0.5, RS = 0.5 and q = B.3 Final distribution for the Robin-Hood + Nottingham Sheriff algorithm, for RB = 0.7, RS = 0.7 and q = B.4 Final distribution for the Robin-Hood + Nottingham Sheriff algorithm, for RB = 0.9, RS = 0.9 and q = xii LIST OF FIGURES Acknowledgements I would like to thank both the French Embassy at Chile and the Chilean Commission in Research and Technology (Conicyt) that granted me a scholarship that allowed me to pursue further education in France and Chile. I am specially thankful to my adviser José Piquer, who demonstrated an amazing dedication guiding me through my studies and who encouraged me to go to France. His support has been incommensurable. I am most grateful to INRIA, the Oasis team, and its former members. Thanks to Denis Caromel, my adviser in France, who accepted to support my thesis. Special thanks to Tomás Barros, Alfredo Illanes, Mauricio Araya, Gonzalo Robledo and Christian Delbé, who helped me with all the paperwork at the beginning of my French life, without their help I probable would had been deported. I would also like to thank all the people who shared their knowledge in useful discussions about my thesis work: Eric Tanter (Objects), Alexandre di Costanzo (ProActive s P2P infrastructure), Nelson Morales (Network Modelling), Angela Ganz (Poisson Processes), Satu Elisa Schaeffer (Natural Networks) and Luis Mateu (Synchronisation). I would like to thank to all people who helped me in non-academic ways during this PhD. First to my Chilean friends whom gave me their support asking me from time to time where are you now? (Geddy, Lemus, Benja, Iván, Fernando, Pato, Pancho, Humberto, Gastón, Teresa, Valeria and Vicky). Second to my French friends whom gave me their support asking me from time to time when you will back? (Arthur, Nico and all the Garibaldi F.C. team). Third to the tennis players (Fernando, Humberto, Luis, Tomás, Tamara, Ángela and Mario). Fourth to the beach-volley players (the Argentine team, specially Tamara and Jimena; Igor, Carlos, Marcela, etc.). Fifth to la vida del estudiante group (Marcelo, Ángela, Diego, Patricio and Elena). Sixth to the co-author by default (Mario). Seventh to my favourite proof-reader (Elisa). Finally, to three special places for me: Stade du Ray, La foyer (Valrose) and Pub van Gogh. It is also my privilege to thank all those who shared their friendship along these last four years. xiv ACKNOWLEDGEMENTS Part I Résumé étendu en français (Extended french abstract) xv Équilibrage de Charge pour des Objets Actifs dans les Grilles de Calcul 1 Introduction et objectifs Cette thèse prétend définir les bases du développement d algorithmes d équilibrage de charge pour le modèle des objets actifs de la librairie ProActive [97] dans le contexte des réseaux à grande échelle (grilles). Dans ProActive, chaque objet actif a son propre fil de commande et peut indépendamment décider dans quel ordre servir la méthode entrante appelé: les appels entrants sont automatiquement stockés dans une file d attente de service. Pour ajouter de l efficacité au paradigme des objets actifs, ProActive fournit une manière de déplacer un objet actif d une machine virtuelle de Java (JVM) à une autre JVM appelée migration [11]. Les références entre l extérieur et les objets actifs qui ont migré doivent demeurer valables après la migration. L opération de migration vient avec une pénalité de communication: un objet actif doit émigrer avec son état complet, ses demandes en suspens, futurs, et des objets passifs. Par conséquent, les applications fournies avec ProActive sont très sensibles à la latence. Lorsque plusieurs objets actifs sont déployés pour un logiciel parallèle, un algorithme d équilibrage de charge peut être employé pour améliorer le temps d exécution d une application en utilisant la migration [45, 47, 89, 104, 109]. La charge de travail en objets actifs peut être équilibrée en envoyant des objets actifs d un processeur fortement chargé à un autre moins chargé, ou en volant des objets actifs d un processeur fortement chargé pour un autre moins chargé. Pour le cas de la grille, l environnement d exécution des objets actifs se compose habituellement de multiples clusters de ressources, et avec ProActive, les objets actifs forment un réseau Pair-a-Pair [24]. Donc, nous algorithme d équilibrage de charge doit également considérer la topologie de ce réseau. Etant donnée l impossibilité d avoir accès à un réseau à grande échelle (plus de 1, 000 nœuds), et de réaliser tout l essai requis, la majeure part du temps nous effectuons de la simulation de réseau pour ajuster les paramètres de l algorithme. Donc, nous présentons nos modèles de grilles basées dans l observation et la mesure de ce que nous considérons les caractéristiques principales de l équilibrage de charge avec des objets actifs: la capacité de traitement des taches et la latence de communication. La communauté de recherche de grilles a commencé à prendre en compte l importance des modèles validés pour le travail de simulation. Par conséquent, il y a eu plusieurs approches dans les dernières années [70, 72, 76, 84, 87]. Cependant, à notre connaissance, notre travail de modélisation et simulation est la première approche qui étudie les caractéristiques d une xvii xviii ÉQUILIBRAGE DE CHARGE POUR DES OBJETS ACTIFS DANS LES GRILLES DE CALCUL partie d une infrastructure de grille. Ce thèse est organisé comme suit: Le concept d un objet est expliqué dans le chapitre 2, suivi du modèle des objets actifs et l implémentation de ProActive. Le chapitre 3 présente le concept de réseau et de grille dans le contexte des calculs parallèles. Le chapitre 4 présente la situation actuelle dans les modèles et les algorithmes d équilibrage de charge. Le chapitre 5 explique pourquoi l équilibrage de charge d une application parallèle développée avec ProActive accélère ces applications et il montre nos politiques pour l algorithme d équilibrage de charge des objets actifs. Dans le chapitre 6 nous présentons et discutons nos modèles de grille et des objets actifs utilisés dans ce travail. Le chapitre 7 présente des conclusions et les discussions de futurs travaux. Dans ce résumé, les chapitres 2,3 et 4 sont présentées dans la section suivante (État de l art), le chapitre 5 est présenté dans la Section 3. Finalement, le chapitre 6 est résumé dans la section 4. 2. ÉTAT DE L ART xix 2 État de l art Cette thèse étudie l intersection de trois sujets: les objets actifs, les algorithmes d équilibrage de charge et les réseaux à grande échelle. Le première traite de l infrastructure sur laquelle nous avons développée notre recherche, la deuxieme est un sujet largement étudié pour la communauté scientifique [20, 36, 92, 108] et technologique [12, 64, 89, 122], mais le troisième est un sujet encore en exploration. Donc, le but de notre recherche est de réaliser une contribution scientifique en utilisant les connaissances établies des deux premier sujets pour construire des algorithmes nouveaux appliqués aux troisième sujet. 2.1 Les objets actifs et ProActive En raison de la popularité et acceptation du paradigme orienté aux objets (OO), plusieurs langages de programmation OO concurrents ont été conçus et mis en application. Ces langages sont basés sur le modèle des objets concurrents où l objet est une organisation active [134]. Néanmoins, du point de vue d un logiciel d exploitation, chaque objet était un grand processus avec un seul fil de commande. Par conséquent, il était impératif d écrire une grande quantité de code additionnel pour soutenir les abstractions des objets. Le modèle de object/thread [95] a été présenté en 1995 dans le contexte d un système d exploitation appelé Clouds [42]. Dans ce modèle, les objets sont des entités passives qui fournissent des fonctions aux données et les threads représentent l écoulement de commandes dans le système par l invocation et l exécution postérieure de méthodes. L avantage de ce modèle est sa bonne exécution, parce que les fils multiples peuvent fonctionner au même temps dans les mono-processeurs avec un bas coût. ProActive est un modèle de programmation d objet actif uniforme. Chaque objet actif a son propre fil de commande et il a la capacité de décider dans quel ordre servir les appels entrants de méthode qui sont automatiquement stockés dans une file d attente des demandes en suspens. Si la file d attente est vide, les objets actifs attendent jusqu à l arrivée d une nouvelle demande, cet état est connue comme wait-for-request. Les objets actifs sont accessibles à distance par l intermédiaire de l invocation d une méthode. Les appels de méthode avec les objets actifs sont asynchrones avec synchronisation automatique laquelle est fournit par les objets de type future (Figure i). La synchronisation est fournie par un mécanisme connu sous le nom de wait-by-necessity [31]. Il y a des rendez-vous courts au début de chaque appel à distance asynchrone qui bloquent l appelant jusqu à ce que l appel ait atteint le contexte de l appelé. ProActive fournit aussi un modèle de communication appelé communication des groupes. La communication de groupes permet de déclencher la méthode d un groupe distribué d objets actifs du même type compatible, avec une génération dynamique des groupes de résultats. Ce mécanisme de communication de groupe, plus certaines opérations de synchronisation (WaitAll, WaitOne, etc.), fo
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x