TR-156: Some Issues in Hierarchical Interconnection Network Design

Abstract

Hierarchical interconnection networks (HINs) have been proposed as a cost-effective way to interconnect large numbers of processors in a multicomputer system. This paper considers two issues concerning the design of binary-hypercube based HINs — the optimum cluster size and the optimum number of levels in the hierarchy. The optimum. cluster size is dependent on the underlying degree of locality in communication. For all of the various locality characterizations that we consider, the optimum cluster size in a two- level binary-hypercube based HIN is shown to be either 4 or 8, over a wide range of network sizes. It is shown that increasing the number of levels to three yields at most a moderate improvement in the cost-benefit ratio, depending on the type of locality characterization considered. For some locality characterizations, the cost-benefit ratio deteriorates. Thus, an appropriate design for a binary-hypercube based HIN appears to be a two-level hierarchy, with a cluster size of either 4 or 8.