Design and analysis of a class of De Bruijn graph based hierarchical networks
Chienhua Chen · 1993
This thesis presents an overview of schemes for obtaining hybrid networks and then introduce a class of hierarchical networks, which is suitable for implementing large multicomputers with VLSI/WSI technology. These networks, called dBCube, employ hypercube topology as a basic cluster, connect many such clusters using a de Bruijn graph, and maintain the same node connectivity for all nodes. A newly introduced scheme for obtaining WSI layout is used to compute the number of tracks needed and the required wafer area. An exact count for the number of tracks in the hypercube and an approximation for the de Bruijn graph are also obtained. Trade-offs of area versus static parameters and the size of the hypercube versus that of the de Bruijn graph are also discussed. To enhance the scalability of the dBCube, we introduce the partially connected dBCube, wherein the use of only few nodes of each cluster as gateways makes it highly scalable in terms of both the hypercube size and the de Bruijn graph size. Performance degradation for proposed partial dBCube has also been determined in terms of the diameter and the average distance. Relative advantages, such as reduction in number of remote links, improved track efficiency and reduced cost, have also been considered in detail.