Tree-hypercube: hierarchical, partitionable multiprocessor interconnection network
Mahmoud Omari · 1992
A new interconnection network is developed that combines the desirable features of trees and hypercubes and thus produce better communication capabilities and lower cost extensibility. The derivation of a family of such Tree-Hypercubes (TH) is presented, and their basic properties such as degree, diameter, and average distance are analyzed. The recursive structure of tree-hypercubes makes it easy to develop simple routing algorithms, which require no detailed knowledge of the network interconnections. The simple structure of the network leads to partitioning flexibility. In addition, the size of partitions is not restricted to be a power of two. Thus, system fragmentation is minimized and system utilization is increased. We have developed partitioning strategies which we used to investigate, by simulation, the fragmentation characteristics of the Buddy System (BS) strategy on hypercubes and our Tree-Hypercube Partitioning System (THPS) strategy on tree-hypercubes. The simulation results show that THPS strategy has much better internal fragmentation than the BS strategy. The simulation results also show that the total fragmentation (which gives more accurate picture of the system utilization) of the tree-hypercube partitioning system strategy is better than that of buddy system strategy.