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

doi:10.19678/j.issn.1000-3428.0065450

摘要/Abstract

摘要： 随着近年来高性能计算系统规模的急剧扩大，高性能互连网络的可靠性成为愈发重要的问题。高维胖树是一种结合了胖树与多维环网优点的网络拓扑结构，凭借其良好的可扩展性与网络性能在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

中图分类号:

TP391

刘博阳, 胡舒凯, 施得君, 卢宏生. VTFTR：高维胖树中的无死锁容错路由算法[J]. 计算机工程, 2022, 48(12): 38-44,53.

LIU Boyang, HU Shukai, SHI Dejun, LU Hongsheng. VTFTR: Deadlock-Free Fault-Tolerant Routing Algorithm in k-Dimension Fat-Tree[J]. Computer Engineering, 2022, 48(12): 38-44,53.

http://www.ecice06.com/CN/Y2022/V48/I12/38

图/表 10

20230112182331

20230112182334

20230112182339

20230112182343

20230112182346

20230112182350

20230112182353

20230112182358

20230112182402

20230112182405

参考文献

[1] Frontier-HPE CRAY EX235A, AMD optimized 3RD generation EPYC 64C 2 GHz[EB/OL].[2022-07-05].https://www.top500.org/system/180047/.
[2] XU J Q, CAI D J, HE J, et al.A fault-tolerant routing strategy with graceful performance degradation for fat-tree topology supercomputer[C]//Proceedings of IEEE International Conference on High Performance Computing and Communications.Washington D.C., USA:IEEE Press, 2019:405-412.
[3] MCNAIRY C.Exascale fault tolerance challenge and approaches[C]//Proceedings of IEEE International Reliability Physics Symposium.Washington D.C., USA:IEEE Press, 2018:15-26.
[4] LEISERSON C E.Fat-trees:universal networks for hardware-efficient supercomputing[J].IEEE Transactions on Computers, 1985, C-34(10):892-901.
[5] ZHANG H Y, WANG K F, ZHANG J M, et al.A fast and fair shared buffer for high-radix router[J].Journal of Circuits, Systems and Computers, 2014, 23(1):1450012.
[6] KIM J, DALLY W J, SCOTT S, et al.Technology-driven, highly-scalable dragonfly topology[C]//Proceedings of International Symposium on Computer Architecture.Washington D.C., USA:IEEE Press, 2008:77-88.
[7] LINDER D H, HARDEN J C.An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubes[J].IEEE Transactions on Computers, 1991, 40(1):2-12.
[8] CHAIX F, AVRESKY D, ZERGAINOH N E, et al.Fault-tolerant deadlock-free adaptive routing for any set of link and node failures in multi-cores systems[C]//Proceedings of IEEE International Symposium on Network Computing and Applications.Washington D.C., USA:IEEE Press, 2010:52-59.
[9] GLIKSBERG J, CAPRA A, LOUVET A, et al.High-quality fault resiliency in fat trees[C]//Proceedings of IEEE Micro.Washington D.C., USA:IEEE Press, 2019:44-49.
[10] MOLLAH M A, YUAN X, PAKIN S, et al.Rapid calculation of max-min fair rates for multi-commodity flows in fat-tree networks[J].IEEE Transactions on Parallel and Distributed Systems, 2018, 29(1):156-168.
[11] PRABHU PRASAD B M, PARANE K, TALAWAR B.Hy-BTree:an efficient tree based topology for FPGA based NoC implementation[C]//Proceedings of IEEE International Conference on Electronics, Computing and Communication Technologies.Washington D.C., USA:IEEE Press, 2021:1-6.
[12] AHN J H, BINKERT N, DAVIS A, et al.HyperX:topology, routing, and packaging of efficient large-scale networks[C]//Proceedings of Conference on High Performance Computing Networking, Storage and Analysis.Washington D.C., USA:IEEE Press, 2009:1-11.
[13] DOMKE J, MATSUOKA S, RADANOV I, et al.The first supercomputer with HyperX topology:a viable alternative to fat-trees?[C]//Proceedings of IEEE Symposium on High-Performance Interconnects.Washington D.C., USA:IEEE Press, 2019:1-4.
[14] LIANG C H, CHENG C H, WU H L, et al.Beyond the performance of three-tier fat-tree:equality topology with low diameter[C]//Proceedings of International Symposium on Computer, Consumer and Control.Washington D.C., USA:IEEE Press, 2018:22-29.
[15] WANG Y D, LI Y M.Hybrid interconnection networks for reducing hardware cost and improving path diversity based on fat-trees and hypercubes[C]//Proceedings of International Symposium on Computing and Networking Workshops.Washington D.C., USA:IEEE Press, 2021:254-260.
[16] ADDA M, PERATIKOU A.Routing and fault tolerance in Z-fat tree[J].IEEE Transactions on Parallel and Distributed Systems, 2017, 28(8):2373-2386.
[17] WANG Y D, LI Y M.Link fault tolerant routing algorithms in mirrored K-ary N-tree interconnection networks[C]//Proceedings of the 8th International Symposium on Computing and Networking Workshops.Washington D.C., USA:IEEE Press, 2021:237-241.
[18] FUJII H, YASUDA Y, AKASHI H, et al.Architecture and performance of the Hitachi SR2201 massively parallel processor system[C]//Proceedings of the 11th International Parallel Processing Symposium.Washington D.C., USA:IEEE Press, 1997:233-241.
[19] SCOTT S, ABTS D, KIM J, et al.The BlackWidow high-radix clos network[C]//Proceedings of the 33rd International Symposium on Computer Architecture.Washington D.C., USA:IEEE Press, 2016:16-28.
[20] KIM J, DALLY W J, TOWLES B, et al.Microarchitecture of a high radix router[C]//Proceedings of the 32nd International Symposium on Computer Architecture.Washington D.C., USA:IEEE Press, 2005:420-431.
[21] PEÑARANDA R, GÓMEZ C, GÓMEZ M E, et al.A new family of hybrid topologies for large-scale interconnection networks[C]//Proceedings of IEEE International Symposium on Network Computing and Applications.Washington D.C., USA:IEEE Press, 2012:220-227.
[22] 方明.高阶互连网络中路由器交换结构及互连拓扑结构研究[D].长沙:中南大学, 2013. FANG M.Research on router switching fabric and network topology for high radix interconnection network[D].Changsha:Central South University, 2013.(in Chinese)
[23] REQUENA C G, VILLAMÓN F G, REQUENA M E G, et al.RUFT:simplifying the fat-tree topology[C]//Proceedings of the 14th IEEE International Conference on Parallel and Distributed Systems.Washington D.C., USA:IEEE Press, 2008:153-160.
[24] WANG R B, LU K, CHEN J, et al.Brief introduction of TianHe exascale prototype system[J].Tsinghua Science and Technology, 2021, 26(3):361-369.
[25] VIGNÉRAS P, QUINTIN J N.Fault-tolerant routing for exascale supercomputer:the BXI routing architecture[C]//Proceedings of IEEE International Conference on Cluster Computing.Washington D.C., USA:IEEE Press, 2015:793-800.
[26] 曹继军, 刘路, 王永庆.源路由胖树网络的端节点动态容错路由方法[J].计算机工程与科学, 2013, 35(3):8-14. CAO J J, LIU L, WANG Y Q.End-point dynamic fault-tolerant approach in source-routing fat trees[J].Computer Engineering & Science, 2013, 35(3):8-14.(in Chinese)
[27] CHALASANI S, RAGHAVENDRA C S, VARMA A.Fault-tolerant routing in MIN-based supercomputers[J].Journal of Parallel and Distributed Computing, 1994, 22(2):154-167.
[28] KAWAZOE A, KUROKAWA Y, FUKUSHI M.A fault-tolerant adaptive routing method based on the passage of faulty nodes[C]//Proceedings of IEEE International Conference on Consumer Electronics.Washington D.C., USA:IEEE Press, 2020:1-2.
[29] KHICHAR J, CHOUDHARY S, MAHAR R.Fault tolerant dynamic XY-YX routing algorithm for network on-chip architecture[C]//Proceedings of International Conference on Intelligent Computing and Control.Washington D.C., USA:IEEE Press, 2017:1-6.
[30] 徐佳庆, 万文, 蔡东京, 等.高维胖树系统中确定性路由容错策略实现[J].计算机应用, 2018, 38(5):1393-1398. XU J Q, WAN W, CAI D J, et al.Implementation of deterministic routing fault-tolerant strategies for K-ary N-bridge system[J].Journal of Computer Applications, 2018, 38(5):1393-1398.(in Chinese)
[31] PEÑARANDA R, GRAN E G, SKEIE T, et al.A new fault-tolerant routing methodology for KNS topologies[C]//Proceedings of the 2nd IEEE International Workshop on High-Performance Interconnection Networks in the Exascale and Big-Data Era.Washington D.C., USA:IEEE Press, 2016:1-8.
[32] WANG Y Y, LEI F, DONG D Z.Exploring node connection modes in multi-rail fat-tree[C]//Proceedings of IEEE International Conference on Cluster Computing.Washington D.C., USA:IEEE Press, 2021:811-812.
[33] 高剑刚, 卢宏生, 何王全, 等.神威E级原型机互连网络和消息机制[J].计算机学报, 2021, 44(1):222-234. GAO J G, LU H S, HE W Q, et al.The interconnection network and message machinasim of Sunway Exascale prototype system[J].Chinese Journal of Computers, 2021, 44(1):222-234.(in Chinese)

选择文件类型/文献管理软件名称

选择包含的内容