Tori, Network Fault-tolerant Routing Technology

Today, when the computer has been widely applied to the practice, people have not stopped pursuing the higher performance: with the more and more complex software, the larger and larger application scale, and the higher and higher solution performance, the higher processing speed is required. The parallel multiprocessor is a possible solution to realize the high computing performance. However, it needs the interconnection network to connect the processors, the storage devices and other peripheries. The interconnection network with high performance is a crucial factor to the performance of the parallel multiprocessors. The Tori network, whose topology is orthogonal, is one of the widely adopted networks in practice.Fault tolerance is a fundamental issue that should be taken into account in the Tori network design. Although these routing and switching technologies, designed for the nonfaulty networks with no deadlock or livelock, have satisfied performance, it is quite possible that the faults would cause them to lose their effectiveness. Therefore, in the case of the faults existing in the network, we should reconsider and redesign these proposed solutions.Targeting the problems mentioned above, the contributions of our research mainly lie in that we have firstly presented a kind of fault model, called the revised convex fault model, and its formation algorithm. Based on the turn model, we have designed a fault-tolerant routing scheme, which is called the two-level-turn-model and could tolerate the revised convex faults in Tori. Through the theoretical analysis, this fault-tolerant routing scheme is deadlock-free. Also, this has been proven by the simulation and the corresponding performance parameters have been collected. In the next, we have investigated the fault-tolerant properties of this two-level-turn-model routing scheme under the concave fault model. Then, we have found that this fault-tolerant routing scheme could also tolerate the concave faults with some limitations in Tori. Furthermore, we have analyzed the drawback of the fault-tolerant routing schemes which are designed based on the fault model. Then, the idea to set the outer ring around the fault ring to overcome this drawback is proposed. Finally, the simulation has shown the effect of the outer ring on the improvement of the network performance.