[PDF] Approches fonctionnelles de la programmation parallèle et des méta

View - Download Approches fonctionnelles de la programmation parallèle et des méta

Previous PDF

Next PDF

Université Paris 12 - Val-de-Marne U.F.R. de sciences Numéro attribué par la bibliothèque : .............

Thèse

pour obtenir le grade de Docteur de l'université Paris 12 - Val-de-Marne discipline : Informatique présentée et soutenue publiquement par

Frédéric GAVA

le 12 décembre 2005

Approches fonctionnelles

de la programmation parallèle et des méta-ordinateurs.

Sémantiques, implantations et certification.

Composition du jury

Président :Thierry PRIOLIRISA-INRIA Rennes

Rapporteurs :Murray COLEUniv. of Edinburgh

Walter DOSCHUniv. of Lübeck

Examinateurs :Jocelyn SÉROTUniv. de Clermont-Ferrand

Anatol SLISSENKOUniv. de Paris 12 - Val-de-Marne

Directeur :Frédéric LOULERGUEUniv. d'Orléans

RemerciementsJe voudrais remercier Thierry PRIOLde m'avoir fait l'honneur de présider mon jury. Je veux également

exprimer toute ma gratitude à Murray COLEet Walter DOSCHpour avoir accepté d'être rapporteurs de

cette thèse. Je remercie aussi vivement Jocelyn SÉROTet Anatol SLISSENKOqui me font le plaisir de

participer au jury.

Frédéric LOULERGUEm'a encadré durant toutes ces années de travail. Je lui suis très reconnaissant des

conseils qu'il m'a prodigués, de son soutien sans faille et de sa patience lors de mes moments de découra-

gement. Ces années de recherches "acharnées» resteront indissociables de ses nombreux méls.

Je ne voudrais pas oublier tous les membres du projet CARAMLdont l'aide m'a été très précieuse.

Je tiens également à remercier tous les membres du Département d'Informatique et particulièrement Flore

TSILA, Franck POMMEREAU, Elisabeth PELZ,Fabrice MOURLINainsi quetous ceuxavecqui j'aiparticipé

à des enseignements.

Merci à Mathieu for its help. J'espère le lui rendre. Merci à Papa pour son abnégation dans la correction

aurthografik de ce mémoire.

Merci à tout les copains, copines, compères et comparses : Antonin et Marion, Manu, Guillaume et Hélène,

Anthonyet Flavie, Manue, Christophe et Raluca, Julien, Louis, Steeve et Magalie, Pierre, June, Matthieu et

Laurence,Alexandre,Cécile, Pierre, Aurélien et tous les autres que j'aurais pu oublier (ne soyez pas vexés).

Même si cette énumeration ressemble plus à un catalogue de prénoms, ils (ou elles) se reconnaîtront.

Je remercie aussi toute ma famille pour son soutien indéfectible (merci Tonton pour l'hôtel pas trop cher

dans le 13ième!). Merci Môman pour tes petits plats et ton pain d'épices...

Je tiens à remercier tout particulièrement Pazzo qui m'a accompagné durant ces trois années de "labeur» et

qui ne pourrapas ronronnerdu résultat final. Tu me manques...Merci à Lulu pournos prochainesaventures.

Merci à tous ceux que j'ai pu oublier et que je ne saurais citerici. Je tiens à saluer la bonne idée de la

première cellule vivante de se diviser et qui, d'une certaine manière, a permis que j'en sois à écrire ces

quelques lignes aujourd'hui.

Ce travail ne serait rien sans les "allez zou, au boulot!» d'une personne dont je ne citerais point le nom. Je

lui suis gré de ne pas m'en vouloir si je lui dis...

Sommaire

1 Introduction1

1.1 Langages pour la programmation parallèle . . . . . . . . . . . .. . . . . . . . . . . . . . 1

1.1.1 Approches extrêmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 1

1.1.2 Approches intermédiaires . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 2

1.2 Le projet CARAMLet les travaux menés . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.1 Sémantiques et certification . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 4

