Dans les environnements d'exécution parallèle, la régulation de charge (ou l'ordonnancement applicatif) est le module responsable du contrôle de l'exécution d'un programme sur les ressources de l'architecture distribuée (processeurs et modules mémoire). En pratique, le choix de la stratégie de régulation la plus performante dépend non seulement de l'application mais doit aussi être adapté en fonction de l'architecture cible. Dès lors, la portabilité d'un code ne peut être assurée que si l'on peut modifier cette stratégie. Dans cette thèse, nous proposons l'utilisation de la description dynamique du flot de données comme l'élément central permettant de séparer le code applicatif de la régulation de charge. Sur cette proposition est basée la construction d'un environnement logiciel, modulaire et générique, qui rend possible la modification ou l'ajustement de la stratégie de régulation de charge. La spécification de cet environnement repose sur l'identification des interfaces de la régulation avec d'une part l'application et d'autre part l'architecture. Cette identification, centrée sur l'exploration macroscopique du flot de données, est originale: nous montrons qu'elle étend d'autres systèmes classiques de régulation de charge. Enfin, la validation expérimentale de cet environnement est réalisée grâce à son intégration dans l'interface de programmation Athapascan-1 de l'environnement Athapascan, du projet APACHE. Différentes stratégies d'ordonnancement, statiques, dynamiques et hybrides, ont ainsi été implantés. Nous présentons les performances de quelques unes de ces stratégies appliquées à des programmes Athapascan-1 sur différentes architectures.

Ce travail présente l'apport de l'ordonnancement pour la programmation parallèle performante d'applications numériques en mécanique et chimie quantique. Nous prenons deux exemples types de résolution de l'équation de Schrödinger --- Boîte Quantique (BQ) et Méthode des Perturbations d'ordre 2 (MP2) --- qui nécessitent de grosses ressources en calcul et mémoire. La programmation traditionnelle (échange de messages et/ou multithreading) des machines parallèles (distribuées ou SMP) est illustrée par les performances obtenues avec le benchmark Linpack sur la grappe I-cluster (INRIA). Le manque de portabilité du code hautement performant obtenu montre l'importance d'un environnement de programmation parallèle permettant de découpler le codage de l'algorithme de son ordonnancement sur la machine cible. Nous introduisons alors Athapascan, qui repose sur l'analyse du flot de données, pour calculer dynamiquement des ordonnancements prouvés efficaces. Un premier critère d'efficacité est le temps de calcul. Sur certains modèles de machines, la théorie et l'expérience montrent que Athapascan permet des ordonnancements qui garantissent des exécutions efficaces pour certains algorithmes adaptés à BQ, de type itératif (méthode de Lanczos). Un deuxième critère fondamental est l'espace mémoire requis pour les exécutions parallèles en calcul numérique ; c'est particulièrement critique pour MP2. Nous proposons d'annoter le Graphe de Flot de Données (GFD) manipulé par Athapascan pour prendre en compte la mémoire et permettre des ordonnancements dynamiques efficaces en mémoire. Pour MP2, dont le GFD est connu statiquement, un ordonnancement efficace en temps et en mémoire est donné.

Cette thèse combine le calcul haute performance à la réalité virtuelle par son apport de méthodes de calcul parallèle pour l'animation d'objets 3D en synthèse d'image. Son application vise plus particulièrement le domaine de la simulation de textiles par modèles physiques. Les lois fondamentales de la dynamique ont en effet été employées pour modéliser le mouvement de plusieurs objets dans un souci de réalisme. Les modèles employés étant numériquement complexes, le calcul d'une image en séquentiel varie de la seconde à plusieurs minutes suivant la complexité du modèle. L'objectif a été de diminuer ce temps par la parallélisation des algorithmes et l'exécution sur grappes de machines multiprocesseurs afin d'obtenir des animations en temps réel. Différentes méthodes d'intégration des équations du mouvement ont été implantées en parallèle. Dans le cas de l'emploi de méthodes implicites, les opérations coûteuses en calcul proviennent de la résolution de systèmes linéaires par la méthode du Gradient Conjugué impliquant des opérations d'algèbre linéaire de type multiplications de matrices creuses et de vecteurs. Ce projet de thèse a contribué à l'obtention de nouvelles structures algorithmiques parallèles efficaces avec l'obtention d'algorithmes asynchrones. Il a également permis de valider l'approche de l'environnement de programmation parallèle Athapascan (projet INRIA-APACHE) avec la mise au point d'applications avec des contraintes temps réel mou ainsi que le contrôle dynamique de son ordonnanceur. Durant ce projet de thèse, un couplage entre la simulation parallèle de textiles et son affichage utilisant l'environnement de visualisation multi-écrans Net Juggler a également été réalisé en faisant communiquer efficacement ces deux programmes parallèles.

