DBCUBE - A NEW CLASS OF HIERARCHICAL MULTIPROCESSOR INTERCONNECTION NETWORKS WITH AREA-EFFICIENT LAYOUT

This paper introduces a class of hierarchical networks, which is suita ble for implementation of large multicomputers in VLSI with Wafer Scal e Integration (VLSI/WSI) technology. These networks, to which we give the name dBCube, employ the hypercube topology as a basic cluster, con nect many such dusters using a de Bruijn graph, and maintain the node connectivity to be the same for all nodes product graph. The size of t his class of regular networks can be easily extended by increments of a cluster size. Local communication, to be satisfied by the hypercube topology, allows easy embedding of existing parallel algorithms, while the de Bruijn graph, which was chosen for JPL's 8096-node multiproces sor, provides the shortest distance between clusters running different parts of an application. A scheme for obtaining WSI layout is introdu ced and used to compute an estimation for the number of tracks needed and the required area on the wafer. The exact count for the number of tracks in the hypercube and an approximation for the de Bruijn graph a re also obtained. Tradeoffs of area versus static parameters and the s ize of the hypercube versus that of the de Bruijn graph are also discu ssed.