• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

A cycle diagnosis strategy for hypercube networks

CHEN Fang,ZHANG Qian   

  1. (School of Computer and Electronic Information,Guangxi University,Nanning 530004,China)
  • Received:2018-07-18 Revised:2018-11-21 Online:2019-07-25 Published:2019-07-25

Abstract:

Traditional fault diagnosis strategies and conditional diagnosis strategies for multiprocessor systems have been widely studied,however, they have not solved the problem of a large number of fault nodes in the system. Therefore, we propose a new cycle diagnosis strategy, which uses the cycle-partitioning method to diagnose Hamilton cycles and find out all the fault nodes in the system. We also give out the cycle diagnosis strategy and some important properties of hypercube networks. Meanwhile, we also propose a quick cycle diagnosis algorithm of hypercube networks to quickly locate all fault nodes in the system. Based on the above strategy and under the PMC model, the cycle diagnosis degree of an ndimensional hypercube network is (n2+n)/2 and the time complexity is
O(n), where n represents the number of processors in multiprocessor systems. Compared with traditional fault diagnosis strategies and condition diagnosis strategies for hypercube networks, the proposed cycle diagnosis strategy  has the advantages of large diagnosis degree and low time complexity.

 

 

 
 

Key words: cycle diagnosis strategy, PMC model, ndimensional hypercube network, diagnosis degree, time complexity