Conditional diagnosability of hypermesh optical multiprocessor systems under the PMC model

Abstract

The hypermeshes are a family of promising optical interconnection topologies for multiprocessor systems. In this paper, the conditional diagnosability of the hypermesh optical multiprocessor systems, under the PMC model, is determined. We derive that the conditional diagnosability of k ⁿ -hypermesh is 4n(k−1)−4k+1, where n≥3 and k≥5. This result shows that the hypermesh optical multiprocessor systems possess strong self-diagnosing abilities.

Keywords:

• interconnection network
• system-level diagnosis
• conditional diagnosability
• PMC model
• hypermesh optical multiprocessor system

2000 AMS Subject Classifications :

• 68M15
• 68M10
• 05C10
• 05C40

Acknowledgements

The authors are grateful to the anonymous referees for their valuable comments and suggestions. This work was supported by the Natural Science Foundation of China (No. 10771227) and the Project for New Century Excellent Talents of Educational Ministry of China (No. NCET-05-0759).

Additional information

Notes on contributors

Qiang Dong

Present address: National Computer Experimental Teaching Demonstration Center, University of Electronic Science and Technology of China, Chengdu 611731, China