Abstract FR:

Dans le cadre de l'etude des reseaux d'interconnexion des machines paralleles a memoire distribuee, nous avons plus particulierement etudie une famille de reseaux appellee cite annulaire. Dans une premiere partie, apres avoir expose une synthese sur les orientations de graphes, nous etudions celles des cites annulaires. Nous determinons, tout d'abord, leur diametre (d) qui est egal a c + s/4 si c s/4 et 2c si c s/4. Ensuite nous proposons deux orientations pour les cites annulaires qui donnent une borne superieure du diametre oriente (entre d et d + 3 suivant les cas), puis nous etablissons une borne inferieure. Ces deux bornes etant confondues dans la plupart des cas, nous concluons que les orientations sont quasi-optimales pour le diametre. La deuxieme partie est consacree aux schemas types de communication: le routage, la diffusion et l'echange total, appliques a ce reseau. Ainsi, nous exhibons une fonction de routage des plus courts chemins sans interblocage (cas statique et adaptatif). Celle-ci utilise au plus deux canaux virtuels, ce qui est optimal. Pour la diffusion, nous avons considere deux modeles, d'une part le modele store-and-forward sous les contraintes h*, ou nous appliquons les techniques du pipeline et des arbres de recouvrements deux a deux arete-disjoints. D'autre part le modele commutation de circuit, dans ce cas nous avons cherche a minimiser le nombre d'etapes: 1 + log#3(2c + 1) sous la contrainte -port et 1 + log#2c + log#2s sous la contrainte 1-port. Enfin, pour l'echange total, nous avons applique les resultats de l'orientation. La troisieme partie presente des resultats d'experimentation sur une machine reconfigurable a base de transputers. Nous comparons l'efficacite de l'echange total sur des grilles bi-dimensionnelle et sur des cites annulaires de meme ordre. Les resultats pour les cites annulaires sont aussi bons voire meilleurs dans certains cas que ceux pour des grilles