La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations n-aires. La croissance du nombre de génomes sequencés créé un stress sur la génomique comparée qui croit, au pire géométriquement, avec la croissance en données de séquence. Aujourd'hui même des laboratoires de taille modeste obtient, de façon routine, plusieurs génomes à la fois - et comme des grands consortia attend de pouvoir réaliser des analyses tout-contre-tout dans le cadre de ses stratégies multi-génomes. Afin d'adresser les besoins à tous niveaux il est nécessaire de repenser les cadres algorithmiques et les technologies de stockage de données utilisés pour la génomique comparée. Pour répondre à ces défis de mise à l'échelle, dans cette thèse nous développons des méthodes originales basées sur les technologies NoSQL et MapReduce. À partir d'une caractérisation des sorts de données utilisés en génomique comparée et d'une étude des utilisations typiques, nous définissons un formalisme pour le Big Data en génomique, l'implémentons dans la plateforme NoSQL Cassandra, et évaluons sa performance. Ensuite, à partir de deux analyses globales très différentes en génomique comparée, nous définissons deux stratégies pour adapter ces applications au paradigme MapReduce et dérivons de nouveaux algorithmes. Pour le premier, l'identification d'événements de fusion et de fission de gènes au sein d'une phylogénie, nous reformulons le problème sous forme d'un parcours en parallèle borné qui évite la latence d'algorithmes de graphe. Pour le second, le clustering consensus utilisé pour identifier des familles de protéines, nous définissons une procédure d'échantillonnage itérative qui converge rapidement vers le résultat global voulu. Pour chacun de ces deux algorithmes, nous l'implémentons dans la plateforme MapReduce Hadoop, et évaluons leurs performances. Cette performance est compétitive et passe à l'échelle beaucoup mieux que les algorithmes existants, mais exige un effort particulier (et futur) pour inventer les algorithmes spécifiques.

Les systèmes de stockage actuels font face à une explosion des données à gérer. A l'échelle actuelle, il serait illusoire d'imaginer une unique entité centralisée capable de stocker et de restituer les données de tous ses utilisateurs. Bien que du point de vue de l'utilisateur, le système de stockage apparaît tel un unique interlocuteur, son architecture sous-jacente est nécessairement devenue distribuée. En d'autres termes, le stockage n'est plus assigné à un équipement centralisé, mais est maintenant distribué parmi de multiples entités de stockage indépendantes, connectées via un réseau. Par conséquent, la bande passante inhérente à ce réseau devient une ressource à prendre en compte dans le design d'un système de stockage distribué. En effet, la bande passante d'un système est intrinsèquement une ressource limitée, qui doit être convenablement gérée de manière à éviter toute congestion du système. Cette thèse se propose d'optimiser l'utilisation de la bande passante dans les systèmes de stockage distribués, en limitant l'impact du churn et des défaillances. L'objectif est double, le but est d'une part, de maximiser la bande passante disponible pour les échanges de données, et d'une autre part de réduire la consommation de bande passante inhérente aux opérations de maintenance. Pour ce faire, nous présentons trois contributions distinctes. La première contribution présente une architecture pair-à-pair hybride qui tient compte de la topologie bas-niveau du réseau, c'est à dire la présence de gateways entre les utilisateurs et le système. La seconde contribution propose un mécanisme de timeout adaptatif au niveau utilisateur, basé sur une approche Bayésienne. La troisième contribution décrit un protocole permettant la réparation efficace de données encodées via des codes à effacement. Enfin, cette thèse se conclut sur la possibilité d'utiliser des techniques d'alignement d'interférence, communément utilisées en communication numérique afin d'accroître l'efficacité des protocoles de réparation de données encodées.

