A Stochastic Edge-Fault-Tolerant Routing Algorithm in Torus Networks
摘要
In a massively parallel system with a large number of elements, it is impossible to ignore the existence of faulty vertices and edges. Effective fault-tolerant routing in such systems relies on storing fault information in a compressed format, known as limited global information, at each non-faulty vertex. The torus network, widely recognized as one of the most popular topologies for interconnection networks of massively parallel systems, presents unique challenges for implementing fault-tolerant routing due to its inherent complexity. Despite its popularity, no effective fault-tolerant routing algorithm utilizing limited global information has been proposed for torus networks until now. This paper introduces a stochastic fault-tolerant routing algorithm for torus networks, capable of handling edge and/or vertex faults. Results from a series of computer simulations demonstrate that the proposed algorithm significantly enhances fault-tolerant routing performance in a massively parallel system.