Soutenance mémoire
Les applications de calcul scientifique nécessitent de par leurs spécificités l’utilisation de modèles de programmation adaptés. Ces modèles doivent répondre à deux besoins : faciliter le développement des applications par l’assemblage d’éléments de multiples origines et permettre leur exécution efficace sur des ressources matérielles parallèles et réparties diverses.
Des paradigmes de programmation pour le calcul à haute performance
Plusieurs paradigmes ont été proposés pour faciliter la gestion du grand nombre de flux d’exécution parallèles nécessaire à l’obtention de hautes performances sur les ressources matérielles utilisées dans le cadre du calcul scientifique. Ces paradigmes peuvent être classifiés en deux catégories suivant qu’ils proposent aux flux d’exécution qui composent l’application la vision d’un espace mémoire unique auquel ils accèdent tous ou d’espaces mémoire distincts pour chacun.
Mémoire partagée
L’accès à un espace mémoire commun par les différents flux d’exécution leur permet d’interagir par l’écriture et la lecture de zones de mémoire convenues. La principale difficulté qui apparaît lors de l’utilisation de cette approche concerne la cohérence des données présentes en mémoire. En effet, l’ensemble des opérations qui constituent une transition entre deux états cohérents ne peut être connu que par le logiciel.
Programmation concurrente avec verrous Une première approche consiste à laisser entièrement aux applications la gestion de ce problème en leur fournissant des mécanismes permettant d’assurer l’exclusion de l’accès aux données. Le mécanisme le plus couramment utilisé est constitué par les verrous d’exclusion mutuelle (mutex) qui permettent d’assurer qu’un unique flux d’exécution possède le verrou à un instant donné en bloquant l’exécution des autres flux qui tentent de l’obtenir pendant ce temps.
À l’échelle d’une machine possédant une mémoire matériellement partagée, ces mécanismes sont offerts par le système d’exploitation et accessibles depuis des langages comme le C ou le C++ via des bibliothèques partagées. La norme Posix [36] (Portable Operating System Interface [for uniX]) spécifie notamment l’interface et le comportement d’une bibliothèque de ce type pour les systèmes Unix. Dans d’autres langages, les mécanismes de synchronisation sont intégrés au langage. Par exemple en Java, le concept de moniteur [35] utilisable à l’aide du mot clef synchronized revient à associer un verrou à chaque objet. Au sein de grappes de calcul ou a fortiori de grilles pour lesquelles il n’existe pas de mémoire partagée au niveau physique, des mécanismes logiciels doivent être mis en place pour offrir une abstraction similaire. On parle de mécanismes de mémoire partagée distribués [54] (Distributed Shared Memory – DSM). Au sein de grappes de calcul qui s’appuient sur des réseaux à haute performance certaines mises en œuvre s’intègrent au système d’exploitation. Elles permettent de conserver la même sémantique de cohérence de données qu’une mémoire physiquement partagée. C’est par exemple ce que propose Kernel Distributed Data Management [39] (kDDM). Le coût de cette approche est toutefois relativement élevé et devient totalement prohibitif à l’échelle de la grille.
Pour résoudre ce problème de performances, une approche consiste à s’appuyer sur un transfert d’information plus important de l’application vers le mécanisme de mémoire partagée distribué. C’est par exemple l’approche adoptée par JuxMem [5] que nous avons utilisé dans nos travaux et qui s’appuie sur l’association d’un verrou à chaque zone de mémoire partagée qui doit être acquis avant tout accès aux données.
L’accès à un espace mémoire unique partagé est intéressant pour les applications dans lesquelles il n’est pas possible de répartir les données traitées entre les flux d’exécution. C’est par exemple le cas des applications qui mettent en œuvre des modèles où la notion de localité a peu d’importance. Par exemple pour simuler l’éclairement d’une scène par des techniques de lancer de rayon, une approche consiste à faire gérer par chaque flux d’exécution un ensemble de photons. Les diverses réflexions et réfractions sur les objets impliquent que ces photons peuvent avoir des effets sur l’ensemble de la scène. Chaque flux d’exécution est donc susceptible d’accéder à l’ensemble des données sans qu’il soit possible d’identifier de motif régulier et il n’est donc pas aisé de proposer une répartition des données a priori entre eux. La gestion manuelle des interactions entre divers flux d’exécution qui accèdent à un même espace mémoire peut cependant s’avérer complexe. Elle nécessite d’étudier tous les risques d’inter-blocages qui peuvent apparaître dès que les flux d’exécution sont susceptibles d’acquérir plusieurs verrous à un instant donné. Quand le nombre de flux d’exécution augmente, cette complexité impose rapidement de se tourner vers des modèles offrant des mécanismes plus adapté.
Espace mémoire global partitionné Afin d’éviter de devoir gérer manuellement l’exclusion mutuelle pour les accès au donné, un paradigme intéressant est offert par le concept d’espace d’adressage mémoire global partitionné (Partitioned Global Address Space – PGAS). Ce paradigme propose de laisser les données accessibles depuis l’ensemble des flux d’exécution mais de répartir leur traitement entre les flux lors de phases parallèles. Ce principe se traduit généralement au niveau des langages par la présence de tableaux pouvant être manipulés par ces boucles parallèles. Il s’agit d’appliquer un traitement sur le contenu des tableaux en répartissant les itérations sur les différents flux d’exécutions. Entre chaque section parallèle, une synchronisation assure que tous les flux d’exécution ont terminé leur traitement .
De nombreuses mises en œuvre de ce paradigme ont été proposées. Certaines sont des extensions au langage Fortran comme par exemple High Performance Fortran [34] (HPF) ou Co-array Fortran [46] (CAF ou F–) dont une partie des extensions a été intégrée au standard Fortran95. Un autre langage qui met en œuvre ce paradigme mais qui est basé sur C est Unified Parallel C [27] (UPC). Finalement, OpenMP [51] propose un ensemble d’annotations qui peuvent être ajoutées à des programmes en C, C++ et Fortran. D’autre part, les langages proposés pour répondre au projet de systèmes de calcul à haute productivité (High Productivity Computing Systems – HPCS) de l’agence Defense Advanced Research Projects Agency (Darpa) aux États-Unis que sont X10 [23], Chapel [22] et Fortress [28] s’appuient aussi à divers degrés sur ce paradigme. Ce type d’approche convient bien à des codes où le parallélisme peut être obtenu en répartissant l’exécution des boucles de traitement de données sur les différents cœurs d’exécution des machines. Contrairement à l’utilisation de verrous d’exclusion mutuelle précédemment évoquée, cette approche repose sur une répartition des donnés entre les flux d’exécution mais cette répartition peut changer au cours de l’exécution de l’application C’est par exemple le cas quand les boucles que contient l’application itèrent sur des dimensions différentes de tableaux multi dimensionnels. Les sections parallèles entre deux synchronisations restent cependant généralement relativement courtes et fréquentes. Ce mécanisme est donc bien adapté à des architecture où les coûts de communication entre cœurs d’exécution sont faibles.
Mémoire distribuée
Lorsque chaque flux d’exécution évolue dans son propre espace mémoire, la coopération entre les différents flux pour mettre en œuvre l’application doit s’appuyer sur des échanges explicites d’information. Différents paradigmes offrent des abstractions de plus ou moins haut niveau pour envoyer et recevoir ces messages.
Passage de messages Le niveau d’abstraction le plus bas consiste à exposer directement à l’application la possibilité d’envoyer et de recevoir des messages comme le supporte le réseau sous-jacent. C’est ce que proposent par exemple les sockets Unix en permettant l’envoi de flux d’octets à destination d’une adresse réseau spécifique. À un niveau d’abstraction à peine plus élevé, des bibliothèques comme Parallel Virtual Machine [30] (PVM) et Message Passing Interface [58, 33] (MPI) proposent de masquer les aspects spécifiques au réseau utilisé. Le destinataire de chaque message peut par exemple y être identifié par son rang dans l’ensemble des flux qui forment l’application plutôt que par une adresse réseau. Ces envois peuvent être bloquant, mais ils peuvent aussi être nonbloquants pour leur permettre d’avoir lieu pendant que les calculs continuent.
Ces échanges de messages point à point entre couples de flux d’exécution deviennent vite compliqués à gérer dès que le nombre de flux d’exécution augmente. Leur efficacité dépend de l’architecture des réseaux et leur optimisation doit prendre en compte les capacités des liens qui connectent les différentes ressources, tant en terme de débit que de latence. Afin de faciliter le développement d’applications pouvant s’exécuter efficacement sur un plus grand nombre de ressources, des interactions offrant un plus haut niveau d’abstraction sont nécessaires.
Opérations de communication collective Les opérations de communication collective proposent des schémas d’interaction classiques au sein de groupes de flux d’exécution. Un exemple simple de ce type d’opération est la barrière (barrier ) qui permet une synchronisation entre les flux d’exécution du groupe en assurant qu’ils ont tous atteint un même point dans leur exécution avant que celle-ci reprenne. Les autres opérations permettent des échanges de données au sein du groupe, on peut par exemple citer :
– la diffusion (broadcast) qui consiste à répliquer une donnée d’un flux donné (la racine) vers l’ensemble des membres du groupe ;
– la répartition (scatter ) qui consiste à répartir une donnée de la racine vers tous les membre du groupe ;
– la réduction (reduce) qui peut être considérée comme l’opération inverse de la diffusion ; elle consiste, à partir de données réparties sur tous membres du groupe, à construire une unique donnée sur la racine ; celle-ci est obtenue par l’application d’une opération de réduction pour regrouper plusieurs valeurs en une seule ;
– le rassemblement (gather ) qui peut être considéré comme l’opération inverse de la répartition ; il consiste à rassembler des données réparties sur l’ensemble des membres du groupe vers la racine.
|
Table des matières
INTRODUCTION
1 Introduction
2 Contexte d’étude
2.1 Des paradigmes de programmation pour le calcul à haute performance
2.1.1 Mémoire partagée
2.1.2 Mémoire distribuée
2.1.3 Analyse
2.2 Des modèles de programmation par composition
2.2.1 Les flux de données et de travail
2.2.2 Les modèles de composants logiciels
2.2.3 Les squelettes algorithmiques
2.2.4 Analyse
2.3 modèles de composants pour le calcul à haute performance
2.3.1 Composants parallèles
2.3.2 Partage de données entre composants
2.3.3 Flux de de travail dans les modèles de composants
2.3.4 Squelettes algorithmiques dans les modèles de composants
2.3.5 Analyse
2.4 Conclusion
3 Notre approche pour l’extension de modèles de composants
3.1 Présentation de l’existant
3.1.1 Approche par extension du code de l’exécutif
3.1.2 Approche par compilation dans les composants
3.1.3 Approche par compilation et utilisation de bibliothèque additionnelle
3.1.4 Approche par transformation de l’assemblage à l’exécution
3.1.5 Approche par programmation sous la forme de composants
3.2 Classification
3.3 Analyse
3.3.1 Exhaustivité
3.3.2 Compatibilité entre extensions
3.3.3 Qualité des fonctionnalités
3.3.4 Adaptation à de nouvelles ressources d’exécution
3.3.5 Simplicité de mise en œuvre
3.3.6 Résumé
3.4 Présentation de notre approche
3.4.1 Une approche basée sur le concept de bibliothèque
3.4.2 Fonctionnalités pour le support de bibliothèques dans les modèles de composants
3.4.3 Mise en œuvre de la généricité et des connecteurs dans un modèle de composants
3.5 Conclusion
4 Description de squelettes algorithmiques dans un modèle de composants
4.1 Analyse préliminaire
4.1.1 Analyse de l’existant
4.1.2 Présentation des concepts
4.1.3 Approche de mise en œuvre
4.2 Modèle
4.2.1 Patron de conception pour la modélisation de la généricité
4.2.2 Support à l’exécution
4.3 Validation
4.3.1 Application à SCA : GenericSCA
4.3.2 Mise en œuvre
4.3.3 Exemples d’utilisation de GenericSCA
4.4 Conclusion
5 Introduction du concept de connecteur dans les modèles de composants hiérarchiques
5.1 Analyse préliminaire
5.1.1 Présentation de l’existant
5.1.2 Exemples synthétiques d’application
5.1.3 Discussion
5.2 Un modèle de composants abstrait avec connecteurs
5.2.1 Présentation de l’approche
5.2.2 Modélisation des concepts
5.2.3 Support à l’exécution
5.2.4 Conclusion
5.3 Validation du modèle
5.3.1 Spécialisation de HLCM pour CCM : HLCM/CCM
5.3.2 Mise en œuvre de l’exemple avec interaction par partage de mémoire avec HLCM/CCM
5.3.3 Mise en œuvre de l’exemple avec interaction par appel de méthode avec HLCM/CCM
5.3.4 Analyse
5.4 Conclusion
6 HLCMi : une plate-forme de mise en œuvre de HLCM
CONCLUSION
