VTFTR：高维胖树中的无死锁容错路由算法

随着近年来高性能计算系统规模的急剧扩大，高性能互连网络的可靠性成为愈发重要的问题。高维胖树是一种结合了胖树与多维环网优点的网络拓扑结构，凭借其良好的可扩展性与网络性能在E级时代具有广阔的应用前景。然而，目前关于高维胖树中容错路由算法的相关研究较为有限，其可靠性问题亟待解决。为提高高维胖树拓扑在高性能互连网络中的容错能力，进一步提高对应超算系统的运行效率，提出一种用于高维胖树中叶交换机故障的容错路由算法VTFTR。该算法结合转向模型与虚通道切换的思想，通过严格控制报文在无故障路径与容错路径中的转向，使用少量的容错虚通道与额外跳步实现高维胖树中的无死锁容错。实验结果表明，在单点故障情况下，VTFTR算法的容错路径较对比算法有2~4个跳步的减少，在4 096个节点规模的网络中，当叶交换机故障数量为10时，在故障叶交换机不同的分布情况下，该算法能够以1.4%~2.0%的吞吐率下降作为代价来保持全网无故障节点之间的互连。

VTFTR: Deadlock-Free Fault-Tolerant Routing Algorithm in k-Dimension Fat-Tree

With the recent rapid increase in the scale of high-performance computing systems, the reliability of high-performance interconnection networks has become a significant research problem.The k-dimension fat-tree is a topology network that combines the advantages of fat-tree topology and k-dimension torus architecture.Its excellent scalability and network performance have shown wide promising applications in the era of Exa-scale computing.However, current research on the fault-tolerant routing algorithm in high-dimensional fat trees is still relatively limited, and reliability issues still need to be addressed.This paper proposes a fault-tolerant routing algorithm called Virtual Turning Fault-Tolerant Routing(VTFTR) for leaf switch faults in the k-dimension fat-tree to improve the fault tolerance of k-dimension fat-tree topology in high-performance interconnection networks and further enhance the work efficiency of supercomputing systems.VTFTR combines the principles of the turning model and virtual channel switching.By strictly controlling the steering of messages in fault-free and fault-tolerant paths, high-dimensional fat trees can achieve deadlock-free fault tolerance with a few fault-tolerant virtual channels and additional hops.The experimental results show that in a single fault scenario, VTFTR can reduce between two and four hops in the fault-tolerant path compared to the existing algorithm.When the number of switch failures in the 4 096-node scale network increases to 10, the network can achieve interconnection of fault-free nodes in the entire network at the cost of a 1.4%-2.0% throughput drop based on the different distributions of fault leaf switches in the network.