Diagnosis of regular structures

被引：8

作者：

Caruso, A ^{[1
]}

Chessa, S ^{[1
]}

Maestrini, P ^{[1
]}

Santi, P ^{[1
]}

机构：

[1] CNR, Ist Elaboraz Informaz, I-56100 Pisa, Italy

来源：

DSN 2000: INTERNATIONAL CONFERENCE ON DEPENDABLE SYSTEMS AND NETWORKS, PROCEEDINGS | 2000年

关键词：

D O I：

10.1109/ICDSN.2000.857538

中图分类号：

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

学科分类号：

0812 ;

摘要：

This paper introduces an efficient diagnosis algorithm for regular structures (EDARS). The algorithm provides a diagnosis which is correct, but possibly incomplete, if the cardinality of the actual fault set is below a "syndrome-dependent bound" asserted by the algorithm itself. The time complexity of EDARS is O(nt) when executed on t-regular structures of size n. The correctness and the completeness degree of EDARS; were evaluated by means of simulation. Grids, hypercubes and Cube-Connected Cycles (CCC) structures were considered. Simulation results with grid structures showed a strong influence of structure degree over diagnosis performance. Furthermore, comparisons of simulation results obtained with hypercubes, CCCs, and grids of same size and degree, showed that diameter and bisection width also appear to influence the performance of EDARS, particularly with respect to diagnosis completeness.

引用

页码：213 / 222

页数：10

共 17 条

[1]

BARSI F, 1976, IEEE T COMPUT, V25, P585, DOI 10.1109/TC.1976.1674658

[2] EFFICIENT DIAGNOSIS OF MULTIPROCESSOR SYSTEMS UNDER PROBABILISTIC MODELS [J].