The hyper-deBruijn multiprocessor networks

Abstract

Hypercube and deBruijn networks each possess certain desirable properties. The architecture proposed is a combination of the hypercube and deBruijn architectures. Thus, it provides flexibility in terms of connections per node and the level of fault-tolerance. The graph structure allows a direct decomposition of the network into VLSI building blocks. These networks possess logarithmic diameter, optimal connectivity and simple routing algorithms amenable to networks with faults. These hyper-deBruijn networks admit many computationally important subnetworks such as rings, multidimensional meshes, complete binary trees and mesh of trees with perfect dilation, in addition to being pancyclic Author(s) Ganesan, E. Dept. of Electr. & Comput. Eng., Massachusetts Univ., Amherst, MA, USA Pradhan, D.K.