PMC模型下超立方体的一种条件诊断算法

doi:10.3969/j.issn.1001-2400.2012.05.025

J4 ›› 2012, Vol. 39 ›› Issue (5): 148-153.doi: 10.3969/j.issn.1001-2400.2012.05.025

• Original Articles • Previous Articles Next Articles

Conditional diagnosability algorithm for hypercube under the PMC model

ZHANG Liguo¹;DU Huimin²;HAN Jungang^1,2

(1. School of Microelectronic, Xidian Univ., Xi'an 710071， China;
2. School of Electronic Engineering, Xi'an Univ. of Posts ＆ Telecommunications, Xi'an 710121， China)

Received:2011-06-03 Online:2012-10-20 Published:2012-12-13
Contact: ZHANG Liguo E-mail:zhanglg@xupt.edu.cn

Abstract

Abstract:

Diagnosis has played an important role in the reliability of the interconnection network. Conditional diagnosability is the method that assumes that none of the neighbors of any vertex in the system are faulty at the same time. This diagnosis method greatly enhances the effectiveness of the diagnosis. A conditional diagnosability algorithm for the hypercube based on the PMC model is proposed in the paper. The nodes of the hypercube are divided into several sets through the diagnosis result between two adjacent nodes, and faulty sets and fault-free sets are identified through the realation among sets and the number of elements in the set. The conditional diagnosability of faulty nodes can be effectively implemented when the number of the faulty nodes do not exceed 4(n-2)+1(n≥5). The time complexity of the algorithm is O(N²)for the n-dimensional hypercube with N nodes.

Key words: hypercube, PMC model, conditional diagnosability, diagnosability algorithm

CLC Number:

中图分类号：TP303

ZHANG Liguo;DU Huimin;HAN Jungang. Conditional diagnosability algorithm for hypercube under the PMC model[J].J4, 2012, 39(5): 148-153.

References

［1］ Preparata F P, Metze G, Chien R T. On the Connection Assignment Problem of Diagnosable Systems［J］. IEEE Trans on Computers, 1967, 16(6): 848-854.
［2］ Barsi F,Grandoni F, Maestrini P. A Theory of Diagnosability of Digital Systems［J］. IEEE Trans on Computers, 1976(7): 585-593.
［3］ Chwa K Y, Hakimi S L. Schemes for Fault-Tolerant Computing:a Comparison of Modularly Redundant and t-Diagnosable Systems［J］. Information and Control, 1981, 49: 212-238.
［4］ Araki T, Shibata Y. (t, k)-Diagnosable System: A Generalization of the PMC Models［J］. IEEE Trans on Computers, 2003, 52(7): 971-975.
［5］ Hsieh S Y, Chuang T Y. The Strong Diagnosability of Regular Networks and Product Networks under the PMC Model［J］. IEEE Trans on Parallel and Distributed Systems, 2009, 20(3): 367-378.
［6］ Caruso A, Chessa S, Maestrini P. Worst-Case Diagnosis Completeness in Regular Graphs under the PMC Model［J］. IEEE Trans on Computers, 2007, 56(7): 917-924.
［7］ Manik M, Gramatova E. Diagnosis of Faulty Units in Regular Graphs under the PMC Model［C］//Design and Diagnostics of Electronic Circuits ＆ Systems. Liberec: IEEE, 2009: 202-205.
［8］ Lai P L, Tan J J M, Chang C P, et al. Conditional Diagnosability Measures for Large Multiprocessor Systems［J］. IEEE Trans on Computers, 2005, 54(2): 165-175.
［9］ Hsua G H, Chianga C F, Shiha L M, et al. Conditional Diagnosability of Hypercubes under the Comparison Diagnosis Model［J］. Journal of Systems Architecture, 2009, 55(2): 140-146.
［10］ Xu Min, Thulasiraman K, Hu Xiaodong. Conditional Diagnosability of Matching Composition Networks Under the PMC Model［J］. IEEE Trans on Circuits and Systems-II: Express Briefs, 2009, 56(11): 875-879.
［11］ Zhou Shuming, Xiao Wenjun. Conditional Diagnosability of Alternating Group Networks［J］. Information Processing Letters, 2010, 110(10): 403-409.
［12］ Zhou Shuming. The Conditional Diagnosability of Twisted Cubes under the Comparison Model［C］//IEEE International Symposium on Parallel and Distributed Processing with Applications. Chengdu: IEEE, 2009: 696-701.
［13］ Chang G Y. Conditional (t,k)-Diagnosis under the PMC Model［J］. IEEE Trans on Parallel and Distributed Systems, 2011, 99(1): 1-16.
［14］ Yang Erjie, Yanga Xiaofan, Donga Qiang, et al. Conditional Diagnosability of Hypermeshes under the Comparison Model［J］. Information Processing Letters, 2011,111(4): 188-193.
［15］ Hsu G H, Chiang C F, Tan J J M. Cmoparison-Based Conditional Diagnosability on the Class of Hypercube-like Network［J］. Journal of Interconnection Networks, 2011, 11(3-4): 143-156.

Conditional diagnosability algorithm for hypercube under the PMC model

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Metrics

Comments

Recommended 0