Les applications parallèles sont de plus en plus complexes et, même si les environnements de développement s'améliorent, de plus en plus difficiles à mettre au point que ce soit du point de vue de leur correction ou, dans le cadre qui nous intéresse, de leurs performances. Un outil intéressant pour la mise au point des performances d'une application est la visualisation de son exécution. Le travail présenté dans ce mémoire porte sur l'étude, la conception et la réalisation d'un environnement interactif extensible de visualisation pour l'évaluation de performance de systèmes parallèles. Un tel environnement permet de reconstituer le comportement d'une application d'après des traces d'exécution et facilite, par le calcul et la présentation d'indices de performances, la compréhension de son fonctionnement et la détection de ses problèmes de performance. Nous commençons par préciser les concepts importants dans un environnement de visualisation et présentons ensuite l'état de l'art en la matière. Nous décrivons ensuite la conception et la réalisation de l'environnement Scope. Cet environnement est validé par rapport aux objectifs initiaux et son utilité est démontrée par l'étude de sessions d'évaluation de performance d'applications concrètes.

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, nous nous intéressons aux techniques et outils qui permettent de concevoir et d'opti- miser les applications parallèles et réparties sur les réseaux et grappes de stations de travail. Le premier problème abordé est celui de la répartition dynamique de charge en environnement fortement hétérogène : pour répartir dynamiquement et efficacement la charge d'une application répartie, il faut (i) être en mesure d'évaluer et de comparer la disponibilité des différentes machines du réseau et (ii) savoir mettre ces informations en correspondance avec les besoins en ressources des tâches de l'application. Pour cela, nous proposons une méthodologie de modélisation empirique du comportement des éléments d'un réseau de stations de travail face à la charge. Cette méthodologie nous permet de construire des indica- teurs de charge multi-dimensions et multi-critères. Pour mettre cette méthodologie en pratique, nous avons conçu LoadBuilder, une plate-forme répartie d'expérimentation. Le deuxième problème abordé est celui de l'accès à des mécanismes et protocoles de communication multipoints fiables et ordonnés, à partir d'un système d'exploitation UNIX. Pour répondre à ce besoin des applications réparties, nous proposons une solution originale, le sys- tème de fichiers virtuel MPCFS. Ce système de fichiers permet la création de groupes de communication dynamiques et la réalisation de communications multipoints dans ces groupes, au travers de simples manipulations de fichiers et répertoires. Nous avons développé un prototype de ce système, qui peut être chargé dynamiquement dans le noyau du système Linux 2.0.

Aujourd'hui, les ordinateurs et l'Internet sont partout dans le monde : dans chaque maison, domaine et plateforme. Dans ce contexte, le standard XML s'est établi comme un moyen insigne pour la représentation et l'échange efficaces des données. Les communications et les échanges d'informations entre utilisateurs, applications et systèmes d'information hétérogènes sont désormais réalisés moyennant XML afin de garantir l'interopérabilité des données. Le codage simple et robuste de XML, à base de données textuelles semi-structurées, a fait que ce standard a rapidement envahi les communications medias. Ces communications sont devenues inter-domaines, partant de l'informatique et s'intégrant dans les domaines médical, commercial, et social, etc. Par conséquent, et au vu du niveau croissant des données XML flottantes entre des utilisateurs non-experts (employés, scientifiques, etc.), que ce soit sur les messageries instantanées, réseaux sociaux, stockage de données ou autres, il devient incontournable de permettre aux utilisateurs non-experts de manipuler et contrôler leurs données (e.g., des parents qui souhaitent appliquer du contrôle parental sur les messageries instantanées de leur maison, un journaliste qui désire regrouper et filtrer des informations provenant de différents flux RSS, etc.). L'objectif principal de cette thèse est l'étude des manipulations des données XML par des utilisateurs non-experts. Quatre principales catégories ont été identifiées dans la littérature : i) les langages visuels orientés XML, ii) les Mashups, iii) les techniques de manipulation des données XML, et iv) les DFVPL (langages de programmation visuel à base de Dataflow), couvrant différentes pistes. Cependant, aucune d'entre elles ne fournit une solution complète. Dans ce travail de recherche, nous avons formellement défini un Framework de manipulation XML, intitulé XA2C (XML-oriented mAnipulAtion Compositions). XA2C représente un environnement de programmation visuel (e.g., Visual-Studio) pour un DFVPL orienté XML, intitulé XCDL (XML-oriented Composition Definition Language) qui constitue la contribution majeure de cette thèse. XCDL, basé sur les réseaux de Pétri colorés, permet aux non-experts de définir, d'arranger et de composer des opérations de manipulation orientées XML. Ces opérations peuvent être des simples sélections/projections de données, ainsi que des opérations plus complexes de modifications de données (insertion, suppression, tatouage, etc.). Le langage proposé traite les données XML à base de documents ou de fragments. En plus de la définition formelle (syntaxique et sémantique) du langage XCDL, XA2C introduit une architecture complète à base d'un compilateur et un environnement d'exécution dédiés. Afin de tester et d'évaluer notre approche théorique, nous avons développé un prototype, intitulé X-Man, avec un Framework d'évaluation pour les langages et outils visuels de programmation orientés XML. Une série d'études de cas et d'expérimentations a été réalisée afin d'évaluer la qualité d'usage de notre langage, et de le comparer aux solutions existantes. Les résultats obtenus soulignent la supériorité de note approche, notamment en termes de qualité d'interaction, de visualisation, et d'utilisation. Plusieurs pistes sont en cours d'exploration, telles que l'intégration des opérations plus complexes (opérateurs de contrôle, boucles, etc.), les compositions automatiques, et l'extension du langage pour gérer la spécificité des formats dérivés du standard XML (flux RSS, RDF, SMIL, etc.)

