规则互连网络的系统级故障诊断研究计算机软件与理论专业论文.docxVIP

重庆大 重庆大学硕士学位论文 英文摘要 PAGE PAGE IV number of nodes of a BC graph. Keywords: Multicomputer System, Interconnection Network, System-Level Diagnosis, Pessimistic Diagnosis, Sequential Diagnosis, Diagnosis Algorithm 重庆大学 重庆大学硕士学位论文 目 录 目 录 中文摘要I 英文摘要 II 1 绪 论 1 1.1 引言 1 1.2 互连网络拓扑结构分类 2 1.3 系统级故障诊断的研究现状 3 1.4 本文组织结构 6 2 基础知识 8 2.1 图论基础知识 8 2.2 系统级故障诊断方法 8 2.3 超立方体及其变体结构 11 2.3.1 超立方体及其变体结构的定义 12 2.3.2 超立方体及其变体结构的性质 14 2.4 本章小结 15 3 两个经典诊断算法 16 3.1 YML 算法 16 3.2 一个基于超立方体的线性时间顺序诊断算法 21 3.3 本章小结 24 4 基于规则互连网络的故障诊断算法 26 4.1 一种高效的基于局部扭曲立方体的悲观诊断算法 26 4.1.1 基础知识 26 4.1.2 算法原理 27 4.1.3 诊断算法 29 4.2 一种基于 BC 图的顺序诊断算法 30 4.2.1 基础知识 30 4.2.2 一个顺序诊断算法 32 4.2.3 BC 图的顺序诊断度 33 4.3 本章小结 35 5 全文总结 36 致 谢 37 参考文献 38 附 录 41 重庆大 重庆大学硕士学位论文 1 绪 论 PAGE PAGE 10 1 绪 论 引言 当前在科技发展、国防建设和经济发展领域中有许多具有深刻影响的重大问 题，如气候模拟与大范围天气预报，核武器系统的研究等均需要存储容量大、计 算速度快的计算机系统，它们要求计算机具有每秒万亿次级浮点运算，甚至更高 级别的计算能力。并行计算机系统、分布式系统以及计算机网络为实现高性能计 算、高容量信息的存储和传输提供了强大的工具，高性能微处理器技术的迅猛发 展，为并行计算机的实现提供了前所未有的、坚实的物质基础，使高性能大规模 计算机系统的实现成为可能。 互连网络（Interconnection Networks）是随着信息技术与计算机科学的发展而 产生的一个跨数学与信息科学的研究领域。互连网络的研究在图论、算法设计与 分析、计算机体系结构、并行与分布及计算机网络与通信等诸多方面都起着非常 重要的作用。多处理器互连网络，简称互连网络（Interconnection Network），是 指由若干个处理器按照一定的方式相互连接而构成的网络。在一个互连网络中， 每个处理器有本地内存和资源，它通过通信链路与其相邻处理器连接。随着计算 机系统规模的扩大和发展，整个系统的稳定性和安全性也成为一个十分重要的问 题。互连网络是实现处理器间相互通信的物质基础，其性质如何直接决定着整个 系统性能的优劣，而且系统的可靠性也在很大程度上依赖于互连网络的可靠性。 当要求计算机系统具有较高的安全性和稳定性时，要设计或选择多机系统的 一个重要参考因素就是容错。如果系统中出现故障设备，该系统仍然能够正常工 作，则称系统具有容错性。容错计算的经典方法是用冗余的硬件资源和软件资源 执行同一个计算任务，再将计算结果进行表决，得到正确的计算结果。这种技术 称为多模冗余，并已得到广泛的应用。但互连网络的规模很大，并且由于实际的 需要，还在不断的增大，因此，采用多模冗余技术实现互连网络容错通信将导致 系统资源和成本的急剧增长。 实现互连网络容错通信的一种切实可行的方法就是故障诊断，其基本思想是 首先定位网络中的故障结点和故障链路，并修理这些故障设备或者替换为非故障 设备。在故障诊断发展的过程中，人们根据故障定位的范围将故障诊断分为以下 四类： ① 门级故障诊断：识别发生故障的门电路。 ② 芯片级故障诊断：识别发生故障的芯片。 ③ 子系统故障诊断：识别发生故障的功能模块。 ④ 系统级故障诊断：识别发生故障的处理器或通信链路。 故障诊断最初只局限于单个元器件的故障或无故障状态的检测，但随着系统 规模的不断扩大和大规模集成电路（VLSI）的不断快速发展，构成计算机和数字 设备的基本组件——芯片的功能越来越强大，而芯片的体积和价格都呈下降之势。 系统级故障诊断将故障定位在系统级，仅考虑系统中的处理器单元和通信链路， 不涉及到处理器内部的芯片或电路，这样就大大降低了故障诊断的复杂性。系统 级故障诊断通过相互测试、诊断，可确定系统中的故障设备，由于这个此方法通