These : vers un modèle de programmation parallèle adapté au calcul scientifique

Informations

• Publié par: Shuit
• Nombre de lectures: 111
• Langue: Français

Extrait

INSTITUT NATIONAL POLYTECHNIQUE DE GRENOBLE
THESE
pour obtenir le titre de
DOCTEUR DE L’INPG
Spécialité : “MATHEMATIQUES APPLIQUEES”
présentée et soutenue publiquement
par
Mathias Doreille
le 14 Décembre 1999
Athapascan 1 : vers un modèle de programmation
parallèle adapté au calcul scientifique
Directeur de thèse :
Jean Louis Roch
Denis Trystram
Composition du jury :
Président : Jean Pierre Verjus
Rapporteurs : Patrick R. Amestoy
François Bodin
Examinateurs : Brigitte Plateau
Jean Louis Roch
Jean Roman
Denis Trystram
préparée au Laboratoire de Modelisation et Calcul
et soutenue au Laboratoire Informatique et Distribution
dans le cadre de l’Ecole Doctorale "Mathématiques et Informatique"Remerciements
Je voudrais tout d’abord remercier Jean Pierre Verjus pour m’avoir fait l’honneur de
présider le jury de cette thèse. J’adresse également tous mes remerciements à Patrick
Amestoy et François Bodin pour avoir bien voulu consacrer une part de leur temps à
rapporter sur ces travaux. Leurs remarques ont certainement permis d’améliorer la qualité
de ce document. Merci également à Jean Roman d’avoir accepté de participer au jury de
cette thèse.
Je remercie également Brigitte Plateau, responsable du projet Apache pour avoir bien
voulu participer au jury et pour l’intérêt qu’elle a accordé à Athapascan 1. Merci à Denis
Trystram pour m’avoir accueilli au sein de l’équipe parallélisme.
Et surtout je remercie Jean Louis Roch qui m’a encadré depuis le DEA et qui m’a
permis de poursuivre en thèse. Je ne saurai jamais lui exprimer toute ma gratitude pour
son aide et son soutien durant ces quatre années.
Je tiens également à remercier Bogdan Dumitrescu pour l’aide qu’il m’a apportée
dans la partie numérique de cette thèse ainsi que sa famille pour son accueil chaleureux
en Roumanie.
Merci à tous les relecteurs de ce document qui ont eu à subir mon orthographe souvent
fantaisiste et qui se sont livrés à une chasse aux fautes des plus fructueuses.
Je tiens également à remercier tous les membres de l’équipe parallélisme qui ont fait
de ces années de thèse des années inoubliables. Merci à François (pas de doute, l’adresse
que tu m’a refilée pour le SN n’était effectivement pas loin du paradis sur terre) et Gerson
qui m’a beaucoup appris sur le Brésil (notamment la signification du mot minhoca). J’ai
eu beaucoup de plaisir à travailler avec eux. Merci également à Paulo pour tous les mo
ments inoubliables passés ensemble et à son cousin Gustavo qui m’a supporté pendant la
difficile phase de rédaction. Merci à mes anciens collèges de bureau Alexandre et Benhur,
à Jean Guillaume participant le plus assidu au séminaire du mardi, à Nicolas, au gang
des poseurs de bombes Alfredo, Gregory, Olivier et Christophe, à Titou qui m’a recueilli
sous son toit, m’évitant ainsi de finir sous les ponts, à Andréa, Ekbel, Gilles, Ilan, Mar-
celo, Marta, Pierre-Eric, Renaud, Roberta, Yves. J’en oublie sûrement, je les prie de bien
vouloir m’en excuser.
Enfin je remercie ma famille qui m’a soutenu et encouragé de loin durant ces années
de thèse, et particulièrement mes parents qui ont bien voulu assister à ma soutenance.
3TABLE DES MATIÈRES
Table des matières
1 Introduction 17
2 Modèles de programmation parallèle haut niveau 23
2.1 Lesarchitecturesdemachinesparalèles.................. 23
2.1.1 Les architectures symétriques à mémoire partagée . . . . . . . . 23
2.1.2 Les ares à mémoire distribuée . . . . . . . . . . . . . . . 24
2.1.3 Les réseaux de multiprocesseurs à mémoire partagée . . . . . . . 24
2.2 Programmation bas niveau des architectures parallèles . . . . . . . . . . 25
2.3 Modèles de programmation parallèle haut niveau . . . . . . . . . . . . . 25
2.3.1 Abstraction du réseau de communication : mémoire partagée dis-
tribuée ............................... 26
2.3.2 Abstraction des processeurs : parallélisme applicatif . . . . . . . 28
2.3.3 Description implicite du parallélisme applicatif . . . . . . . . . . 29
2.3.3.1 Extraction du parallélisme à la compilation . . . . . . . 30
2.3.3.2 E du pme à l’exécution . . . . . . . . 30
2.4 Exemples de langages de programmation parallèle haut niveau . . . . . . 32
2.4.1 Cilk................................. 32
2.4.1.1 Modèle de programmation . . . . . . . . . . . . . . . 32
2.4.1.2 Implantation....................... 33
2.4.1.3 Évaluations théoriques et expérimentales . . . . . . . . 33
2.4.1.4 Bilan........................... 34
2.4.2 Jade................................. 34
2.4.2.1 Modèle de programmation . . . . . . . . . . . . . . . 35
2.4.2.2 Implantation....................... 35
2.4.2.3 Évaluations théoriques et expérimentales . . . . . . . . 36
2.4.2.4 Bilan........................... 36
2.5 Conclusion ................................. 37
5TABLE DES MATIÈRES
I Athapascan-1 39
3 Athapascan 1: modèle de programmation 41
3.1 Présentationdumodèledeprogrammation................. 41
3.1.1 Tâches et communications par objets partagés . . . . . . . . . . . 41
3.1.2 Sémantique des accès aux objets partagés . . . . . . . . . . . . . 42
3.1.3 Référence contrainte sur un objet partagé : droit d’accès . . . . . 43
3.1.4 Synchronisations entre tâches créatrices et tâches créées . . . . . 45
3.1.5 Ramase-mietessurlesobjetspartagés.............. 46
3.1.6 Informations pour le système d’exécution . . . . . . . . . . . . . 46
3.2 Exemples.................................. 47
3.2.1 Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.2 Élimination de Gauss par colonnes . . . . . . . . . . . . . . . . . 49
3.3 Discussion sur le modèle de programmation . . . . . . . . . . . . . . . . 50
3.3.1 Programmation par continuation explicite . . . . . . . . . . . . . 51
3.3.2 Structuration des données du programme . . . . . . . . . . . . . 51
3.4 Conclusion ................................. 52
4 Modèle d’exécution d’un programme Athapascan 1 55
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Flot de données comme représentation de l’exécution . . . . . . . . . . . 56
4.3 Modèle d’exécution et flot de données . . . . . . . . . . . . . . . . . . . 58
4.3.1 Calculdescontraintesdeflot.................... 59
4.3.2 Contrôledescontraintesdeflot................... 62
4.3.3 Ordonnancement des tâches du graphe de flot de données . . . . . 64
4.3.4 Conclusion : modèle d’exécution général d’Athapascan 1 . . . . . 64
4.4 Analyse du coût du modèle d’ex . . . . . . . . . . . . . . . . . . 65
4.4.1 Analyse du coût sur une machine à mémoire partagée . . . . . . . 66
4.4.2 Analyse du coût sur une à mémoire distribuée . . . . . . 67
4.4.2.1 Graphe et ordonnancement centralisés . . . . . . . . . 68
4.4.2.2 Ordonnancement pseudo statique du graphe . . . . . . 71
4.5 Conclusion ................................. 73
5 Algorithmes d’ordonnancement d’un graphe de flot de données 75
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2 Modélisationdelamachineparalèle.................... 76
5.2.1 Modèles d’exécution à mémoire partagée . . . . . . . . . . . . . 77
5.2.2 M d’e à mémoire distribuée . . . . . . . . . . . . 77
5.3 Modélisation du programme parallèle : précédence versus flot de données 78
5.3.1 Grandeurs caractéristiques d’un graphe de flot de données . . . . 79
5.3.2 Degré de connaissance du graphe de flot de données à l’exécution 80
6TABLE DES MATIÈRES
5.4 Algorithmes d’ordonnancement . . . . . . . . . . . . . . . . . . . . . . 81
5.4.1 Ordonnancement sans délai de communication . . . . . . . . . . 81
5.4.2 Or avec délai de . . . . . . . . . . 83
5.4.2.1 Recouvrement des communications par des calculs . . 84
5.4.2.2 Réduction des . . . . . . . . . . . . . 85
5.4.2.3 Ordonnancement à la volée avec délai de communication 86
5.5 Un algorithme d’or à la volée avec délai de 86
5.6 Application des algorithmes d’ordonnancement à l’exécution d’un pro-
grammeAthapascan-1 ........................... 88
5.6.1 Machineàmémoirepartagée.................... 89
5.6.2 Machine à mémoire distribuée : mémoire partagée simulée . . . . 89
5.6.3 Machine à mémoire distribuée : modèle de communication de Hwang
et al. ................................ 89
5.6.3.1 Graphe inconnu, coût inconnu . . . . . . . . . . . . . . 90
5.6.3.2 Graph