1.2.2 Extensions et bibliothèque de structures de données .. . . . . . . . . . . . . . . . 5

1.2.3 Opérations globalisées . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 7

1.3 Plan du mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 7

1.3.1 Sémantiques et certification . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 8

1.3.2 Extensions et bibliothèque de structures de données .. . . . . . . . . . . . . . . . 8

1.3.3 Opérations globalisées . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 8

2 Programmation fonctionnelle BSP9

2.1 Bulk-Synchronous Parallelism . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 9

2.1.1 Architecture parallèle BSP . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 9

2.1.2 Modèle d'exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 10

2.1.3 Modèle de coût . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 11

2.2 Processus explicites + BSP = mode direct?=SPMD . . . . . . . . . . . . . . . . . . . . . 11

2.3 Bulk-Synchronous Parallel ML . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 12

I Sémantiques et certification15

3 Sémantiques opérationnelles de BSML17

3.1 Introduction auλ-calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1.1 Définition duλ-calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1.2 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 19

3.1.3 Substitutions explicites . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 20

3.1.4 Langages fonctionnels et sémantiques opérationnelles . . . . . . . . . . . . . . . 21

3.2 Sémantiques de BSML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 22

3.2.1 Syntaxe d'un mini-langage parallèle applicatif . . . .. . . . . . . . . . . . . . . 22

3.2.2 Sémantique naturelle . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 24

3.2.3 Sémantique à "petits pas» . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 26

3.2.4 Sémantique distribuée . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 34

3.2.5 Imbrication de vecteurs parallèles . . . . . . . . . . . . . . .. . . . . . . . . . . 38

3.3 Comparaison avec les anciens calculs . . . . . . . . . . . . . . . .. . . . . . . . . . . . 39

3.A Annexe : preuves des lemmes . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 40

3.A.1 Déterminisme de?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.A.2 Confluence forte de?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.A.3 Équivalence entre?et?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.A.4 Confluence forte de?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.A.5 Équivalence entre?et?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4 Une machine abstraite BSP pour BSML49

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 49

iii ivSOMMAIRE

4.2 Définition et correction d'une machine abstraite . . . . . .. . . . . . . . . . . . . . . . . 49

4.2.1 Définition d'une machine abstraite . . . . . . . . . . . . . . . .. . . . . . . . . . 50

4.2.2 Retour sur les substitutions . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 50

4.2.3 Correction d'une machine abstraite . . . . . . . . . . . . . . .. . . . . . . . . . 51

4.3 Définition d'une BSP-CAM . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 52

4.3.1 Machine abstraite CAM . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 52

4.3.2 Transition de la CAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 53

4.3.3 De la CAM à la BSP-CAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 54

4.4 Compilation de BSML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 55

4.4.1 Termes séquentiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 55

4.4.2 Primitives parallèles . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 55

4.4.3 Correction de la BSP-CAM . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 57

4.4.4 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 59

4.A Annexe, preuves des conditions . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 61

5 Bibliothèque de programmes BSML65

5.1 Fonctions BSP classiques avec la BSMLlib . . . . . . . . . . . . .. . . . . . . . . . . . 65

5.1.1 Exemples de fonctions asynchrones . . . . . . . . . . . . . . . .. . . . . . . . . 65

5.1.2 Fonctions d'échange total . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 66

5.1.3 Fonctions pour la diffusion d'une valeur . . . . . . . . . . .. . . . . . . . . . . . 67

5.1.4 Fonctions pour le calcul des préfixes . . . . . . . . . . . . . . .. . . . . . . . . . 71

5.1.5 Exemple de fonctions destructurant un vecteur de listes . . . . . . . . . . . . . . . 76

5.2 Implantation de la bibliothèque BSMLlib . . . . . . . . . . . . .. . . . . . . . . . . . . 78

5.2.1 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 78

5.2.2 Une implantation modulaire . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 78

5.2.3 Prévision des performances . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 80

6 Certification de programmes BSML83

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 83

6.2 Présentation succinte deCoq. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

6.2.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 84

