La programmation parallèle et les algorithmes data-parallèles sont depuis plusieurs décennies les principales techniques de soutien l'informatique haute performance. Comme toutes les propriétés non-fonctionnelles du logiciel, la conversion des ressources informatiques dans des performances évolutives et prévisibles implique un équilibre délicat entre abstraction et automatisation avec une précision sémantique. Au cours de la dernière décennie, de plus en plus de professions ont besoin d'une puissance de calcul très élevée, mais la migration des programmes existants vers une nouvelle configuration matérielle et le développement de nouveaux algorithmes à finalité spécifique dans un environnement parallèle n'est jamais un travail facile, ni pour les développeurs de logiciel, ni pour les spécialistes du domaine. Dans cette thèse, nous décrivons le travail qui vise à simplifier le développement de programmes parallèles, en améliorant également la portabilité du code de programmes parallèles et la précision de la prédiction de performance d'algorithmes parallèles pour des environnements hétérogènes. Avec ces objectifs à l'esprit, nous avons proposé un modèle de transition nommé SGL pour la modélisation des architectures parallèles hétérogènes et des algorithmes parallèles, et une mise en œuvre de squelettes parallèles basés sur le modèle SGL pour le calcul haute performance. SGL simplifie la programmation parallèle à la fois pour les machines parallèles classiques et pour les nouvelles machines hiérarchiques. Il généralise les primitives de la programmation BSML. SGL pourra plus tard en utilisant des techniques de Model-Driven pour la génération de code automatique á partir d'une fiche technique sans codage complexe, par exemple pour le traitement de Big-Data sur un système hétérogène massivement parallèle. Le modèle de coût de SGL améliore la clarté de l'analyse de performance des algorithmes, permet d'évaluer la performance d'une machine et la qualité d'un algorithme

Proposition d'un langage: fpz (functional parallel programming), qui repond au modele propose en sparc quant a la communication, qui est un langage fonctionnel et qui integre la possibilite de specificication de types abstraits et de fonction generiques d'une facon semblable a lpg. Exposition de deux systemes: sparc (systemes paralleles communicants) et lpg (langage de programmation generique).

L'accroissement d'efficacité des réseaux d'interconnexion et la vulgarisation des machines multiprocesseurs permettent la réalisation de machines parallèles à 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ême 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 multiprocesseurssymétriques (SMP). Il porte plus précisément sur l'évaluation et le réglage dunoyau 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 combinela 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éseaustatique 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égère des communications et des calculs. La progression des communications exige la scrutation de l'état du réseau et l'enchaînement 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.

Les ordinateurs parallèles offrent une alternative intéressante pour les applications de calcul scientifique, grandes consommatrices de ressources de calcul et de mémoire. Cependant, la programmation efficace de ces machines est souvent difficile et les implantations obtenues sont généralement peu portables. Nous proposons dans cette thèse un modèle de programmation parallèle permettant une programmation simple, portable et efficace des applications parallèles. Ce modèle est basé sur une décomposition explicite de l'application en tâches de calculs qui communiquent entre elles par l'intermédiaire d'objets en mémoire partagée. La sémantique des accès aux données partagées est quasi séquentielle et les précédences entre les tâches sont implicitement définies pour respecter cette sémantique. Nous présentons dans une première partie la mise en oeuvre de ce modèle de programmation dans l'interface applicative C++ Athapascan-1. Une analyse à l'exécution des dépendances de données entre tâches permet d'extraire le flot de données et donc les précédences entre les tâches à exécuter. Des algorithmes d'ordonnancement adaptables à l'application et à la machine cible sont également utilisés. Nous montrons comment, sur architecture distribuée, la connaissance du flot de données entre les tâches peut être utilisée par le système pour réduire les communications et gérer efficacement la mémoire partagée distribuée. Ce modèle de programmation et sa mise en oeuvre dans l'interface applicative Athapascan-1 sont ensuite validés expérimentalement sur différentes architectures et différentes applications d'algèbre linéaire, notamment la factorisation creuse de Cholesky avec partitionnement bidimensionnel. La facilité de programmation de ces applications grâce à cette interface et les résultats obtenus (amélioration des performances par rapport au code de factorisation dense de Cholesky de la bibliothèque ScaLapak sur une machine à 60 processeurs par exemple) confirment l'intérêt du modèle de programmation proposé.

