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 .
[2] 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 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] 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 .
[5] 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 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .