these

Informations

• Publié par: Viej
• Nombre de lectures: 42
• Langue: Français

Extrait

INSTITUT NATIONAL POLYTECHNIQUE DE GRENOBLE
THESE
pour obtenir le titre de
DOCTEUR DE L’INPG
Spécialité : "INFORMATIQUE : SYSTEMES ET COMMUNICATIONS"
présentée et soutenue publiquement
par
Gerson G. H. Cavalheiro
le 22 Novembre 1999
ATHAPASCAN-1 : Interface générique pour
l’ordonnancement dans un environnement
d’exécution parallèle
Directeur de thèse :
Jean Louis Roch
Brigitte Plateau
Composition du jury :
Rapporteurs : M. Bertil Folliot
M. Jean Marc Geib
Examinateurs : M. Bertil Folliot
M. Jean François Méhaut
Mme Brigitte Plateau
M. Michel Riveill, Président
M. Jean Louis Roch
préparée au Laboratoire de Modélisation et Calcul
et soutenue au Laboratoire Informatique et Distribution
dans le cadre de l’Ecole Doctorale "Mathématiques et Informatique"

Remerciements
Le voici le fruit de 4 ans de travail : ma thèse. Bien qu’elle porte seulement
mon nom, ce document représente l’engagement d’un grand nombre de personnes.
J’essaye ici de ne pas oublier de remercier toutes ces personnes qui m’ont aidé d’une
façon ou d’une autre.
Tout d’abord il faut souligner qui cette thèse n’aurait pas vu le jour sans la
bourse qui m’a été conférée par la CAPES, dans un accord avec le COFECUB.
Merci donc à Marta Elias qui était toujours disponible pour m’assister dans les
différentes situations auxquelles je me suis trouvé confronté.
Je tiens à remercier Michel Riveill pour avoir accepté de présider le jury de ma
soutenance et Jean Marc Geib pour la confiance qu’il a accordée à mon travail. Je
remercie aussi tout particulièrement Bertil Folliot et Jean François Méhaut, ils ont
pris le temps de lire ce document et de me donner leurs commentaires qui ont été
très importants pour sa qualité finale.
Et bien sûr je remercie Brigitte Plateau, qui m’a donné l’honneur de travailler
dans son équipe et qui à diverses reprises m’a soutenu lors de mes coups de fatigue...
Enfin un grand merci à mes collèges qui se sont volontiers jetés sur des chapitres
de ma thèse pour faire des corrections dans le texte. Comme je pense que quand
même j’ai laissé traîner quelques fautes, je ne vais pas leur faire la honte de citer
leurs noms dans ce paragraphe.
Mais il n’y a pas eu que la thèse : il y a eu aussi tout un travail qui est venu
avant.
Travailler avec Jean Louis Roch m’a beaucoup appris ; je suis loin de pouvoir
oublier mon passage chez les APACHEs sous sa direction. Et les A1 Boys avec qui
j’ai eu grand plaisir à travailler pendant ces années : Jean Guillaume, Nicolas et
surtout François et Mathias, de vrais guerriers avec lesquels je suis très fier d’avoir
fait un bout de chemin. Il y a eu aussi Emmanuel Jeannot et Yves, qui m’ont aidé à
mieux digérer certaines parties de ma recherche.
Et je n’oublie pas l’A0 Te a m, Jacques Briat, Marcelo et Alexandre, ce dernier
a été le témoin de tout le chemin qui j’ai parcouru jusqu’aux dernières nuits. Sans
compter Benhur, le SOS dans les moments du comment peut on faire...
Et il y avait aussi les autres habitants de ce laboratoire : Chassin, Jean Marc,
Gregory, Olivier, Thierry, Gilles, Renaud, Martha, Ekbel, Naddef, Trystram et Briat,
avec eux j’ai eu la chance de discuter dans les couloirs, dans la cafétte ou au cours
des séminaires – de sujets techniques ou bien d’autres. Et, bien sûr, ma joie ne serait
pas complète sans mes copains de bureaux, Alfredo et Christophe : ensemble nous
3Remerciements
avons essayé de trouver les réponses aux problèmes les plus fondamentaux de la
vie, tels que définir l’horaire d’ouverture des fenêtres...
Un grand merci aussi aux autres brésiliens du laboratoire : Andréa, Gustavo,
Paulo et Ricardo, ils ont été en quelque sorte ma famille d’emprunt.
Et je ne peux pas oublier de remercier le soutien très technique de Claudine,
Corinne, Helene, Joëlle, Khadija et Philippe.
Finalement, une fois arrivé à la fin, ma pensée revient à ma famille et à ma
belle famille que nous avons laissées au Brésil. La confiance qu’ils m’ont toujours
accordée a été d’une grande valeur pour aller jusqu’au bout.
À mon père, qui m’a donné mon premier livre.
Et surtout, surtout, à Luciana, qui a eu les plus divers rôles dans ces 4 ans –
d’infirmière à professeur de langue – pendant que je jouais l’étudiant (parfois ma
ladroit...). Si j’ai réussi à remplir le contrat, réel ou moral, avec toute les personnes
qui j’ai citées ci dessus, je le dois avant tout à elle.
4Table des matières
1 Introduction 15
I Ordonnancement dans les environnements de program
mation parallèle : état de l’art 19
2 L’ordonnancement d’une application parallèle 21
2.1 Définition du problème de l’ordonnancement . . . . . . . . . . . . 22
2.1.1 Caractérisation informelle de l’ordonnancement . . . . . . . 22
2.1.2 Visions de l’ordonnancement . . . . . . . . . . . . . . . . . 23
2.1.2.1 L’or côté système . . . . . . . . . 23
2.1.2.2 L’ordonnancement côté application . . . . . . . . 24
2.2 Comment réaliser l’or applicatif . . . . . . . . . . . . 25
2.2.1 Contrôle de la localisation de données . . . . . . . . . . . . 25
2.2.2 Contrôle de la localisation et de l’entrelacement des tâches . 26
2.3 Comment calculer l’ordonnancement applicatif . . . . . . . . . . . 28
2.3.1 Le sous-système de manipulation d’information . . . . . . . 28
2.3.2 Lesous-systèmededécision................. 30
2.3.3 Classification des algorithmes d’ordonnancement . . . . . . 31
2.3.4 Grandeurs caractéristiques des applications . . . . . . . . . 32
2.4 Versuneinterfacegénérique..................... 33
2.5 Conclusion .............................. 35
3 Environnements pour l’ordonnancement 37
3.1 Équilibrage de charge dynamique . . . . . . . . . . . . . . . . . . 37
5Table des matières
3.1.1 GTLB............................. 38
3.1.2 DPC++............................ 39
3.2 Partage de charge dynamique . . . . . . . . . . . . . . . . . . . . . 40
3.2.1 Cid.............................. 41
3.2.2 Cilk.............................. 42
3.2.3 Millipede . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2.4 Jade.............................. 46
3.2.5 Dynamo............................ 47
3.3 Ordonnancement statique . . . . . . . . . . . . . . . . . . . . . . . 48
3.3.1 PYRROS/RAPID....................... 49
3.3.2 MetisetSCOTCH...................... 50
3.4 Conclusion .............................. 51
II Une interface générique pour l’ordonnancement 55
Avant propos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4 Fondements des stratégies d’ordonnancement applicatif 59
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2 Lesstratégiesstatiques........................ 63
4.2.1 Ordonnancements de type partage de charge . . . . . . . . 63
4.2.1.1 Durée des tâches : ordonnancement de Coffman
Graham ...................... 63
4.2.1.2 Prise en compte des communications : ordonnan
cementETF.................... 64
4.2.1.3 Regroupement des c : ordonnan
cementDSC.................... 64
4.2.2 Ordonnancements de type équilibrage de charge . . . . . . 65
4.2.3 Ordonnancement statique et applications régulières . . . . . 66
4.3 Les stratégies dynamiques . . . . . . . . . . . . . . . . . . . . . . 66
4.3.1 Équilibrage de charge dynamique . . . . . . . . . . . . . . 67
4.3.2 Partage de charge dynamique . . . . . . . . . . . . . . . . 68
4.3.3 Limites théoriques des stratégies dynamiques . . . . . . . . 69
6Table des matières
4.3.3.1 Préemptionetperformances............ 70
4.3.3.2 Inefficacité en espace mémoire des stratégies
aveugles...................... 71
4.4 Ordonnancement hybride . . . . . . . . . . . . . . . . . . . . . . . 72
4.5 Fondements communs : l’analyse du flot de données . . . . . . . . 73
4.5.1 Représentation de l’exécution par un graphe . . . . . . . . . 74
4.5.2 Formalisation du problème d’ordonnancement . . . . . . . 77
4.6 Le constructeur de tâches : l’interface entre l’application et l’ordon
nancement............................... 79
4.7 Conclusion .............................. 80
5 L’exécutif : interface entre l’ordonnancement et l’architecture 83
5.1 Outils de base pour la programmation des architectures parallèles . . 83
5.1.1 Différents types d’architecture parallèle . . . . . . . . . . . 84
5.1.2 Exploitation du parallélisme inter-nœuds et communications 85
5.1.3 Recouvrement des temps d’attente par le multithreading .. 85
5.2 Uneabstractiondemachineparalèle................. 86
5.3 Mécanismes pour l’ordonnancement applicatif . . . . . . . . . . . . 87
5.3.1 Manipulation des données