6.2.2 Assistant de preuves . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 84

6.2.3 Langage de programmation . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 85

6.2.4Coqet BSML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

6.3 Formalisation des primitives BSML . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 88

6.3.1 Axiomes et paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 88

6.3.2 Cohérence et acceptation de l'ajout des axiomes BSML .. . . . . . . . . . . . . . 90

6.4 Développements de fonctions certifiées . . . . . . . . . . . . . .. . . . . . . . . . . . . 90

6.4.1 Fonction certifiée utilisant unmkpar. . . . . . . . . . . . . . . . . . . . . . . . 90

6.4.2 Fonction certifiée utilisant unapply. . . . . . . . . . . . . . . . . . . . . . . . . 92

6.4.3 Fonction de communication certifiée utilisant unproj. . . . . . . . . . . . . . . 93

6.4.4 Composition de vecteurs parallèles . . . . . . . . . . . . . . .. . . . . . . . . . 97

6.5 Création d'une bibliothèque BSMLlib certifiée . . . . . . . .. . . . . . . . . . . . . . . 99

6.5.1 Echange total . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 100

6.5.2 Rassemblement d'un vecteur parallèle . . . . . . . . . . . . .. . . . . . . . . . . 100

6.5.3 Demander et recevoir des valeurs d'autres processeurs . . . . . . . . . . . . . . . 101

6.5.4 Diffusion en 2 phases . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 102

6.5.5 Réduction directe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 103

6.5.6 Décalage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 104

6.5.7 Fonction de tri parallèle . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 104

6.5.8 Extraction de code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 105

6.5.9 Autres applications possibles . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 106

6.A Code de l'extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 107

vSOMMAIRE II Extensions et bibliothèque de structures de données 111

7 Compositions parallèles113

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 114

7.2 La superposition parallèle . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 114

7.2.1 Présentation informelle . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 115

7.2.2 Modèle de coût informel . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 116

7.2.3 Choix d'une stratégie pour l'évaluation des super-threads . . . . . . . . . . . . . . 116

7.3 Sémantiques pour la superposition . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 117

7.3.1 Sémantiques sans super-threads . . . . . . . . . . . . . . . . . .. . . . . . . . . 117

7.3.2 Syntaxe des super-threads . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 119

7.3.3 Nouvelle forme de sémantique . . . . . . . . . . . . . . . . . . . . .. . . . . . . 119

7.3.4 Règles génériques et parallèles . . . . . . . . . . . . . . . . . .. . . . . . . . . . 120

7.3.5 Règles de la superposition . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 122

7.3.6 Contextes d'évaluation . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 122

7.3.7 Communications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 123

7.3.8 Nouvelle sémantique . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 123

7.4 Implantation de la superposition parallèle . . . . . . . . . .. . . . . . . . . . . . . . . . 124

7.4.1 Nouvelle implantation des primitives BSML . . . . . . . . .. . . . . . . . . . . 125

7.4.2 Fonctions nécessaires à l'implantation de la superposition . . . . . . . . . . . . . 126

7.5 Implantation de la juxtaposition parallèle . . . . . . . . . .. . . . . . . . . . . . . . . . . 128

7.5.1 Présentation informelle . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 128

7.5.2 Modèle de coût . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 129

7.5.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .129

7.5.4 Implantation avec la superposition . . . . . . . . . . . . . . .. . . . . . . . . . . 129

7.6 Exemples et expériences . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 131

7.6.1 Exemple d'utilisation . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 131

7.6.2 Expériences du calcul des préfixes . . . . . . . . . . . . . . . . .. . . . . . . . . 132

7.A Preuves des théorèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 135

7.A.1 Confluence forte de?→. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

7.A.2 Équivalence de?→et de?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

8 Structures de données parallèles137

8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 137

8.2 Description des modules en OCaml . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 138

8.2.1 Définition des structures . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 138

8.2.2 Définition des signatures . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 139

8.2.3 Abstraction des structures . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 139

8.3 Implantation des dictionnaires . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 141

8.3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 141

