The (direct binary) hypercube interconnection network has very frequently been employed in the construction of distributed-memory parallel computing systems. It offers low diameter and is so robust that it can very efficiently emulate a wide variety of other popular interconnection networks. However, the major drawback of the hypercube is the increase in the number of communication channels for each processor with an increase in the total number of processors in the system. This drawback has direct effect on the VLSI complexity of the hypercube and as a result it restricts inadvertently its adaptation in the construction of high-performance massively parallel systems. This paper investigates the properties of a new family of interconnection networks which are produced from the hypercube by a uniform reduction in the number of edges for each node. This family of networks is a generalization of the reduced hypercube (RH) family of interconnection networks introduced earlier by Ziavras. The edge reduction technique produces interconnection networks with much lower VLSI complexity than hypercubes, while the new networks maintain to high extent the very powerful hypercube properties. An extensive comparison of the proposed generalized reduced hypercube (GRH) networks with conventional hypercubes and RH's is presented. A routing algorithm is also presented, and it is concluded that GRH's are often good alternatives to hypercubes and RH's for the construction of massively parallel computers.
Return to the "selected publications" page