Independent connections: an easy characterization of baseline-equivalent multistage interconnection networks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 1989

Independent connections: an easy characterization of baseline-equivalent multistage interconnection networks

Résumé

In this paper we study topological properties of multistage interconnection networks. We define the interconnection schem between two stages as a pair of functions (f, g) which associate with a cell or node x, labelled as a binary string, this two f(x) ans g(x). We consider a class of connections called independent connections. Using our graph characterization of networks topologically equivalent to the Baseline network, we show that all the Banyan networks built with independent connections are isomorphic. Finally, we show that if the interconnection scheme is defined by using permutations on the links induced by a permutation of the index digit (PIPID permutation) then the connection is independent. As these PIPID are associated with a very simple bit directed routing, they are used to define most of the networks introduced un the litterature. Therefore all these networks are aesily shown to be equivalent.
Fichier principal
Vignette du fichier
76-BeFo89-equivalent MIN.pdf (3.05 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03013436 , version 1 (18-11-2020)

Identifiants

Citer

Jean-Claude Bermond, Jean-Michel Fourneau. Independent connections: an easy characterization of baseline-equivalent multistage interconnection networks. Theoretical Computer Science, 1989, 64 (2), pp.191-201. ⟨10.1016/0304-3975(89)90061-3⟩. ⟨hal-03013436⟩
22 Consultations
93 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More