Le pattern mining est un domaine du data mining dont le but est l'extraction de régularité dans les données. Ce document présente nos contributions au domaine selon 3 axes : 1. Le domaine du pattern mining est jeune et il y existe encore beaucoup de types de régularités qu'un analyste serait intéressé de découvrir mais qui ne sont pas encore gérées. Nous avons contribué à deux nouveaux types de patterns: les patterns graduels et les patterns périodiques avec "ruptures". Nous avons aussi proposé ParaMiner, un algorithme original pour le pattern mining générique, qui permet à des analystes de spécifier directement le type de patterns qui les intéressent. 2. Le pattern mining demande beaucoup de ressources de calcul. Pour réduire le temps de calcul, nous avons étudié comment exploiter le parallélisme des processeurs multicoeurs. Nos résultats montrent que des techniques classiques en pattern mining sont mal adaptées au parallélisme, et nous avons proposé des solutions. 3. Notre objectif à long terme est de rendre le pattern mining plus facile à utiliser par les analystes. Il y a beaucoup à faire dans ce but, actuellement les analystes doivent travailler sur de longues listes de millions de patterns. Nous présentons nos premiers résultats, dans le contexte de la fouille de traces d'exécution de processeurs.

Afin de pouvoir répondre au mieux aux différents appels d'offres, les constructeurs de grappe de calcul ont besoin d'outils et de méthodes permettant d'aider au mieux la prise de décisions en terme de design architectural. Nos travaux se sont donc intéressés à l'estimation des temps de calcul et à l'étude de la congestion sur le réseau InfiniBand. Ces deux problèmes sont souvent abordés de manière globale. Néanmoins, une approche globale ne permet pas de comprendre les raisons des pertes de performance liées aux choix architecturaux. Notre approche s'est donc orientée vers une étude plus fine. Pour évaluer les temps de calcul, la démarche proposée s'appuie sur une analyse statique ou semistatique du code source afin de le découper en blocs, avant d'effectuer un micro-benchmarking de ces blocs sur l'architecture cible. Pour l'estimation des temps de communication, un modèle de répartition de bande passante pour le réseau InfiniBand a été développé, permettant ainsi de prédire l'impact lié aux communications concurrentes. Ce modèle a ensuite été intégré dans un simulateur pour être validé sur un ensemble de graphes de communication synthétiques et sur l'application Socorro.

Les automates cellulaires ont été introduits il y a une soixantaine d'années par von Neumann et Ulam qui cherchaient à définir les caractéristiques d'un système formel apte au calcul universel et à l'auto-reproduction. Leur utilité a été rapidement reconnue dans des domaines variés comme la physique et la biologie, pour modéliser des phénomènes complexes. En informatique, ils offrent un cadre privilégié pour l'étude du parallélisme massif. Leur description est simple et bien formalisée. Ils ont a la même puissance de calcul que les machines de Turing et de plus la richesse algorithmique propre aux machines parallèles tout en restant un modèle physiquement réaliste. Dans le cadre unificateur de la reconnaissance de langages, je m'intéresse aux questions de complexité sur les automates cellulaires, avec une attention particulière aux petites classes de complexité : calcul en temps réel (i.e. temps minimal) et en temps linéaire; en effet, c'est pour ces classes que l'apport du parallélisme est remarquable par rapport au mode séquentiel. Avec pour objectif de préciser les capacités de ce modèle et de mieux comprendre ce qu'est un calcul parallèle, trois tendances majeures se dégagent de mes travaux : l'étude des limites de ce modèle, la comparaison avec d'autres modèles de calcul et la question de l'influence de certains paramètres comme la dimension ou le voisinage sur ses capacités de reconnaissance.

