Efficient Communication On K-ary N-cube Networks

The interconnection communication subsystem is an important part of parallel processing computer systems. With the trends of increasing processor speed, increasing size of parallel systems and separation of processors as complete computers, the communication support between the processors has become more and more important to the overall performance of the parallel system. Therefore, realizing a high-performance communication subsystem is critical to the performance of a parallel system. The performance of interconnection communication subsystem is usually restricted by routing algorithm and communication mode and the power of the underlying interconnection network cannot be used fully. Therefore, the interconnection communication subsystem is inefficient.The objective of this dissertatoin is to take the challenge of providing efficient communication on k-ary n-cube networks. We lay stress on the research of adaptive routing algorithms and multicast algorithms.The problem of deadlock question caused by physical topology structure or routing should be solved before the adaptive routing algorithm. Focusing on the particular characteristics of virtual cut-through switching network, we find that message dependencies are localized between adjacent queues. Using this characteristic, we design the novel strategy of flow control called RIFC(Routing Information-based Flow Control). The flow control strategy of RIFC builds on virtual cut-through switching and credit-based flow control mechanism and analyzes the routing information to realize the point-point flow control. Based on the RIFC, we design the fully adaptive routing (FAR) algorithm. In the k-ary n-cube networks without wraparound connections, when the flow control strategy of RIFC is accepted, FAR algorithm can get the goals including deadlock-free and minimal distance even if the cyclic dependencies exist. In this dissertation, the detail proof is provided for these conclusions.We adapt the source code of NETSIM that is a simulator of network and realize the flow control of RIFC and FAR algorithm in NETSIM. We adopt the actual application programs to test the performance of FAR on RSIM. The simulation results show that FAR routingalgorithm owns preferable performance compared with dimensional order routing algorithm on 2D mesh network.By the combination of flow control of Bubble and RIFC, we design the new strategy of flow control called RIABFC (Routing Information-based And Bubble-based Flow Control) for k-ary n-cube networks with wraparound connections. Based on the RIABFC, we design the new fully adaptive routing (NFAR) algorithm. In this dissertation, we prove that NFAR routing algorithm is deadlock-free for the virtual cut-through k-ary n-cube networks with wraparound connections when the flow control of RIABFC is accepted.In order to evaluate the performance of NFAR algorithm and multicast algorithm, we design the simulator named as RingNetSim. RingNetSim is programmed with C++ language and realizes the structure of ring network and is driven by scatter events. We adopt different communication patterns to test the performance of NFAR on RingNetSim. The simulation results show that the performance of routing algorithm of NFAR is better than the dimensional order routing algorithm on two-dimension ring network.In the interconnection network subsystem, realizing the concise and efficient multicast operation is a perfect method to achieve the well communication performance. Moreover, the programming modes of distributing memory and distributed sharing memory demand the underlying interconnection network to support the collective communication. The multicast is the base of other operations in collective communication. We decide to realize the multicast operation with hardware support. For two-deminsion ring network, we realize the encoding/decoding operation of multi-destination address and duplication of packet. In order to support the multi-destination routing, we design the multicast routing algorithm-2DMR(2-D Multicast Routing). At the same time, we prove that the multicast routing algorithm is deadlock-free. The performance evaluation of 2DMR algorithm is done on the simulator of RingNetSim. The simulation results show that 2DMR algorithm can support the multicast operation well and improve the performance of system. Finally, the adaptive router is designed to support the multicast operation in the two-deminsion ring network. The testing results of real application indicate the performance of router is well.