交错立方体在故障情形下的诊断度和诊断算法

计算机工程与科学

交错立方体在故障情形下的诊断度和诊断算法

王喜1,2，张书奎2

（1.苏州工业职业技术学院,江苏苏州 215004；2.苏州大学计算机科学与技术学院,江苏苏州 215006）

收稿日期:2019-04-12 修回日期:2019-08-19 出版日期:2020-04-25 发布日期:2020-04-25
基金资助:
国家自然科学基金（61874087,61802304，61772417,61834005，61602377,61634004）；陕西省国际科技合作计划（2018KW-006）;陕西省科技统筹创新工程（2016KTZDGY02-04-02）；陕西省重点研发计划（2017GY-060）

Diagnosability and a new diagnosis algorithm

of Cross-cube in fault situation

WANG Xi1,2,ZHANG Shu-kui2

（1.Suzhou Institute of Industrial Technology,Suzhou 215004;

2.School of Computer Science and Technology,Soochow University,Suzhou 215006,China）

Received:2019-04-12 Revised:2019-08-19 Online:2020-04-25 Published:2020-04-25

摘要/Abstract

摘要：

基于并行系统的超级计算机一直是学术界和工业界的研究热点。作为并行系统的基础,互连网络的性质直接决定了系统的性能。交错立方体作为超立方体的变形,是一种重要的互连网络,其与超立方体相比具有低直径等优越性。利用PMC诊断模型和图论方法,研究了交错立方体在故障情形下诊断度的精确值。然后提出该情形下的诊断算法,并分析了算法的时间复杂度。进一步通过仿真实验,验证在多种故障参数下,该诊断算法的高效性优于文献算法。本文的研究能够更加精确地度量交错立方体的可靠性。

关键词: 交错立方体, 诊断度, 诊断算法, 互连网络

Abstract:

Supercomputers based on parallel systems have always been a hot research topic in academia and industry. As the basis of parallel systems, the properties of interconnection network determine the system performance directly. As a variant of hypercube, cross-cube is a significant interconnection network, which has superior properties such as low diameter compared with hypercube. This paper uses PMC diagnostic model and graph theory method to study the exact value of the diagnostic degree of cross-cube in fault situation. Then, a diagnosis algorithm is proposed and its time complexity is analyzed. Furthermore, simulation experiments verify that the diagnostic algorithm has higher efficiency than some literature algorithms under a variety of fault parameters. Our research can measure the reliability of cross-cube more accurately.

Key words: cross-cube, diagnosability, diagnosis algorithm, interconnection network

王喜1,2，张书奎2. 交错立方体在故障情形下的诊断度和诊断算法[J]. 计算机工程与科学.

WANG Xi1,2,ZHANG Shu-kui2.

Diagnosability and a new diagnosis algorithm

of Cross-cube in fault situation

[J]. Computer Engineering & Science.

[1]	施得君, 李宏亮, 胡舒凯. 基于Clos网络的高阶路由器结构[J]. 计算机工程与科学, 2023, 45(12): 2099-2112.
[2]	曹继军. 面向HPC和DC的可重构光互连网络体系结构综述[J]. 计算机工程与科学, 2022, 44(06): 951-963.
[3]	梁崇山, 戴艺, 徐炜遐. 一种基于Chiplet集成技术的超高阶路由器设计[J]. 计算机工程与科学, 2022, 44(02): 207-213.
[4]	汪鑫, 林放, 刘轶, 钱德沛. 基于OMNet++的大规模InfiniBand互连网络模拟系统[J]. 计算机工程与科学, 2021, 43(05): 792-798.
[5]	王超, 曹继军, 罗章, 赖明澈, 徐炜遐. 面向HPC互连网络的低延迟前向纠错编码研究与实现[J]. 计算机工程与科学, 2020, 42(11): 1965-1972.
[6]	谢旻, 张伟, 周恩强, 董勇. 面向天河互连网络的可扩展通信框架实现技术[J]. 计算机工程与科学, 2020, 42(10高性能专刊): 1720-1729.
[7]	蒋句平, 董德尊, 唐虹, 齐星云, 常俊胜, 庞征斌. 大规模高性能互连拓扑性能分析[J]. 计算机工程与科学, 2020, 42(10高性能专刊): 1730-1736.
[8]	孙晓乐, 钱亚龙, 齐新新, 张云放, 陈娟, 袁远, 董勇. 片上互连网络的功耗特征分析与优化[J]. 计算机工程与科学, 2020, 42(07): 1141-1150.
[9]	陈芳，张乾. 超立方体网络环诊断策略的研究[J]. 计算机工程与科学, 2019, 41(07): 1191-1196.
[10]	任秀江1，王磊1，周建毅1，谢向辉2. 面向网络通信的高实时压缩引擎设计[J]. 计算机工程与科学, 2018, 40(04): 594-601.
[11]	任秀江1，斯添浩1，周建毅1，谢向辉2. 基于网络包延迟偏差的硬件动态拥塞控制机制[J]. 计算机工程与科学, 2018, 40(02): 200-209.
[12]	路文斌，宋新亮，卢宏生，丁亚军. 一种高阶混合互连网络拓扑结构[J]. 计算机工程与科学, 2017, 39(10): 1781-1787.
[13]	宣恒农，苗春玲，赵冬. 基于蝙蝠算法的系统级故障诊断研究[J]. J4, 2016, 38(04): 640-647.
[14]	宣恒农1,张润驰1,何涛2,刘凌波1. PMC模型下的一个贪婪诊断算法[J]. J4, 2015, 37(08): 1430-1435.
[15]	方磊，董德尊，吴际，夏军，王克非. CbRouter:一种利用交叉开关旁路的双向链路片上网络路由器[J]. J4, 2015, 37(02): 199-206.