The authors present a novel approach to the design of a class of hierarchical interconnection networks for multiprocessor systems. This approach, based on an architecture providing separate networks for each level, gives a general and flexible way to construct efficient hierarchical networks. The performance and cost-effectiveness of the resulting networks are analyzed and compared in detail, using both unbuffered and buffered network models. It is shown that, if the design parameters are determined based on the degree of locality, the cost-effectiveness of a hierarchical network can be significantly improved. In addition, the authors investigate how to construct a cost-effectiveness hierarchical network by determining appropriate design parameters. Two associated algorithms are developed for this purpose.>

Hierarchical interconnection networks exploit locality in communication to reduce the number of links in the networks.In this paper, we propose a cla8s of general hierarchical interconnection network8 for message-passing architectures.We show that a new approach to design, choosing the appropriate number of interface nodes, considerably reduces not only intercluster trafic density but also intracluster trafic density.

A hypercube with extra connections added between pairs of nodes through otherwise unused links is investigated. The extra connections are made in a way that maximizes the improvement of the performance measure of interest under various traffic distributions. The resulting hypercube, called the enhanced hypercube, requires a simple routing algorithm and is guaranteed not to create any traffic-congested points or links. The enhanced hypercube achieves noticeable improvement in diameter, mean internode distance, and traffic density, and it also is more cost effective than a regular hypercube. An efficient broadcast algorithm that can considerably speed up the broadcast process in enhanced hypercubes is provided.>

Extra Group Networks, a class of fault-tolerant multistage interconnection networks, are introduced. An EGN-m of size N is designed to have m+1 unique-path multistage-networks of size N/m. This approach of constructing the network allows that an EGN-m can provide full-access capability in the presence of multiple faults, up to m, in any stage. EGNs can also maintain the permutation capability of the unique-path multistage-network of size N in the presence of any single fault. It is shown that EGNs are more cost-effective than other previously proposed fault-tolerant multistage-interconnection networks with a similar fault-tolerant capability.>