L'informatique a changé profondément les aspects méthodologiques du processus de découverte dans les différents domaines du savoir. Les chercheurs ont à leur disposition aujourd'hui de nouvelles capacités qui permettent d'envisager la résolution de nouveaux problèmes. Les plates-formes parallèles et distribuées composées de ressources partagées entre différents participants peuvent rendre ces nouvelles capacités accessibles à tout chercheur et offrent une puissance de calcul qui a été limitée jusqu'à présent aux projets scientifiques les plus grands (et les plus riches). Dans ce document qui regroupe les résultats obtenus pendant cette thèse, nous explorons quatre facettes différentes de la façon dont les organisations s'engagent dans une collaboration sur de plates-formes parallèles et distribuées. En utilisant des outils classiques de l'analyse combinatoire, de l'ordonnancement multi-objectif et de la théorie des jeux, nous avons montré comment calculer des ordonnancements avec un bon compromis entre les résultats obtenus par les participants et la performance globale de la plate-forme. En assurant des résultats justes et en garantissant des améliorations de performance pour les différents participants, nous pouvons créer une plate-forme efficace où chacun se sent toujours encouragé à collaborer et à partager ses ressources. Tout d'abord, nous étudions la collaboration entre organisations égoïstes. Nous montrons que le comportement égoïste entre les participants impose une borne inférieure sur le makespan global. Nous présentons des algorithmes qui font face à l'égoïsme des organisations et qui présentent des résultats équitables. La seconde étude porte sur la collaboration entre les organisations qui peuvent tolérer une dégradation limitée de leur performance si cela peut aider à améliorer le makespan global. Nous améliorons les bornes d'inapproximabilité connues sur ce problème et nous présentons de nouveaux algorithmes dont les garanties sont proches de l'ensemble de Pareto (qui regroupe les meilleures solutions possibles). La troisième forme de collaboration étudiée est celle entre des participants rationnels qui peuvent choisir la meilleure stratégie pour leur tâches. Nous présentons un modèle de jeu non coopératif pour le problème et nous montrons comment l'utilisation de "coordination mechanisms" permet la création d'équilibres approchés avec un prix de l'anarchie borné. Finalement, nous étudions la collaboration entre utilisateurs partageant un ensemble de ressources communes. Nous présentons une méthode qui énumère la frontière des solutions avec des meilleurs compromis pour les utilisateurs et sélectionne la solution qui apporte la meilleure performance globale.

Nous proposons tout d'abord une étude de plusieurs problèmes de l'algorithmique distribuée. Nous fournissons un modèle formel appliqué aux réseaux de diffusion anonymes. Dans ce modèle, nous caractérisons les graphes dans lesquels il est possible de résoudre l'énumération et l'élection. Cette caractérisation se base sur la notion d'homomorphisme de graphes. Nous proposons deux algorithmes dont la complexité est polynomiale et qui améliorent les complexités exponentielles connues jusqu'à présent. Dans un second temps, nous étudions le problème du calcul de l'état global et nous introduisons la notion de weak snapshot. Nous montrons qu'il existe des solutions pour ce problème dans les réseaux anonymes. Nous présentons plusieurs résultats concernant le calcul de l'état global en liaison avec des applications telles que le calcul de points de reprise, la détection de la terminaison ou encore le calcul d'une cartographie du réseau. Dans un cadre plus pratique, nous présentons la conception, le développement et l'implémentation des algorithmes proposés pour le calcul de l'état global au sein du logiciel de simulation et de visualisation ViSiDiA.

La croissance exponentielle de la génération de données pour la bioinformatique couplée à une stagnation des fréquences d'horloge des processeurs modernes accentuent la nécessité de fournir des implémentation tirant bénéfice des capacités parallèles des ordinateurs modernes. Cette thèse se concentre sur des algorithmes et implementations pour des problèmes de bioinformatique. Plusieurs types de parallélisme sont décrits et exploités. Cette thèse présente des applications en génétique, avec un outil de détection de QTL paralllisé sur GPU, en comparaison de structures de protéines, avec un outil permettant de trouver des régions similaires entre protéines parallélisé sur CPU, ainsi qu'à l'analyse de larges graphes avec une implémentation multi-GPUs d'un nouvel algorithme pour le problème du "All-Pairs Shortest Path".

