Abstract FR:

Le domaine des graphes et reseaux d'interconnexion se propose d'etudier les problemes de communications dans les machines paralleles. La premiere partie de cette these est une etude complete des graphes recursifs circulants g(cdm,d). Nous commencons par une etude structurelle de ces graphes (proprietes, diametre, construction recursive). Nous decomposons ensuite ces graphes en cycles hamiltoniens arete-disjoints. Puis, nous donnons un algorithme de construction d'arbres arcs-disjoints dans le temps pour effectuer un echange total en temps optimal selon le protocole delta-port, temps constant. Dans une seconde partie, nous nous interessons a la diffusion vagabonde et a l'echange total vagabond dans quelques graphes (chemin, cycle, arbres d-aires complets et hypercubes). Nous donnons des bornes maximales pour les temps necessaires a l'execution de ces schemas de communication, et des algorithmes atteignant ces bornes. Ce nouveau modele introduit en 1993, est adapte a des machines paralleles dont les routeurs auraient pas ou peu de memoire locale. Dans la troisieme partie de ce document, nous presentons notre realisation logicielle, griap, destinee a la validation de schemas de communication. Griap se compose de differents modules permettant de generer les listes d'adjacences de familles de graphes, de simuler l'execution de schemas de diffusion ou du routage intensif en modele hot potato. Une interface graphique a ete adaptee pour interpreter facilement la grande quantite d'informations emanant d'une simulation