Depuis la fin des années 80, s'exprime dans le monde industriel la nécessité de nouvelles organisations et de réseaux d'entreprises plus propices à une meilleure productivité. Ces nouvelles structures qui sont supposées améliorer la performance industrielle demandent que soient analysées et maîtrisées les relations d'échange interentreprises. En effet, la conception des produits, leur fabrication et leur conditionnement, leur commercialisation et leur distribution sont le fait, non plus d'entreprises isolées et autarciques, mais de réseaux d'entreprises de plus en plus complexes, pouvant prendre de surcroît différentes formes. C'est dans ce contexte, que le concept d'Architecture Industrielle apparaît et se définit comme le regroupement d'entreprises dont les relations ont un caractère durable. Parmi ces différentes architectures, nous nous intéresserons ici à celles qui mettent en relation des donneurs d'ordres et des fournisseurs. À ces ensembles d'entreprises, regroupées autour d'un objectif désormais commun, correspond un besoin de coordination de l'ensemble des actions réparties chez les différents partenaires. Nous nous sommes intéressés dans nos travaux à une formalisation de la conduite entre entreprises basée sur les notions de prise de décision distribuée et de coopération, notions qui s'opposent à la structuration hiérarchisée encore récemment dominante dans de nombreux secteurs industriels. L'ensemble de ce mémoire s'organise en quatre chapitres. Dans une première partie, nous caractérisons l'aide à la décision et le pilotage distribué des flux interentreprises. Les deux chapitres suivants constituent le coeur de notre travail. Nous y présentons notre démarche qui se fonde sur une modélisation de l'Architecture Industrielle et sur une formalisation de la coopération par un ensemble de négociations bilatérales. Enfin, le dernier chapitre reprend l'ensemble de notre démarche à travers un exemple issu du monde industriel.

Cette thèse a pour objectif d'assister la construction collaborative d'une théorie ; chaque individu doit pouvoir formuler et tester empiriquement sa propre compréhension partielle, et sans aucun effort supplémentaire contribuer à une compréhension globale partagée par le groupe. <br />Une série d'explorations touchant aux mécanismes biologiques sous-tendant la cognition, au rôle du langage en tant que vecteur de partage et de formalisation et au cycle global de construction de théorie, conduisent à un cahier des charges pour une ‘machine abstraite' qui compose des théories partielles au sein d'une conversation.<br />La machine abstraite ‘Austin' est ensuite spécifiée de façon détaillée ; elle est fondée sur l'utilisation de trois types d'actes de langage : assertions, questions et promesses. Des ‘schémas conversationnels normalisés' y concourent au traitement de l'information. De bonnes propriétés sont démontrées : terminaison en temps fini, confluence (le résultat final n'est pas affecté par l'indéterminisme du aux échanges concurrents lors de la conversation), complexité raisonnable, composition naturelle des programmes reconnus par cette machine abstraite, facilité d'analyse graphique pour ces programmes. Une grammaire générative inspirée des graphes conceptuels est proposée pour les énoncés. La ‘résolution collaborative de Sudoku' est développée comme illustration du calcul basée sur cette grammaire, puis programmée sur un prototype Java de la machine abstraite.<br />Par comparaison à la ‘programmation logique concurrente', puis aux ‘systèmes multi-experts à architecture blackboard', ‘Austin' apparaît être un compromis entre le ‘modèle déclaratif' et le ‘modèle impératif', combinant la contrôlabilité du premier avec l'expressivité du second.

Dans le domaine de l'électronique embarquée, les applications de communications numériques et de traitement d'images imposent des contraintes de temps très fortes tout en admettant une limitation en ressources et performances des unités de traitement. La restriction quant à la mémoire utilisable peut être préjudiciable pour des domaines tels que le codage vidéo. Une solution pour atteindre les objectifs d'implantation temps-réel peut passer par une distribution sur une architecture matérielle parallèle. Cette problématique constitue le cadre de ces travaux. Plus précisément, il s'agit de développer un processus de prototypage rapide dédié aux architectures parallèles à base de plusieurs processeurs de traitement numérique du signal de dernière génération (FPGA, DSP). L'aspect optimisation du point de vue de la mémoire allouée est abordé ici de manière plus précise.<br />La chaîne de prototypage a été élaborée autour de SynDEx, outil développé à l'INRIA basé sur la méthodologie AAA. Cette dernière vise à améliorer l'implantation d'un algorithme sur une architecture multi-processeurs en déterminant une distribution et ordonnancement optimaux. SynDEx réalise la phase d'adéquation proprement dite, et génère un exécutif indépendant de la cible. Nous avons dans un premier temps contribué à l'automatisation du processus sur cible multi-processeurs, en rajoutant d'une couche fonctionnelle, et en développant de nouveaux noyaux spécifiques pour des processeurs de traitement numérique du signal.<br />Dans un contexte embarqué, nos préoccupations se sont ensuite penchées sur la minimisation de la mémoire pour le code généré. C'est un problème encore très ouvert pour des architectures multi-composants. La solution trouvée, grâce aux algorithmes de coloriage de graphe, aboutit à une amélioration significative des résultats d'implantation distribuée. Le portage vers des plates-formes multi-composants est aujourd'hui automatique, notamment en intégrant directement dans l'outil SynDEx l'optimisation mémoire.<br /> Une autre partie importante de ces travaux a concerné le développement et l'intégration, à travers notre processus de prototypage, d'applications conséquentes dans les domaines du traitement des images (MPEG-4, LAR) et celui des télécommunications (MC-CDMA, UMTS). Les résultats obtenus valident l'ensemble du processus proposé, et démontrent son adaptation à des systèmes globalement orientés traitement de l'information. Le mémoire se conclut en ouvrant sur de nouvelles perspectives, en s'intéressant notamment à des systèmes multi-couches réunissant des couches « transport » de télécommunication numériques et des couches « services » de traitement des images.

