De nombreux problèmes scientifiques et industriels ont besoin de la résolution de systèmes linéaires non symétriques à grande échelle, qui sont décrits par des matrices creuses de très grande taille. On utilise fréquemment dans ce cas des méthodes numériques itératives et on fait appel au parallélisme pour une résolution rapide et efficace. L'algorithme GMRES(m) est une méthode itérative qui donne de bons résultats dans la plupart des cas. Mais on observe une limitation à sa parallélisation en raison des nombreuses communications produites. Dans quelques cas, la convergence est atteinte très lentement, voire jamais. Nous présentons dans cette thèse une méthode hybride GMRES(m)/LS-Arnoldi qui accélère la convergence grâce à la connaissance des valeurs propres calculées parallèlement par la méthode d'Arnoldi pour les cas réels, avec son implantation sur des supercalculateurs. Une extension aux cas complexes est également étudiée. La dernière tendance du calcul global, le calcul de grille, propose l'exploitation massive des ressources vacantes des réseaux locaux ainsi que sur Internet. Son avantage peut être énorme pour l'exécution d'applications parallèles. L'environnement XtremWeb est un système de grille léger, tolérant aux défaillances et sécurisé pour l'exécution d'applications parallèles. Il est un environnement de calcul haute-performance, une plate- forme de grille logicielle d'expérimentation pour des institutions académiques ou industrielles. Nous présentons dans cette thèse les implantations de la méthode GMRES(m) sur ce système de grille XtremWeb ainsi que sur un environnement distribué de calcul LAM-MPI. Nous avons fait de multiples tests sur grille et supercalculateur. Des performances que nous avons obtenues, nous constatons les avantages et les inconvénients de ces plates-formes de calcul différentes.

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.

Actuellement, l'accélération des opérations de traitement d'images est principalement obtenue par l'utilisation de calculateurs parallèles. De tels processeurs, a flot d'instructions unique et a flots de données multiples (simd), sont développés, mais s'ils s'avèrent efficaces pour les opérations de traitement d'images dites de bas niveau, ou la structure des données reste la même, ils se heurtent a de nombreux problèmes lorsqu'il s'agit des opérations de moyen et de haut niveau. Notamment lors des opérations de moyen niveau, une réorganisation aléatoire des données sur les processeurs doit être effectuée, tache difficilement exécutable sur les structures parallèles synchrones a mémoire distribuée. Le but de cette thèse était d'étendre les capacités d'un calculateur simd, afin qu'il puisse exécuter, efficacement, les opérations de traitement d'images de moyen niveau. L'étude des algorithmes représentatifs de cette classe d'opérations dégage les limites de ce calculateur que des modifications d'architecture permettent d'affranchir. C'est ainsi que Sympatix, le nouveau calculateur SIMD, a été proposé. Afin de le valider, son modèle comportemental décrit en VHDL langage de description de matériel a été élaboré. Grâce a ce modèle, les performances de la nouvelle structure sont ainsi directement mesurées, par simulations d'algorithmes de traitement d'images. L'approche par modélisation VHDL permet, de plus, d'effectuer la conception électronique descendante du système, ce qui, par ailleurs, offre un couplage aise entre les modifications architecturales du système et leur cout électronique. Les résultats obtenus montrent que Sympatix est adapte aux opérations de traitement d'images de bas et de moyen niveau, qu'il est ouvert a un calculateur de haut niveau, et qu'il est capable de supporter d'autres applications de vision. Ce manuscrit présente également, une méthodologie de conception descendante, basée sur le vhdl, et destinée aux architectes de systèmes électroniques

Cette thèse aborde un ensemble de problèmes lies a la conception et a la mise en œuvre d'un noyau de communication faisant partie de Parx, un noyau de système d'exploitation pour machines multiprocesseurs sans mémoire, développe dans le cadre du projet de recherche européen esprit supernode. Le noyau réalisé une machine virtuelle, vis-a-vis des communications, dans laquelle l'ensemble de processeurs est complètement connecte indépendamment de la topologie du réseau d'interconnexion sous-jacent. La machine virtuelle offre une interface qui facilite l'exploitation correcte du haut degre de parallélisme physique des machines visées. Après un état de l'art des architectures d'ordinateurs massivement parallèles, il est propose un modèle de processus et une structure de noyau de système parallèle. Le modèle est base sur un ensemble d'entités bien adaptées au contrôle de l'exécution des programmes parallèles composes de processus communicants. Ces entités, qui étendent la notion traditionnelle de processus, intègrent des concepts nouveaux visant la meilleure exploitation de l'architecture physique. Dans le modèle de processus communicants, ceux-ci ne coopèrent que par échange de messages. Le contrôle, correct et efficace, de la communication et la synchronisation entre processus s'exécutant sur une architecture multi-processeurs sans mémoire commune est le thème central de cette thèse. Notre étude s'oriente vers la conception d'un noyau de communication, pour lequel les problèmes concernant essentiellement le routage de messages sans interblocage dans le réseau de processeurs et les protocoles de communication entre processus adéquats au modèle de programmation utilisé

Nous étudions la mise en œuvre d'algorithmes parallèles sur des ordinateurs a mémoire distribuée. A travers plusieurs exemples issus de la programmation dynamique, de l'algèbre linéaire et du traitement d'images, nous exposons les problèmes lies a la programmation de ces machines: topologie d'interconnexion, stratégie d'allocation des données, équilibrage des calculs et minimisation du volume de communication inter-processeurs. Les exemples étudiés sont pour la plupart des algorithmes séquentiels couteux en temps de calcul et en place mémoire, et pour lesquels il est très intéressant d'avoir une parallélisation efficace. Nous avons choisi des problèmes dont l'implémentation sur des machines a mémoire distribuée n'est pas aisée, essentiellement a cause de la grande interdépendance entre les différentes taches composant les algorithmes