L'objectif de cette thèse était de proposer, puis de valider expérimentalement, un ensemble de méthodes algorithmiques permettant le remaillage parallèle de maillages distribués, en s'appuyant sur une méthode séquentielle de remaillage préexistante. Cet objectif a été atteint par étapes : définition de structures de données et de schémas de communication adaptés aux maillages distribués, permettant le déplacement à moindre coût des interfaces entre sous-domaines sur les processeurs d'une architecture à mémoire distribuée ; utilisation d'algorithmes de répartition dynamique de la charge adaptés aux techniques parallèles de remaillage ; conception d'algorithmes parallèles permettant de scinder le problème global de remaillage parallèle en plusieurs sous-tâches séquentielles, susceptibles de s'exécuter concurremment sur les processeurs de la machine parallèle. Ces contributions ont été mises en oeuvre au sein de la bibliothèque parallèle PaMPA, en s'appuyant sur les briques logicielles MMG3D (remaillage séquentiel de maillages tétraédriques) et PT-Scotch (repartitionnement parallèle de graphes). La bibliothèque PaMPA offre ainsi les fonctionnalités suivantes : communication transparente entre processeurs voisins des valeurs portées par les noeuds, les éléments, etc. ;remaillage, selon des critères fournis par l'utilisateur, de portions du maillage distribué, en offrant une qualité constante, que les éléments à remailler soient portés par un unique processeur ou bien répartis sur plusieurs d'entre eux ; répartition et redistribution de la charge des maillages pour préserver l'efficacité des simulations après remaillage.

