【作者】 孙丽萍； 杨小帆； 杭后俊；

【Author】 SUN Li-ping1,2 , YANG Xiao-fan1, HANG Hou-jun2 (1 College of Computer Science, Chongqing University, Chongqing 400044, China; 2 Department of Computer Science, Anhui Normal University, Wuhu 241000, China)

【机构】 重庆大学计算机学院； 安徽师范大学计算机系；

【摘要】 悲观诊断与精确诊断相比,可以提高系统的自诊断能力。局部扭曲立方体是超立方体的一种变体,具有可并行处理的某些性质。在PMC模型下,研究了局部扭曲立方体的诊断问题,提出了一个O（Nlog₂N）的悲观诊断算法,N是处理器总数。经典的YML算法所需时间为O(N^2.5),因此,该算法在时间复杂度方面是高效的。更多还原

【Abstract】 In comparison with precise diagnosis, pessimistic diagnosis can enhance the self-diagnosing capability of a system. Locally twisted cube is one of the hypercube variants, which possesses some features desirable for parallel processing. This paper addresses the fault diagnosis of locally twisted cube under the PMC model and propose an O(N log2 N) algorithm for pessimistic diagnosis of locally twisted cube, where N is the total number of the processors. In comparison, the classical YML algorithm takes O(N 2.5) time to achieve the same goal. In terms of time overload, the presented algorithm is efficient.更多还原