The block shift network: interconnection strategies for large parallel systems
Yi Feng Pan · 1992
As an interconnection network, hypercube topology offers certain advantages such as high data bandwidth and low message latency to achieve computational efficiency. However, a significant drawback of this topology is that the number of ports per node increases with the number of nodes. In addition, in many applications not all the links are used equally frequently, and links on certain dimensions may be idle most of the time during a computation. This suggests that we can provide connections over certain dimensions only and can still attain comparable performance. In this dissertation, we propose a new network, called the Block Shift Network (BSN), for constructing very large multicomputer systems for efficient parallel processing. The idea behind the design is to provide links over certain dimensions only in order to maintain a comparable performance while reducing the number of links used. The BSN is a hierarchical structure with local nodes connected tightly and remote nodes connected loosely. Hence, the topology matches the communication requirements of most parallel application algorithms. Three routing algorithms useful in different situations are presented and their relative merits are discussed. The topological properties are analyzed and compared with those of existing popular networks. The average queueing delay time, the probability of acceptance and the bandwidth of the network are derived through two analytical models. The results show that the BSN surpasses the hypercube in several respects while retaining most of its advantages, especially when the traffic has the locality property. Basic data movement operations on the BSN are designed to support parallel computation. Three classes of typical applications are also mapped onto the BSN. Time complexity analysis indicates that not only do all these data movement operations and algorithms have the same order of magnitude in time as those for a hypercube of the same size, but also the constant factors in the time complexities of these operations and algorithms are very close to those of their counterparts for the hypercube. In some cases, the BSN algorithms have an even smaller time complexity. While the degree of the hypercube is logarithmically proportional to the network size, the degree of the BSN is constant.