these

these

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

Description

These`present´ ee´ parIlan GinzburgPour obtenir le grade de Docteurde l’Institut National Polytechnique de Grenoble(Arretˆ e´ ministeriel´ du 30 mars 1992)Specialit´ e´ : InformatiqueAthapascan-0b : Integration´ efficace et portable demultiprogrammation leg´ ere` et de communicationsDate de soutenance : 12 septembre 1997Composition du juryJacques Briat, responsable de these`Jean-Marc Geib, president´ du jury et rapporteurJean-Francois¸ Mehaut,´ examinateurBrigitte Plateau, directeur de these`Thierry Priol, rapporteurThese` prepar´ ee´ au sein duLaboratoire de Modelisation´ et de Calcul (LMC)Si cette these` n’est signee´ que de mon nom, il est pourtant clair que son contenuest une œuvre collective.Tout a commence´ par un DEA et je remercie Jacques Briat d’avoir accepted´ em’encadrer alors qu’il savait que j’avais dej´ a` programme´ en COBOL. Il m’a et´ e´ ensuited’une grande aide pendant la these,` present´ et disponible (y compris dimanches et joursf´eries)´ quand j’avais besoin de lui, tout en me laissant une grande liberte.´Brigitte Plateau m’a aide`´ ad egager´ les grandes orientations de cette these.` Sescapacites´ de travail et de synthese` sont etonnantes.´ Merci a` elle d’avoir aussi su meredonner de la motivation quand celle-ci s’essoufflait un peu. . .Merci ensuite a` Marcelo Pasin, qui outre le fait de m’avoir supporte´ pendant pres`de trois ans, a et´ e´ d’une grande efficacite´ dans le dev´ eloppement d’Athapascan-0b ettres` ...

Sujets

Informations

Publié par
Nombre de visites sur la page 41
Langue Français
Signaler un problème

These`
present´ ee´ par
Ilan Ginzburg
Pour obtenir le grade de Docteur
de l’Institut National Polytechnique de Grenoble
(Arretˆ e´ ministeriel´ du 30 mars 1992)
Specialit´ e´ : Informatique
Athapascan-0b : Integration´ efficace et portable de
multiprogrammation leg´ ere` et de communications
Date de soutenance : 12 septembre 1997
Composition du jury
Jacques Briat, responsable de these`
Jean-Marc Geib, president´ du jury et rapporteur
Jean-Francois¸ Mehaut,´ examinateur
Brigitte Plateau, directeur de these`
Thierry Priol, rapporteur
These` prepar´ ee´ au sein du
Laboratoire de Modelisation´ et de Calcul (LMC)

