Conditional diagnosability algorithm for hypercube under the PMC model

被引：1

作者：

Zhang, Liguo ^{[1
]}

Du, Huimin ^{[2
]}

Han, Jungang ^{[1
,2
]}

机构：

[1] School of Microelectronic, Xidian Univ.

[2] School of Electronic Engineering, Xi'an Univ. of Posts and Telecommunications

来源：

Xi'an Dianzi Keji Daxue Xuebao/Journal of Xidian University | 2012年 / 39卷 / 05期

关键词：

Conditional diagnosability; Diagnosability algorithm; Hypercube; PMC model;

D O I：

10.3969/j.issn.1001-2400.2012.05.025

中图分类号：

学科分类号：

摘要：

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 2) for the n-dimensional hypercube with N nodes.

引用

页码：148 / 153

页数：5

共 15 条

[1]

Preparata F.P., Metze G., Chien R.T., On the connection assignment problem of diagnosable systems, IEEE Trans on Computers, 16, 6, pp. 848-854, (1967)

[2]

Barsi F., Grandoni F., Maestrini P., A theory of diagnosability of digital systems, IEEE Trans on Computers, 7, pp. 585-593, (1976)

[3]

Chwa K.Y., Hakimi S.L., Schemes for fault-tolerant computing: A comparison of modularly redundant and t-diagnosable systems, Information and Control, 49, pp. 212-238, (1981)

[4]

Araki T., Shibata Y., (t, k)-diagnosable system: A generalization of the PMC models, IEEE Trans on Computers, 52, 7, pp. 971-975, (2003)

[5]

Hsieh S.Y., Chuang T.Y., The strong diagnosability of regular networks and product networks under the PMC model, IEEE Trans on Parallel and Distributed Systems, 20, 3, pp. 367-378, (2009)

[6]

Caruso A., Chessa S., Maestrini P., Worst-case diagnosis completeness in regular graphs under the PMC model, IEEE Trans on Computers, 56, 7, pp. 917-924, (2007)

[7]

Manik M., Gramatova E., Diagnosis of faulty units in regular graphs under the PMC model, Design and Diagnostics of Electronic Circuits & Systems, pp. 202-205, (2009)

[8]

Lai P.L., Tan J.J.M., Chang C.P., Et al., Conditional diagnosability measures for large multiprocessor systems, IEEE Trans on Computers, 54, 2, pp. 165-175, (2005)

[9]

Hsua G.H., Chianga C.F., Shiha L.M., Et al., Conditional diagnosability of hypercubes under the comparison diagnosis model, Journal of Systems Architecture, 55, 2, pp. 140-146, (2009)

[10]

Xu M., Thulasiraman K., Hu X., Conditional diagnosability of matching composition networks under the PMC model, IEEE Trans on Circuits and Systems-II: Express Briefs, 56, 11, pp. 875-879, (2009)

← 1 2 →