(t, k)-Diagnosability for Regular Networks

被引：7

作者：

Chang, Guey-Yun ^{[1
]}

机构：

[1] Natl Cent Univ, Dept Comp Sci & Informat Engn, Tao Yuan 320, Taiwan

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2010年 / 59卷 / 09期

关键词：

Diagnosability; diagnosis algorithm; fault diagnosis; matching composition; network; PMC model; system-level diagnosis; (t; k)-diagnosis; torus; COMPARISON DIAGNOSIS MODEL; MATCHING COMPOSITION NETWORKS; SEQUENTIAL DIAGNOSIS; ENHANCED HYPERCUBES; DIAGNOSABILITY; SYSTEMS; GRAPHS;

D O I：

10.1109/TC.2010.16

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

System-level diagnosis aims to identify faulty processors in a multiprocessor system by means of analyzing the test results among the processors. (t, k)-Diagnosis, which is one of the most important system-level diagnosis strategies, requires at least k faulty processors identified in each iteration provided there are at most t faulty processors, where t >= k. In this paper, a new (t, k)-diagnosis algorithm for regular networks is proposed. Experimental results show that the proposed algorithm has larger values of t for tori and matching composition networks, in comparison with previous (t, k)-diagnosis algorithms.

引用

页码：1153 / 1157

页数：5

共 19 条

[1]

Araki T, 2003, IEEE T COMPUT, V52, P971, DOI 10.1109/TC.2003.1214345

[2]

ARMSTRONG JR, 1981, IEEE T COMPUT, V30, P587, DOI 10.1109/TC.1981.1675844

[3] Diagnosability of regular systems [J].

Caruso, A ;

Chessa, S ;

Maestrini, P ;

Santi, P .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2002, 45 (02) :126-143

[4] Worst-case diagnosis completeness in regular graphs under the PMC model [J].

Caruso, Antonio ;

Chessa, Stefano ;

Maestrini, Piero .

IEEE TRANSACTIONS ON COMPUTERS, 2007, 56 (07) :917-924

[5] Diagnosability of t-connected networks and product networks under the comparison diagnosis model [J].

Chang, CP ;

Lai, PL ;

Tan, JJM ;

Hsu, LH .

IEEE TRANSACTIONS ON COMPUTERS, 2004, 53 (12) :1582-1590

[6] (t, k)-diagnosability of multiprocessor systems with applications to grids and tori [J].

Chang, Guey-Yun ;

Chen, Gen-Huey .

SIAM JOURNAL ON COMPUTING, 2007, 37 (04) :1280-1298

[7] (t, k)-diagnosis for matching composition networks under the MM* model [J].

Chang, Guey-Yun ;

Chen, Gen-Huey ;

Chang, Gerard J. .

IEEE TRANSACTIONS ON COMPUTERS, 2007, 56 (01) :73-79

[8] (t, k)-diagnosis for matching composition networks [J].

Chang, GY ;

Chen, GH ;

Chang, GJ .

IEEE TRANSACTIONS ON COMPUTERS, 2006, 55 (01) :88-92

[9] Diagnosabilities of regular networks [J].

Chang, GY ;

Chang, GJ ;

Chen, GH .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2005, 16 (04) :314-323

[10]

DAHABURA AT, 1984, IEEE T COMPUT, V33, P486

← 1 2 →