Si cette these` n’est signee´ que de mon nom, il est pourtant clair que son contenu
est une œuvre collective.
Tout a commence´ par un DEA et je remercie Jacques Briat d’avoir accepted´ e
m’encadrer alors qu’il savait que j’avais dej´ a` programme´ en COBOL. Il m’a et´ e´ ensuite
d’une grande aide pendant la these,` present´ et disponible (y compris dimanches et jours
f´eries)´ quand j’avais besoin de lui, tout en me laissant une grande liberte.´
Brigitte Plateau m’a aide`´ ad egager´ les grandes orientations de cette these.` Ses
capacites´ de travail et de synthese` sont etonnantes.´ Merci a` elle d’avoir aussi su me
redonner de la motivation quand celle-ci s’essoufflait un peu. . .
Merci ensuite a` Marcelo Pasin, qui outre le fait de m’avoir supporte´ pendant pres`
de trois ans, a et´ e´ d’une grande efficacite´ dans le dev´ eloppement d’Athapascan-0b et
tres` enrichissant lors de nos nombreux echanges.´ C’est a` lui que l’on doit entre autres
la stabilisation d’Athapascan-0b et la documentation etof´ fee.´
Un grand merci a` Messieurs Jean-Marc Geib, Jean-Francois Mehaut´ et Thierry
Priol d’avoir accepte´ de rapporter sur cette these` malgre´ les contraintes d’emploi du
temps. Leurs remarques m’ont et´ e´ utiles.
Ces remerciements ne seraient pas complets sans citer les autres membres de l’equipe´
APACHE sans lesquels ce travail aurait et´ e´ moins agreable´ et moins productif. Michel
Christaller et Michel Riviere` qui ont toujours accepte´ de partager leurs experiences´
“Athapascanesques”, Jean-Louis Roch qui par ses idees´ a contribue`´ a orienter (et re-
orienter et re-re-orienter...) Athapascan-0b vers ce qu’il est aujourd’hui et ceux qui
par leur presence´ ont rendu agreables´ (et moins longues) ces quelques annees´ de these` :
Eric Maillet, Fred´ eric´ Guinand, Benhur Stein, Francois¸ Galilee,´ Paulo Fernandes et
tous les autres. . .
Pour finir, merci a` la societ´ e´ Hewlett-Packard qui en ignorant superbement mes
candidatures rep´ et´ ees´ m’a permis (malgre´ moi?) de continuer et de finir cette these,`
et merci a` la societ´ e´ Intel, qui en acceptant au contraire ma candidature m’a rendu
1presque agreable´ la phase de redaction.´
Enfin, la these` n’etant´ pas tout, merci a` Karine, a` ma famille et a` mes amis pour le
reste.
Ilan Ginzburg,
Grenoble, Septembre 1997.
Vous pouvez m’y joindre a` l’adressegilan@iil.intel.com.`TABLE DES MATIERES 5
Table des matier` es
1 Introduction 11
1.1 Objectif de la the`se........................... 11
1.2 Structure du document . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Communication 15
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Definitions´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Bibliotheques` de communication . . . . . . . . . . . . . . . . . . . . 17
2.3.1 NX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.2 Express . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.3 Parmacs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.4 P4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.5 Zipcode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 PVM................................... 19
2.4.1 Presentation´ . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.2 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 MPI................................... 21
2.5.1 Presentation´ . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.2 Exemple d’architecture . . . . . . . . . . . . . . . . . . . . . 24
2.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Multiprogrammation leg´ er` e 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Caracteristiques´ d’un processus leger´ . . . . . . . . . . . . . . . . . . 28
3.3 Raisons d’utiliser les processus legers´ . . . . . . . . . . . . . . . . . 29
3.4 Fonctionnalites´ des legers´ POSIX . . . . . . . . . . . . . . 31
3.4.1 Creation,´ vie et mort . . . . . . . . . . . . . . . . . . . . . . 31
3.4.2 Synchronisation . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4.3 Donnees´ privees´ et pile . . . . . . . . . . . . . . . . . . . . . 33
3.4.4 Signaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4.5 Annulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.5 Processus legers´ et le systeme` d’exploitation . . . . . . . . . . . . . . 35
3.5.1 N vers 1 (niveau utilisateur) . . . . . . . . . . . . . . . . . . 36
`6 TABLE DES MATIERES
3.5.2 1 vers 1 (niveau noyau) . . . . . . . . . . . . . . . . . . . . . 37
3.5.3 N vers P (N P)........................ 38
3.6 Ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.6.1 FIFO . . . . . . . . . . . . . . . . . . . . . 39
3.6.2 Ordonnancement round-robin ................. 40
3.6.3 Autres ordonnancements . . . . . . . . . . . . . . . . . . . . 40
3.6.4 Priorites´ et mutex ........................ 40
3.7 Processus legers´ et codes existants . . . . . . . . . . . . . . . . . . . 42
3.7.1 Compatibilite´ d’une fonction avec la multiprogrammation leg´ ere` 42
3.7.2 Causes possibles des problemes` . . . . . . . . . . . . . . . . 43
3.8 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4 Multiprogrammation et communications 45
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 Definitions´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 Systemes` existants . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3.1 TPVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3.2 Nexus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.3 Chant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.4 MPI-F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3.5 PM2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3.6 DTMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.7 Athapascan-0a . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4 Resum´ e´ ................................. 55
4.4.1 Modele` de programmation . . . . . . . . . . . . . . . . . . . 55
4.4.2 Implantation . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.5 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5Presentation´ d’Athapascan-0b 61
5.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Structure et concepts . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2.1 Tachesˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.2.2 Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.2.3 Demarrage´ et initialisation . . . . . . . . . . . . . . . . . . . 65
5.2.4 Fils et synchronisation . . . . . . . . . . . . . . . . . . . . . 65
5.2.5 Ports . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2.6 Tampons . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2.7 Types de donne´s........................ 66
5.2.8 Operations´ bloquantes et asynchrones . . . . . . . . . . . . . 66
5.2.9 Ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . 67
5.3 interface de programmation . . . . . . . . . . . . . . . . . . . . . . . 67
5.4 Fonctionnalite´s............................. 69
5.4.1 Initialisation et terminaison . . . . . . . . . . . . . . . . . . 69`TABLE DES MATIERES 7
5.4.2 Creation´ et utilisation de tampons . . . . . . . . . . . . . . . 70
5.4.3 Declaration´ et appel de service . . . . . . . . . . . . . . . . . 71
5.4.4 Creation´ locale de processus legers´ . . . . . . . . . . . . . . 72
5.4.5 Synchronisation locale . . . . . . . . . . . . . . . . . . . . . 73
5.4.6 Creation´ de port . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.4.7 Envoi et reception´ de messages . . . . . . . . . . . . . . . . . 74
5.5 Demarche´ gen´ erale´ d’utilisation . . . . . . . . . . . . . . . . . . . . 75
6R ealisation´ 77
6.1 Problematique´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.1.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
´6.1.2 Etats d’un fil d’execution´ communiquant . . . . . . . . . . . 77
6.1.3 Integration´ efficace . . . . . . . . . . . . . . . . . . . . . . . 79
6.2 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.3 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.3.1 Athapascan-0b . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3.2 Akernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.4 Avancement des communications . . . . . . . . . . . . . . . . . . . . 89
6.4.1 Utilisation monoprogramme´ ................. 89
6.4.2 multiprogramme´.................. 90
6.5 Validation des choix . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7 Performance d’Athapascan-0b 93
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.2 Fonctionnalites´ de base . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.2.1 Creation´ locale d’un fil d’execution´ . . . . . . . . . . . . . . 94
7.2.2 Commutation de processus leger´ . . . . . . . . . . . . . . . . 98
7.2.3 Envoi et reception´ d’un message . . . . . . . . . . . . . . . . 100
7.2.4 Appels de service . . . . . . . . . . . . . . . . . . . . . . . . 106
7.3 Fonctionnalites´ compose´s.......................108
7.3.1 Recouvrements . . . . . . . . . . . . . . . . . . . . . . . . . 108
7.3.2 Appel et retour paralleles` . . . . . . . . . . . . . . . . . . . . 112
´7.3.3 Echange total . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.4 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
8 Conclusion et perspectives 119`8 TABLE DES MATIERESTABLE DES FIGURES 9
Table des figures
2.1 Deux modes de communication entre tachesˆ PVM. . . . . . . . . . . 20
2.2 Separation´ des communications par les communicateurs MPI . . . . . 23
3.1 Processus lourds monoprogrammes´ et multiprogramme´s........ 28
3.2 Transitions d’etat´ d’un fil d’execution.´ . . . . . . . . . . . . . . . . . 32
3.3 Plusieurs fils d’execution´ sont lies´ a` une entite´ noyau.......... 36
3.4 Chaque fil d’execution´ est lie`´ a une entite´ noyau. . . . . . . . . . . . 37
3.5 Un ensemble de fils d’execution´ se partage un ensemble d’entites´ noyau. 38
3.6 Inversion de priorite´ non bornee´ sur un monoprocesseur. . . . . . . . 41
5.1 Deux tachesˆ dans une machine parallele` Athapascan-0b. . . . . . . . 64
6.1 Transitions d’etat´ d’un fil d’execution´ effectuant des communications. 78
6.2 Communication d’un processus lourd. . . . . . . . . . . . . . . . . . 81
6.3 d’un leger´ . . . . . . . . . . . . . . . . . . 81
6.4 de plusieurs processus legers.´ . . . . . . . . . . . . . 82
6.5 Architecture d’Athapascan-0b. . . . . . . . . . . . . . . . . . . . . . 83
7.1 Temps de creation´ d’un processus leger´ DCE et Athapascan-0b sur
AIX 3.2, fonction du nombre de processus legers´ dej´ ap` resents.´ . . . . 95
7.2 Deux modes de creation´ d’un leger´ DCE sur AIX 3.2. . . . 95
7.3 Temps de creation´ d’un processus leger´ Pthreads ou Athapascan-0b
sur AIX 4.2, fonction du nombre de processus legers´ dej´ ap` r esents.´ . . 96
7.4 Perturbation du temps de creation´ d’un processus leger´ Pthreads sur
AIX 4.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.5 Temps de commutation de fils DCE ou Athapascan-0b sur AIX 3.2,
fonction du nombre de processus legers´ presents.´ Ordonnancement a`
partage de temps sans priorite´s...................... 98
7.6 Temps de commutation de fil DCE ou Athapascan, fonction du nombre
de threads presents.´ Ordonnancement FIFO ou round-robin avec prio-
rite´s.................................... 99
7.7 Temps d’envoi de messages, Athapascan-0b et MPI-F sur AIX 3.2. . . 101
7.8 Temps d’envoi de petits messages, et MPI-F sur AIX 3.2.101n
n
n
10 TABLE DES FIGURES
7.9 Diagramme temporel d’un “ping-pong” pour messages de taille nulle
en Athapascan-0b sur AIX 3.2. . . . . . . . . . . . . . . . . . . . . . 104
7.10 Temps d’appel de service, de service urgent et d’envoi. Athapascan-0b
sur AIX 3.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7.11 Temps total d’un echange´ “ping-pong” avec plusieurs fils communi-
cants par nœud. Athapascan-0b sur AIX 3.2. . . . . . . . . . . . . . . 109
7.12 Temps total d’un echange´ avec plusieurs fils communi-
cants par nœud – gros messages. Athapascan-0b sur AIX 3.2. . . . . . 109
7.13 “Ping-pong” classique et “ping-pong” dans lequel les messages sont
envoyes´ simultanement´ des deux nœuds. MPI-F sur AIX 3.2. . . . . . 110
7.14 Duree´ de recouvrement sur le nœud “ping” pendant un echange´ “ping-
pong” complet (envoi et reception).´ Athapascan-0b sur AIX 3.2. . . . 111
7.15 Appel de services par un fil et recup´ eration´ des resultats.´ . . . . . . 112
7.16 de et recup´ eration´ des resultats,´ petits parametres` et
r´esultats. Athapascan-0b sur AIX 3.2. . . . . . . . . . . . . . . . . . 113
7.17 Appel de services et recup´ eration´ des resultats.´ Athapascan-0b sur
AIX 3.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.18 Appels de services, echange´ total entre les services puis renvoi de re-´
sultats. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.19 Appels de services, echange´ total puis renvoi de resultats.´ Athapascan-
0b sur AIX 3.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.20 Propagation du retard de creation´ de service lors d’un echange´ total
entre deux services. . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.1 Visualisation de traces prises lors de l’execution´ de l’application de
dynamique moleculaire.´ . . . . . . . . . . . . . . . . . . . . . . . . . 120