互连网络是实现多计算机系统中处理器之间相互通信的有效机制,系统的可靠性在很大程度上依赖于互连网络的可靠性,它是决定系统性能的重要因素之一。随着系统规模的扩大,系统部件出错的可能性也越来越大。为了得到系统的高可靠性和高可用性,系统级故障诊断是确定系统中故障处理器的一个有效方法。它是首先由相邻处理器之间通过相互测试而形成症候,进而根据症候来进行故障诊断的过程。本文主要致力于互联网络的系统级故障诊断研究。首先,介绍了系统级故障诊断领域的现实意义及其研究现状,并详细介绍了系统级故障诊断的相关概念和方法,以及几类经典的故障诊断模型和诊断策略。然后,介绍了几类经典的互连网络模型(交叉立方体、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图的结点数。