Efficient class of interconnection networks for parallel computations

A new class of interconnection networks is presented for interconnecting the processors of general purpose massively parallel computers. This new class of interconnection networks, recursively connected networks (RCN), is constructed by methodically connecting together a number of basic networks, referred to as atoms, through the recursive application of a complete graph compound. A specific instance of this class, RCN-CUBE, where the basic atom is a binary hypercube, is shown to have desirable network properties such as small diameter, small degree, high bandwidth and optimal connectivity; and these compare favorably to those of other related networks. Convenient routing strategies are derived for the RCN class, which require only local information to route messages between nodes whenever routing within the basic atom requires only local information. RCN is shown to emulate the binary hypercube well under any permutation when the basic atom performs a binary hypercube emulation well; and RCN-CUBE can emulate the binary hypercube with only a small multiplicative factor increase in time performance. The time performance of RCN on various fundamental data movement operations frequently used in the design of parallel algorithms is analyzed and evaluated as a function of the performance on the basic atom used, and RCN-CUBE performance is shown to be very close to that required by the binary hypercube.