these

Publié par

`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 ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 34
Nombre de pages : 150
Voir plus Voir moins

`
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´eRemerciements
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 135Table 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. . . . . . . . . . . . . 67VI 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

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.