Cette thèse définit un modèle d'exécution de programmes parallèles basés sur l'appel de procédures exécutées à distance par des processus légers. L'équivalence de deux exécutions dans le modèle procédural parallèle sert de guide pour la construction d'un mécanisme de réexécution déterministe pour le noyau exécutif Athapascan-0a. Le modèle étudié n'est pas spécifique à Athapascan et peut s'appliquer à d'autres environnements de programmation. Les modèles concernés utilisent des ressources partagées actives. Dans cette famille de modèles se trouvent, entre autres, les modèles d'appels de procédures à distance, les modèles Clients-Serveurs et les modèles à objets actifs. Le modèle exploite des événements abstraits composés d'événements de plus bas niveau. Le nombre d'événements enregistrés est ainsi réduit sans surcoût de calcul lié à cette réduction. Le mécanisme de réexécution déterministe réalisé pour Athapascan-0a est validé expérimentalement. Une méthodologie de mesures systématiques est appliquée pour mesurer le surcoût en temps dû à l'enregistrement des traces nécessaires à la réexécution. Les mesures des temps d'exécution s'effectuent pour des programmes parallèles synthétiques générés à partir de modèles d'algorithmes. Les surcoûts mesurés montrent une faible intrusion du mécanisme d'enregistrement des traces.

De nombreuses méthodes de calcul numérique parallèle sont développées pour utiliser les super-ordinateurs d'aujourd'hui, mais ces méthodes utilisent rarement les mécanismes de régulation et perdent en efficacité sur des problèmes non structurés. En particulier, la simulation numérique, par dynamique moléculaire (DM), du mouvement des atomes des protéines dans les structures biologiques est un de ces problèmes irréguliers qui demande beaucoup de puissance de calcul. Cette thèse, à travers la réalisation d'un programme parallèle de DM opérationnel pour l'étude des protéines, s'intéresse à montrer l'apport des processus légers pour la parallélisation de ce type d'application. Ce travail s'inscrit dans le projet INRIA-IMAG APACHE de réalisation du support d'exécution ATHAPASCAN pour les applications parallèles irrégulières et en collaboration avec le laboratoire BMC du CEA-Grenoble. Après une introduction sur la parallélisation d'applications, nous présentons les concepts de base de la parallélisation par des processus légers et des échanges de messages. La deuxième partie du document propose une synthèse des éléments du modèle de DM pour l'étude des protéines et présente la méthode du rayon de coupure pour l'approximation des forces. Dans la suite nous proposons une parallélisation de cette méthode du rayon de coupure par décomposition du domaine de simulation. Nous étudions plusieurs stratégies de placement des calculs afin de trouver le meilleur compromis entre l'équilibre de charge et la minimisation des communications. Puis nous montrons comment la multiprogrammation permet de recouvrir les communications par des calculs. Enfin nous terminons en proposant un mécanisme d'équilibre dynamique de la charge de calcul. De nombreuses mesures sur le IBM-SP1 et le CRAY-T3E sont présentées et montrent l'extensibilité de nos algorithmes parallèles.

Cette thèse s'est déroulée au sein du projet APACHE (CNRS-INPG-INRIA-UJF) dont l'objectif est l'étude de l'ensemble des aspects liés à la mise en oeuvre efficace et portable d'applications irrégulières et dont les études sont concrétisées par l'environnement Athapascan. Dans l'environnement Athapascan le «débogage pour les performances» est basé sur le traçage logiciel des exécutions des applications parallèles suivi de l'analyse des traces et de la visualisation des exécutions tracées. L'objectif de la thèse était de fournir aux programmeurs un outil de visualisation les aidant à identifier les "erreurs de performances" de leurs programmes en leur donnant une représentation aussi claire que possible de l'exécution de ces programmes. La principale contribution de la thèse est la conception et la réalisation d'un outil appelé Pajé combinant les trois propriétés essentielles d'interactivité, d'extensibilité et d'aptitude au passage à l'échelle. L'extensibilité permet de prendre en compte l'absence de stabilisation des modèles de programmation parallèles et d'offrir la possibilité d'ajouter à Pajé des visualisations non envisagées lors de sa conception. Elle est assurée par une architecture en graphe de modules génériques, communiquants par des protocoles bien spécifiés. L'interactivité donne au programmeur le contrôle sur la visualisation par des actions telles que déplacement dans le temps ou inspection du contenu des objets visualisés, etc. Pour limiter le volume de données qu'elle implique de conserver en mémoire, une structure de données appelée fenêtre de visualisation a été définie ainsi que les algorithmes permettant de la faire glisser efficacement dans le temps. L'aptitude au passage à l'échelle est liée à la capacité de représenter un nombre potentiellement important d'objets graphiques (processus légers, communications, tâches, etc...) évoluant dynamiquement. Elle est essentiellement assurée en facilitant la visualisation à différents niveaux d'abstraction, en sorte que le passage d'un niveau à un autre simule une action de zoom.

Dans leur présentation traditionnelle, les systèmes à mémoire distribuée virtuellement partagée (MVP, en anglais DSM) permettent à des processus de partager un espace d'adressage commun selon un modèle de cohérence fixé : cohérence séquentielle, à la libération, etc. Les pro- cessus peuvent habituellement être distribués sur des noeuds physiquement distincts et leurs in- teractions par la mémoire commune sont implémentées (de manière transparente) par la MVP, en utilisant une bibliothèque de communication. Dans la plupart de travaux dans ce domaine, il est sous-entendu que la MVP et l'architecture sous-jacente sont données. Le programmeur doit alors adapter son application à ce cadre fixe, afin d'obtenir une exécution efficace. Cette approche impose des limitations statiques et ne permet pas de comparer des approches alternatives. La contribution de cette thèse consiste à proposer une plate-forme générique d'implémentation et d'expérimentation appelée DSM-PM2, qui permet de développer et d'optimiser conjointement les applications distribuées et le(s) protocole(s) de cohérence de la MVP sous-jacente. Cette plate-forme, implémentée entièrement au niveau logiciel, est portable sur plusieurs architectures de grappes hautes performances. Elle fournit les briques de bases nécessaires pour implémenter et évaluer une large classe de protocoles de cohérence multithreads dans un cadre unifié. Trois mo- dèles de cohérence sont actuellement supportés : la cohérence séquentielle, la cohérence à la libéra- tion et la cohérence Java. Plusieurs études de performance ont été effectuées à l'aide d'applications multithreads pour l'ensemble des protocoles proposés, sur différentes plates-formes. DSM-PM a été validé par son utilisation en tant que cible d'un système de compilation Java pour des grappes appelé Hyperion.

En informatique, la notion de processus léger ou thread est désormais omniprésente. En effet, les threads permettent à un programme d'une part d'exploiter pleinement les ordinateurs multiprocesseurs et d'autre part d'exprimer son parallélisme intrinsèque. Dans le domaine du calcul hautes performances, les threads permettent de recouvrir des communications ou plus généralement des entrées/sorties avec du calcul. Ils permettent aussi aux divers composants de l'application de progresser indépendamment les uns des autres, ce qui est nécessaire avec l'utilisation d'environnements de programmation toujours plus complexes comme MPI ou Corba.<br /><br />Mes travaux avaient pour objectif principal d'aboutir à la conception d'une bibliothèque de threads performante sur une vaste gamme d'architectures (machines mono ou multiprocesseurs, technologie "multithreading simultané", ...) et capable d'offrir les fonctionnalités demandées par les programmes de calcul hautes performances. Dans un premier temps, j'ai proposé une extension du modèle des Scheduler Activations pour le noyau Linux permettant d'être réactif aux interruptions dans une bibliothèque de threads utilisateurs. J'ai ensuite étendu ce mécanisme de manière à unifier la gestion des interruptions et des scrutations dans un environnement multithreadé. Enfin, j'ai proposé un mécanisme de prise de traces permettant de reconstituer précisément le déroulement d'un programme multithreadé, y compris lorsque l'ordonnancement est à deux niveaux.<br /><br />Ces travaux ont été implémentés au sein du logiciel PM2. La bibliothèque Marcel offre des threads performants sur une vaste gamme de processeurs et de systèmes en restant suffisamment flexible pour permettre aux applications qui le nécessitent de diriger précisément l'ordonnancement de leurs threads. Les applications peuvent être tracées de manière à pouvoir reconstituer et observer leur comportement précis. La trace obtenue peut être convertie au format du logiciel Pajé qui permet alors de visualiser graphiquement le déroulement de l'application.

L'objectif des travaux présentés est la conception etl'implémentation d'outils d'aide à la mise au point d'applications parallèles, pour en éliminer les erreurs de logique et de performance. Les plateformes parallèles cibles sont des grappes de plusieurs dizaines de noeuds multiprocesseurs. Les programmes parallèles considérés mettent en oeuvre un réseau de fils d'exécution \textit((threads)) évoluant dynamiquement et qui communiquent par mémoire commune à l'intérieur d'un même noeud et par passage de message entre deux noeuds distincts. Deux problèmes sont abordés principalement. Tout d'abord, la recherche d'erreurs fugitives provenant de l'indéterminisme du modèle de programmation est traitée par l'adaptation de méthodes de ré-exécution déterministe à ce modèle. L'autre problème est la complexité de la dynamique des exécutions de programmes parallèles, qui rend difficile leur compréhension et l'identification des erreurs. Un outil de visualisation interactif, «scalable» et extensible, basé sur l'analyse de traces d'exécution, permet de faciliter cette compréhension. Les difficultés que pose l'intégration des outils développés dans un environnement cohérent de mise au point sont ensuite identifiées et des solutions sont esquissées.

Les applications de simulation numérique nécessitant la résolution de problèmes d'Équations aux Dérivées Partielles (EDP) sont souvent parallélisées à l'aide d'une méthode de décomposition de domaine. Ces méthodes mathématiques sont naturellement ouvertes au parallélisme, cependant leur exploitation efficace sur les machines parallèles devient difficile lorsque les applications ont un comportement irrégulier. C'est le cas par exemple lorsque les problèmes mathématiques sont résolus dans des domaines géométriques complexes ou lorsque l'on utilise des techniques d'adaptation de maillage. Une technique de programmation se prêtant bien à la mise en oeuvre d'applications irrégulières est la multiprogrammation basée sur des réseaux de processus légers communicants. Dans cette thèse nous réalisons une étude approfondie de l'apport de ce paradigme de programmation à la résolution de problèmes d'EDP par des méthodes de décomposition de domaine et nous montrons qu'il existe une écriture algorithmique générique de celles-ci. Une de nos principales contributions réside dans la conception et réalisation d'un harnais informatique, appelé Ahpik, permettant une programmation aisée d'applications reposant sur les méthodes de décomposition de domaine. Ce harnais fournit un support générique adaptable à de nombreuses méthodes mathématiques, qu'elles soient synchrones ou asynchrones, avec ou sans recouvrement. Une conception orientée objet permet d'encapsuler les détails de gestion des processus légers et des communications, ce qui facilite l'implantation de nouvelles méthodes. Nous avons utilisé l'environnement Ahpik dans le cadre de la résolution de problèmes d'EDP classiques et notamment pour un problème en mécanique de fluides de grande taille.

Dans cette thèse de doctorat, nous étudions des algorithmes et des implémentations pour accélérer la résolution de systèmes linéaires denses en utilisant des architectures composées de processeurs multicœurs et d'accélérateurs. Nous nous concentrons sur des méthodes basées sur la factorisation LU. Le développement de notre code s'est fait dans le contexte de la bibliothèque MAGMA. Tout d'abord nous étudions différents solveurs CPU/GPU hybrides basés sur la factorisation LU. Ceux-ci visent à réduire le surcoût de communication dû au pivotage. Le premier est basé sur une stratégie de pivotage dite "communication avoiding" (CALU) alors que le deuxième utilise un préconditionnement aléatoire du système original pour éviter de pivoter (RBT). Nous montrons que ces deux méthodes surpassent le solveur utilisant la factorisation LU avec pivotage partiel quand elles sont utilisées sur des architectures hybrides multicœurs/GPUs. Ensuite nous développons des solveurs utilisant des techniques de randomisation appliquées sur des architectures hybrides utilisant des GPU Nvidia ou des coprocesseurs Intel Xeon Phi. Avec cette méthode, nous pouvons éviter l'important surcoût du pivotage tout en restant stable numériquement dans la plupart des cas. L'architecture hautement parallèle de ces accélérateurs nous permet d'effectuer la randomisation de notre système linéaire à un coût de calcul très faible par rapport à la durée de la factorisation. Finalement, nous étudions l'impact d'accès mémoire non uniformes (NUMA) sur la résolution de systèmes linéaires denses en utilisant un algorithme de factorisation LU. En particulier, nous illustrons comment un placement approprié des processus légers et des données sur une architecture NUMA peut améliorer les performances pour la factorisation du panel et accélérer de manière conséquente la factorisation LU globale. Nous montrons comment ces placements peuvent améliorer les performances quand ils sont appliqués à des solveurs hybrides multicœurs/GPU. / In this PhD thesis, we study algorithms and implementations to accelerate the solution of dense linear systems by using hybrid architectures with multicore processors and accelerators. We focus on methods based on the LU factorization and our code development takes place in the context of the MAGMA library. We study different hybrid CPU/GPU solvers based on the LU factorization which aim at reducing the communication overhead due to pivoting. The first one is based on a communication avoiding strategy of pivoting (CALU) while the second uses a random preconditioning of the original system to avoid pivoting (RBT). We show that both of these methods outperform the solver using LU factorization with partial pivoting when implemented on hybrid multicore/GPUs architectures. We also present new solvers based on randomization for hybrid architectures for Nvidia GPU or Intel Xeon Phi coprocessor. With this method, we can avoid the high cost of pivoting while remaining numerically stable in most cases. The highly parallel architecture of these accelerators allow us to perform the randomization of our linear system at a very low computational cost compared to the time of the factorization. Finally we investigate the impact of non-uniform memory accesses (NUMA) on the solution of dense general linear systems using an LU factorization algorithm. In particular we illustrate how an appropriate placement of the threads and data on a NUMA architecture can improve the performance of the panel factorization and consequently accelerate the global LU factorization. We show how these placements can improve the performance when applied to hybrid multicore/GPU solvers.