超立方体多计算机的系统级故障诊断研究

论文摘要

最近几年,大规模多处理器系统在计算领域起到了越来越重要的作用。但是,随着处理单元的增多,系统部件出错的可能性也随之增加。为了得到系统的高可靠性和高可用性,系统级故障诊断在并行计算领域具有重要地位。它是指系统中各个单元通过互相诊断得到诊断结果即:故障症侯,然后根据这个故障症侯来检测出故障结点以利于及时地更换掉故障结点。超立方体是一类具有良好的拓扑性质和网络参数的互联网络模型,所以对于他们的研究与应用在互联网络的研究中备受关注并且在现实中,一些并行计算机就是基于超立方体构建的。由于超立方体具有很多优秀的性质（对称性,可递归构建性,泛圈性,相对于结点个数的对数级直径,等等）,我们就可以通过利用这些性质来设计高效率的算法。本文就是通过充分挖掘超立方体的性质来设计高效的故障诊断算法。我们首先介绍了系统级故障诊断领域的研究的主要内容和研究现状,分析了超立方体及其变体的结构和性质。在介绍基于超立方体的新的故障诊断算法之前,我们介绍了故障诊断领域里的两个经典的诊断算法即:Sullivan 针对一般的t-可诊断系统而设计的O（t3+|E|）时间复杂度的算法和杨小帆教授利用圈分解技术针对超立方体结构设计的O（Nlog2N）时间复杂度的算法。根据上面的研究,我们设计了两个新的故障诊断算法。我们通过对超立方体中可嵌入的完全非平衡生成树的研究来提高这两个算法的效率。这两个算法都是基于广度优先搜索算法。利用超立方体中的完全非平衡生成树及其在超立方体中特殊的性质,我们提高了广度优先搜索算法的效率。第一个算法中我们利用杨小帆教授关于最大连通分图的容错度理论设计了一个O（Nlog2N）时间复杂度的算法但其容错能力为4n-7（其中包括3 个误诊断的结点）。此算法虽然和现在最好的算法在时间复杂度上相当,但其拥有较强的容错能力。此算法通过广度优先搜索算法来建立最大连通分图从而孤立故障结点达到诊断故障结点的目的。第二个算法也是基于广度优先搜索策略。通过深入挖掘超立方体中完全非平衡生成树的性质,并引入杨小帆教授的圈分解的思想,我们设计了一个线性时间复杂度的算法。此算法的容错能力是2n-2,低于第一个算法但时间复杂度优于第一个算法。在这个算法中,我们为了使算法达到线性时间复杂度提出了树分解的

论文目录

• 中文摘要
• 英文摘要
• 1 绪论
• 1.1 引言
• 1.2 并行计算机中的系统级故障诊断
• 1.3 超立方体结构及其变体
• 1.4 本章小结及本文的研究重点
• 2 基础知识
• 2.1 图论基础知识
• 2.2 超立方体及其性质
• 2.3 本章小结
• 3 多处理器系统的经典系统级故障诊断算法
• 3.1 PMC 模型分析
• 3.2 两个经典诊断算法
• 3+|E|）时间复杂度的算法'>3.2.1 基于分支限界的O（t³+|E|）时间复杂度的算法
• 3.2.2 基于圈分解的故障诊断算法
• 3.3 本章小结
• 4 基于超立方体树的两个新型故障诊断算法
• 4.1 一个O（N1092N）时间复杂度的故障诊断算法
• 4.1.1 基础知识
• 4.1.2 算法中的数据结构
• 4.1.3 算法描述
• 4.1.4 算法正确性证明及时间复杂度分析
• 4.2 一个线性时间复杂度的一步悲观诊断算法
• 4.2.1 基础知识
• 4.2.2 算法中的数据结构
• 4.2.3 算法描述
• 4.2.4 算法正确性及时间复杂度分析
• 4.3 本章小结
• 5 全文总结
• 致谢
• 参考文献
• 附录 A
• 附录 B
• 附录 C