The Research Of The High-Performance Deadlock-free Multicast Routing Algorithrn For K-Ary N-Cubes Networks

The interconnection network is one of the most essential subsystem in high performance parallel multiprocessors computer systems. It determines the performance of the inter-node communication. K-ary n-cubes are one of the most popular, versatile and efficient topological structures of interconnection networks. In k-ary n-cubes, each node is physically connected to adjacent nodes only, along all dimensions. This represents an important plus of k-ary n-cubes, which facilites their hardware implementation and adds to their scalability. Most research on multiprocessor architectures focuses on k-ary n-cubes due to their hardware advantages and heoretical generality. Muticast routing technology is all through very important research topic in area of k-ary n-cubes interconnection network. Thus, the research of muticast routing technology for k-ary n-cube network in theory and application has very important theoretical and practical significance.In this thesis a new muticast routing algorithm, called Multicast Routing Based on Independent Flit Flow (MRIFF), for k-ary n-cube network is proposed, which is deadlock-free. In MRIFF, flits flow independent of each other and, thus, they must carry additional information indentifying the message that they belong to. The additional information is used to avoid deadlock. MRIFF allows nodes to send flits as soon as internode links are available for transmission. The MRIFF muticast routing algorithm eliminates the need to implement deadlock avoidance, detection, and recovery mechanisms, but needs larger output buffers.Finally, a series of extensive simulation experiments have been performed to evaluate the performance of the new proposed muticast routing algorithm by OPNET under various traffic modes. The simulation results show that MRIFF algorithm proposed offers better performance than the previously published routing algorithms, such as dimension order routing (DOR), hardware tree-based routing(HTA), deadlock-free multicast routing algorithm (DFMR) in terms of message delay, average overhead, average load. The research in the thesis provides a theoretical and practical solution for implementing muticast routing in k-ary n-cubes network.