From dual-cube to metacube: efficient low-degree alternatives to hypercube

The hypercube has been widely used as the interconnection network in parallel computers. However, when dealing with the parallel computers of very large scale, the port limitation due to the technology greatly forbid the use of hypercube networks. The hypercube-based SGI Origin2000, a newly developed multiprocessor system, tried to solve this problem by introducing a Cray router. In this paper we first describe a hypercube-like network, called dual-cube, that was motivated by the structure of Origin2000. A dual-cube DC(m) has m+1 links per node where m is the degree of a cluster (m-cube), one more link is used for connecting to a node in another cluster. The dual-cube mitigates the problem of port limitation in the large-scale hypercube network while keeps most of the topological properties of the hypercube network. Then, we describe an interconnection network that extends dual-cube into a more general network called metacube. The metacube has a two-level cube structure with two parameters representing the dimensions of the two-level cubes. Metacube is much more flexible than dual-cube and can solve the port limitation problem completely. The dual-cube and metacube networks can be applied to SGI Origin2000 to connect large number of processors without using Cray router.