8.3.2 Implantation des opérations classiques . . . . . . . . . . .. . . . . . . . . . . . . 142

8.3.3 Itérer sur un dictionnaire . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 143

8.4 Rebalancement de la localisation des données . . . . . . . . .. . . . . . . . . . . . . . . 144

8.5 Implantation des ensembles . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 145

8.5.1 Transformations d'un vecteur parallèle d'ensembles. . . . . . . . . . . . . . . . 146

8.5.2 Définitions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 146

8.5.3 Union de deux ensembles . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 146

8.5.4 Intersection de deux ensembles . . . . . . . . . . . . . . . . . . .. . . . . . . . 148

8.5.5 Différence de deux ensembles . . . . . . . . . . . . . . . . . . . . .. . . . . . . 150

8.6 Implantation des Piles et Files . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 152

8.7 Exemple d'une application scientifique . . . . . . . . . . . . . .. . . . . . . . . . . . . . 154

8.A Preuves des opérations ensemblistes . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 158

8.A.1 Preuves des opérations de l'union . . . . . . . . . . . . . . . . .. . . . . . . . . 158

8.A.2 Preuves des opérations de l'intersection . . . . . . . . . .. . . . . . . . . . . . . 159

8.A.3 Preuves des opérations de la différence . . . . . . . . . . . .. . . . . . . . . . . 161

9 Mémoires externes en BSML165

viSOMMAIRE

9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 165

9.2 Mémoires externes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 166

9.2.1 Modèle EM-BSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 166

9.2.2 Présentation d'algorithmes existant en mémoires externes . . . . . . . . . . . . . 167

9.3 Mémoires externes en BSML . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 169

9.3.1 Rappel des E/S en OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 169

9.3.2 Problèmes des E/S OCaml en BSML . . . . . . . . . . . . . . . . . . . .. . . . 169

9.3.3 Solution proposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 170

9.3.4 Nouveau modèle, le modèle EM-BSP

2. . . . . . . . . . . . . . . . . . . . . . . 171

9.3.5 Nouvelles primitives . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 173

9.4 Sémantique dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 175

9.5 Coût des nouvelles primitives et expérimentations . . . .. . . . . . . . . . . . . . . . . . 178

9.5.1 Coût EM

2-BSP des primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

9.5.2 Implantation des primitives . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 181

9.5.3 Exemple d'utilisation de nos primitives . . . . . . . . . . .. . . . . . . . . . . . 182

9.5.4 Expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 185

9.A Preuve du théorème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 186

III Opérations globalisées189

10 ML parallèle minimalement synchrone191

10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 191

10.2 Modèle de coût et d'exécution . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 192

10.3 Langage MSPML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 193

10.3.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 194

10.4 Sémantiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 195

10.4.1 Syntaxe d'un mini langage parallèle applicatif . . . .. . . . . . . . . . . . . . . . 195

10.4.2 Sémantique naturelle . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 197

10.4.3 Sémantique à "petits pas» . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 200

10.4.4 Sémantique distribuée . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 207

10.5 Implantation de MSPML . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 211

10.5.1 ModuleTcpip. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

10.5.2 ModuleMspml. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

10.6 Exemple et expériences . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 212

10.6.1 Réduction et préfixe parallèles . . . . . . . . . . . . . . . . . .. . . . . . . . . . 212

10.6.2 Implantation du patron algorithmique "Diffusion» .. . . . . . . . . . . . . . . . 214

10.6.3 Plus petits éléments . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 215

10.6.4 Expériences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 215

10.A Annexe, preuves des lemmes . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 218

10.A.1 Confluence forte de?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218

10.A.2 Confluence forte de?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

10.A.3 Équivalence entre?et?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

11 Programmation de méta-ordinateurs225

11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 225

11.2 DMM, un modèle pour le méta-calcul départemental . . . . .. . . . . . . . . . . . . . . 225

11.3 ML pour le méta-calcul départemental . . . . . . . . . . . . . . .. . . . . . . . . . . . . 227

11.3.1 Noyau de primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 227