La donnée sismique depuis sa conception (modélisation d'acquisitions sismiques), dans sa phase de traitement (prétraitement et migration) et jusqu'à son exploitation pour en extraire les informations géologiques pertinentes nécessaires à l'identification et l'exploitation optimale des réservoirs d'hydrocarbures (interprétation), génère un volume important de calculs. Lors de la phase d'imagerie, ce volume est d'autant plus important que les différentes simulations mises en jeu se veulent fidèles à la physique du sous sol. Une puissance de calcul importante est donc nécessaire pour réduire le temps, et donc le coût, des études en imagerie sismique et pour améliorer le résultat final de ces études en reproduisant plus fidèlement les phénomènes physiques mis en jeu et en considérant de plus larges plages de fréquences. Lors de la phase d'interprétation, le calcul d'attributs sismiques (type : cohérence, lissage, analyse spectrale, etc.) offre une aide de choix à l'interprétateur. Ces calculs se font usuellement selon un cycle itératif pour sélectionner les paramètres les plus adaptés. Ce cycle est rendu fastidieux par la complexité et donc le temps des calculs. L'exploitation optimale des ressources de calcul disponibles dans la station d'interprétation est nécessaire pour raccourcir ce cycle ainsi que pour la mise en œuvre d'algorithmes de traitements plus performants. Les technologies accélératrices permettent de déléguer certains types de calculs à des unités puissantes (GPGPU, FPGA, MIC) dans le cadre de plateformes hétérogènes en alternative au CPU utilisé habituellement. La puissance de calcul accessible par ce biais dépasse de plusieurs ordres de grandeur ce que peuvent proposer les architectures généralistes utilisées traditionnellement en calcul hautes performances. Ces nouvelles architectures sont une alternative très intéressante pour augmenter la puissance de calcul sans augmenter pour autant la puissance électrique consommée et thermique dissipée. Néanmoins, les contraintes d'utilisation font qu'à l'heure actuelle ces nouveaux types de calculateurs sont difficiles à programmer et à optimiser dans le cadre du calcul scientifique et conduisent à des codes dédiés à une architecture particulière. Les simulations reposant sur la résolution de l'équation des ondes en 2D ou 3D discrétisée sur des grilles (utilisées pour la modélisation et la migration sismiques), ainsi que les algorithmes de traitement d'images (utilisés lors de l'interprétation des données sismiques) sont des candidats potentiels pour une implémentation très efficace sur ces nouvelles architectures. Dans cette thèse, nous proposons une étude de l'apport, des contraintes ainsi que des limites éventuelles de ces technologies accélératrices pour l'imagerie et l'interprétation sismiques. Dans la première partie du manuscrit, après une brève introduction à l'imagerie sismique dans le premier chapitre, nous passons en revue dans le deuxième chapitre les algorithmes utilisés dans ce cadre pour mettre en exergue la complexité de ces algorithmes et les besoins en puissance de calcul qui en découlent. Nous exposons ensuite dans le chapitre 3 les différentes technologies matérielles et logicielles actuelles permettant de répondre à ces besoins. Dans la deuxième partie de ce manuscrit, nous étudions l'impact de l'utilisation des technologies accélératrices en imagerie sismique (chapitre 4) et dans le cadre de l'interprétation sismique (chapitre 5). Dans le chapitre 4, nous proposons ainsi diverses implémentations d'algorithmes utilisés en imagerie sismique reposant sur la simulation de la propagation des ondes sismiques dans le sous- sol via une discrétisation de l'équation d'onde en 2D et en 3D et sa résolution par différences finies. Nous analysons le comportement de ces implémentations sur divers types d'accélérateurs. Nous montrons qu'une prise en compte fine des ressources disponibles au niveau de l'unité de calcul (bandes passantes, capacité mémoire, organisation des données en mémoire et motifs d'accès à ses différents niveaux) est nécessaire pour tirer partie de chaque type d'architecture et au-delà de cela, de chaque génération d'une architecture donnée. De plus, les communications entre l'accélérateur et la machine hôte ont un coût qu'il est nécessaire de limiter pour ne pas pénaliser les temps de calcul. Nous proposons différentes techniques pour minimiser ces coûts et analysons leur comportement. Ces implémentations reposent sur une décomposition du domaine de simulation global, qui peut être de taille importante, en sous-domaines ce qui induit également des communications entre nœuds dans le cadre de systèmes à mémoire distribuée. Dans le chapitre 5, une étude similaire est proposée pour le calcul d'attributs sismiques. Contrairement aux algorithmes d'imagerie sismique, ce sont les ressources de la station de travail locale qui sont exploitées pour tendre vers un calcul interactif des attributs facilitant ainsi la tâche de l'interprétateur. Une implémentation performante de la transposition de cubes sismiques 3D est proposée. Elle sert de base aux algorithmes étudiés par la suite. Est étudiée ensuite une première classe d'algorithmes basés sur le calcul de la similarité entre traces sismiques voisines : cohérence, calcul de pendage ainsi qu'un algorithme innovant mis au point lors de cette étude. Les calculs sur accélérateur graphique du lissage gaussien par filtres FIR et IIR sont comparés. Des facteurs d'accélération variant entre 8 et 160 par rapport aux processeurs classiques sont reportés. Ces travaux ouvrent la voie à une intégration complète et systématique des accélérateurs de calcul tout le long du cycle de traitement des données sismiques et ce d'autant plus que nous avons démontré que cette intégration ne se fait pas aux dépends de la fiabilité et de la maintenabilité du code existant.

Nous nous intéressons dans ce manuscrit au langage ReactiveML, qui est une extension de ML avec des constructions inspirées des langages synchrones. L'idée de ces langages est de diviser l'exécution d'un programme en une suite d'instants logiques discrets. Cela permet de proposer un modèle de concurrence déterministe que l'on peut compiler vers du code séquentiel impératif. La principale application de ReactiveML est la simulation discrète, par exemple de réseaux de capteurs. Nous cherchons ici à programmer des simulations à grande échelle, ce qui pose deux questions : sait-on les programmer de façon simple et modulaire ? sait-on ensuite exécuter ces programmes efficacement ? Nous répondons à la première question en proposant une extension du modèle synchrone appelée domaines réactifs. Elle permet de créer des instants locaux invisibles de l'extérieur. Cela rend possible le raffinement temporel, c'est-à-dire le remplacement d'une approximation d'un système par une version plus détaillée sans changer son comportement externe. Nous développons dans ce manuscrit la sémantique formelle de cette construction ainsi que plusieurs analyses statiques, sous forme de systèmes de types-et-effets, garantissant la sûreté des programmes dans le langage étendu. Enfin, nous montrons également plusieurs implémentations parallèles du langage pour tenter de répondre à la question du passage à l'échelle des simulations. Nous décrivons tout d'abord une implémentation avec threads communiquant par mémoire partagée et basée sur le vol de tâches, puis une seconde implémentation utilisant des processus lourds communiquant par envoi de messages.

La résolution de très grands systèmes linéaires creux est une composante de base algorithmique fondamentale dans de nombreuses applications scientifiques en calcul intensif. La résolution per- formante de ces systèmes passe par la conception, le développement et l'utilisation d'algorithmes parallèles performants. Dans nos travaux, nous nous intéressons au développement et l'évaluation d'une méthode hybride (directe/itérative) basée sur des techniques de décomposition de domaine sans recouvrement. La stratégie de développement est axée sur l'utilisation des machines mas- sivement parallèles à plusieurs milliers de processeurs. L'étude systématique de l'extensibilité et l'efficacité parallèle de différents préconditionneurs algébriques est réalisée aussi bien d'un point de vue informatique que numérique. Nous avons comparé leurs performances sur des systèmes de plusieurs millions ou dizaines de millions d'inconnues pour des problèmes réels 3D .