PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Caruso A., Chessa S., Santi P., Maestrini P. Diagnosis of Regular Structures. Technical report, 1999.
 
 
Abstract
(English)
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 degree of completeness of the diagnosis provided by 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 grids, hypercubes and CCCs 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.
Subject System-level diagnosis
PMC model
Regular structures
Processor grids
D.4.5 Reliability. Fault-Tolerance
B.1.3 Control StructureReliability, Testing and Fault.Tolerance. Diagnostics
B.8.1 Reliability, Testing and Fault Tolerance
C.1.2 Multiple Data Stream Architectures (Multiprocessors)


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional