La problématique de cette thèse se place à l’interface entre le domaine scientifique du contrôle non destructif par ultrasons (CND US) et l’adéquation algorithme architecture. Le CND US comprend un ensemble de techniques utilisées pour examiner un matériau, qu’il soit en production ou maintenance. Afin de détecter d’éventuels défauts, de les positionner et les dimensionner, des méthodes d’imagerie et de reconstruction ont été développées au CEA-LIST, dans la plateforme logicielle CIVA.L’évolution du matériel d’acquisition entraine une augmentation des volumes de données et par conséquent nécessite toujours plus de puissance de calcul pour parvenir à des reconstructions en temps interactif. L’évolution multicoeurs des processeurs généralistes (GPP), ainsi que l’arrivée de nouvelles architectures comme les GPU rendent maintenant possible l’accélération de ces algorithmes.Le but de cette thèse est d’évaluer les possibilités d’accélération de deux algorithmes de reconstruction sur ces architectures. Ces deux algorithmes diffèrent dans leurs possibilités de parallélisation. Pour un premier, la parallélisation sur GPP est relativement immédiate, contrairement à celle sur GPU qui nécessite une utilisation intensive des instructions atomiques. Quant au second, le parallélisme est plus simple à exprimer, mais l’ordonnancement des nids de boucles sur GPP, ainsi que l’ordonnancement des threads et une bonne utilisation de la mémoire partagée des GPU sont nécessaires pour obtenir un fonctionnement efficace. Pour ce faire, OpenMP, CUDA et OpenCL ont été utilisés et comparés. L’intégration de ces prototypes dans la plateforme CIVA a mis en évidence un ensemble de problématiques liées à la maintenance et à la pérennisation de codes sur le long terme. / This thesis work is placed between the scientific domain of ultrasound non-destructive testing and algorithm-architecture adequation. Ultrasound non-destructive testing includes a group of analysis techniques used in science and industry to evaluate the properties of a material, component, or system without causing damage. In order to characterize possible defects, determining their position, size and shape, imaging and reconstruction tools have been developed at CEA-LIST, within the CIVA software platform.Evolution of acquisition sensors implies a continuous growth of datasets and consequently more and more computing power is needed to maintain interactive reconstructions. General purprose processors (GPP) evolving towards parallelism and emerging architectures such as GPU allow large acceleration possibilities than can be applied to these algorithms.The main goal of the thesis is to evaluate the acceleration than can be obtained for two reconstruction algorithms on these architectures. These two algorithms differ in their parallelization scheme. The first one can be properly parallelized on GPP whereas on GPU, an intensive use of atomic instructions is required. Within the second algorithm, parallelism is easier to express, but loop ordering on GPP, as well as thread scheduling and a good use of shared memory on GPU are necessary in order to obtain efficient results. Different API or libraries, such as OpenMP, CUDA and OpenCL are evaluated through chosen benchmarks. An integration of both algorithms in the CIVA software platform is proposed and different issues related to code maintenance and durability are discussed.

La méthode d’imagerie la plus répandue dans l’industrie pétrolière est la RTM (Reverse Time Migration) qui repose sur la simulation de la propagation des ondes dans le sous-sol. Nous nous sommes concentrés sur un propagateur d'ondes élastiques 3D en milieu anisotrope de type TTI (Tilted Transverse Isotropic). Nous avons directement travaillé dans le code de recherche de Total DIVA (Depth Imaging Velocity Analysis), basé sur une discrétisation par la méthode de Galerkin Discontinue et le schéma Leap-Frog, et développé pour le calcul parallèle intensif – HPC (High Performance Computing). Nous avons ciblé plus particulièrement deux contributions possibles qui, si elles supposent des compétences très différentes, ont la même finalité : réduire les coûts de calculs requis pour la simulation. D'une part, les conditions aux limites classiques de type PML (Perfectly Matched Layers) ne sont pas stables dans des milieux TTI. Nous avons proposé de formuler une CLA (Conditions aux Limites Absorbantes) stable dans des milieux anisotropes. La méthode de construction repose sur les propriétés des courbes de lenteur, ce qui donne à notre approche un caractère original. D'autre part, le parallélisme initial, basé sur une décomposition de domaine et des communications par passage de messages à l'aide de la bibliothèque MPI, conduit à un déséquilibrage de charge qui détériore son efficacité parallèle. Nous avons corrigé cela en remplaçant le paradigme parallélisme par l'utilisation de la programmation à base de tâches sur support d'exécution. Cette thèse a été réalisée dans le cadre de l'action de recherche DIP (Depth Imaging Partnership) qui lie la compagnie pétrolière Total et Inria. / The most common method of Seismic Imaging is the RTM (Reverse Time Migration) which depends on wave propagation simulations in the subsurface. We focused on a 3D elastic wave propagator in anisotropic media, more precisely TTI (Tilted Transverse Isotropic). We directly worked in the Total code DIVA (Depth Imaging Velocity Analysis) which is based on a discretization by the Discontinuous Galerkin method and the Leap-Frog scheme, and developed for intensive parallel computing – HPC (High Performance Computing). We choose to especially target two contributions. Although they required very different skills, they share the same goal: to reduce the computational cost of the simulation. On one hand, classical boundary conditions like PML (Perfectly Matched Layers) are unstable in TTI media. We have proposed a formulation of a stable ABC (Absorbing Boundary Condition) in anisotropic media. The technique is based on slowness curve properties, giving to our approach an original side. On the other hand, the initial parallelism, which is based on a domain decomposition and communications by message passing through the MPI library, leads to load-imbalance and so poor parallel efficiency. We have fixed this issue by replacing the paradigm for parallelism by the use of task-based programming through runtime system. This PhD thesis have been done in the framework of the research action DIP (Depth Imaging Partnership) between the Total oil company and Inria.

Cette thèse vise à définir une méthodologie de mise en œuvre d’applications performantes sur les processeurs embarqués du futur. Ces architectures nécessitent notamment d’exploiter au mieux les différents niveaux de parallélisme (grain fin, gros grain) et de gérer les communications et les accès à la mémoire. Pour étudier cette méthodologie, nous avons utilisé un processeur cible représentatif de ces architectures émergentes, le processeur CELL. Le détecteurde points d’intérêt de Harris est un exemple de traitement régulier nécessitant des unités de calcul intensif. En étudiant plusieurs schémas de mise en oeuvre sur le processeur CELL, nous avons ainsi pu mettre en évidence des méthodes d’optimisation des calculs en adaptant les programmes aux unités spécifiques de traitement SIMD du processeur CELL. L’utilisation efficace de la mémoire nécessite par ailleurs, à la fois une bonne exploitation des transferts et un arrangement optimal des données en mémoire. Nous avons développé un outil d’abstraction permettant de simplifier et d’automatiser les transferts et la synchronisation, CELL MPI. Cette expertise nous a permis de développer une méthodologie permettant de simplifier la mise en oeuvre parallèle optimisée de ces algorithmes. Nous avons ainsi conçu un outil de programmation parallèle à base de squelettes algorithmiques : SKELL BE. Ce modèle de programmation propose une solution originale de génération d’applications à base de métaprogrammation. Il permet, de manière automatisée, d’obtenir de très bonnes performances et de permettre une utilisation efficace de l’architecture, comme le montre la comparaison pour un ensemble de programmes test avec plusieurs autres outils dédiés à ce processeur. / This thesis aims to define a design methodology for high performance applications on future embedded processors. These architectures require an efficient usage of their different level of parallelism (fine-grain, coarse-grain), and a good handling of the inter-processor communications and memory accesses. In order to study this methodology, we have used a target processor which represents this type of emerging architectures, the Cell BE processor.We have also chosen a low level image processing application, the Harris points of interest detector, which is representative of a typical low level image processing application that is highly parallel. We have studied several parallelisation schemes of this application and we could establish different optimisation techniques by adapting the software to the specific SIMD units of the Cell processor. We have also developped a library named CELL MPI that allows efficient communication and synchronisation over the processing elements, using a simplified and implicit programming interface. This work allowed us to develop a methodology that simplifies the design of a parallel algorithm on the Cell processor.We have designed a parallel programming tool named SKELL BE which is based on algorithmic skeletons. This programming model providesan original solution of a meta-programming based code generator. Using SKELL BE, we can obtain very high performances applications that uses the Cell architecture efficiently when compared to other tools that exist on the market.

La méthode des éléments frontières pour l’équation des ondes (BEM) est utilisée en acoustique eten électromagnétisme pour simuler la propagation d’une onde avec une discrétisation en temps(TD). Elle permet d’obtenir un résultat pour plusieurs fréquences à partir d’une seule résolution.Dans cette thèse, nous nous intéressons à l’implémentation efficace d’un simulateur TD-BEM sousdifférents angles. Nous décrivons le contexte de notre étude et la formulation utilisée qui s’exprimesous la forme d’un système linéaire composé de plusieurs matrices d’interactions/convolutions.Ce système est naturellement calculé en utilisant l’opérateur matrice/vecteur creux (SpMV). Nousavons travaillé sur la limite du SpMV en étudiant la permutation des matrices et le comportementde notre implémentation aidé par la vectorisation sur CPU et avec une approche par bloc surGPU. Nous montrons que cet opérateur n’est pas approprié pour notre problème et nous proposonsde changer l’ordre de calcul afin d’obtenir une matrice avec une structure particulière.Cette nouvelle structure est appelée une matrice tranche et se calcule à l’aide d’un opérateur spécifique.Nous décrivons des implémentations optimisées sur architectures modernes du calculhaute-performance. Le simulateur résultant est parallélisé avec une approche hybride (mémoirespartagées/distribuées) sur des noeuds hétérogènes, et se base sur une nouvelle heuristique pouréquilibrer le travail entre les processeurs. Cette approche matricielle a une complexité quadratiquesi bien que nous avons étudié son accélération par la méthode des multipoles rapides (FMM). Nousavons tout d’abord travaillé sur la parallélisation de l’algorithme de la FMM en utilisant différentsparadigmes et nous montrons comment les moteurs d’exécution sont adaptés pour relâcher le potentielde la FMM. Enfin, nous présentons des résultats préliminaires d’un simulateur TD-BEMaccéléré par FMM . / The time-domain BEM for the wave equation in acoustics and electromagnetism is used to simulatethe propagation of a wave with a discretization in time. It allows to obtain several frequencydomainresults with one solve. In this thesis, we investigate the implementation of an efficientTD-BEM solver using different approaches. We describe the context of our study and the TD-BEMformulation expressed as a sparse linear system composed of multiple interaction/convolutionmatrices. This system is naturally computed using the sparse matrix-vector product (SpMV). Wework on the limits of the SpMV kernel by looking at the matrix reordering and the behavior of ourSpMV kernels using vectorization (SIMD) on CPUs and an advanced blocking-layout on NvidiaGPUs. We show that this operator is not appropriate for our problem, and we then propose toreorder the original computation to get a special matrix structure. This new structure is called aslice matrix and is computed with a custom matrix/vector product operator. We present an optimizedimplementation of this operator on CPUs and Nvidia GPUs for which we describe advancedblocking schemes. The resulting solver is parallelized with a hybrid strategy above heterogeneousnodes and relies on a new heuristic to balance the work among the processing units. Due tothe quadratic complexity of this matrix approach, we study the use of the fast multipole method(FMM) for our time-domain BEM solver. We investigate the parallelization of the general FMMalgorithm using several paradigms in both shared and distributed memory, and we explain howmodern runtime systems are well-suited to express the FMM computation. Finally, we investigatethe implementation and the parametrization of an FMM kernel specific to our TD-BEM, and weprovide preliminary results.

