The hyper-deBruijn networks: scalable versatile architecture
- 1 January 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 4 (9), 962-978
- https://doi.org/10.1109/71.243525
Abstract
Both Hypercube and deBruijn networks possess desirable properties. It should beunderstood, though, that some of the attractive features of one are not found in theother. The architecture proposed in this paper is a combination of these architectures,providing some of the desirable properties of both the networks such as admitting manycomputationally 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 networks can be a potential candidate for VLSI multiprocessor networks. The proposed network possesses logarithmic diameter, optimalconnectivity, and simple routing algorithms amendable to networks with faults.Importantly, in addition to being pancyclic, these hyper-deBruijn networks admit mostcomputationally important subnetworks including rings, multidimensional 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 technique provides the fastest OTA broadcasting in binary deBruijn networks as well. The recent renewed interest in binary deBruijn networks makes this later result valuable.Keywords
This publication has 22 references indexed in Scilit:
- The hyper-deBruijn multiprocessor networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A multiple copy approach for delivering messages under deadline constraintsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Product-shuffle networks: toward reconciling shuffles and butterfliesDiscrete Applied Mathematics, 1992
- The banyan-hypercube networksIEEE Transactions on Parallel and Distributed Systems, 1990
- The de Bruijn multiprocessor network: a versatile parallel processing and sorting network for VLSIIEEE Transactions on Computers, 1989
- Topological properties of hypercubesIEEE Transactions on Computers, 1988
- Embedding of tree networks into hypercubesJournal of Parallel and Distributed Computing, 1985
- Connectivity of Regular Directed Graphs with Small DiametersIEEE Transactions on Computers, 1985
- The cube-connected cycles: a versatile network for parallel computationCommunications of the ACM, 1981
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971