these
150 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
150 pages
Français
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 ...

Informations

Publié par
Nombre de lectures 22
Langue Français

Extrait

` 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 . . . . . . . . . . . . . . .
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents