Adaptive diagnosis for torus systems under the comparison model

Abstract

System level diagnosis is an important technique for fault detection and location in multiprocessor computing systems. Adaptive diagnosis, proposed by Nakajima, is one of many practical approach system level diagnostic schemes. As far as we know, the adaptive approach under the MM model has only been discussed in relation to a completely connected system. In this paper, we consider the problem of adaptive fault diagnosis for systems modelled by a cycle and a torus under the MM model. For cycles, we give some useful properties for identifying faulty vertices, show the minimum number of test rounds and provide some efficient test assignments. We also present two adaptive diagnosis algorithms for tori and show the minimum number of tests for these algorithms. Moreover, the two algorithms take linear time both for overall testing and syndrome decoding.

Keywords:

• adaptive diagnosis
• comparison model
• MM model
• cycle
• torus

2010 AMS Subject Classifications :

• 05C38
• 05C85
• 68R10
• 94C12
• 94C15

Acknowledgements

The author would like to thank Prof. C.H. Tsai for his very constructive suggestions. This work was supported in part by the National Science Council of the Republic of China under Contract NSC 99-2115-M-259-007-MY2.