Cette thèse combine le calcul haute performance à la réalité virtuelle pour permettre la conception de méthodes de couplage de composants parallèles à l'intérieur d'applications distribuées et interactives.<br /> Un nouveau modèle de couplage est présenté, conçu selon des critères de modularité, simplicité, efficacité et extensibilité. La construction des applications repose sur une séparation entre la programmation de modules parallèles réutilisables et la définition de l'application sous forme de graphe de flux de données contenant des mécanismes de filtrage et de synchronisations, permettant d'exprimer des schémas de communication collective et des politiques de couplage avancées.<br /> Ce travail sur le couplage interactif est complété par une extension haut niveau concernant le rendu distribué. En exploitant une description modulaire de la scène 3D en primitives indépendantes basées sur l'utilisation de shaders, des réseaux de filtrage permettent de combiner plusieurs flux pour acheminer efficacement les informations aux machines de rendu. Ce système est très extensible et permet la création de nouvelles applications exploitant la puissance des cartes graphiques pour décharger certains calculs des processeurs et réduire les transferts réseau.<br /> De nombreuses applications nouvelles sont ainsi développées, combinant des algorithmes de vision parallélisés immergeant l'utilisateur dans l'environnement virtuel, et des interactions avec des objets contrôlés par des simulations physiques distribuées (poterie, collisions, fluides).

So far, the distributed computing community has either assumed that all the processes of a distributed system have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. These are two extremes of the same general model: namely, n processes use l different identifiers, where 1 l n. We call this model homonymous model. To determine the power of homonymous model as well as the importance of identifiers in distributed computing, this thesis studies the consensus problem, one of the most famous distributed computing problem. We give necessary and sufficient conditions on the number of identifiers for solving consensus in a distributed system with t faulty processes in the synchronous case. We show that in crash, send omission and general omission failures model, the uniform consensus is solvable even if processes are anonymous. Thus, identifiers are not useful in that case. However identifiers become important in Byzantine failures model: 3t + 1 identifiers is necessary and sufficient for Byzantine agreement. Surprisingly the number of identifiers must be greater than n+3t 2 in presence of three facets of uncertainty: partial synchrony, Byzantine failures and homonyms. This demonstrates two differences from the classical model (which has l = n): there are situations where relaxing synchrony to partial synchrony renders agreement impossible, and, in the partially synchronous case, increasing the number of correct processes can actually make it harder to reach agreement.