L'approche objet permet des applications plus évoluées et plus fiables et des développements spécifiques moins coûteux et évolutifs. Les objectifs de ce travail sont, d'une part, de contribuer à la conceptualisation complète de modèles de simulation à objet et d'autre part, de les implémenter en utilisant des techniques de programmation concurrente. Après une présentation, au chapitre I, des concepts des systèmes de production et de leur gestion, nous avons évalué, au chapitre II, les différents modèles de structure et de simulation pour les systèmes de production. Le chapitre ID propose une démarche d'analyse pour identifier des classes d'objets en cinq types du domaine: physiques, rôles, incidents, interactions et spécifications. Chacune de ces classes est spécifiée par quatre modèles: communication, information, transition d'état et processus. Dans le chapitre IV, nous avons conceptualisé une architecture générale des objets actifs, une plateforme de simulation à objets concurrents et des classes d'objets sémantiques tels que les transactions, les moyens de production et les décisions pour l'établissement des modèles de simulation de production. Nous avons illustré, au chapitre V, l'implémentation des coopérations spatiales et temporelles entre objets concurrents dans la simulation avec des concepts processus "légers" basés sur l'outil Meijin++.

Avec l'arrivée des données moléculaires vers la fin des années 70, nous avons assisté à la découverte de nouveaux mécanismes d'évolution primordiaux dont l'échange du matériel génétique entre les espèces. Un tel échange peut se faire horizontalement, quand l'organisme intègre le matériel génétique provenant d'un autre organisme qui n'est pas son descendant direct, ou verticalement, quand l'organisme reçoit du matériel génétique à partir de son ancêtre le plus proche. Le problème de la détection et de la classification des transferts horizontaux de gènes (THG) est parmi les plus ardus en bioinformatique. Dans cette thèse, nous décrivons cinq nouveaux algorithmes pour la détection de THGs complets ou partiels qui seront basés sur des comparaisons topologiques et métriques entre un arbre d'espèces et un arbre de gène inférés pour le même ensemble d'espèces. Ces algorithmes incluent l'algorithme de détection de THGs complets ainsi que ses versions interactive et consensus. Les deux algorithmes de détection de transferts partiels que nous avons proposés peuvent être vus comme une généralisation de l'algorithme de détection de transferts complets. Ils peuvent être utilisés pour identifier des gènes mosaïques. Nous présentons aussi dans cette thèse une version parallèle de l'algorithme de détection de THGs complets, ainsi qu'une plateforme pour la transformation semi-automatique de programmes bioinformatiques séquentiels en programmes parallèles. Une interface Web intégrant tous les programmes développés dans le cadre de ce projet doctoral a aussi été mise au point. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : algorithmes bioinformatiques, arbre phylogénétique, programmation parallèle, réseau réticulé, transfert horizontal de gènes (THG).

