Reducing the number of sequential diagnosis iterations in hypercubes

被引：8

作者：

Santi, P

Chessa, S

机构：

[1] CNR, Ist Informat & Telemat, I-56124 Pisa, Italy

[2] Univ Pisa, Dipartimento Informat, I-56127 Pisa, Italy

[3] CNR, Ist Sci & Tecnol Informaz, I-56124 Pisa, Italy

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2004年 / 53卷 / 01期

关键词：

massively parallel systems; system-level diagnosis; sequential diagnosis; hypercubes;

D O I：

10.1109/TC.2004.1255796

中图分类号：

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

学科分类号：

0812 ;

摘要：

dIn this note, we use a vertex-isoperimetric inequality to show that the number of test and repair iterations needed to perform sequential diagnosis of d-dimensional hypercubes is upper bounded by d - r, where r is an element of theta(d). This result improves the best bound of d test and repair iterations previously known. Numerical evaluation has shown that the actual value of r ranges from 0.16d to 0.31d.

引用

收藏

页码：89 / 92

页数：4

相关论文

共 13 条

[1] 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

[2] Adaptive system-level diagnosis for hypercube multiprocessors [J].

Feng, C ;

Bhuyan, LN ;

Lombardi, F .

IEEE TRANSACTIONS ON COMPUTERS, 1996, 45 (10) :1157-1170

[3] CHARACTERIZATION OF CONNECTION ASSIGNMENT OF DIAGNOSABLE SYSTEMS [J].

HAKIMI, SL ;

AMIN, AT .

IEEE TRANSACTIONS ON COMPUTERS, 1974, C 23 (01) :86-88

[4]

Katona G.O.H, 1975, STUD SCI MATH HUNG, V10, P131

[5] A COMPARATIVE-EVALUATION OF 4 BASIC SYSTEM-LEVEL DIAGNOSIS STRATEGIES FOR HYPERCUBES [J].

KAVIANPOUR, A ;

KIM, KH .

IEEE TRANSACTIONS ON RELIABILITY, 1992, 41 (01) :26-37

[6] A LINEAR-TIME ALGORITHM FOR SEQUENTIAL DIAGNOSIS IN HYPERCUBES [J].

KHANNA, S ;

FUCHS, WK .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1995, 26 (01) :48-53

[7] A graph partitioning approach to sequential diagnosis [J].

Khanna, S ;

Fuchs, WK .

IEEE TRANSACTIONS ON COMPUTERS, 1997, 46 (01) :39-47

[8]

Kranakis E, 2000, IEEE T COMPUT, V49, P1013, DOI 10.1109/12.888036

[9]

Leader Imre, 1991, P S APPL MATH, V44, P57, DOI 10.1090/psapm/044/1141923

[10] ON CONNECTION ASSIGNMENT PROBLEM OF DIAGNOSABLE SYSTEMS [J].

PREPARATA, FP ;

METZE, G ;

CHIEN, RT .

IEEE TRANSACTIONS ON ELECTRONIC COMPUTERS, 1967, EC16 (06) :848-+