Abstract FR:

Cette thèse traite des aspects complémentaires des machines parallèles à mémoire distribuée. Un premier chapitre établit un état de l'art des techniques de communications mises en oeuvre dans les machines existantes ou en projet. Cette étude permet d'introduire différents modèles de communication et pose le problème du choix du réseau d'interconnexion. Les modes de communication des nouvelles machines parallèles sont du type commutation de circuit, comme le routage wormhole qui remplace désormais le classique store-and-forward. Le deuxième chapitre concerne l'utilisation efficace des canaux virtuels en wormhole pour éviter les interblocages. On montre comment utiliser un nombre minimum de canaux virtuels pour les réseaux quelconques et pour des familles courantes de réseaux d'interconnexion. Dans le troisième chapitre nous décrivons un algorithme de diffusion optimal pour les tores bidimensionnels qui utilise un routage synchrone de type commutation de circuit. L'algorithme repose sur un découpage récursif du tore en 5 parties égales. Le quatrième chapitre traite de la topologie des réseaux d'interconnexion. Etant donné un graphe, l'excentricité moyenne d'un sommet est définie comme la distance moyenne de ce sommet à tous les autres. Le calcul de ce paramètre est difficile dans le cas des graphes de de Bruijn. Dans ce chapitre nous donnons des bornes inferieures et supérieures de l'excentricité moyenne pour ces graphes. Le chapitre suivant donne une implantation efficace et générique de l'algorithme de la Transformée de Fourier rapide sur les réseaux de de Bruijn. On utilise le résultat suivant sur la conjonction de ces réseaux: le produit cartésien de deux de Bruijn est un de Bruijn