DESIGN AND ANALYSIS OF A CLASS OF HIGHLY SCALABLE HIERARCHICAL NETWORKS - PDBCUBE

A class of hierarchical networks called the dBCube, that provides cost -effective and high-performance communication in large multicomputer s ystems, has recently been introduced. Such a compound graph of a hyper cube and a de Bruijn (dB) graph utilizes every node of the hypercube a s a gateway for intercluster communication. This paper presents a part ially connected dBCube subclass (PdBCube), wherein the use of fewer no des as gateways makes the PdBCube highly scalable in terms of both the hypercube and the dB size. This enhancement in scalability can be ach ieved by two different approaches to assigning gateways. Performance d egradation of the proposed PdBCube is illustrated in terms of diameter and average distance. Improvement in track efficiency and reduction i n cost are observed to be directly related to a decrease in the number of remote links. (C) 1994 Academic Press, Inc.