Ce travail porte sur l'étude des méthodes de décomposition de domaine et leur application pour résoudre des problèmes de contrôle optimal régis par des équations aux dérivées partielles. Le principe de ces méthodes consiste à ramener des problèmes de grande taille sur des géométries complexes en une suite de sous-problèmes de taille plus petite sur des géométries plus simples. En considérant une décomposition sans recouvrement, l'intérêt de ces méthodes pour les problèmes de contrôle optimal réside au niveau de l'intégration de l'équation d'état, puisqu'il est possible de partitionner le problème en une suite de problèmes plus petits, quitte à contraindre les interfaces entre les sous-domaines à obéir à des conditions de raccordement afin de déduire la solution globale à partir des solutions locales. Dans une première partie, nous étudions le cas elliptique. Nous considérons simultanément la minimisation de la fonction coût et des raccordements sur les frontières entre les sous-domaines. Cette combinaison de problèmes de minimisation et de méthodes de décomposition de domaine est traitée par des techniques de Lagrangien augmenté. Nous montrons que, sur le domaine décomposé, le problème initial se réduit à la recherche d'un point-selle. Une étude des méthodes de Lagrangien nous a permis de choisir une variante d'algorithmes existants dans la littérature et de les combiner avec un algorithme de décomposition de domaine. Dans la seconde partie, nous développons l'extension de cette approche aux problèmes de contrôle optimal régis par des systèmes paraboliques en considérant uniquement une décomposition en espace du domaine de calcul. Dans une dernière partie, nous considérons une décomposition de domaine avec recouvrement à chaque pas de la minimisation. D'une part, nous construisons un algorithme parallèle en utilisant la méthode de Schwarz multiplicative en tant que solveur. Ceci permet de déduire naturellement l'état adjoint par transposition des systèmes directs locaux. L'algorithme global défini par la méthode de minimisation de type quasi-Newton et ce solveur de Schwarz constitue une méthode robuste de résolution du problème de contrôle optimal, mais coûteuse. D'autre part, et plus particulièrement, pour des problèmes de grande taille, l'algorithme de type quasi-Newton, combiné avec le solveur de Krylov BiCGSTAB préconditionné par une méthode de Schwarz additive, est plus compétitif dans la mesure oû l'on obtient de bonnes performances parallèles. De nombreux résultats sont présentés pour préciser le comportement des algorithmes d'optimisation quand ils sont utilisés avec des méthodes de Schwarz.

De nombreuses études ont été menées lors des vingt dernières années dans le domaine de l'auralisation.Elles consistent à rendre audible les résultats d'une simulation acoustique. Ces études se sont majoritairementfocalisées sur les algorithmes de propagation et la restitution du champ acoustique dans desenvironnements complexes. Actuellement, de nombreux travaux portent sur le rendu sonore en tempsréel.Cette thèse aborde la problématique du rendu sonore dynamique d'environnements complexes selonquatre axes : la propagation des ondes sonores, le traitement du signal, la perception spatiale du son etl'optimisation informatique. Dans le domaine de la propagation, une méthode permettant d'analyser lavariété des algorithmes présents dans la bibliographie est proposée. A partir de cette méthode d'analyse,deux algorithmes dédiés à la restitution en temps réel des champs spéculaires et diffus ont été extraits.Dans le domaine du traitement du signal, la restitution est réalisée à l'aide d'un algorithme optimisé despatialisation binaurale pour les chemins spéculaires les plus significatifs et un algorithme de convolutionsur carte graphique pour la restitution du champ diffus. Les chemins les plus significatifs sont extraitsgrace à un modèle perceptif basé sur le masquage temporel et spatial des contributions spéculaires.Finalement, l'implémentation de ces algorithmes sur des architectures parallèles récentes en prenant encompte les nouvelles architectures multi-coeurs et les nouvelles cartes graphiques est présenté.

L'accroissement d'efficacite des réseaux d'interconnexion et la vulgarisation des machines multiprocesseurs permettent la réalisation de machines parallèles a mémoire distribuée de faible coût: les grappes de multiprocesseurs. Elles nécessitent l'exploitation à la fois du parallélismeà grain fin, interne à un multiprocesseur offert par la multiprogrammation légère, et du parallélisme à gros grain entre les différents multiprocesseurs. L'exploitation simultanée de ces deux types de parallélisme exige une méthode de communication entre les processus légers qui ne partagent pas le mêmme espace d'adressage. Le travail de cette thèse porte sur le problème de l'Intégration de la multiprogrammation légère et des communications sur grappes de multiprocesseurs symétriques (SMP). II porte plus précisément sur evaluation et le reglage du noyau exécutif ATHAPASCAN-0 sur ce type d'architecture. ATHAPASCAN-0 est un noyau exécutif, portable, développé au sein du projet APACHE (CNRS-INPG-INRIA-UJF), qui combine la multiprogrammation légère et la communication par échange de messages. La portabilité est assurée par une organisation en couches basée sur les standards POSIX threads et MPI largement répandus. ATHAPASCAN-0 étend le modèle de réseau statique de processus «lourds» communicants tel que MPI, PVM, etc,à celui d'un réseau dynamique de processus légers communicants. La technique de base est la multiprogrammation lègere des communications et des calculs. La progression des communications exige la scrutation de état du reseau et l'enchainement des opérations de transferts. L'efficacité repose sur la minimisation de ces opérations. De plus, l'emploi de multiprocesseurs ajoute des problèmes spécifiques dus à l'apparition d'un parallélisme réel entre calcul et communication. Ces problèmes sont présentés et des solutions sont proposées pour l'environnement ATHAPASCAN-0. Ces solutions sont évaluées sur des grappes de multiprocesseurs. / The continuous price reduction for commodity PC multiprocessors and the availability of fast network interfaces have made cluster of multiprocessors an attractive low-price alternative to build parallel systems. Multiprocessor clusters offer two levels of parallelism: a fine grain parallelism inside a single multiprocessor and a coarse grain among them. A mechanism must be provided to exploit both levels of parallelism simultaneously. This requires to provide communications between threads belonging to different addresses spaces. This dissertation addresses the problem of integrating threads and communications on ATHAPASCAN-0 run time system. ATHAPASCAN-0 is a portable run time for cluster of multiprocessors developed as part of the APACHE project (CNRS-INPG-INRIA-UJF). Portability is achieved by a layered organization based on standards like POSIX threads and MPI. The ATHAPASCAN-0 run time system extends the heavy-weight process communication model of message passing libraries such as MPI, PVM, etc, into a lighter dynamic network of communicating threads. Multiprogramming is the key concept used. Communication progress is based on a network polling basis to handle incoming messages and to deliver outgoing communications requests. Performance is strongly dependent on the way these operations are implemented. Additionally, multiprocessors introduce some programming problems like overhead of cache coherency mechanisms, method of managing concurrent accesses and efficient mutex locking to avoid unnecessary context switching. These problems are analyzed and solutions are implemented in the ATHAPASCAN-0 run time system. An evaluation of these solutions is performed on a cluster of multiprocessors.

L'accroissement d'efficacite des réseaux d'interconnexion et la vulgarisation des machines multiprocesseurs permettent la réalisation de machines parallèles a mémoire distribuée de faible coût: les grappes de multiprocesseurs. Elles nécessitent l'exploitation à la fois du parallélismeà grain fin, interne à un multiprocesseur offert par la multiprogrammation légère, et du parallélisme à gros grain entre les différents multiprocesseurs. L'exploitation simultanée de ces deux types de parallélisme exige une méthode de communication entre les processus légers qui ne partagent pas le mêmme espace d'adressage. Le travail de cette thèse porte sur le problème de l'Intégration de la multiprogrammation légère et des communications sur grappes de multiprocesseurs symétriques (SMP). II porte plus précisément sur evaluation et le reglage du noyau exécutif ATHAPASCAN-0 sur ce type d'architecture. ATHAPASCAN-0 est un noyau exécutif, portable, développé au sein du projet APACHE (CNRS-INPG-INRIA-UJF), qui combine la multiprogrammation légère et la communication par échange de messages. La portabilité est assurée par une organisation en couches basée sur les standards POSIX threads et MPI largement répandus. ATHAPASCAN-0 étend le modèle de réseau statique de processus «lourds» communicants tel que MPI, PVM, etc,à celui d'un réseau dynamique de processus légers communicants. La technique de base est la multiprogrammation lègere des communications et des calculs. La progression des communications exige la scrutation de état du reseau et l'enchainement des opérations de transferts. L'efficacité repose sur la minimisation de ces opérations. De plus, l'emploi de multiprocesseurs ajoute des problèmes spécifiques dus à l'apparition d'un parallélisme réel entre calcul et communication. Ces problèmes sont présentés et des solutions sont proposées pour l'environnement ATHAPASCAN-0. Ces solutions sont évaluées sur des grappes de multiprocesseurs. / The continuous price reduction for commodity PC multiprocessors and the availability of fast network interfaces have made cluster of multiprocessors an attractive low-price alternative to build parallel systems. Multiprocessor clusters offer two levels of parallelism: a fine grain parallelism inside a single multiprocessor and a coarse grain among them. A mechanism must be provided to exploit both levels of parallelism simultaneously. This requires to provide communications between threads belonging to different addresses spaces. This dissertation addresses the problem of integrating threads and communications on ATHAPASCAN-0 run time system. ATHAPASCAN-0 is a portable run time for cluster of multiprocessors developed as part of the APACHE project (CNRS-INPG-INRIA-UJF). Portability is achieved by a layered organization based on standards like POSIX threads and MPI. The ATHAPASCAN-0 run time system extends the heavy-weight process communication model of message passing libraries such as MPI, PVM, etc, into a lighter dynamic network of communicating threads. Multiprogramming is the key concept used. Communication progress is based on a network polling basis to handle incoming messages and to deliver outgoing communications requests. Performance is strongly dependent on the way these operations are implemented. Additionally, multiprocessors introduce some programming problems like overhead of cache coherency mechanisms, method of managing concurrent accesses and efficient mutex locking to avoid unnecessary context switching. These problems are analyzed and solutions are implemented in the ATHAPASCAN-0 run time system. An evaluation of these solutions is performed on a cluster of multiprocessors.

