Le but de ce memoire est d'étudier les voies possibles pour minimiser le sur-coût des communications consécutif à la parallélisation d'algorithmes numériques sur machines parallèles à mémoire distribuée. La première voie explorée consiste à optimiser les schémas de communication des données et résultats mis en oeuvre dans les versions parallèles de noyaux de calcul. Nous proposons notamment de nouveaux algorithmes pour réaliser une transposition de matrices carrées allouées par blocs, sur différentes topologies de réseaux d'interconnexion. Nous avons également étudié le problème de l'échange total. Ce schéma de communication se retrouve fréquemment dans les versions parallèles d'algorithmes numériques (comme dans l'algorithme du gradient conjugué). Nous proposons des algorithmes efficaces d'échange total pour des topologies toriques. La deuxième voie qui a été explorée consiste à recouvrir les communications par du calcul. Nous avons étudié quelques principes algorithmiques de base permettant de masquer au mieux les communications. Ceux-ci sont basés, notamment, sur des techniques d'enchainement de phases de calcul et de communication, ainsi que sur le re-ordonnancement local de tâches afin d'optimiser le recouvrement. Ces techniques sont illustrées sur des algorithmes parallèles de calcul de transformée de Fourier. Les différentes implantations de ces algorithmes sur de nombreuses machines parallèles à mémoire distribuée (T3D de Cray, SP2 d'IBM, iPSC-860 et Paragon d'Intel) montrent le gain en temps d'exécution apporté par ces méthodes.

Les résultats obtenus dans cette thèse portent principalement sur l' étude des communications dans les architectures parallèles, distribuées ou réseaux d'interconnexion.<br>Dans le chapitre 1 nous présentons brièvement une rapide classification des machines parallèles. Puis nous décrivons en détails les principaux mécanismes de routage des messages existant à l'heure actuelle dans de telles machines. Nous détaillons en particulier, les nouveaux mécanismes de routage du type "wormhole". Ce chapitre contient également un bref rappel des principales notions de théorie des graphes utilisées pour la modélisation des machines parallèles à mémoire distribuée.<br>Les chapitres 2, 3 et 4 dressent une synthèse des travaux qui nous paraissent les plus significatifs sur quelques principaux problèmes de communications globales (diffusion, échange total et multidistribution) par commutation de circuits, tout au moins lorsque l'on cherche essentiellement à minimiser le nombre d'étapes des protocoles.<br>Dans le chapitre 5 nous résumons en premier lieu nos travaux sur la décomposition hamiltonienne du réseau Butterfly généralisé, puis en second lieu nous donnons notre approche au problème des larges graphes à degré et diamètre fixés.