Cette étude consiste à résoudre de grands systèmes linéaires creux sur des calculateurs massivement parallèles. Ces systèmes linéaires, souvent rencontrés lors de la simulation numérique de problèmes de mécanique des structures par des codes de calcul par éléments finis, sont résolus avec des coûts très importants en temps de calcul et en espace mémoire. Dans cette thèse, nous mettons au point un parallélisme à deux niveaux et l'intégrons dans les méthodes de décomposition de domaine de type FETI. La démarche s'est organisée autour de trois chapitres principaux. Dans un premier temps, nous mettons en œuvre un solveur direct pour inverser des systèmes linéaires creux qui peuvent être symétriques ou non symétriques, réels ou complexes, à second membre simple ou multiple. La mise en œuvre, basée sur une technique de renumérotation de type dissection emboîtée, est complétée par un point utile dans beaucoup de méthodes de décomposition de domaine (construction d'un préconditionneur ou formulation de l'opérateur de FETI) : la détection de modes à énergie nulle des systèmes singuliers. Dans un deuxième temps, nous parallélisons le solveur direct à travers un modèle de parallélisme à mémoire partagée (multi-threading) pour tirer profit des nouveaux processeurs multi-coeurs. Dans un troisième temps, nous intégrons cette version multi-threads du solveur dans les méthodes FETI pour inverser les problèmes locaux en parallèle. Les résultats de cette étude mettent en évidence l'utilité des travaux effectués et l'intérêt d'utiliser comme solveur local dans les méthodes FETI un solveur direct parallèle robuste et efficace. Tout ceci peut donner accès à de nouvelles gammes de problèmes en calcul des structures. Il serait intéressant de revoir le parallélisme à gros grains entre sous-domaines dans les méthodes FETI. Cela pourrait consister à utiliser la version du solveur direct à second membre multiple pour améliorer plus la méthode itérative utilisée dans la résolution du problème d'interface.

Les calculs de réactivité constituent une brique fondamentale dans la simulation des coeurs des réacteurs nucléaires. Ceux-ci conduisent à la résolution de problèmes aux valeurs propres généralisées via l'algorithme de la puissance inverse. A chaque itération, on est amené à résoudre un système linéaire de manière approchée via un algorithme d'itérations imbriquées. Il est difficile de traiter les modélisations très fines avec le solveur développé à EDF, au sein de la plate-forme Cocagne, en raison de la consommation mémoire et du temps de calcul. Au cours de cette thèse, on étudie une méthode de décomposition de domaine de type Schur dual. Plusieurs placements de l'algorithme de décomposition de domaine au sein du système d'itérations imbriquées sont envisageables. Deux d'entre eux ont été implémentés et les résultats analysés. Le deuxième placement, utilisant les spécificités des éléments finis de Raviart-Thomas et de l'algorithme des directions alternées, conduit à des résultats très encourageants. Ces résultats permettent d'envisager l'industrialisation de la méthodologie associée.

Cette thèse porte sur le traitement des requêtes par similarité sur les données de haute dimensionnalité, notamment multimédias, et, parmi elles, les images plus particulièrement. Ces requêtes, notamment celles des k plus proches voisins (kNN), posent des problèmes de calcul de par la nature des données elles-mêmes et de la taille de la base des données. Nous avons étudié leurs performances quand une méthode de partitionnement est appliquée sur la base de données pour obtenir et exploiter des classes. Nous avons proposé une taille et un nombre optimaux de ces classes pour que la requête puisse être traitée en temps optimal et avec une haute précision. Nous avons utilisé la recherche séquentielle comme base de référence. Ensuite nous avons proposé des méthodes de traitement de requêtes parallèles sur une grappe de machines. Pour cela, nous avons proposé des méthodes d'allocation des données pour la recherche efficace des kNN en parallèle. Nous proposons de même, un nombre réduit de noeuds sur la grappe de machines permettant néanmoins des temps de recherche sous-linéaires et optimaux vis-à-vis des classes déterminées précédemment. Nous avons utilisé des donnés synthétiques et réelles pour les validations pratiques. Dans les deux cas, nous avons pu constater des temps de réponse et une qualité des résultats supérieurs aux méthodes existantes, lesquelles, au-delà d'un faible nombre des dimensions, deviennent inefficaces.

