在MM*比较模型下Mbius立方体的一个快速诊断算法  

A Fast Diagnosis Algorithm on Mbius Cube Under the MM* Comparison Model

作　　者：阳惠[1] 杨小帆[1] 

机构地区：[1]重庆大学计算机学院,重庆400044

出　　处：《计算机学报》2007年第7期1125-1131,共7页Chinese Journal of Computers

基　　金：本课题得到教育部新世纪人才计划(NCET-05-0759);教育部博士点基金(20050611001);重庆市自然科学基金CSTC(2006BB2231;2005BB2191);重庆大学研究生科技创新基金(200701Y1A0050191)资助

摘　　要：基于比较的诊断是多计算机故障诊断的一种实用方法．Mbius立方体是超立方体结构的一种变形,具有并行处理所需的某些性质．文章在MM比较模型下研究了Mbius立方体的诊断问题．利用Mbius立方体中圈的分布特性,提出了一个新的诊断算法．通过数据的适当组织,该算法的运行时间为O(Nlog_2~2 N),其中N表示处理器总数．而经典的Sengupta-Dahbura诊断算法所需时间为O(N^5)．因此,新算法在诊断时间方面明显优于Sengupta- Dahbura算法．Comparison-based diagnosis is a practical approach to the system-level fault diagnosis of multicomputers. The Moebius cube is a variant of the hypercube, which possesses some features desirable for parallel processing. This paper addresses the fault diagnosis of the M6bius cube under the MM^＊ comparison model. By employing the distributed property of cycles over a M6bius cube, the authors present a new diagnosis algorithm. With elaborately organized data, this algorithm can operate in O（Nlog2^2N） time, where N stands for the total number of nodes. In comparison, the classical Sengupta-Dahbura diagnosis algorithm takes as much as O（N^5） time to achieve the same goal. As a consequence, the proposed algorithm is remarkably superior to the Sengupta-Dahbura algorithm in terms of the time overhead.

关 键 词：多计算机系统 系统级故障诊断 基于比较的诊断算法 M(o)bius立方体 

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