Wei-Kuo Chiang and Rong-Jaye Chen
Department of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.
This paper introduces a new interconnection network of hypercubes for massively parallel systems, called the multilevel hypercube (MQ), which is constructed by recursively connecting a number of identical hypercubes for hierarchical expansion. With the same number of nodes, the MQ has about two-thirds the diameter of a comparable hypercube and has fewer links than a comparable hypercube. The node-connectivity of the MQ is equal to its degree thus, it is optimal fault-tolerant. Based on the MQ, we can design a network by choosing the parameters of the MQ such that the network is more suitable for some specific objectives. We propose a method to obtain the MQ with a minimum degree under a given total number of nodes. Especially, the MQ is shown to emulate a hypercube of the same size with dilation 3. This result guarantees that all the algorithms designed for the hypercube can be executed on the MQ with small degradation in time performance. Moreover, the time performance of the MQ on two fundamental parallel algorithms (descend/ascend and broadcasting) is shown to be very close to that of a hypercube. In addition, we obtain an estimate of the track requirement for the MQ, which is about one-third that of a comparable hypercube.
Keywords: hypercubes, interconnection networks, routing, emulation, parallel algorithms, VLSI implementation
Received May 6, 1995; revised January 1, 1996.
Communicated by Shing-Tsaan Huang.