Plusieurs types d’expérimentation existent pour étudier et comprendre les systèmes biologiques. Dans ces travaux, nous nous intéressons à la simulation in silico, c’est-à-dire à la simulation numérique de modèles sur un ordinateur. Les systèmes biologiques sont composés d’entités, à la fois nombreuses et variées, en interaction les unes avec les autres. Ainsi, ils peuvent être modélisés par l’intermédiaire de deux approches complémentaires : l’approche population-centrée et l’approche individu-centrée. Face à la multitude et à la variété des phénomènes composant les systèmes biologiques, il nous semble pertinent de coupler ces deux approches pour obtenir une modélisation mixte. En outre, en raison de la quantité conséquente d’informations que représente l’ensemble des entités et des interactions à modéliser, la simulation numérique des systèmes biologiques est particulièrement coûteuse en temps de calcul informatique. Ainsi, dans ce mémoire, nous proposons des solutions techniques de parallélisation permettant d’exploiter au mieux les performances offertes par les architectures multicoeur et multiprocesseur et les architectures graphiques pour la simulation de systèmes biologiques à base de modélisations mixtes. Nous appliquons nos travaux au domaine de la coagulation du sang et plus particulièrement à l’étude de la cinétique biochimique à l’échelle microscopique ainsi qu’à la simulation d’un vaisseau sanguin virtuel. Ces deux applications nous permettent d’évaluer les performances offertes par les solutions techniques de parallélisation que nous proposons, ainsi que leur pertinence dans le cadre de la simulation des systèmes biologiques. / Several types of experimentation exist to study and understand biological systems. Inthis document, we take an interest in in silico simulation, i.e. numerical simulation ofmodels on a computer. Biological systems are made of many various entities, interactingwith each other. Therefore, they can be modeled by two complementary approaches: thepopulation-based approach and the individual-based one. Because of the multitude anddiversity of the phenomena constituting biological systems, we find the coupling of thesetwo approaches relevant to provide a hybrid modelisation. Moreover, because of the hugequantity of data that the entities and interactions represent, numerical simulation of biologicalsystems is especially computationaly intensive. This is why, in this document, we proposeparallel computing methods to take advantage of the performances offered by multicore andmultiprocessor architectures and by graphical ones for the simulation of biological systemsusing hybrid modelisations. We apply our work to blood coagulation and especially to thestudy of biochemical kinetics at the microscopic scale and the simulation of a virtual bloodvessel. These two applications enable us to assess both the performances obtained by theparallel computing methods we proposed and their relevance for biological systems simulation.

