PERFORMANCE ANALYSIS OF A CLASS OF HIERARCHICAL HYPERCUBE MULTICOMPUTER NETWORKS

Hierarchical interconnection networks (HINs) have been proposed to interconnect large numbers of processors in a multicomputer system. It has been shown that HINs provide better cost-benefit ratios than the corresponding nonhierarchical interconnection networks. This article discusses performance of two schemes that improve fault-tolerance of binary hypercube-based HINs. Both these schemes use hardware redundancy. In one, a standby-spare node is provided to reduce the impact of key node failures on the network reliability; in the other, a part of the network is duplicated. Both these schemes improve the network reliability substantially. The analysis presented here shows that, from a performance point of view, neither of the two schemes dominates the other for all parameter values and system characteristics. If the system supports applications that have varying degrees of communication locality and/or different computation-communication ratios, the duplication scheme is to be recommended. On the other hand, when applications exhibit high degrees of communication locality and high computation-communication ratios, the standby-spare node scheme provides better performance. The impact of three routing algorithms is also considered. We derive bounds on message delay and saturation message generation rate and compare the performance of these routing algorithms in achieving these bounds. It is shown by means of analytical and simulation models that performance of the replication scheme is less sensitive to the routing algorithm used.