Computer Science ›› 2017, Vol. 44 ›› Issue (6): 83-90.doi: 10.11896/j.issn.1002-137X.2017.06.014

Previous Articles     Next Articles

Hypercube Network Diagnosis Algorithm under Comparison Model

CHEN Miao-jiang, LIANG Jia-rong and ZHANG Qian   

  • Online:2018-11-13 Published:2018-11-13

Abstract: An efficient diagnosis is very important for a multiprocessor system.The ability to identify all the faulty nodes in a multiprocessor system is known as diagnosability.In the comparison model,the diagnosis is performed by sending two identical signals from a processor to a pair of distinct neighbors,and comparising the responses.To improve the diagnosability of hypercube network,we presented a novel hypercube network algorithm under the comparison mo-del,which uses the characteristic of the hypercube links to produce a topology netword ES(k;n) and obtains a three-binary diagnosis syndrome to determine the fault node of the system.In the optimal conditions,the diagnosability of algorithm is 4n,which is bigger than its ordinary diagnosability n.

Key words: Fault diagnosis,Comparison diagnosis model,Hypercube network,System-level diagnosis

[1] PREPARATA F P,METZE G,CHIEN R T.On the connection assignment problem of diagnosable system[J].IEEE Trans.on Electronic Computers,1967,6(12):848-854.
[2] BRASI F,GRANDONI F,MAESTRINI P.A theory of diagnosa-bility of digital systems[J].IEEE Trans.on Computers,1976,5(6):585-593.
[3] XUAN H N,ZHANG D F,ZHANG M.The equation diagnosis on PMC fault model[J].Acta Electronica Sinica,2003,31(5):694-697.(in Chinese) 宣恒浓,张大方,张明.PMC故障模型的方程诊断[J].电子学报,2003,31(5):987-990.
[4] GUO C,LIANG J R,LENG M.The Conditional Fault Diagnosis of PMC Model[J].Acta Electronica Sinica,2015,3(11):2331-2337.(in Chinese) 郭晨,梁家荣,冷明.基于PMC模型的条件故障诊断[J].电子学报,2015,3(11):2331-2337.
[5] MALEK M.A comparison connection assignment for diagnosis of multiprocessor systems[C]∥Proc.Seventh Int’l Symp Computer Architecture.New York:ACM,1980:31-35.
[6] MAENG J,MALEK M.A comparison connection assignmentfor self-diagnosis of multiprocessor systems[C]∥The 11th International Symposium on Fault Tolerant Computing.Edinburgh,Scotland,1981:173-175.
[7] ARMSTRONG J R,GRAY F G.Fault Diagnosis in a Boolean n cube array of microprocessors[J].IEEE Trans.Computers,1981,0(8):587-590.
[8] KAVIANPOUR A,KIM K H.Diagnosability of hypercube under the pessimistic One-step diagnosis strategy[J].IEEE Trans.Computers,1991,0(2):232-237.
[9] SENGUPTA A,DAHBURA A.On Self-Diagnosable multiprocessor systems:diagnosis by the comparison approach[J].IEEE Trans.Computers,1992,1(11):1386-1396.
[10] YANG X F,TANG Y Y.Efficient fault identification of diagnosable systems under the comparison model[J].IEEE Trans.Computers,2007,6(12):1612-1618.
[11] LAI P L.A system algorithm for identifying faults on hypercube-like networks under the comparison model[J].IEEE Trans on Reliability,2012,2(4):452-459.
[12] YE L C,LIANG J R.A fast pessimistic diagnosis algorithm for hypercube-like network under the comparison model[J].IEEE Trans.on Computers,2016,5(9):2884-2888.
[13] YE T L,HSIEH S Y.A scalable comparison-based diagnosis algorithm for hypercube-like networks[J].IEEE Tran.on relia-bility,2013,2(4):789-799.
[14] TSAI C H.A quick pessimistic diagnosis algorithm for hyper-cube-like multiprocessor systems under the PMC model[J].IEEE Tran.on computers,2013,2(2):259-267.
[15] HSIEH S Y,CHEN Y S.Strongly diagnosable systems under the comparison diagnosis model[J].IEEE Trans.on Compu-ters,2008,7(12):1720-1725.
[16] XIONG X,LIANG J R,MA Q.Research on (t,k)-diagnosability for exchanged hypercube network[J].Journal on Communications,2016,7(3):190-198.(in Chinese) 熊茜,梁家荣,马强.交换超立方网络的(t,k)故障诊断度研究[J].通信学报,2016,7(3):190-198.
[17] WANG D.Diagnosability of hypercubes and enhanced hyper-cubes under the comparison diagnosis model[J].IEEE Trans.on Computers,1999,8(12):1369-1374.

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .