规则互连网络的系统级故障诊断研究

论文摘要

互连网络是实现多计算机系统中处理器之间相互通信的有效机制,系统的可靠性在很大程度上依赖于互连网络的可靠性,它是决定系统性能的重要因素之一。随着系统规模的扩大,系统部件出错的可能性也越来越大。为了得到系统的高可靠性和高可用性,系统级故障诊断是确定系统中故障处理器的一个有效方法。它是首先由相邻处理器之间通过相互测试而形成症候,进而根据症候来进行故障诊断的过程。本文主要致力于互联网络的系统级故障诊断研究。首先,介绍了系统级故障诊断领域的现实意义及其研究现状,并详细介绍了系统级故障诊断的相关概念和方法,以及几类经典的故障诊断模型和诊断策略。然后,介绍了几类经典的互连网络模型（交叉立方体、0-M?bius立方体、1-M?bius立方体和局部扭曲立方体）的定义和性质。悲观诊断策略通过牺牲一小部分结点不能正确诊断为代价,提高了系统的自诊断能力。通过分析局部扭曲立方体的0-测试子图的最大连通分量和其中故障结点分布之间的关系,可以将对一个n维局部扭曲立方体的诊断转化为两个n– 1维的局部扭曲立方体上的诊断。在此基础上,本文中提出了一个快速悲观诊断算法。在系统中最多有个2n– 2个故障结点的情况下,此算法能以至多错误诊断一个无故障结点为代价,诊断出所有故障结点。该算法的时间复杂度为是O（Nlog2N）,这里N是系统中结点数。而经典的YML算法所需时间为O（N2.5）。因此,新算法在时间复杂度方面是高效的。当可诊断系统的一步诊断度受到其互连结构中最小顶点度的限制时,顺序诊断是对多计算机系统进行故障诊断的一种更为实际的方法。BC图是近年来提出一类互连网络拓扑结构。本文在PMC模型下提出了一个基于BC图的顺序诊断算法。该算法表明了n维BC图是?（NloglogN /logN）-可诊断的,这里N = 2n是BC图的结点数。

论文目录

• 中文摘要
• 英文摘要
• 1 绪论
• 1.1 引言
• 1.2 互连网络拓扑结构分类
• 1.3 系统级故障诊断的研究现状
• 1.4 本文组织结构
• 2 基础知识
• 2.1 图论基础知识
• 2.2 系统级故障诊断方法
• 2.3 超立方体及其变体结构
• 2.3.1 超立方体及其变体结构的定义
• 2.3.2 超立方体及其变体结构的性质
• 2.4 本章小结
• 3 两个经典诊断算法
• 3.1 YML 算法
• 3.2 一个基于超立方体的线性时间顺序诊断算法
• 3.3 本章小结
• 4 基于规则互连网络的故障诊断算法
• 4.1 一种高效的基于局部扭曲立方体的悲观诊断算法
• 4.1.1 基础知识
• 4.1.2 算法原理
• 4.1.3 诊断算法
• 4.2 一种基于BC 图的顺序诊断算法
• 4.2.1 基础知识
• 4.2.2 一个顺序诊断算法
• 4.2.3 BC 图的顺序诊断度
• 4.3 本章小结
• 5 全文总结
• 致谢
• 参考文献
• 附录