Pac est un système de calcul formel dédié a une machine Mind massivement parallèle. Dans une première partie, l'architecture du système est décrite. Elle est illustrée par une modélisation théorique et pratique de la parallélisation du produit de deux polynômes. Le système Pac est implante sur la machine t40 de Fps (32 processeurs). Dans une deuxième partie, l'arithmétique nodale en précision infinie sur les rationnels est étudiée. Différents algorithmes sont dégagés, notamment pour la multiplication, la division et le pgcd d'entiers de taille quelconque. Une vectorisation de l'arithmétique de base est discutée et expérimentée

Une architecture parallèle pour le traitement d'images, articulée autour d'un bus rapide, est étudiée en vue d'effectuer des rectifications géométriques d'images satellites de grande dimension. Une parallélisation de l'algorithme est proposée en tenant compte d'une optimisation possible du découpage de l'image

On considère la résolution exacte des systèmes linéaires en parallèle et on traite deux aspects de base du problème : le calcul du noyau d'une matrice dont les coefficients sont dans un corps fini et la résolution des systèmes à coefficients entiers. On évalue les couts des différents algorithmes proposes, en mettant l'accent sur couts des communications

Dans cette thèse, nous proposons successivement deux modèles discrets par réseaux d'automates cellulaires, du processus de subduction-érosion en<br />tectonique des plaques, puis présentons les simulations informatiques parallèles correspondantes.<br /><br />Après une présentation de la tectonique des plaques et des marges convergentes de type II (avec érosion), nous présentons les deux tendances de modélisation existantes, étudions leurs avantages et inconvénients respectifs et montrons l'intérêt de développer une démarche radicalement différente. Nous exposons alors nos hypothèses de travail relativement restrictives et leurs limites, en commençant d'abord par présenter la géométrie d'ensemble du "plan de coupe de modélisation" et sa dynamique, puis en énumérant les phénomènes à reproduire, enfin, en introduisant des échelles de temps et la représentation de l'érosion par une altération (un changement de matière) due au vieillissement.<br /><br />En ce qui concerne les modélisations plus précisément, nous nous inspirons très fortement du "Sand Pile Model" uni-dimensionnel pour développer notre propre modèle uni-dimensionnel et introduire la notion de réseau d'automates cellulaires fini généralisé. Dans le cas du modèle bi-dimensionnel, partant du même principe, nous cherchons à implémenter un modèle d'avalanches dans un tas de sable représenté par un réseau d'automates cellulaires bi-dimensionnel. Constatant que la multiplication des informations stockées dans la structure même du réseau offre un meilleur rendu-visuel, nous choisissons alors de généraliser cette méthode et abordons la description de notre propre réseau d'automates cellulaires.<br /><br />Les temps de calcul respectifs de chacune des simulations séquentielles ainsi que le fait que les réseaux d'automates cellulaires constituent un modèle canonique du calcul parallèle à fine granularité, nous incitent à développer des simulations parallèles et à les porter sur des ordinateurs parallèles tels que le CRAY T3E et l'ORIGIN 2000. Après avoir exposé la stratégie de décomposition de domaine que nous avons employée (avec équi-répartition de la charge des sous-domaines sur l'ensemble des processeurs et minimisation de la taille des problèmes aux interfaces), nous montrons l'intérêt d'utiliser une bibliothèque d'échanges de messages appropriée dans le cadre d'une décomposition de domaine régulière sur une architecture parallèle à mémoire distribuée.<br /><br />Les résultats obtenus sont révélateurs (pour la simulation bi-dimensionnelle du moins) de la très bonne parallélisabilité du problème posé. Ils nous permettent de présenter quelques copies d'écran des animations graphiques<br />obtenues et leur validation d'un point de vue géotectonique. Des développements futurs pourraient être orientés vers la mise au point d'une plate-forme logicielle parallèle adaptée, puis vers une étude de qualification de la concentration des déformations au sein de la plaque chevauchante.

Le développement des techniques d'intégration permet de réaliser des circuits de 10**(5) a 10**(6) transistors et, dans un futur proche, des circuits encore plus complexes. Les problèmes de CAO deviennent donc de plus en plus ardus, comme la simulation logique ou le placement. Cette même évolution nous autorise a réaliser des machines parallèles très puissantes pour résoudre ces problèmes. Nous proposons l'architecture d'un réseau cellulaire asynchrone. Ce réseau, compose de nxn cellules dont chacune est physiquement connectée à ses quatre voisines, dispose d'un mécanisme de communication permettant l'acheminement de messages d'une cellule quelconque a n'importe quelle autre. Un circuit intégré, incluant un réseau de 2 x 2 cellules dédié à la simulation logique, a été réalisé. Utilisant cette architecture cellulaire nous avons développé un placeur, qui a partir d'une configuration initiale, minimise la longueur des connexions par échanges de paires. Nous avons aborde la manière dont le placement pourrait être amélioré par la méthode de recuit simule. Ces deux applications, différentes de l'architecture cellulaire, nous permettent de constater que beaucoup de parties sont communes aux deux circuits. Nous énonçons certaines règles de façon à rendre la conception plus rapide et plus sure