Abstract FR:

Le but de mon travail est d'optimiser les communications qui jouent un role crucial dans le developpement des reseaux. Pour cela, je me suis plus particulierement attachee aux communications structurees. J'ai considere des protocoles de communications non dependants de la topologie de la machine. Les problemes correspondants etant souvent np-complets, je me suis interessee a des heuristiques. Peu de travaux ont ete realises dans ce domaine et la plupart d'entre-eux s'attachent au probleme de la diffusion uniquement. Durant ma these, j'ai developpe des heuristiques pour d'autres formes de communications, telles que l'echange total, la distribution ou la multi-distribution. J'ai propose une technique assez generale basee sur la notion de couplage de poids maximum dans un graphe. Lorsque nous avons applique notre approche a des topologies classiques nous avons obtenu des resultats optimaux dans de nombreux cas. J'ai egalement cherche a valider mon approche dans le cas de topologie resultant du partage d'une machine entre plusieurs utilisateurs. Le sous-ensemble de processeurs a la disposition d'un utilisateur est donc un sous-ensemble de la topologie originale, dans mon cas la grille. J'ai compare mon approche generale aux meilleurs algorithmes connus pour cette classe de graphes (sous-grilles). Mon approche s'est revelee en general la plus performante. Enfin, dans le but d'aborder les communications dans des reseaux de plus grandes tailles, je me suis interessee a des communications reparties. Dans ce cadre, chaque processeur a une vue restreinte du reseau, il ne connait que ses voisins. Il s'agit de calculer le nombre maximum d'etapes necessaires, dans un tel environnement, pour effectuer un echange total. Calculer un pire cas permet d'assurer a l'utilisateur une certaine qualite de service en lui garantissant qu'en un nombre fixe d'etapes son echange total sera termine.