一种高效的基于BC图的t/k-诊断算法  

An Efficient Diagnosis Algorithm of BC Graphs

作　　者：邓伟[1] 杨晓帆[1] 吴中福[1] 

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

出　　处：《电子学报》2006年第4期698-701,共4页Acta Electronica Sinica

基　　金：国家发改委基金项目(CNGI-04-15-3A);重庆市自然科学基金(No.CSTC;2005BB2191)

摘　　要：为了提高系统级故障诊断中的诊断度,人们以牺牲很小一部分结点不能正确诊断为代价,提出了t/k-故障诊断策略.BC图是包括了超立方体和多种变形立方体的一类图.对于结点总数为N的BC图,本文提出了一个O(Nlog2N)的t/k-故障诊断算法.目前尚未有相关t/k-故障诊断算法的文章发表,但与著名的悲观一步t-故障诊断算法(t/k-故障诊断算法在k=1时的情况)的O(N2.5)相比较,在时间复杂度上本文算法是高效的.The t/k-diagnosis strategy of system-level diagnosis significantly increases the self-diagnosing capability of multiprocessor systems at the cost of at most k fault-free nodes being incorrectly identified as faulty. The BC graphs are a large class of network topologies, which include several known structures as special cases. Although the t/k-diagnosabilities of the BC graphs have recently been determined, the efficient t/k-diagnosis algorithm of the BC graphs has yet to be developed. In this paper, we present an O （N log2 N） time algorithm for the t/k-diagnosis of the BC graphs, where N is the number of nodes of the system in concern.

关 键 词：系统级故障诊断 诊断算法 BC图 宽度优先搜索 

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