Les systèmes de calcul actuels sont généralement des grappes de machines composés de nombreux processeurs à l'architecture fortement hiérarchique. Leur exploitation constitue le défi majeur des implémentations de modèles de programmation tels MPI ou OpenMP. Une pratique courante consiste à mélanger ces deux modèles pour bénéficier des avantages de chacun. Cependant ces modèles n'ont pas été pensés pour fonctionner conjointement ce qui pose des problèmes de performances. Les travaux de cette thèse visent à assister le développeur dans la programmation d'application de type hybride. Il s'appuient sur une analyse de la hiérarchie architecturale du système de calcul pour dimensionner les ressources d'exécution (processus et threads). Plutôt qu'une approche hybride classique, créant un processus MPI multithreadé par noeud, nous évaluons de façon automatique des solutions alternatives, avec plusieurs processus multithreadés par noeud, mieux adaptées aux machines de calcul modernes.

Dans ce mémoire nous abordons de prime abord la reconstruction d'arbres et de réseaux phylogénétiques, à travers deux méthodes d'inférence. Les arbres et les réseaux sont deux supports pour la représentation de l'évolution d'un groupe d'espèces étudiées. Les modèles d'évolution d'espèces qui seront traités sont les suivants : 1) Le modèle arborescent classique qui a longtemps été le seul support formel pour la représentation des relations génétiques entre les espèces. 2) Le modèle en réseau qui permet de représenter des mécanismes phylogénétiques importants pouvant jouer un rôle clé dans l'évolution et pouvant s'expliquer par le phénomène de l'évolution réticulée. Nous nous sommes particulièrement intéressés aux algorithmes d'inférence de réseaux de transferts horizontaux de gènes. Un transfert horizontal de gènes permet à deux espèces de s'échanger, partiellement ou totalement, différents gènes au cours de l'évolution. Le travail effectué sur la reconstruction d'arbres et de réseaux phylogénétiques a mené à la publication de trois articles. Ensuite, nous abordons le problème de réduction du temps d'exécution de différents programmes bioinformatiques. Ce problème a pris de l'ampleur à cause de la croissance du volume de données biologiques et du blocage de la puissance des ordinateurs autour de 3,4GHZ depuis environ deux ans. Nous décrivons un procédé d'accélération des calculs effectués par différents algorithmes d'inférence et de représentation de l'évolution des espèces, en utilisant le parallélisme. Le parallélisme mis en place a été réalisé à travers une librairie standard de passage de messages (Message Passing Interface). Nous montrons les différentes formes de parallélisme, les architectures de systèmes parallèles, quelques environnements qui permettent de supporter l'exécution des applications de façon à exprimer le parallélisme, ainsi que les approches utilisées pour paralléliser différents modèles d'évolution. Les versions parallèles des algorithmes d'évolution ont été développées et installées sur une « grappe » (i.e. cluster) Linux ayant 16 lames possédant chacune deux processeurs et sa propre mémoire. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : algorithmes d'évolution, arbre phylogénétique, réseau phylogénétique, transferts horizontaux de gènes, programmation parallèle, Message Passing Interface (MPI).

La Radio Logicielle (SDR) est une radio dont les transformations de la forme d'onde, modulation, démodulation des signaux d'un système radio sont mises en œuvre par du logiciel plutôt que par du matériel à fonctionnalité spécifique. Avec cette approche, l'adaptation du système à une autre norme de communication, ou même l'évolution vers une technologie plus récente peuvent être réalisés par mise à jour du logiciel sans remplacement du matériel qui serait long et coûteux. L'architecture de communication logicielle (Software Communication Architecture, SCA), est une architecture ouverte largement acceptée pour les projets de SDR. La spécification SCA minimise le coût de portage des applications en fournissant une couche d'abstraction qui rend transparentes les méthodes spécifiques de chaque système. Dans cette thèse, on s'intéresse au développement et à la programmation d'une plateforme SDR conforme à SCA.Les nouvelles plateformes de SDR sont en général implémentées sur des plateformes multiprocesseurs système sur puce (MPSoC) exploitant ses importantes ressources de calculs avec une bonne efficacité énergique. Les possibilités d'un rapide développement, déploiement et vérification des logiciels embarqués parallèles sur ces nouvelles plateformes MPSoC sont autant de points clés pour satisfaire les objectifs de performance tout en respectant les délais de mise à disposition sur le marché et le coût de développement.On a proposé un flot de conception pour la SDR avec l'exploration architecturale systématique et l'optimisation multi-objective utilisant le modèle de programmation hybride (distribué client/serveur + parallèle).On a étudié aussi la synthèse de topologie de réseau-sur-puce (PSTRP) qui est une partie du flot de conception. Le problème de la synthèse de la topologie du réseau-sur-puce peut se modéliser sous forme de programme linéaire en nombres entiers. Les résultats montrent que les contraintes d'implémentation, comme la hiérarchie du réseau sur puce, doivent être prises en compte pour obtenir un résultat à la fois mathématiquement optimisé et électroniquement réalisable.