La conception d'applications scientifiques à base de couplage de code est une tâche complexe car elle demande de concilier une facilité de programmation et une obtention de haute performance. En outre, les ressources matérielles (supercalculateurs, grappes de calcul, grilles) permettant leur exécution forment un ensemble hétérogène en constante évolution. Les modèles à base de composants logiciels forment une piste prometteuse pour gérer ces deux sources de complexité car ils permettent d'exprimer les interactions entre les différents constituants d'une application tout en offrant des possibilités d'abstraction des ressources. Néanmoins, les modèles existants ne permettent pas d'exprimer de manière satisfaisante les applications constituées de motifs répliqués dynamiques et hiérarchiques. Ainsi, cette thèse vise à améliorer l'existant - et en particulier la plate-forme générique de simulation numérique SALOME - pour une classe d'applications très répandue : les applications à base de décomposition de domaine et la variante utilisant le raffinement de maillage adaptatif. Tout d'abord, nous avons proposé d'étendre le modèle de composition spatial et temporel de SALOME en ajoutant la possibilité de définir dynamiquement la cardinalité des composants. Cela demande en particulier de gérer les communications de groupes ainsi induites. La proposition a été implémentée dans SALOME et validée via une application de décomposition de domaine à base de couplage de plusieurs instances de Code_Aster. Ensuite, nous avons étudié la pertinence d'utiliser un modèle de composant supportant des connecteurs natifs (MPI, mémoire partagée, appel de méthode) pour permettre une composition plus fine des interactions entre composants. Les résultats d'expériences montrent que des performances équivalentes aux versions natives sont obtenues tout en permettant de manipuler facilement l'architecture de l'application. Enfin, nous avons étudié les extensions nécessaires aux modèles à composants (abstraction,hiérarchie, dynamicité) pour la conception d'applications de raffinement de maillage adaptatif. Les modèles de composants spatio-temporels les plus avancés permettent ainsi d'exprimer ce type d'application mais les performances sont limitées par leur mise en œuvre centralisée ainsi que par le manque de moyens efficaces pour modifier à la volée des assemblages de composants.

Le développement du multimédia, avec l'émergence des architectures parallèles, a ravivé l'intérêt de la programmation flux de données pour la conception de systèmes embarqués. En effet, la programmation flux de données offre une approche de développement suffisamment flexible pour créer des applications complexes tout en exprimant la concurrence et le parallélisme explicitement. Paradoxalement, la plupart des études portent sur des modèles flux de données statiques, même si un processus de développement pragmatique nécessite l'expressivité et la practicité d'un langage de programmation basé sur un modèle flux de données dynamiques, comme le langage de programmation utilisé dans le cadre de Reconfigurable Video Coding. Dans cette thèse, nous décrivons un environnement de développement pour la programmation flux de données qui facilite le développement multimédia pour des plates-formes multi-coeur embarquées. Cet environnement de développement repose sur une architecture logicielle modulaire qui bénéficie de techniques modernes de génie logiciel telles que la méta modélisation et la programmation orientée aspect. Ensuite, nous développons une implémentation logicielle optimisée des programmes flux de données ciblant aussi bien les ordinateurs de bureau que les plates-formes embarquées. Notre implémentation vise à combler le fossé entre la practicité du langage de programmation et l'efficacité de son exécution. Enfin, nous présentons un ensemble d'algorithmes de projection et d'ordonnancement d'acteurs qui permettent l'exécution de programmes flux de données dynamiques sur des plates-formes multi-coeur avec des performances extensibles. / The development of multimedia technology, along with the emergence of parallel architectures, has revived the interest on dataflow programming for designing embedded systems. Indeed, dataflow programming offers a flexible development approach in order to build complex applications while expressing concurrency and parallelism explicitly. Paradoxically, most of the studies focus on static dataflow models of computation, even if a pragmatic development process requires the expressiveness and the practicality of a programming language based on dynamic dataflow models, such as the language included in the Reconfigurable Video Coding framework. In this thesis, we describe a complete development environment for dataflow programming that eases multimedia development for embedded multi-core platforms. This development environment is built upon a modular software architecture that benefits from modern software engineering techniques such as meta modeling and aspect-oriented programming. Then, we develop an optimized software implementation of dataflow programs targeting desktop and embedded multi-core platforms. Our implementation aims to bridge the gap between the practicality of the programming language and the efficiency of the execution. Finally, we present a set of runtime actors mapping/scheduling algorithms that enable the execution of dynamic dataflow programs over multi-core platforms with scalable performance.

