作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2022, Vol. 48 ›› Issue (12): 38-44,53. doi: 10.19678/j.issn.1000-3428.0065450

• 先进计算技术 • 上一篇    下一篇

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

刘博阳1, 胡舒凯2, 施得君1, 卢宏生3   

  1. 1. 战略支援部队信息工程大学, 郑州 450001;
    2. 江南计算技术研究所, 江苏 无锡 214100;
    3. 国家并行计算机工程技术研究中心, 北京 100190
  • 收稿日期:2022-08-08 修回日期:2022-09-22 发布日期:2022-10-24
  • 作者简介:刘博阳(1997—),男,硕士研究生,主研方向为高性能互连网络;胡舒凯,工程师、硕士;施得君,工程师、博士研究生;卢宏生(通信作者),正髙级工程师。
  • 基金资助:
    国家重点研发计划(2021YFB0301000)。

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

LIU Boyang1, HU Shukai2, SHI Dejun1, LU Hongsheng3   

  1. 1. Strategic Support Force Information Engineering University, Zhengzhou 450001, China;
    2. Jiangnan Institute of Computing Technology, Wuxi, Jiangsu 214100, China;
    3. National Research Center of Parallel Computer Engineering and Technology, Beijing 100190, China
  • Received:2022-08-08 Revised:2022-09-22 Published:2022-10-24

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

关键词: 高性能互连网络, 高维胖树, 容错路由算法, 高性能计算, 死锁预防

Abstract: 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.

Key words: high performance interconnection network, k-dimension fat-tree, fault-tolerant routing algorithm, high performance computing, deadlock prevention

中图分类号: