Shuffle-ring: overcoming the increasing degree of hypercube

Abstract

The hypercube as a parallel interconnection network has been studied by many for tens of years due to its many merits. However, its increasing node degree is an obvious weakness. Some networks such as the Cube-Connected Circle and the DeBruijn Network have been proposed to overcome the increasing degree of the hypercube. In this paper, we present a new, cost-effective network which outperforms the cube network. It can overcome the increasing degree of the cube network while keeping the advantages of the cube network such as logarithmic diameter, easy routing, optimal fault tolerance, and suitability for the ASCEND/DESCEND class of parallel problems. Furthermore, the proposed network achieves the logarithmic diameter with a very small constant node degree, 3 or 4.