A Class of Recursive Interconnection Networks: Architectural Characteristics and Hardware Cost

We propose and analyze a new class of interconnection networks, RCC, for interconnecting the processors of a general purpose parallel computer system. The RCC is constructed incrementally through the recursive application of a complete graph compound. The RCC integrate positive features of both complete networks and a given basic network. This paper presents the principles of constructing RCC and analyzes its architectural characteristics, its message routing capability, and its hardware cost A specific instance of this class, RCC-CUBE, is shown to have desirable network properties such as small diameter, small degree, high density, high bandwidth, and high fault tolerance and is shown that they compare favorably to those of the hypercube, the 2-D mesh, and the folded hypercube. Moreover, RCC-CUBE is shown to emulate the hypercube in constant time under any message distribution. The hardware cost and physical time performance are estimated under some packaging constraints for RCC-CUBE and compared to those of the hypercube, the folded hypercube, and the 2-D mesh demonstrating an overall cost effectiveness for RCC-CUBE. Hence, the RCC-CUBE appears to be a good candidate for next generation massively parallel computer systems.