Dans cette thèse , nous proposons d’étudier des questions sur le parallélism de tâcheavec dépendance de données dans le cadre de machines multicoeur avec des accélérateurs.La solution proposée a été développée en utilisant l’interface de programmation hauteniveau XKaapi du projet MOAIS de l’INRIA Rhône-Alpes.D’abord nous avons étudié des questions liés à une approche d’exécution totalementasyncrone et l’ordonnancement par vol de travail sur des architectures multi-GPU. Le volde travail avec localité de données a montré des résultats significatifs, mais il ne prend pasen compte des différents ressources de calcul. Ensuite nous avons conçu une interface etune modèle de coût qui permettent d’écrire des politiques d’ordonnancement sur XKaapi.Finalement on a évalué XKaapi sur un coprocesseur Intel Xeon Phi en mode natif.Notre conclusion est double. D’abord nous avons montré que le modèle de programma-tion data-flow peut être efficace sur des accélérateurs tels que des GPUs ou des coproces-seurs Intel Xeon Phi. Ensuite, le support à des différents politiques d’ordonnancement estindispensable. Les modèles de coût permettent d’obtenir de performance significatifs surdes calculs très réguliers, tandis que le vol de travail permet de redistribuer la charge encours d’exécution. / In this thesis, we propose to study the issues of task parallelism with data dependencies onmulticore architectures with accelerators. We target those architectures with the XKaapiruntime system developed by the MOAIS team (INRIA Rhône-Alpes).We first studied the issues on multi-GPU architectures for asynchronous execution andscheduling. Work stealing with heuristics showed significant performance results, but didnot consider the computing power of different resources. Next, we designed a schedulingframework and a performance model to support scheduling strategies over XKaapi runtime.Finally, we performed experimental evaluations over the Intel Xeon Phi coprocessor innative execution.Our conclusion is twofold. First we concluded that data-flow task programming canbe efficient on accelerators, which may be GPUs or Intel Xeon Phi coprocessors. Second,the runtime support of different scheduling strategies is essential. Cost models providesignificant performance results over very regular computations, while work stealing canreact to imbalances at runtime. / Esta tese investiga os desafios no uso de paralelismo de tarefas com dependências dedados em arquiteturas multi-CPU com aceleradores. Para tanto, o XKaapi, desenvolvidono grupo de pesquisa MOAIS (INRIA Rhône-Alpes), é a ferramenta de programação basedeste trabalho.Em um primeiro momento, este trabalho propôs extensões ao XKaapi a fim de sobre-por transferência de dados com execução através de operações concorrentes em GPU, emconjunto com escalonamento por roubo de tarefas em multi-GPU. Os resultados experimen-tais sugerem que o suporte a asincronismo é importante à escalabilidade e desempenho emmulti-GPU. Apesar da localidade de dados, o roubo de tarefas não pondera a capacidadede processamento das unidades de processamento disponíveis. Nós estudamos estratégiasde escalonamento com predição de desempenho em tempo de execução através de modelosde custo de execução. Desenvolveu-se um framework sobre o XKaapi de escalonamentoque proporciona a implementação de diferentes algoritmos de escalonamento. Esta tesetambém avaliou o XKaapi em coprocessodores Intel Xeon Phi para execução nativa.A conclusão desta tese é dupla. Primeiramente, nós concluímos que um modelo deprogramação com dependências de dados pode ser eficiente em aceleradores, tais comoGPUs e coprocessadores Intel Xeon Phi. Não obstante, uma ferramenta de programaçãocom suporte a diferentes estratégias de escalonamento é essencial. Modelos de custo podemser usados no contexto de algoritmos paralelos regulares, enquanto que o roubo de tarefaspoder reagir a desbalanceamentos em tempo de execução.