Ce travail a été effectué dans le contexte d'un projet financé par l'ERC, Defying Amdahl's Law (DAL), dont l'objectif est d'explorer les techniques micro-architecturales améliorant la performance des processeurs multi-cœurs futurs. Le projet prévoit que malgré les efforts investis dans le développement de programmes parallèles, la majorité des codes auront toujours une quantité signifiante de code séquentiel. Pour cette raison, il est primordial de continuer à améliorer la performance des sections séquentielles des-dits programmes. Le travail de recherche de cette thèse porte principalement sur l'étude des différences entre les sections parallèles et les sections séquentielles de programmes multithreadés (MT) existants. L'exploration de l'espace de conception des futurs processeurs multi-cœurs est aussi traitée, tout en gardant à l'esprit les exigences concernant ces deux types de sections ainsi que le compromis performance-surface. / This thesis work is done in the general context of the ERC, funded Defying Amdahl's Law (DAL) project which aims at exploring the micro-architectural techniques that will enable high performance on future many-core processors. The project envisions that despite future huge investments in the development of parallel applications and porting it to the parallel architectures, most applications will still exhibit a significant amount of sequential code sections and, hence, we should still focus on improving the performance of the serial sections of the application. In this thesis, the research work primarily focuses on studying the difference between parallel and serial sections of the existing multi-threaded (MT) programs and exploring the design space with respect to the processor core requirement for the serial and parallel sections in future many-core with area-performance tradeoff as a primary goal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Les architectures de calcul haute performance de nos jours sont des architectures hiérarchiques et hétérogènes: hiérarchiques car elles sont composées d’une hiérarchie de mémoire, une mémoire distribuée entre les noeuds et une mémoire partagée entre les coeurs d’un même noeud. Hétérogènes due à l’utilisation des processeurs spécifiques appelés Accélérateurs tel que le processeur CellBE d’IBM et les CPUs de NVIDIA. La complexité de maîtrise de ces architectures est double. D’une part, le problème de programmabilité: la programmation doit rester simple, la plus proche possible de la programmation séquentielle classique et indépendante de l’architecture cible. D’autre part, le problème d’efficacité: les performances doivent êtres proches de celles qu’obtiendrait un expert en écrivant le code à la main en utilisant des outils de bas niveau. Dans cette thèse, nous avons proposé une plateforme de développement pour répondre à ces problèmes. Pour cela, nous proposons deux outils : BSP++ est une bibliothèque générique utilisant des templates C++ et BSPGen est un framework permettant la génération automatique de code hybride à plusieurs niveaux de la hiérarchie (MPI+OpenMP ou MPI + Cell BE). Basée sur un modèle hiérarchique, la bibliothèque BSP++ prend les architectures hybrides comme cibles natives. Utilisant un ensemble réduit de primitives et de concepts intuitifs, BSP++ offre une simplicité d'utilisation et un haut niveau d' abstraction de la machine cible. Utilisant le modèle de coût de BSP++, BSPGen estime et génère le code hybride hiérarchique adéquat pour une application donnée sur une architecture cible. BSPGen génère un code hybride à partir d'une liste de fonctions séquentielles et d'une description de l'algorithme parallèle. Nos outils ont été validés sur différentes applications de différents domaines allant de la vérification et du calcul scientifique au traitement d'images en passant par la bioinformatique. En utilisant une large sélection d’architecture cible allant de simple machines à mémoire partagée au machines Petascale en passant par les architectures hétérogènes équipées d’accélérateurs de type Cell BE. / Today’s high-performance computing architectures are hierarchical and heterogeneous. With a hierarchy of memory, they are composed of distributed memory between nodes and shared memory between cores of the same node. heterogeneous due to the use of specific processors called accelerators such as the CellBE IBM processor and/or NVIDIA GPUs. The programming complexity of these architectures is twofold. On the one hand, the problem of programmability: the programming should be simple, as close as possible to the conventional sequential programming and independent of the target architecture. On the other hand, the problem of efficiency: performance should be similar to those obtained by a expert in writing code by hand using low-level tools. In this thesis, we proposed a development platform to address these problems. For this, we propose two tools: BSP++ is a generic library using C++ templates and BSPGen is a framework for the automatic hybrid multi-level hierarchy (MPI + OpenMP or MPI + Cell BE) code generation.Based on a hierarchical model, the BSP++ library takes the hybrid architectures as native targets. Using a small set of primitives and intuitive concepts, BSP++ provides a simple way to use and a high level of abstraction of the target machine. Using the cost model of BSP++, BSPGen predicts and generates the appropriate hierarchical hybrid code for a given application on target architecture. BSPGen generates hybrid code from a sequential list of functions and a description of the parallel algorithm.Our tools have been validated with various applications in different fields ranging from verification to scientific computing and image processing through bioinformatics. Using a wide selection of target architecture ranging from simple shared memory machines to Petascale machines through the heterogeneous architectures equipped with Cell BE accelerators.