Hierarchical shuffle-exchange and de Bruijn networks

Abstract

We present two new classes of interconnection networks for SIMD computers, namely the hierarchical shuffle-exchange (HSE) and hierarchical de Bruijn (HdB) networks. These new networks are efficient in implementing a wide range of algorithms, including all of those in the classes Ascend and Descend. The networks are highly regular and scalable and thus well-suited to VLSI implementation. In addition, they can be adjusted to match the pin limitations imposed by the packaging technology. We compare the HSE and HdB networks with hypercube, 2-dimensional mesh, 3-dimensional mesh, shuffle-exchange, hypernet, de Bruijn and cube-connected cycles networks. The HSE and HdB networks are shown to have advantages in terms of regularity, scalability and performance.