HIERARCHICAL INTERCONNECTION NETWORKS FOR MULTICOMPUTER SYSTEMS

Multicomputer systems are distributed-memory MIMD systems. Communication in these systems occurs through explicit message passing. Therefore, the underlying processor interconnection network plays an important and direct role in determining their performance. Several types of interconnection networks have been proposed in the literature. Unfortunately, no network is “universally” better. Ideally, therefore, systems should use more than one such network. Furthermore, systems that have large numbers of processors should be able to exploit locality in communication in order to obtain improved performance. This paper proposes the use of hierarchical interconnection networks to meet both these requirements. A performance analysis of a class of hierarchical interconnection networks is presented. This analysis includes both static analysis (i.e., queueing delays are neglected) and queueing analysis. In both cases, the hierarchical networks are shown to have better cost-benefit ratios. The queueing analysis is also validated (within our model) by several simulation experiments. The impact of two performance enhancement schemes—replication of links and improved routing algorithms—on hierarchical interconnection network performance is also presented. © 1990 IEEE