Diagnosability and a new diagnosis algorithm
of Cross-cube in fault situation

Abstract

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

WANG Xi1,2,ZHANG Shu-kui2.

Diagnosability and a new diagnosis algorithm

of Cross-cube in fault situation

[J]. Computer Engineering & Science.

References ［14］

［1］	Zhang Ling-bo,Huang Zi-juan.Development and deployment of “Tianhe-3” exascale prototype machine［EB/OL］.［2018-12-12］. http://military.people.com.cn/n1/2018/0727/c1011-30173475.html.(in Chinese)
［2］	Preparata F,Metz G,Chien R.On the connection assignment problem of diagnosable systems ［J］.IEEE Transactions on Electronic Computers,1967,16(6):848-854.
［3］	Chang G-Y, Chen G-H, Chang G J.(t,k)-diagnosis for matching composition networks under the MM* model ［J］.IEEE Transactions on Computers,2007,56(1):73-79.
［4］	Hakimi S,Amin A.Characterization of connection assignment of diagnosable systems ［J］.IEEE Transactions on Computers,1974,23(1): 86-88.
［5］	Lin Li-mei,Hsieh S Y,Chen R,et al.The relationship between g-restricted connectivity and g-good-neighbor fault
	diagnosability of general regular networks ［J］.IEEE Transactions on Reliability,2018,67(1):285-296.
［6］	Guo Chen,Peng Shuo,Wang Bo,et al.Survey on fault diagnosis of interconnect networks ［J］.Journal of Frontiers of Computer Science and Technology,2018,12(10):1531-1546.(in Chinese)
［7］	Yan Shao-hua,Fan Jian-xi.Diagnosability of cross-cube under PMC diagnostic model ［J］.Computer Engineering and Applications,2011,47(17):83-86.(in Chinese)
［8］	Cao Qian,Chen Qi,Zhang Shu-kui,et al.Conditional diagnosability of K3-free graph under PMC model ［J］.Application Research of Computers,2017,34(8):2380-2382.(in Chinese)
［9］	Zhang Li-guo,Du Hui-min,Han Jun-gang.Conditional diagnosability algorithm for hypercube under the PMC model ［J］.Journal of Xidian University (Natural Science Edition),2012,39(5):148-153.(in Chinese)
［10］	Xu Li-qiong, Zhou Shu-ming, Lian Guan-qin. Conditional diagnosability of multiprocessor systems based on complete-transposition graphs ［J］.Discrete Applied Mathematics,2018,247:367-379.
［11］	Dahbura A,Masson G.A fault identification algorithm for diagnosable systems ［J］.IEEE Transactions on Computers,1984,33(6): 486-492.
［12］	Xu Jun-ming.Graph theory and its application［M］.3rd ed. Hefei:China University of Science and Technology Press,2010.(in Chinese)
［13］	Haq E.Cross-cube: A new fault tolerant hypercube-based network ［C］∥Proc of the 5th International Parallel Processing Symposium,1991: 471-474.
［14］	Wang Xi,He Fu-nan,Zhang Shu-kui.A restricted fault-free unicast algorithm in cross-cubes ［J］.Journal of Southwest China Normal University (Natural Science Edition),2018,43(9):51-59.(in Chinese)
	附中文参考文献：
［1］	张凌博,黄子娟.“天河三号”E级原型机完成研制部署［EB/OL］.［2018-12-12］. http://military.people.com.cn/n1/2018/0727/c1011-30173475.html.
［6］	郭晨,彭硕,王博,等.互连网络的故障诊断研究综述［J］.计算机科学与探索,2018,12(10):1531-1546.
［7］	闫少华,樊建席.Cross-cube在PMC诊断模型下的诊断性［J］.计算机工程与应用,2011,47(17):83-86.
［8］	曹骞,陈琪,张书奎,等.无K3子图的互连网络在PMC模型下的条件可诊断度［J］.计算机应用研究,2017,34(8):2380-2382.
［9］	张丽果,杜慧敏,韩俊刚.PMC模型下超立方体的一种条件诊断算法［J］.西安电子科技大学学报(自然科学版),2012,39(5):148-153.
［12］	徐俊明.图论及其应用［M］.第3版.合肥：中国科学技术大学出版社,2010.
［14］	王喜,何福男,张书奎.交错立方体上限制容错单播算法的研究［J］.西南师范大学学报(自然科学版),2018,43(9):51-59.

[1]	CAO Ji-jun. Review of reconfigurable optical interconnection network architecture for HPC and DC [J]. Computer Engineering & Science, 2022, 44(06): 951-963.
[2]	WANG Xin, LIN Fang, LIU Yi, QIAN De-pei. A large-scale Infiniband interconnection network simulation system based on OMNet++ [J]. Computer Engineering & Science, 2021, 43(05): 792-798.
[3]	WANG Chao, CAO Jijun, LUO Zhang, LAI Mingche, XU Weixia. Research and implementation of lowlatency forward error correction coding for HPC interconnection network [J]. Computer Engineering & Science, 2020, 42(11): 1965-1972.
[4]	XIE Min, ZHANG Wei, ZHOU En-qiang, DONG Yong. Implementation of scalable communication framework on TH-express interconnection [J]. Computer Engineering & Science, 2020, 42(10高性能专刊): 1720-1729.
[5]	JIANG Ju-ping, DONG De-zun, TANG Hong, QI Xing-yun, CHANG Jun-sheng, PANG Zheng-bin. Performance evaluation of large-scale HPC interconnection network topologies [J]. Computer Engineering & Science, 2020, 42(10高性能专刊): 1730-1736.
[6]	LU Wen-bin,SONG Xin-liang,LU Hong-sheng,DING Ya-jun. A high-radix hybrid topology in interconnection networks [J]. Computer Engineering & Science, 2017, 39(10): 1781-1787.
[7]	XUAN Hengnong,MIAO Chunling,ZHAO Dong. Systemlevel fault diagnosis based on bat algorithm [J]. J4, 2016, 38(04): 640-647.
[8]	XUAN Hengnong1,ZHANG Runchi1,HE Tao2,LIU Lingbo1. A greedy diagnosis algorithm for PMC model [J]. J4, 2015, 37(08): 1430-1435.
[9]	LEI Fei，DONG Dezun，LIAO Xiangke. SuperStar：A scalable high-radix topology in high performance interconnection network [J]. J4, 2014, 36(06): 1034-1041.
[10]	LIU Lu，ZHANG Lei，XIE Min，WANG Yongqing. Design of network interface in Tianhe1A interconnection system [J]. J4, 2013, 35(2): 18-25.
[11]	WANG Yongqing1,WANG Kefei1,XIAO Liquan1,LIU Lu1,PANG Zhengbin2. ptimization and design of high radix asymmetric crossbar [J]. J4, 2013, 35(11): 42-47.
[12]	LEI Fei，DONG De-zun，CHAI Yan-tao，WANG Ke-fei，LI Cun-lu. Survey and evaluation of high-radix topology in high performance interconnection network [J]. J4, 2013, 35(11): 111-118.
[13]	WANG Yongqing,ZHANG Minxuan. A Design of the Reliable Link Layer for Virtual CutThrough Switching [J]. J4, 2012, 34(8): 119-124.
[14]	. [J]. J4, 2008, 30(9): 128-131.

Diagnosability and a new diagnosis algorithm

of Cross-cube in fault situation

PDF

Knowledge

Abstract

Cite this article

share this article

References ［14］

Related Articles 14

Recommended Articles

Metrics

Comments