La cité annulaire

Résumé du livre

Dans le cadre de l'étude des réseaux d'interconnexion des machines parallèles à mémoire distribuée, nous avons plus particulièrement étudié une famille de réseaux appelée cité annulaire. Dans une première partie, après avoir expose une synthèse sur les orientations de graphes, nous étudions celles des cités annulaires. Nous déterminons, tout d'abord, leur diamètre (D) qui est égal à D = c + s/4 si c supérieur ou égal à s/4 et D = 2c si c inférieur ou égal à s/4. Ensuite nous proposons deux orientations pour les cités annulaires qui donnent une borne supérieure du diamètre orienté (entre D et D + 3 suivant les cas), puis nous établissons une borne inférieure. Ces deux bornes étant confondues dans la plupart des cas, nous concluons que les orientations sont quasi-optimales pour le diamètre. La deuxième partie est consacrée aux schémas types de communication : le routage, la diffusion et l'échange total, appliqués à ce réseau. 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 considéré deux modèles, d'une part le modèle store-and-forward sous les contraintes H*, où nous appliquons les techniques du pipeline et des arbres de recouvrements deux à deux arete-disjoints. D'autre part le modèle commutation de circuit, dans ce cas nous avons cherché à minimiser le nombre d'étapes : 1 + [log3 (2c + 1)] sous la contrainte -port et 1 + [log2c] + [log2s] sous la contrainte 1-port. Enfin, pour l'échange total, nous avons applique les résultats de l'orientation. La troisième partie présente des résultats d'expérimentation sur une machine reconfigurable à base de transputers. Nous comparons l'efficacité de l'échange total sur des grilles bi-dimensionnelle et sur des cités annulaires de même ordre. Les résultats pour les cités annulaires sont aussi bons voire meilleurs dans certains cas que ceux pour des grilles