Abstract FR:

Cette thèse traite d'un ensemble de problèmes liés à l'acheminement des messages dans les machines parallèles à mémoire distribuée. L'accent est mis sur des solutions extensibles qui nécessitent un nombre de ressources indépendant de la taille de la machine. A travers l'exemple des machines supernodes (dont les processeurs sont interconnectés par un réseau de clos 3-étages) nous montrons que l'acheminement des messages par reconfiguration dynamique est difficilement envisageable dans des machines de grande taille. Nous nous intéressons ensuite au routage des messages dans des réseaux à topologie quelconque, et proposons une nouvelle méthode de génération de fonctions de routage sans inter blocage. La nouvelle génération des machines parallèles intègre de plus en plus de fonctions dans le matériel, notamment le routage des messages. Pour que cette intégration soit la plus efficace possible, des méthodes nouvelles de représentation compacte de l'information de routage sont nécessaires. Santoro et Khatib ont proposé une méthode, le routage par intervalles, bien adaptée aux réseaux généraux. La deuxième partie de cette thèse s'inscrit dans la continuité de ce type de travail et propose de nouvelles méthodes de génération de fonctions de routage par intervalles. Deux cas sont considérés: le tore, et les réseaux généraux. Nous insistons plus particulièrement sur des solutions sans inter blocage, caractéristique rarement prise en compte. De plus dans le cas du tore, les longueurs des chemins sont proches des optima. Enfin, nous proposons une extension de la notion de routage par intervalles, le schéma d'étiquetage étendu (see), qui permet de représenter un spectre plus large de fonctions de routage