Les caractéristiques topologiques d'un objet sont fondamentales dans le traitement d'image. Dansplusieurs applications, notamment l'imagerie médicale, il est important de préserver ou de contrôlerla topologie de l'image. Cependant la conception de telles transformations qui préservent à la foi la topologie et les caractéristiques géométriques de l'image est une tache complexe, en particulier dans le cas du traitement parallèle.Le principal objectif du traitement parallèle est d'accélérer le calcul en partagent la charge de travail à réaliser entre plusieurs processeurs. Si on approche cet objectif sous l'angle de la conception algorithmique, les stratégies du calcul parallèle exploite l'ordre partiel des algorithmes, désigné également par le parallélisme naturel qui présent dans l'algorithme et qui fournit deux principales sources de parallélisme : le parallélisme de données et le parallélisme fonctionnelle.De point de vue conception architectural, il est essentiel de lier l'évolution spectaculaire desarchitectures parallèles et le traitement parallèle. En effet, si les stratégies de parallèlisation sont devenues nécessaire, c'est grâce à des améliorations considérables dans les systèmes de multitraitement ainsi que la montée des architectures multi-core. Toutes ces raisons font du calculeparallèle une approche très efficace. Dans le cas des machines à mémoire partagé, il existe un autreavantage à savoir le partage immédiat des données qui offre plus de souplesse, notamment avec l'évolution du système d'interconnexion entre processeurs, dans la conception de ces stratégies etl'exploitation du parallélisme de données et le parallélisme fonctionnel.Dans cette perspective, nous proposons une nouvelle stratégie de parallèlisation, baptisé SD&M(Split, Distribute and Merge) stratégie qui couvrent une large classe d'opérateurs topologiques.SD&M a été développée afin de fournir un traitement parallèle de tout opérateur basée sur latransformation topologique. Basé sur cette stratégie, nous avons proposé une série d'algorithmestopologiques parallèle (nouvelle version ou version adapté). Nos principales contributions sont :(1)Une nouvelle approche pour calculer la ligne de partage des eaux basée sur ‘MSF transform'.L'algorithme proposé est parallèle, préserve la topologie, n'a pas besoin d'extraction préalable deminima et adaptée pour les machines parallèle à mémoire partagée. Il utilise la même approchede calcule de flux proposé par Jean Cousty et il ne nécessite aucune étape de tri, ni l'utilisationd'une file d'attente hiérarchique. Cette contribution a été précédé par une étude intensive desalgorithmes de calcule de la ligne de partage des eaux dans le cas discret.(2)Une étude similaire sur les algorithmes d'amincissement a été menée. Elle concerne seizealgorithmes d'amincissement qui préservent la topologie. En sus des critères de performance,nous somme basé sur deux critères qualitative pour les comparer et les classés. Après cetteclassification, nous avons essayé d'obtenir de meilleurs résultats grâce avec une version adaptéede l'algorithme d'amincissement proposé par Michel Couprie.(3)Une méthode de calcul amélioré pour le lissage topologique grâce à la combinaison du calculparallèle de la distance euclidienne (en utilisant l'algorithme Meijster) et l'amincissement/épaississement parallèle (en utilisant la version adaptée de l'algorithme de Couprie déjàmentionné). / Topological features of an object are fundamental in image processing. In many applications,including medical imaging, it is important to maintain or control the topology of the image. Howeverthe design of such transformations that preserve topology and geometric characteristics of the inputimage is a complex task, especially in the case of parallel processing.Parallel processing is applied to accelerate computation by sharing the workload among multipleprocessors. In terms of algorithm design, parallel computing strategies profits from the naturalparallelism (called also partial order of algorithms) present in the algorithm which provides two main resources of parallelism: data and functional parallelism. Concerning architectural design, it is essential to link the spectacular evolution of parallel architectures and the parallel processing. In effect, if parallelization strategies become necessary, it is thanks to the considerable improvements in multiprocessing systems and the rise of multi-core processors. All these reasons make multiprocessing very practical. In the case of SMP machines, immediate sharing of data provides more flexibility in designing such strategies and exploiting data and functional parallelism, notably with the evolution of interconnection system between processors.In this perspective, we propose a new parallelization strategy, called SD&M (Split Distribute andMerge) strategy that cover a large class of topological operators. SD&M has been developed in orderto provide a parallel processing for many topological transformations.Based on this strategy, we proposed a series of parallel topological algorithm (new or adaptedversion). In the following we present our main contributions:(1)A new approach to compute watershed transform based on MSF transform, that is parallel,preserves the topology, does not need prior minima extraction and suited for SMP machines.Proposed algorithm makes use of Jean Cousty streaming approach and it does not require any sortingstep, or the use of any hierarchical queue. This contribution came after an intensive study of allexisting watershed transform in the discrete case.(2)A similar study on thinning transform was conducted. It concerns sixteen parallel thinningalgorithms that preserve topology. In addition to performance criteria, we introduce two qualitativecriteria, to compare and classify them. New classification criteria are based on the relationshipbetween the medial axis and the obtained homotopic skeleton. After this classification, we tried toget better results through the proposal of a new adapted version of Couprie's filtered thinningalgorithm by applying our strategy.(3)An enhanced computation method for topological smoothing through combining parallelcomputation of Euclidean Distance Transform using Meijster algorithm and parallel Thinning–Thickening processes using the adapted version of Couprie's algorithm already mentioned.

Depuis les premiers ordinateurs on est en quête de machines plus rapides, plus puissantes, plus performantes. Après avoir épuisé le filon de l’augmentation de la fréquence, les constructeurs se sont tournés vers les multi-cœurs. Le modèle de calcul actuel repose sur les threads de l'OS qu’on exploite à travers différents langages à constructions parallèles. Cependant, la programmation multithread reste un art délicat car le calcul parallèle découpé en threads souffre d’un grand défaut : il est non déterministe.Pourtant, on peut faire du calcul parallèle déterministe, à condition de remplacer le modèle des threads par un modèle s’appuyant sur l’ordre partiel des dépendances. Dans cette thèse, nous proposons un modèle alternatif d’architecture qui exploite le parallélisme d’instructions (ILP) présent dans les programmes. Nous proposons de nombreuses techniques pour s’affranchir de la plupart des dépendances architecturales et obtenir ainsi un ILP qui croît avec la taille de l’exécution. L’ILP qu’on atteint de cette façon est suffisant pour permettre d’alimenter plusieurs milliers de cœurs. Les dépendances architecturales sérialisantes ayant été supprimées, l’ILP peut être bien mieux exploité que dans les architectures actuelles. Un code VHDL au niveau RTL de l’architecture a été développé pour en mesurer les avantages. Les résultats de synthèse d’un processeur allant de 2 à 64 cœurs montrent que la vitesse du matériel que nous proposons reste constante et que sa surface varie linéairement avec le nombre de cœurs. Cela prouve que le modèle d’interconnexion proposé est extensible. / The pursuit for faster and more powerful machines started from the first computers. After exhausting the increase of the frequency, the manufacturers have turned to another solution and started to introduce multiples cores on a chip. The computational model is today based on the OS threads exploited through different languages offering parallel constructions. However, parallel programming remains an art because the thread management by the operating system is not deterministic.Nonetheless, it is possible to compute in a parallel deterministic way if we replace the thread model by a model built on the partial order of dependencies. In this thesis, we present an alternative architectural model exploiting the Instruction Level Parallelism (ILP) naturally present in applications. We propose many techniques to remove most of the architectural dependencies which leads to an ILP increasing with the execution length. The ILP which is reached this way is enough to allow feeding thousands of cores. Eliminating the architecutral dependencies serializing the run allows to exploit the ILP better than in actual microarchitectures. A VHDL code at the RTL level has been implemented to mesure the benefits of our design. The results of the synthesis of a processeur ranging from 2 to 64 cores are reported. They show that the speed of the proposed material keeps constant and the surface grows linearly with the number of cores : our interconnect solution is scalable.

La comparaison de séquences est une des tâches fondamentales de la bioinformatique. Les nouvelles technologies de séquençage conduisent à une production accélérée des données génomiques et renforcent les besoins en outils rapides et efficaces pour effectuer cette tâche. Dans cette thèse, nous proposons un nouvel algorithme de comparaison intensive de séquences, explicitement conçu pour exploiter toutes les formes de parallélisme présentes dans les microprocesseurs de dernière génération (instruction SIMD, architecture multi-coeurs). Cet algorithme s'adapte également à un parallélisme massif que l'on peut trouver sur des accélérateurs de type FPGA ou GPU. Cet algorithme a été mis en oeuvre à travers le logiciel PLAST (Parallel Local Alignment Search Tool). Différentes versions sont disponibles suivant les données à traiter (protéine et/ou ADN). Une version MPI a également été mise au point pour un déploiement sur un cluster de PCs. En fonction de la nature des données et des technologies employées des accélérations de 3 à 20 ont été mesurées par rapport à la référence du domaine, le logiciel BLAST, pour un niveau de qualité équivalent.

Cette thèse propose une extension de la logique de séparation pour les programmes parallèles et orientés-objets. La logique de séparation est un formalisme récent et prometteur pour vérifier les programmes impératifs. Cependant, jusqu'à présent, la logique de séparation a été appliquée à des programmes utilisant un opérateur parallèle irréaliste (||) et des verrous non-ré-entrants (contrairement au langage Java). Dans cette thèse, nous adaptons la logique de séparation aux opérateurs "fork" et "join" (utilisés par de nombreux langages: C, Java, etc...) et aux verrous ré-entrants (utilisés par le langage Java).<br /><br />Cette adaptation inclut un système de vérification pour des programmes similaires aux programmes Java. Ce système est constitué d'un ensemble de triplets de Hoare qui forment un algorithme de vérification. La preuve de correction de ce système a été effectuée et ce système a été évalué sur plusieurs exemples ambitieux (dont la classe Itérateur de la librairie Java et un algorithme de couplage de verrous).<br /><br />En plus de l'extension décrite ci-dessus, plusieurs analyses utilisant la logique de séparation ont été inventées.<br /><br />La première analyse consiste à spécifier les séquences d'appels de méthodes autorisées (appelés "protocoles") dans les classes. Cette analyse décrit finement des protocoles complexes (telle que celui de la classe Itérateur). En outre, nous avons proposé une nouvelle technique permettant de vérifier que les spécifications d'un programme sont correctes en utilisant les protocoles.<br /><br />La seconde analyse permet de montrer qu'une formule en logique de séparation n'implique pas une autre formule. Cela est utile dans les vérificateurs de programmes car ceux-ci doivent fréquemment démontrer des implications entre formules. L'intérêt de cette analyse est que sa complexité est basse : cela permet de l'utiliser souvent sans consommer beaucoup de ressources.<br /><br />La troisième analyse permet de paralléliser automatiquement des programmes. Cette analyse prend en entrée des programmes prouvés en logique de séparation et rend en sortie des programmes parallélisés, optimisés, et prouvés. Notre analyse utilise la sémantique de séparation de l'opérateur "*" pour détecter quand deux sous programmes accèdent à des parties disjointes du tas. Dans ce cas, la parallélisation est possible. L'algorithme de détection est implémenté par un système de réécriture.

Ces travaux portent sur la validation de modèles de systèmes sur puce (SoC) au niveau transactionnel (TLM). Ces modèles servent notamment au développement du logiciel embarqué. Le matériel est intrinsèquement parallèle mais le simulateur utilise un seul processeur. Les principales entités parallèles du matériel (processeurs, DMA, arbitres de bus, ...) sont représentées en TLM par des processus asynchrones, qui doivent être ordonnancés lors des simulations. Cet ordonnancement est indéterministe afin de mieux représenter le parallélisme physique.<br /><br />Cela pose un problème pour la validation par simulations : il faut couvrir l'espace des ordonnancements en plus de celui des données. En effet, un ordonnanceur déterministe peut cacher des erreurs, car il ne montre qu'un comportement parmi d'autres. Des ordonnancements aléatoires permettent d'observer plus de comportements mais la couverture est incertaine. Un parcours exhaustif de tous les ordonnancements serait beaucoup trop long pour des tests réels.<br /><br />Nous présentons une solution pour couvrir efficacement l'espace des ordonnancements. Celle-ci est basée sur de la réduction d'ordre partiel dynamique. L'idée est d'observer l'influence de l'ordonnancement sur les communications entre processus, pour générer dynamiquement de nouveaux ordonnancements, menant très probablement à des états finaux différents. En itérant sur chaque nouvel ordonnancement, nous obtenons un jeu complet d'ordonnancements, qui garantit la détection, pour un jeu fixé de données, de toutes les erreurs locales et de tous les inter-blocages.<br /><br />Toujours avec l'objectif d'une meilleure représentativité du matériel, les développeurs ont ajouté du temps imprécis à leurs modèles TLM, sous forme de délais bornés. Pour la validation par simulations, cela oblige à couvrir aussi l'espace des temporisations. Nous présentons une extension à la réduction d'ordre partiel dynamique pour résoudre ce problème. Le nouvel algorithme et son prototype retournent un ensemble de jeux de durées, qui garantit de nouveau la détection complète des erreurs locales et inter-blocages pour des données fixées.<br /><br />Enfin, nous étudions comment paralléliser le simulateur SystemC afin de profiter des machines multiprocesseurs, tout en respectant la spécification de SystemC et les particularités des modèles TLM.

La conception de systèmes de traitement d'images parallèles mariant dans une même architecture, des microprocesseurs évolués et des opérateurs spécialisés est une tache délicate, du fait de la diversité des problèmes a prendre en compte. La présente étude identifie une certaine manière de réaliser et d'interfacer des opérateurs spécialisés a une unité centrale de type microprocesseur. Les deux orientations qui ont guide ce travail sont la recherche d'opérateurs spécialisés polyvalents et reconfigurables et leurs connexions a un bus système, et non a des bus video spécialisés. Ce travail de recherche propose une certaine architecture de circuits dédies au traitement d'images et deux propositions de réalisation de ces derniers sous la forme de circuits asic. Un de ces circuits a pu être réalisé dans le cadre de cette étude en utilisant des outils de type compilateurs de silicium. Ce travail s'intègre dans un projet plus vaste, dont le but est de développer un système pour le traitement d'image industriel, très performant, modulaire, base sur la parallélisation dans des structures de type mimd, d'une unité de traitement d'image élémentaire autonome composée d'un microprocesseur dote d'un coprocesseur parallèle adapte au traitement d'images

Pour évaluer l'impact d'une exposition à long terme à une pollution atmosphérique, il est nécessaire de procéder à des simulations sur de longues périodes (plusieurs mois, voir plusieurs années). Dans certains cas comme la pollution photochimique, le temps de calcul est rédhibitoire. Cela pousse soit vers une intensification des calculs grâce à la parallélisation, soit vers la simulation de scénarios représentatifs. Durant cette thèse, nous avons procédé à la parallélisation du code TRANSCHIM. L'efficacité obtenue pour des simulations avec une chimie photo oxydante est satisfaisante, mais le gain de temps reste limité pour des simulations inertes. De plus, dans le cadre du projet CITY DELTA, une méthode de scénarios épisodiques à été développée pour évaluer les concentrations de fond sur la région parisienne. Cette méthode, basée sur le tri statistique de journées météorologiques, a été validée par confrontation aux mesures de capteurs pour la période étudiée (avril à septembre 1999).

Le calcul de prévisions fiables des inondations ne peut se concevoir sans l'utilisation de toutes les informations disponibles. Les équations mathématiques qui permettent la construction d'un modèle, les images satellites par exemple qui décrivent le domaine, mais aussi les mesures faites in situ. Ces observations sont nécessaires à la bonne qualité des prévisions puisqu'elles sont le seul témoin de la réalité du terrain. Le but de ce mémoire est de présenter et de tester des méthodes fondées sur le contrôle optimal permettant une utilisation optimale de toute les informations disponibles. Diverses applications de ces méthodes seront présentées : l'estimation de paramètres, l'analyse de sensibilité et le couplage de modèles.

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).