L'objet de cette thèse est l'étude de la parallélisation d'algorithmes du calcul scientifique et<br />leur implémentation sur des ordinateurs parallèles à mémoire partagée et sur des réseaux systoliques.<br /> Un accent particulier est mis sur l'obtention de résultats de complexité. La thèse est organisée autour<br /> d'articles et textes de conférences qui sont analysés et discutés dans une première partie de façon à <br />permettre de replacer les problèmes traités dans leur contexte.<br />Dans le premier chapitre, nous présentons les principaux résultats théoriques concernant <br />l'étude de complexité des algorithmes parallèles, ainsi qu'une description critique de l'architecture <br />de référence, qui est une machine de type MIMD à mémoire partagée. Le chapitre suivant est dédie" à <br />l'ensemble des résultats de complexité concernant les algorithmes de diagonalisation et <br />l'élimination de Gauss, il a pour but d'illustrer la méthodologie. Il existe en tout dix écritures possibles de la méthode de Gauss, qui conduisent principalement à deux grandes classes de graphes de précédente, conceptuellement différents : les graphes de type "glouton" et ceux du type "2 pas".<br />Ces types de graphes se rencontrent d'une manière plus générale dans d'autres problèmes <br />d'algèbre linéaire et même dans certaines méthodes non numériques de la théorie des graphes. <br />Nous développons les résultats de complexité concernant ces deux types de graphes sur les exemples<br /> les plus courant (versions kji et kij de Gauss en parallèle), puis nous montrons comment adapter<br /> l'étude en prenant en compte t'es temps de communication entre tes processeurs, ce qui rend le modèle<br /> théorique plus réaliste.<br />Le chapitre 6 est consacré aux architectures systoliques. Le problème du chemin algébrique permet <br />d'unifier plusieurs problèmes informatiques. Nous présentons un réseau résolvant ce problème en Sn-2 <br />pas sur un réseau de taille n(n+l ). De plus, quelques modifications permettent de calculer des projections<br /> en filtrage adaptatif en vu d'obtenir une solution en temps réel pour le traitement numérique des signaux.<br />Avant de conclure, nous présentons des résultats complémentaires de parallélisation effective sur d'autres<br /> types d'architectures : l'étude de l'algorithme du gradient conjugué sur des super calculateurs <br />(CRAY-XMP et IBM 3090-VF).

Ce mémoire présente la technique employée pour réaliser la simulation en VHDL d'une architecture d'estimateur de canaux pour récepteur à traitement spatiotemporel. Par l'utilisation de réseaux systoliques adaptés pour une future implantation matérielle FPGA, il est possible de démontrer qu'on peut utiliser l'estimation par corrélation et l'estimation par la minimisation de l'erreur quadratique moyenne pour estimer les canaux à la réception d'un système de communication sans fil. Avant tout, une brève revue scientifique sur les systèmes de communication sans-fil est effectué et les deux méthodes d'estimation sont analysées avec Matlab afin de démontrer qu'elles peuvent combattre les distorsions et les évanouissements subis par le signal lors de la transmission. Par la suite, il est proposé d'associer l'utilisation de l'architecture des réseaux systoliques avec les multiplications matricielles. Finalement, deux de ces architectures systoliques sont implantées et utilisées pour la réalisation en VHDL des deux méthodes d'estimation des canaux.

Différents résultats de complexité sont présentés pour les communications et le calcul sur des machines à mémoire distribuée. Les topologies concernées sont le réseau linéaire, l'anneau, la grille, l'hypercube et le réseau complet. Un réseau systolique est présenté pour l'algorithme de diagonalisation de Jordan. Une étude sur l'accélération et une étude de l'allocation des données sont formulées dans le contexte des mémoires distribuées