E. Ganesan et Dk. Pradhan, THE HYPER-DEBRUIJN NETWORKS - SCALABLE VERSATILE ARCHITECTURE, IEEE transactions on parallel and distributed systems, 4(9), 1993, pp. 962-978
Citations number
38
Categorie Soggetti
System Science","Computer Applications & Cybernetics","Engineering, Eletrical & Electronic
Both Hypercube and deBruijn networks possess desirable properties. It
should be understood, though, that some of the attractive features of
one are not found in the other. The architecture proposed in this pape
r is a combination of these architectures, providing some of the desir
able properties of both the networks such as admitting many computatio
nally important networks, flexibility in terms of connections per node
as well as level of fault-tolerance. Also the network allows a simple
VLSI layout, scalability as well as decomposability. Thus, these netw
orks can be a potential candidate for VLSI multiprocessor networks. Th
e proposed network possesses logarithmic diameter, optimal connectivit
y, and simple routing algorithms amendable to networks with faults. Im
portantly, in addition to being pancyclic, these hyper-deBruijn networ
ks admit most computationally important subnetworks including rings, m
ultidimensional meshes, complete binary trees, and mesh of trees with
perfect dilation. Techniques for optimal one-to-all (OTA) broadcasting
in these networks are presented. As an intermediate result, this tech
nique provides the fastest OTA broadcasting in binary deBruijn network
s as well. The recent renewed interest in binary deBruijn networks mak
es this later result valuable.