11.3.2 Premiers exemples asynchrones . . . . . . . . . . . . . . . . . .. . . . . . . . . 228

11.4 Sémantique dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 229

11.4.1 Syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 229

11.4.2 Règles de réduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 231

11.4.3 Règles de contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 233

11.5 Exemples et expérimentations . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 235

11.5.1 Diffusion d'une valeur dans un méta-ordinateur . . . .. . . . . . . . . . . . . . . 236

viiSOMMAIRE

11.5.2 Calcul des préfixes départementaux . . . . . . . . . . . . . . .. . . . . . . . . . 237

11.5.3 Implantation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 238

11.5.4 Expériences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 238

11.A Preuve de la confluence forte de?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

12 Travaux connexes243

12.1 Modèles et langages parallèles de "haut niveau» . . . . . .. . . . . . . . . . . . . . . . . 243

12.1.1 Modèles de parallélisme structuré . . . . . . . . . . . . . . .. . . . . . . . . . . 243

12.1.2 Modèles dérivés de BSP . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 245

12.1.3 Langages et bibliothèques de "haut niveau» . . . . . . . .. . . . . . . . . . . . . 245

12.1.4 Sémantiques et certification de programmes BSP . . . . .. . . . . . . . . . . . . 247

12.1.5 Structures de données . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 250

12.2 Modèles et langages pour le méta-calcul . . . . . . . . . . . . .. . . . . . . . . . . . . . 250

12.2.1 Sémantiques de la désynchronisation des barrières BSP . . . . . . . . . . . . . . . 250

12.2.2 Modèles pour le méta-calcul . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 251

12.2.3 Langages pour le méta-calcul . . . . . . . . . . . . . . . . . . . .. . . . . . . . 253

13 Conclusion et perspectives255

13.1 Apports de cette thèse . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 255

13.1.1 Partie 1 : Sémantiques, sûreté, implantation et certification . . . . . . . . . . . . . 255

13.1.2 Partie 2 : Opérations de multi-traitement, structures de données parallèles et en-

trées/sorties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .256

13.1.3 Partie 3 : Opérations asynchrones et globalisées . . .. . . . . . . . . . . . . . . . 259

13.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 260

13.2.1 Le projet PROPAC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260

13.2.2 BSML : applications et nouvelles implantations . . . .. . . . . . . . . . . . . . . 262

13.2.3 Langages pour le méta-calcul et les grilles de calcul. . . . . . . . . . . . . . . . . 262

Publications265

Bibliographie267

1Introduction

C ERTAINSproblèmes, comme la simulation de phénomènes physiques ou chimiques de grande taille ture d'algorithmes pour ce type de machines demeure plus difficile que pour celles strictement

séquentielles et la conception de langages adaptés est un sujet de recherche actif nonobstant la fréquente

utilisation de la programmation concurrente.

En effet, la conception d'un langage de programmation est lerésultat d'un compromis qui détermine

l'équilibre entre les différentes qualités du langage telles que l'expressivité, la sûreté, la prédiction des per-

formances, l'efficacité ou bien la simplicité de la sémantique. Dans le cas de langages pour le parallélisme,

les propriétés ainsi obtenues diffèrent considérablementselon les choix effectués.

Afin de préciser les termes de ces choix, nous allons tout d'abord faire un rapide parcours des solutions

existantes pour la programmation de machines parallèles. Puis, nous préciserons quels ont été ces choix

dans le contexte des recherches qui ont précédé le présent travail. Le cadre ayant été posé, nous aborderons

alors les motivations qui ont présidé aux recherches présentées dans ce tapuscrit.

1.1 Langages pour la programmation parallèle

Nous examinons dans un premier temps, deux approchesextrêmes : la programmationconcurrenteet la pa-

rallélisation automatique; puis, dans un second temps, desapproches intermédiaires : le data-parallélisme,

les patrons algorithmiques et enfin les extensions non-concurrentesde langages fonctionnels.

1.1.1 Approches extrêmes

Programmation concurrente.L'approche la plus répandue pour la programmation parallèles est la

