Abstract FR:

Le travail présenté dans cette thèse est une étude des maillages de types nid d'abeilles et hexagonaux en dimension deux, trois et supérieure. Ils sont considérés comme des réseaux d'interconnexion point à point. Ces maillages sont intéressants pour plusieurs raisons : ils sont réguliers, possèdent des symétries et on les retrouve dans de nombreux domaines tel que l'imagerie informatique, les réseaux de neurones, les réseaux mobiles, la chimie organique, etc. . . Dans le plan, nous étudions quelques propriétés topologiques sur le maillage de type nid d'abeilles et ses variantes : les nids d'abeilles losanges, carrés ou étoiles. Ce dernier est un nouveau maillage qui possède des caractéristiques topologiques intéressantes. Une description des maillages hexagonaux, ainsi que des variantes toriques de tous ces maillages est également donnée. Nous présentons ensuite une extension en dimension trois et plus du maillage en nid d'abeilles, et du maillage hexagonal. Ces maillages sont basés sur les vecteurs orthogonaux aux faces d'un tétraèdre régulier, et sur la généralisation en dimension k de ces vecteurs. Une analyse comparative avec la grille conclue chacun de ces chapitres. En seconde partie, des algorithmes de communication globales sont décrits sur chacun des maillages précédents. Les algorithmes de routages et de diffusion que nous présentons sont optimaux en nombre d'étapes de communication, sauf pour deux d'entre eux (à une constante près). Ils sont aussi asymptotiquement optimal en temps du fait du nombre constant d'opérations utilisées entre chaque étape de communication