一种高效的基于局部扭曲立方体的悲观诊断算法  

An Efficient Pessimistic Diagnosis Algorithm on Locally Twisted Cube

作　　者：孙丽萍[1,2] 杨小帆[1] 杭后俊[3] 

机构地区：[1]重庆大学计算机学院 [2]安徽师范大学计算机系,安徽芜湖241000 [3]安徽师范大学计算机系

出　　处：《微电子学与计算机》2007年第10期171-173,共3页Microelectronics & Computer

基　　金：教育部新世纪优秀人才计划(NCET-05-0759);教育部博士点基金(20050611001)

摘　　要：悲观诊断与精确诊断相比,可以提高系统的自诊断能力。局部扭曲立方体是超立方体的一种变体,具有可并行处理的某些性质。在PMC模型下,研究了局部扭曲立方体的诊断问题,提出了一个O(Nlog_2N)的悲观诊断算法,N是处理器总数。经典的YML算法所需时间为O(N^(2.5)),因此,该算法在时间复杂度方面是高效的。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^25） time to achieve the same goal. In terms of time overload, the presented algorithm is efficient.

关 键 词：系统级故障诊断 悲观诊断算法 局部扭曲立方体 PMC模型 

分 类 号：TP306.3[自动化与计算机技术—计算机系统结构]