L'accroissement d'efficacite des réseaux d'interconnexion et la vulgarisation des machines multiprocesseurs permettent la réalisation de machines parallèles a mémoire distribuée de faible coût: les grappes de multiprocesseurs. Elles nécessitent l'exploitation à la fois du parallélismeà grain fin, interne à un multiprocesseur offert par la multiprogrammation légère, et du parallélisme à gros grain entre les différents multiprocesseurs. L'exploitation simultanée de ces deux types de parallélisme exige une méthode de communication entre les processus légers qui ne partagent pas le mêmme espace d'adressage. Le travail de cette thèse porte sur le problème de l'Intégration de la multiprogrammation légère et des communications sur grappes de multiprocesseurs symétriques (SMP). II porte plus précisément sur evaluation et le reglage du noyau exécutif ATHAPASCAN-0 sur ce type d'architecture. ATHAPASCAN-0 est un noyau exécutif, portable, développé au sein du projet APACHE (CNRS-INPG-INRIA-UJF), qui combine la multiprogrammation légère et la communication par échange de messages. La portabilité est assurée par une organisation en couches basée sur les standards POSIX threads et MPI largement répandus. ATHAPASCAN-0 étend le modèle de réseau statique de processus «lourds» communicants tel que MPI, PVM, etc,à celui d'un réseau dynamique de processus légers communicants. La technique de base est la multiprogrammation lègere des communications et des calculs. La progression des communications exige la scrutation de état du reseau et l'enchainement des opérations de transferts. L'efficacité repose sur la minimisation de ces opérations. De plus, l'emploi de multiprocesseurs ajoute des problèmes spécifiques dus à l'apparition d'un parallélisme réel entre calcul et communication. Ces problèmes sont présentés et des solutions sont proposées pour l'environnement ATHAPASCAN-0. Ces solutions sont évaluées sur des grappes de multiprocesseurs. / The continuous price reduction for commodity PC multiprocessors and the availability of fast network interfaces have made cluster of multiprocessors an attractive low-price alternative to build parallel systems. Multiprocessor clusters offer two levels of parallelism: a fine grain parallelism inside a single multiprocessor and a coarse grain among them. A mechanism must be provided to exploit both levels of parallelism simultaneously. This requires to provide communications between threads belonging to different addresses spaces. This dissertation addresses the problem of integrating threads and communications on ATHAPASCAN-0 run time system. ATHAPASCAN-0 is a portable run time for cluster of multiprocessors developed as part of the APACHE project (CNRS-INPG-INRIA-UJF). Portability is achieved by a layered organization based on standards like POSIX threads and MPI. The ATHAPASCAN-0 run time system extends the heavy-weight process communication model of message passing libraries such as MPI, PVM, etc, into a lighter dynamic network of communicating threads. Multiprogramming is the key concept used. Communication progress is based on a network polling basis to handle incoming messages and to deliver outgoing communications requests. Performance is strongly dependent on the way these operations are implemented. Additionally, multiprocessors introduce some programming problems like overhead of cache coherency mechanisms, method of managing concurrent accesses and efficient mutex locking to avoid unnecessary context switching. These problems are analyzed and solutions are implemented in the ATHAPASCAN-0 run time system. An evaluation of these solutions is performed on a cluster of multiprocessors.