Parametrically described regular semigroup interconnection networks for large-scale multicomputers

We propose a new topology for multicomputer networks: parametrically described, regular, and based on semigroups (PRS) networks (or R/sub s/(N, v, g) graphs with the order N, the degree v, the girth g, and the number of equivalence classes s). Many classes of networks such as hypercubes, circulants, cube-connected cycles, etc. are shown to be special cases of the proposed network. We explore the basic structure, topological properties, optimization of parameters and synthesis of optimal networks having the minimal diameter for the given parameters of the graph. Correspondingly, we examine the optimal characteristics with respect to transit delays and structural survival in such networks. The PRS networks reaching the lower bounds on the diameter were synthesized. In some cases, we found that the new network has a better diameter than classes of networks described in the literature provided they have the same vertex and edge complexity.