A Class ofParametric Regular Networks for Multicomputer Architecturesl
Oleg G. Monakhov, Emilia A. Monakhova · 2000
Introd uction A new class of multicomputer interconnection networks is proposed and analyzed: Parametrically described, Regular, and based on Semigroups (PRS) networks (or R8(N,v,g) graphs with the order N, the degree v, the girth g, and the number of equivalence classes s). The class of PRS networks includes many classes of known networks (hypercubes, circulant networks, cube-connected cycles, etc.) as special cases. We explore the basic topological properties ( connectivity, isomorphism, lower bounds on the diameter and the average distance, etc.) of the proposed graphs and syn- thesize the optimal PRS networks having the minimal diameter for the given parameters of the graph. The PRS networks and their subclass -multidimensional circulants -are compared to hypercubes: the optimal P RS graph 's diameter is ~ O.211og2 N (for 9 = 6) and the circulant's diameter is ~ O.321og2 N whereas the hypercube 's diameter is log2 N, provided they have the same vertex and edge complexity. A design of interconnection networks for parallel com- puter system architectures and distributed memory computer systems requires a study of undirected dense regular graphs with small diameters. Graphs with these properties can be found within the class of Cayley graphs, in particular in the class of circulant graphs (Du et al., 1990; Monakhova, 1991; Bermond et al., 1995) and also within the class of PRS graphs introduced in Monakhov (1979). The PF.S graphs are a generaliza- tion of circulants, hypercubes, cube-connected cycles (Preparata and Vuillemin, 1981), chordal ring networks (Arden and Lee, 1981) and other classes of graphs used as interconnection networks of computer systems. In K wai and Parhami (1996, 1998) Gaussian cubes are considered as generalization of hypercubes which also represent a subclass of the PRS graphs. Notice that hypercubes have a logarithmic estimate on the diame- ter only provided that a degree of a node grows with N as log N. The graphs from the class of PRS netwoks have a logarithmic estimate on the diameter (from N) for a fixed degree of a node of the graph in contrast to hypercubes. The other classes of graphs are presented in Scherson (1991) and Corbett (1992) with logarithmic estimate on the diameter .