Le formalisme CSP (Problème de Satisfaction de Contraintes) permet de représenter de nombreux problèmes de manière simple et efficace. Cependant, une partie de ces problèmes ne peut être résolue de manière classique et centralisée. Les causes peuvent être diverses : temps de rapatriement des données prohibitif, sécurité des données non garantie, etc. Les CSP Distribués(DisCSP), domaine intersectant celui des SMA et des CSP, permettent de modéliser et de résoudre ces problèmes naturellement distribués. Les raisonnements intra-agent et inter-agents sont alors basés sur un ensemble de relations entre différentes variables. Les agents interagissent afin de construire une solution globale à partir des solutions locales. Nous proposons, dans ce travail, un algorithme de résolution de DisCSP nommé Distributed Backtracking with Sessions (DBS) permettant de résoudre des DisCSP où chaque agent dispose d'un problème local complexe. DBS a la particularité de ne pas utiliser de nogoods comme la majorité des algorithmes de résolution de DisCSP mais d'utiliser à la place des sessions. Ces sessions sont des nombres permettant d'attribuer un contexte à chaque agent ainsi qu'à chaque message échangé durant la résolution du problème. Il s'agit d'un algorithme complet permettant l'utilisation de filtres sur les messages échangés sans remettre en cause la preuvede complétude. Notre proposition est évaluée, dans les cas mono-variable et multi-variables par agents, sur différents benchmarks classiques (les problèmes de coloration de graphes distribués et les DisCSP aléatoires) ainsi que sur un problème d'exploration en environnement inconnu.

Cette thèse vise à la conception d'un environnement pour le calcul haute performance dans un cadre d'optimisation numérique. Les outils de conception et d'optimisation sont répartis dans plusieurs équipes distantes, académiques et industrielles, qui collaborent au sein des memes projets. Les outils doivent etre fédérésau sein d'un environnement commun afin d'en faciliter l'accès aux chercheurs et ingénieurs. L'environnement que nous proposons, pour répondre aux conditions précédentes, se compose d'un système de workflow et d'un système de calcul distribué. Le premier a pour objctif de faciliter la tache de conception tandis que le second se charge de l'exécution sur des ressources de calcul distribuées. Bien sur, des suystèmes de communication entre les deux systèmes doivent etre développés. Les calculs doivent etre réalisés de manière efficace, en prenant en compte le parallélisme interne de certains codes, l'exécution synchrone ou asynchrone des taches, le transfert des données et les ressources matérielles et logicielles disponibles. De plus, l'environnement doit assurer un bon niveau de tolérance aux pannes et aux défaillances logicielles, afin de minimiser leur influence sur le résultat final ou sur le temps de calcul. Une condition importante est de pouvoir implanter un dispositif de reprise sur erreur, de telle sorte que le temps supplémentaire de traitement des erreurs soit très inférieur au temps de ré-exécution total.Dans le cadre de ce travail, notyre choix s'est porté sur le moteur de workflow Yawl, qui présente de bonnes caractéristiques en termes i) d'indépendancze vis à vis du matériel et du logiciel et ii) de mécanisme de reprise sdur erreur. Pour la partie calcul distribué, nos expériences ont été réalisées sur la plateforme Grid5000, en utilisant 64 machines différentes réparties sur cinq sites géographiques. Ce document d&taille les choix de conception de cet environnement ainsi que les ajouts et modifications que nous avons apportées à Yawl pour lui permettre de fonctionner sur une plateforme distribuée.

Across the wide range of multiprocessor architectures, all seem to share one common problem: they are hard to program. It is a general belief that parallelism is a software problem, and that perhaps we need more sophisticated compilation techniques to partition the application into concurrent threads. Many experts also make the point that the underlining architecture plays an equally important architecture before one may expect significant progress in the programmability of multiprocessors. Our approach favors a convergence of these viewpoints. The convergence of dataflow and von Neumann architecture promises latency tolerance, the exploitation of a high degree of parallelism, and light thread switching cost. Multithreaded dataflow architectures require a high degree of parallelism to tolerate latency. On the other hand, it is error-prone for programmers to partition the program into large number of fine grain threads. To reconcile these facts, we aim to advance the state of the art in automatic thread partitioning, in combination with programming language support for coarse-grain, functionally deterministic concurrency. This thesis presents a general thread partitioning algorithm for transforming sequential code into a parallel data-flow program targeting a multithreaded dataflow architecture. Our algorithm operates on the program dependence graph and on the static single assignment form, extracting task, pipeline, and data parallelism from arbitrary control flow, and coarsening its granularity using a generalized form of typed fusion. We design a new intermediate representation to ease code generation for an explicit token match dataflow execution model. We also implement a GCC-based prototype. We also evaluate coarse-grain dataflow extensions of OpenMP in the context of a large-scale 1024-core, simulated multithreaded dataflow architecture. These extension and simulated architecture allow the exploration of innovative memory models for dataflow computing. We evaluate these tools and models on realistic applications.