Cette thèse présente nos travaux de recherche qui ont comme principal objectif d'assurer la portabilité des performances et le passage à l'échelle des applications scientifiques complexes exécutées sur des plates-formes multi-coeurs parallèles et hiérarchiques. La portabilité des performances est obtenue lorsque l'ordonnancement des tâches d'une application permet de réduire les périodes d'inactivité des coeurs de la plate-forme. Cette portabilité des performances peut être affectée par différents problèmes tels que des déséquilibres de charge, des communications coûteuses et des surcoûts provenant de l'ordonnancement des tâches. Le déséquilibre de charge est la conséquence de comportements de charges irrégulières et dynamiques, où le volume de calcul varie dynamiquement en fonction de la tâche et de l'étape de simulation. Les communications coûteuses sont provoquées par un ordonnancement qui ne prend pas en compte les différents temps de c! ommunication entre tâches sur une plate-forme hiérarchique. Cela est accentué par des communications non uniformes et asymétriques au niveau mémoire et réseau. Enfin, ces surcoûts peuvent être générés par des algorithmes de placement trop complexes dont les coûts ne seraient pas compensés par les gains de performance. Pour atteindre cet objectif de portabilité des performances, notre approche repose sur une récolte d'informations précises sur la topologie de la machine qui vont aider les algorithmes d'ordonnancement de tâches à prendre les bonnes décisions. Dans ce contexte, nous avons proposé une modélisation générique de la topologie des plates-formes parallèles. Le modèle comprend des latences et des bandes passantes mesurées de la mémoire et du réseau qui mettent en évidence des asymétries. Ces informations sont utilisées par nos trois algorithmes d'équilibrage de charge nommés NucoLB, HwTopoLB, et HierarchicalLB. De plus, ces algorithmes utilisent des informations provenant de l'exécution de l'application. NucoLB se concentre sur les aspects non uniformes de plates-formes parallèles, alors que HwTopoLB considère l'ensemble de la hiérarchie pour ses décisions, et HierarchicalLB combine ces algorithmes hiérarchiquement pour réduire son surcoût d'ordonnanceme! nt de tâches. Ces algorithmes cherchent à atténuer le déséquilibre de charge et des communications coûteuses tout en limitant les surcoûts de migration des tâches. Les résultats expérimentaux avec les trois régulateurs de charge proposés ont montré des améliorations de performances sur les meilleurs algorithmes de l'état de l'art: NucoLB a présenté jusqu'à 19% d'amélioration de performances sur un noeud de calcul; HwTopoLB a amélioré les performances en moyenne de 19%, et HierarchicalLB a surclassé HwTopoLB de 22% en moyenne sur des plates-formes avec plus de dix noeuds de calcul. Ces résultats ont été obtenus en répartissant la charge entre les ressources disponibles, en réduisant les coûts de communication des applications, et en gardant les surcoûts d'équilibrage de charge faibles. En ce sens, nos algorithmes d'équilibrage de charge permettent la portabilité des performances pour les applications scientifiques tout en étant indépendant de l'application et de l'architecture du système.

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.

Dans cette thèse, nous décrivons la conception et l'implémentation d'une plate-forme logicielle de spéculation de threads, ou fils d'exécution, appelée VMAD, pour "Virtual Machine for Advanced Dynamic analysis and transformation", et dont la fonction principale est d'être capable de paralléliser de manière spéculative un nid de boucles séquentiel de différentes façons, en ré-ordonnançant ses itérations. La transformation à appliquer est sélectionnée au cours de l'exécution avec pour objectifs de minimiser le nombre de retours arrières et de maximiser la performance. Nous effectuons des transformations de code en appliquant le modèle polyédrique que nous avons adapté à la parallélisation spéculative au cours de l'exécution. Pour cela, nous construisons au préalable un patron de code qui est "patché" par notre "runtime", ou support d'exécution logiciel, selon des informations de profilage collectées sur des échantillons du temps d'exécution. L'adaptabilité est assurée en considérant des tranches de code de tailles différentes, qui sont exécutées successivement, chacune étant parallélisée différemment, ou exécutée en séquentiel, selon le comportement des accès à la mémoire observé. Nous montrons, sur plusieurs programmes que notre plate-forme offre de bonnes performances, pour des codes qui n'auraient pas pu être traités efficacement par les systèmes spéculatifs de threads proposés précédemment. / In this thesis, we present a Thread-Level Speculation (TLS) framework whose main feature is to speculatively parallelize a sequential loop nest in various ways, to maximize performance. We perform code transformations by applying the polyhedral model that we adapted for speculative and runtime code parallelization. For this purpose, we designed a parallel code pattern which is patched by our runtime system according to the profiling information collected on some execution samples. We show on several benchmarks that our framework yields good performance on codes which could not be handled efficiently by previously proposed TLS systems.