Devant les difficultés croissantes liées au coût en développement, en consommation, en surface de silicium, nécessaires aux nouvelles optimisations des architectures monocœur, on assiste au retour en force du parallélisme et des coprocesseurs spécialisés dans les architectures. Cette technique apporte le meilleur compromis entre puissance de calcul élevée et utilisations des ressources. Afin d'exploiter efficacement toutes ces architectures, il faut partitionner le code en tâches, appelées codelet, avant de les distribuer aux différentes unités de calcul. Ce partionnement est complexe et l'espace des solutions est vaste. Il est donc nécessaire de développer des outils d'automatisation efficaces pour le partitionnement du code séquentiel. Les travaux présentés dans cette thèse portent sur l'élaboration d'un tel processus de partitionnement. L'approche d'Astex est basée sur la spéculation, en effet les codelets sont construits à partir des profils d'exécution de l'application. La spéculation permet un grand nombre d'optimisations inexistantes ou impossibles statiquement. L'élaboration, la gestion dynamique et l'usage que l'on peut faire de la spéculation sont un vaste sujet d'étude. La deuxième contribution de cette thèse porte sur l'usage de la spéculation dans l'optimisation des communications entre processeur et coprocesseur et traite en particulier du cas du GPGPU, i.e. l'utilisation d'un processeur graphique comme coprocesseur de calcul intensif.

Sur plusieurs problèmes il est difficile d'avoir un seul algorithme qui résout optimalement (en temps d'exécution) toutes ses instances. Ce constat motive l'élaboration des approches permettant de combiner plusieurs algorithmes résolvant le même problème. Les approches permettant la combinaison d'algorithmes peuvent être mise en oeuvre au niveau système (en construisant des bibliothèques, des langages et composants adaptatifs etc.) ou au niveau purement algorithmique. Ce travail se focalise sur les approches génériques de combinaison d'algorithmes au niveau algorithmique avec en particulier l'approche du portfolio d'algorithmes. Un portfolio d'algorithmes définit une exécution concurrente de plusieurs algorithmes résolvant un même problème. Dans une telle exécution, les algorithmes sont entrelacées dans le temps et/ou l'espace. Sur une instance à résoudre, l'exécution est interrompue dès qu'un des algorithmes trouve une solution. Nous proposons dans cette thèse une classification des techniques de combinaison d'algorithmes. Dans celle ci nous précisons pour chaque technique le contexte le plus adapté pour son utilisation. Nous proposons ensuite deux techniques de construction des portfolio d'algorithmes. La première technique est basée sur une adaptation de la méthode des plus proches voisins en apprentissage automatique pour la combinaison des algorithmes. Cette technique est adaptative car elle essaie sur chaque instance de trouver un sous ensemble d'algorithmes adaptés pour sa résolution. Nous l'appliquons dans la combinaison des algorithmes itératifs pour la résolution des systèmes linéaires et nous montrons sur un jeu d'environ mille matrices creuses qu'elle permet de réduire le nombre d'itérations et le temps nécéssaire dans la résolution. En outre, sur certains jeux d'expérimentations, ces résultats montrent que la technique proposée peut dans la plupart des cas trouver l'algorithme le plus adapté à sa résolution. La seconde technique est basée sur le problème de partage de ressources que nous formulons. Etant donnés, un problème cible, un jeu de données le représentant, un ensemble d'algorithmes candidats le résolvant et le comportement en temps d'exécution du jeu de données sur les algorithmes candidats, le problème de partage de ressources a pour objectif de trouver la meilleure répartition statique des ressources aux algorithmes candidats de sorte à minimiser en moyenne le temps de résolution du jeu de données cibles. Ce problème vise à trouver une solution en moyenne plus robuste que chacun des algorithmes candidats pris séparémment. Nous montrons que ce problème est NP-complet et proposons deux familles d'algorithmes approchés et exacts pour le résoudre. Nous validons les solutions proposées en prenant des données issues d'une base de données pour SAT. Les résultats obtenus montrent que les solutions proposées permettent effectivement de bénéficier de la complémentarité des algorithmes résolvant un même problème pour la construction des algorithmes robustes.

Dans cette thèse, nous montrons que les optimisations source-à-source sont un moyen efficace pour générer des programmes irréguliers ou parallèles performants à partir d'une implémentation. Après avoir présenté l'évolution des architectures des processeurs, nous proposons deux méthodes distinctes. La première pour extraire des codelets d'un programme irréguliers, les optimiser et prédire les performances du programme modifié. L'autre pour limiter l'impact des problèmes d'alignements dus à la vectorisation ou aux conflits de bancs. Nous présentons aussi différentes techniques de parallélisation, l'une générant des codelets parallèles, l'autre ordonnançant un graphe de taches sur un système hétérogène.