programmation concurrente. Elle implique la combinaison d'un langage séquentiel (usuellement C ou For-

tran) avec une bibliothèque de communications par passage de messages (à la base avec deux opérations,

l'envoi d'un message et sa réception) comme MPI [245] (Message Passing Interface) ou PVM [114] (Pa-

rallel Virtual Machine).

Ce style de programmation est évidemment très expressif carle programmeur définit non seulement

l'algorithme parallèle mais aussi les détails de la réalisation des communicationsviades protocoles. Cette

liberté va de pair avec une difficulté de mise au point des programmes. La complexité des programmes

devienttelle, qu'ilest souventimpossiblede prévoircorrectementleurstemps de calcul. De plus, les risques

d'indéterminismes et d'interblocages rendent la validation formelle des programmes trop complexe [7] et

gêneleurportabilité.Notonsqueces problèmesdemeurentnéanmoinsdansles langagesconcurrentsde plus

haut niveau comme Jocaml [72, 120] ou Concurrent ML [217] où,en plus, des problèmes d'implantation

des langages se présentent (leπ-calcul synchrone [210] est, par exemple, considéré comme impossible à

implanter efficacement). Parallélisation automatique.Danslespectredessolutionspossiblesauxproblèmesdegrandestailles,

la programmationséquentielle,viaune parallélisation automatique du code, a été longuement étudiée. Bien

qu'idéale pour sa facilité d'écriture, elle est surtout limitée à l'utilisation de tableaux et de boucles [55],

ce qui oblige le compilateur à découvrir le parallélisme implicite et à produire le meilleur programme

parallèle possible à partir d'une spécification qui est parfois, dans le pire des cas, strictement séquentielle.

Le problème étant, en général, indécidable, des heuristiques sont utilisées. Mais vu la subtilité de certains

algorithmes parallèles [156], cette méthode ne peut être utilisée de façon générale et satisfaisante.

1

2CHAPITRE 1. INTRODUCTION

On retrouve aussi cette approche dans la programmation fonctionelle avec notamment la réduction en

parallèle de graphes [2]. Ces systèmes n'expriment pas directement les algorithmes parallèles et ne per-

mettent pas la prévision des temps d'exécution car les processus physiques y sont implicites et la stratégie

d'évaluation parallèle n'est pas décrite par la sémantique. De plus, leur extensibilité à un grand nombre de

processeursest limitée par la structure de graphequi est partagéeet par l'utilisation d'unglaneur de cellules

parallèle (aussi appelé "ramasse miettes»;Garbage Collectoren anglais). Enfin, et cela quel que soit le

langage séquentiel employé, le coût de l'administration des tâches (qui sont créées dynamiquement) peut

être largement supérieur à celui de l'exécution proprementdite des tâches lorsque celles-ci sont trop petites

(problème dit degranularité).

Il paraît donc indispensable de mettre au point des méthodesde programmation parallèle plus générales

que la parallélisation automatique du code (ou que de la réduction parallèles de graphes) mais aussi plus

simples que la programmation concurrente. La conception d'un langage parallèle est alors un compromis

entre la possibilité pour le programmeur de contrôler les aspects nécessaires à une prédiction précise des

performances (mais sans rendre les programmes trop difficiles à écrire) et l'abstraction de ces fonctionna-

lités qui sont nécessaires à la simplification de l'écrituredes programmes parallèles (mais sans les rendre

inefficaces).quotesdbs_dbs30.pdfusesText_36

[PDF] inrap congo

[PDF] inrap congo brazzaville

[PDF] h1n1 grippe aviaire

[PDF] grippe h1n1 2016

[PDF] grippe h1n1 symptomes

[PDF] symptome grippe h1n1 chez l'homme

[PDF] grippe a symptomes

[PDF] grippe b

[PDF] grippe h1n1 2017

[PDF] grippe porcine h1n1

[PDF] cit seconde

[PDF] si seconde

[PDF] dissertation passion

[PDF] carte bruges pdf

[PDF] texte argumentatif exemple sur le sport