Multicast Algorithms On Hypercube Interconnection

The interconnection network is one of the most essential subsystem in high performance computing systems. It determines the performance of the inter-node communication. Due to rapid development of VLSI technology and the new technology such as multicore, multithreaded and SoCs, both the size of interconnection network and the performance of processor increase dramatically. However, the performance increase of interconnection network is much slower. It becomes the new bottleneck gradually. Therefore, besides the research of new interconnecting technology such as optical interconnecting, the collective communication based on multicast and reduction becomes the hot spot. With the increase of network size, the possibility of node failure also increases. The high performance computing system should degrade gracefully when node failure occurred. So it's important guarantee the fault-tolerant, reliable communication between non-faulty nodes.Hypercube is one of the most popular, versatile and efficient topological structures of interconnection networks. With high-radix router and serial transport, the hypercube with large dimension can connect a huge number of nodes. Therefore, the scalability won't be a shortcoming of hypercube for a long time.This dissertation is the research of multicast algorithms on hypercube interconnection, including the multicast on non-faulty hypercube and the multicast on faulty hypercube.The multicast overhead is one the metric of performance. Based on the locality between multicast destination nodes, we propose the clustering model. Due to the small degree of cluster and nice locality between destination nodes inside cluster, the overhead is small for inner-cluster. It decreases the overhead of multicast traffic.We present a multicast tree algorithm and a multicast path algorithm based on the clustering model, in which message routing can be fully distributed. Compared with existing works, our multicast algorithms are with higher utility of locality and reduce the multicast traffic significantly.The locally subcube-connected hypercube is the fault tolerant model for hypercube, whose capacity is much greater than others. We propose the reachability model for locally subcube-connected hypercube. This model is fully distributed without centric controller. We proofs that it is routable for arbitrary two non-faulty nodes with reachability. We present three algorithms for exchanging, updating locality, and an algorithm for local subcube-connectivity detecting. All these algorithms are efficient and fully distributed. It is suitable for hardware implementation due to that the major operations are bitwise.We present an efficient fault tolerant routing algorithm based on the reachability model. Compared with existing works, our routing algorithm is fully distributed, with lower complexity. It is suitable for hardware implementation due to that the major operations are bitwise.We also present the first fault tolerant multicast algorithm based on the reachability model for locally subcube-connected hvpercube. It is efficient, fully distributed and with low complexity. It is suitable for hardware implementation due to that the major operations are bitwise.