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
    Caruso, A
    Chessa, S
    Maestrini, P
    Santi, P
    [J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2002, 45 (02): : 126 - 143
  • [2] Adaptive system-level diagnosis for hypercube multiprocessors
    Feng, C
    Bhuyan, LN
    Lombardi, F
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 1996, 45 (10) : 1157 - 1170
  • [3] CHARACTERIZATION OF CONNECTION ASSIGNMENT OF DIAGNOSABLE SYSTEMS
    HAKIMI, SL
    AMIN, AT
    [J]. 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
    KAVIANPOUR, A
    KIM, KH
    [J]. IEEE TRANSACTIONS ON RELIABILITY, 1992, 41 (01) : 26 - 37
  • [6] A LINEAR-TIME ALGORITHM FOR SEQUENTIAL DIAGNOSIS IN HYPERCUBES
    KHANNA, S
    FUCHS, WK
    [J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1995, 26 (01) : 48 - 53
  • [7] A graph partitioning approach to sequential diagnosis
    Khanna, S
    Fuchs, WK
    [J]. 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
    PREPARATA, FP
    METZE, G
    CHIEN, RT
    [J]. IEEE TRANSACTIONS ON ELECTRONIC COMPUTERS, 1967, EC16 (06): : 848 - +
12