these

these

Documents
150 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

`N˚d’ordre 1170 THESEAnn´ee 2006Pr´esent´ee `aUniversit´e de Franche-Comt´eUFR Sciences et TechniquesLaboratoire d’Informatique de l’Universit´e de Franche-Comt´ePour obtenir le´GRADE DE DOCTEUR DE L’UNIVERSITE DE´FRANCHE-COMTESp´ecialit´e InformatiqueCalcul it´eratif asynchrone sur infrastructurepair-`a-pair : la plate-forme JaceP2PparPhilippe VUILLEMINSoutenue le 24 octobre 2006 devant la commission d’examen :´M. Vicente HERNANDEZ Professeur `a l’Universit´e Polytechnique de Valence, EspagneRapporteurs´M. Yves ROBERT Professeur `a l’Ecole Normale Sup´erieure de LyonDirecteur de Th`ese M. Jacques BAHI Professeur `a l’Universit´e de Franche-Comt´eCo-encadrant M. Rapha¨el COUTURIER Professeur `a l’Universit´e de Franche-Comt´e´ ´Mme Fabienne JEZEQUEL Maˆıtre de Conf´erences (HDR) `a l’Universit´e de Paris 2ExaminateursM. David LAIYMANI Maˆıtre de Conf´erences `a l’Universit´e de Franche-Comt´eRemerciementsLes travaux pr´esent´es dans ce document n’auraient pas pu ˆetre r´ealis´es sans l’aide et le soutiende plusieurs personnes. Je tiens `a les remercier tout particuli`erement.Tout d’abord,ungrand Merci a` Jacques, mon directeur de th`ese et mon fid`ele co´equipierde congr`es. Merci pourta confiance, ta disponibilit´e, ton soutien et tes conseils extrˆemementpertinents.Merci `a toi, Rapha¨el, toi sans qui mon travail de th`ese n’aurait pas aussi bien ´evolu´e.Je tiens ´egalement a` te remercier pour ton amiti´e, ta g´en´erosit´e et ta bonne ...

Sujets

Informations

Publié par
Nombre de visites sur la page 22
Langue Français
Signaler un problème
` N˚d’ordre 1170 THESE Ann´ee 2006 Pr´esent´ee `a Universit´e de Franche-Comt´e UFR Sciences et Techniques Laboratoire d’Informatique de l’Universit´e de Franche-Comt´e Pour obtenir le ´GRADE DE DOCTEUR DE L’UNIVERSITE DE ´FRANCHE-COMTE Sp´ecialit´e Informatique Calcul it´eratif asynchrone sur infrastructure pair-`a-pair : la plate-forme JaceP2P par Philippe VUILLEMIN Soutenue le 24 octobre 2006 devant la commission d’examen : ´M. Vicente HERNANDEZ Professeur `a l’Universit´e Polytechnique de Valence, Espagne Rapporteurs ´M. Yves ROBERT Professeur `a l’Ecole Normale Sup´erieure de Lyon Directeur de Th`ese M. Jacques BAHI Professeur `a l’Universit´e de Franche-Comt´e Co-encadrant M. Rapha¨el COUTURIER Professeur `a l’Universit´e de Franche-Comt´e ´ ´Mme Fabienne JEZEQUEL Maˆıtre de Conf´erences (HDR) `a l’Universit´e de Paris 2 Examinateurs M. David LAIYMANI Maˆıtre de Conf´erences `a l’Universit´e de Franche-Comt´e Remerciements Les travaux pr´esent´es dans ce document n’auraient pas pu ˆetre r´ealis´es sans l’aide et le soutien de plusieurs personnes. Je tiens `a les remercier tout particuli`erement. Tout d’abord,ungrand Merci a` Jacques, mon directeur de th`ese et mon fid`ele co´equipier de congr`es. Merci pourta confiance, ta disponibilit´e, ton soutien et tes conseils extrˆemement pertinents. Merci `a toi, Rapha¨el, toi sans qui mon travail de th`ese n’aurait pas aussi bien ´evolu´e. Je tiens ´egalement a` te remercier pour ton amiti´e, ta g´en´erosit´e et ta bonne humeur par- ticuli`erement contagieuse. Du point de vue professionnel, maintenant, je ne te remercierai jamais assez pour toute l’aide que tu m’a fournie en tant qu’encadrant et pour la patience dont tu as fait preuve avec moi durant ces trois ann´ees. Je tiens ´egalement `a remercier Yves Robert et Vicente Herna´ndez de m’avoir fait l’hon- neur d’accepter d’ˆetre rapporteurs de cette th`ese, ainsi que Fabienne J´ez´equel et David Laiymani pour avoir accept´e d’ˆetre membres de mon jury. Merci `a vous, Kamel et Flavien, pour votre aide et vos conseils techniques. Une partie des travaux pr´esent´es dans ce document n’aurait pas´et´e possible sans vous. Un grand Merci aussi et surtout pour ces moments de d´etente et de discussion tellement agr´eables. Je souhaite ´egalement remercier chaleureusement Ronan Guivarch et Dominique Chalon pour leurs corrections et leurs conseils tr`es pr´ecieux lors la relecture de ce document. Merci a` Michel, Sylvain, Jean-Luc, Marc, Abdallah, Arnaud, Bruno, Pierre-Alain, St´ephane, Hussam, Jean-Claude et Ahmed pour les moments agr´eables pass´es ensemble et pour cette ambiance de travail toujours joviale. Enfin, je tiens aussi et surtout a` remercier mes parents pour leur soutien inconditionnel ainsi que tous mes proches de France et d’Espagne, famille et amis, qui m’ont soutenu et encourag´e depuis le d´ebut. `A tous, mon infinie gratitude... Table des mati`eres Introduction 1 ´I Etat de l’art 5 1 Les grilles de calcul 7 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Biblioth`eques de communication pour les grilles de calcul . . . . . . . . . . . . . 8 1.2.1 La notion de passage de messages. . . . . . . . . . . . . . . . . . . . . . . 8 1.2.2 Les appels de proc´edure `a distance . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Les grappes de calcul distantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1 Legion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.2 Globus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.3 JACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4 Le calcul global . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.1 La tol´erance aux pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4.2 SETI@home. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4.3 XtremWeb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.4.4 Condor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2 Les syst`emes pair-a`-pair 21 2.1 Introduction et d´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Caract´eristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.1 La d´ecentralisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.2 L’extensibilit´e et l’h´et´erog´en´eit´e . . . . . . . . . . . . . . . . . . . . . . . . 23 `II TABLE DES MATIERES 2.2.3 L’auto-organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2.4 L’anonymat et la s´ecurit´e des utilisateurs . . . . . . . . . . . . . . . . . . 24 2.3 Taxonomie des architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.1 Les architectures pseudo-centralis´ees . . . . . . . . . . . . . . . . . . . . . 25 2.3.2 Les architectures de type Pur Pair-`a-Pair . . . . . . . . . . . . . . . . . . 26 2.3.3 Les architectures Hybrides avec nœuds d’indexation . . . . . . . . . . . . 28 2.4 Environnements de d´eveloppement pair-`a-pair . . . . . . . . . . . . . . . . . . . . 30 2.4.1 JXTA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.4.2 JNGI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.4.3 ProActive P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3 Contexte scientifique : les algorithmes it´eratifs 35 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 Algorithmes it´eratifs s´equentiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3 Algorithmes parall`eles it´eratifs synchrones . . . . . . . . . . . . . . . . . . . . . . 37 3.3.1 Mod`ele avec communications synchrones (ISCS) . . . . . . . . . . . . . . 38 3.3.2 Mod`ele avec communications asynchrones (ISCA) . . . . . . . . . . . . . 38 3.3.3 La d´etection de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.4 Algorithmes parall`eles it´eratifs asynchrones (IACA) . . . . . . . . . . . . . . . . 40 3.4.1 Mod`ele algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.4.2 Repr´esentation graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.4.3 La d´etection de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.5 JACE : un environnement d’ex´ecution distribu´e pour le calcul it´eratif asynchrone 43 3.5.1 Architecture de JACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.5.2 Les communications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.5.3 Bilan. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.6 Conclusion et probl´ematique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 II Contribution 51 4 Calcul it´eratif et infrastructures pair-a`-pair 53 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 `TABLE DES MATIERES III 4.2 Comportement des algorithmes it´eratifs parall`eles dans un contexte de nœuds volatiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2.1 Inconv´enients des synchronisations . . . . . . . . . . . . . . . . . . . . . . 55 4.2.2 Avantages des it´erations asynchrones . . . . . . . . . . . . . . . . . . . . . 57 4.3 Pr´esentation g´en´erale des techniques de multid´ecomposition . . . . . . . . . . . . 59 4.4 Multid´ecomposition pour les probl`emes lin´eaires . . . . . . . . . . . . . . . . . . 60 4.4.1 Mod`ele algorithmique de la multid´ecomposition pour les probl`emes lin´eaires 60 4.4.2 Quelques cas de convergence . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.4.3 Mise en œuvre de l’algorithme parall`ele sans recouvrement de donn´ees . . 64 4.4.4 Le recouvrement de donn´ees . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.5 Multid´ecomposition pour les syst`emes non lin´eaires . . . . . . . . . . . . . . . . . 72 4.5.1 R´esolution s´equentielle du probl`eme . . . . . . . . . . . . . . . . . . . . . 72 4.5.2 Mod`ele algorithmique de la multid´ecomposition pour les probl`emes non lin´eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.5.3 L’algorithme Multisplitting-Newton . . . . . . . . . . . . . . . . . . . . . 77 4.5.4 Repr´esentation graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5 La plate-forme JaceP2P 83 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.2 Pr´esentation g´en´erale de la plate-forme JaceP2P . . . . . . . . . . . . . . . . . . 84 5.2.1 Les caract´eristiques de la plate-forme . . . . . . . . . . . . . . . . . . . . . 85 5.2.2 Architecture de la plate-forme . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.2.3 Les diff´erents types d’utilisateurs . . . . . . . . . . . . . . . . . . . . . . . 88 5.3 Les fonctionnalit´es de JaceP2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.3.1 L’amorc¸age : connexion d’un pair sur la plate-forme JaceP2P . . . . . . . 88 5.3.2 Le lancement d’une application . . . . . . . . . . . . . . . . . . . . . . . . 90 5.3.3 La d´etection de pannes ou de d´econnexions . . . . . . . . . . . . . . . . . 92 5.3.4 La mise a` jour des Registres d’application . . . . . . . . . . . . . . . . . . 93 5.3.5 La sauvegarde et le red´emarrage d’une tˆache apr`es d´econnexion . . . . . . 95 5.3.6 La d´etection de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.4 L’interface de programmation de JaceP2P . . . . . . . . . . . . . . . . . . . . . . 99 5.4.1 Les variables de l’interface . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.4.2 Les m´ethodes de l’interface . . . . . . . . . . . . . . . . . . . . . . . . . . 100 `IV TABLE DES MATIERES 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6 Mise en œuvre et exp´erimentations 105 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.2 Exp´erimentations sur processeurs stables . . . . . . . . . . . . . . . . . . . . . . . 105 6.2.1 Pr´esentationmath´ematiqueduprobl`eme:r´esolutiond’unsyst`emed’´equations d’ondes non lin´eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.2.2 Conditions d’exp´erimentations . . . . . . . . . . . . . . . . . . . . . . . . 107 6.2.3 Exp´erimentations sur processeurs h´et´erog`enes et r´eseau homog`ene . . . . 108 6.2.4 Exp´erimentations sur processeurs h´et´erog`enes et r´eseaux h´et´erog`enes . . . 110 6.2.5 Bilan. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.3 Exp´erimentations dans un contexte pair-`a-pair avec JaceP2P . . . . . . . . . . . 112 6.3.1 R´esolution d’un syst`eme lin´eaire : le probl`eme de Poisson . . . . . . . . . 112 6.3.2 R´esolution d’un syst`eme non lin´eaire avec un probl`eme de transport de compos´es polluants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Conclusion - Perspectives 121 Bibliographie 127 Liste des publications personnelles 135 Table des figures 1.1 Architecture RMI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1 Comparaison entre le mod`ele pair-`a-pair et le mod`ele client-serveur. . . . . . . . 23 2.2 Exemple d’architecture centralis´ee. . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3 Exemple de graphe form´e par l’interconnexion des pairs. . . . . . . . . . . . . . . 27 2.4 Processus de recherche par inondation. . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5 Exemple d’un r´eseau de pairs simples et de super-nœuds. . . . . . . . . . . . . . 28 2.6 Exemple d’un r´eseau de super-nœudscommuniquant via le protocole Pur Pair-`a- Pair. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.7 Exemple de r´eseau de super-nœuds tous interconnect´es. . . . . . . . . . . . . . . 29 3.1 Exemple d’ex´ecution d’un algorithme de type ISCS. . . . . . . . . . . . . . . . . 38 3.2 Exemple d’ex´ecution d’un algorithme de type ISCA. . . . . . . . . . . . . . . . . 39 3.3 Exemple d’ex´ecution d’un algorithme IACA classique. . . . . . . . . . . . . . . . 43 3.4 Insertion en file d’un message dans le mode synchrone. . . . . . . . . . . . . . . . 46 3.5 Insertion en file d’un message dans le mode asynchrone. . . . . . . . . . . . . . . 47 4.1 Exemple d’ex´ecution d’unalgorithme parall`ele it´eratif synchronesur pairsvolatiles. 56 4.2 Exempled’ex´ecutiond’unalgorithmeparall`eleit´eratifasynchronesurpairsvolatiles. 58 4.3 Une matrice M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61l 4.4 Les diff´erentes d´ecompositions par bloc de A en M −N pour L=3. . . . . . . . 62l l −14.5 Les trois matrices M pour le cas L =3. . . . . . . . . . . . . . . . . . . . . . . 62 l 4.6 Les trois matrices de pond´eration E pour le cas L = 3 sans recouvrement delk donn´ees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.7 D´ecomposition en bandes de la matrice A et des vecteurs x et b. . . . . . . . . . 65 4.8 Exemple de d´ecoupage d’une matrice A de taille 9×9 sur trois processeurs avec recouvrement de deux lignes de donn´ees a` chaque interface. . . . . . . . . . . . . 67 VI TABLE DES FIGURES 4.9 Lesmatricesdepond´erationE danslecasou` L=3et ou` lesvaleursrecouverteslk de x prises en compte sont celles calcul´ees localement. . . . . . . . . . . . . . . . 69 4.10 Lesmatricesdepond´erationE danslecasou` L=3et ou` lesvaleursrecouverteslk de x prises en compte sont celles calcul´ees par l’autre processeur. . . . . . . . . . 70 4.11 Lesmatricesdepond´erationE danslecasou` L=3et ou` lesvaleursrecouverteslk de x prises en compte sont une moyenne de toutes celles calcul´ees. . . . . . . . . 71 4.12 Repr´esentation graphique de la m´ethode de Newton. . . . . . . . . . . . . . . . . 74 4.13 D´ecomposition de la Jacobienne du vecteur et de la fonction. . . . . . . . . . . . 77 4.14 Exemple d’ex´ecution synchrone (ISCA) de l’algorithme de Multisplitting-Newton sur deux processeurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.15 Exemple d’ex´ecution asynchrone de l’algorithme de Multisplitting-Newton sur deux processeurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.1 Un r´eseau de Super-Nœuds et l’enregistrement de quatre D´emons. . . . . . . . . 89 5.2 La r´eservation de pairs de calcul au lancement d’une application. . . . . . . . . . 91 5.3 Envoi du Registre d’application aux D´emons r´eserv´es par le Lanceur. . . . . . . . 91 5.4 Les battements de cœur effectu´es par les D´emons sur leurs pairs contrˆoleurs. . . 93 5.5 La mise `a jour du Registre d’application. . . . . . . . . . . . . . . . . . . . . . . . 94 5.6 La strat´egie de tourniquet utilis´ee pour l’envoi des clones aux pairs de sauvegardes. 96 5.7 La proc´edure de sauvegarde des taˆches T et T . . . . . . . . . . . . . . . . . . . 962 3 5.8 Lar´ecup´erationducloneleplusr´ecentsurlespairsdesauvegardeapr`esd´econnexion de D3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.1 Influencedurecouvrementsurunegrilledetaille 700×700 avec unegrappelocale h´et´erog`ene de 40 processeurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6.2 Influence du recouvrement sur une grille de taille 1000×1000 avec une grappe locale h´et´erog`ene de 40 processeurs. . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.3 Influence du recouvrement sur une grille de taille 1300×1300 avec une grappe locale h´et´erog`ene de 40 processeurs. . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.4 Influence du recouvrement sur une grille de taille 1000×1000 avec une grappe distante h´et´erog`ene de 16 processeurs. . . . . . . . . . . . . . . . . . . . . . . . . 111 6.5 Influence des communications perturbatrices sur une grille de taille 1000×1000 avec une grappe distante h´et´erog`ene de 16 processeurs. . . . . . . . . . . . . . . . 112 6.6 Temps d’ex´ecution du probl`eme de Poisson sur 80 pairs en fonction de n avec diff´erents nombres de d´econnexions. . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.7 Tempsd’ex´ecution duprobl`eme d’Advection-Diffusion sur48 pairsenfonction de n avec diff´erents nombres de d´econnexions. . . . . . . . . . . . . . . . . . . . . . 118