多计算机系统为人类实现高性能计算、大容量分布式信息存储和传输提供了强大的工具,多机系统的广泛使用已经成为当代信息社会的一个重要标志。随着系统规模的日益扩大,系统中出现故障的可能性也随之增大。因此,如何维持系统的高可靠性和可用性就成为一个迫切需要解决的问题。提高系统可靠性的一个主要手段就是及时诊断出系统中发生故障的结点机和通信链路,以便于维护人员能够尽快修复出现故障的部分,恢复系统的正常工作状态。系统级故障诊断作为故障诊断和定位的一个强有力工具,在容错领域得到了广泛的应用。其基本思想是充分利用系统中各个独立结点机的通信、处理能力,让它们相互测试,通过对测试结果进行综合分析,得出诊断结论。这种方法不必使用专用设备进行测试,在不增加系统额外成本的条件下就可以实现系统的快速自诊断,具有极高的应用价值。在系统级故障诊断众多的研究课题中,最核心的是故障诊断问题,即根据结点机相互测试的结果(症候),设计有效的诊断算法来识别系统中的故障。本文的研究工作主要就是围绕这一问题展开的。具体而言,本文研究了多计算机系统在不同测试模型和诊断策略下的故障诊断问题,并取得了下列结果:1.提出了广义立方体网络的t/k (k = 3)-故障诊断算法与传统的精确诊断和悲观诊断策略相比,t/k (k≥2)诊断策略在允许少量(不超过k个)无故障结点被误诊断为故障的代价下,大幅度地提高了系统的自诊断能力。广义立方体网络是一类规则互连网络拓扑结构的总称,它包括了超立方体及其多种变形立方体结构。近年来,人们研究了广义立方体的t/k-诊断度,证明了一个n维的广义立方体当满足条件k≤n + 1,t = (k + 1)n– (k + 1) (k + 2)/2 + 1时是t/k-可诊断的,然而目前尚无有效的t/k (k≥2)诊断算法。在PMC模型下,本文首次提出了广义立方体网络的t/k (k = 3)故障诊断算法,该算法的时间复杂度为O(Nlog2N),其中N = 2n表示结点总数。这项研究成果对研究其它类型的t/k诊断算法,以及把t/k诊断推向实用具有一定的理论意义。2.提出了t-可诊断系统的人工免疫诊断算法人工免疫系统是一类基于生物免疫系统的功能、原理、基本特征及相关免疫学说建立的用于解决各种复杂问题的计算系统。通过分析生物免疫系统中抗体与抗原之间的关系,我们定义了一个亲合度函数来评估由潜在故障集产生的症候(抗体)与输入症候(抗原)之间的相似程度,并基于克隆选择原理提出了一个t-可诊断系统的人工免疫诊断算法。理论分析和计算机仿真实验证实了该算法的有效性。3.提出了t-可诊断系统的群体智能诊断算法群体智能是人们受到自然界中群居生物群体行为的启发而提出的一种智能计算或优化的方法。群体智能利用群体优势,在没有集中控制,不提供全局模型的前提下,为寻找复杂问题解决方案提供了新的思路,受到国际智能计算研究领域学者的广泛关注。本文中,我们借助群体智能方法研究了三个不同的测试模型(PMC模型,对称比较模型和非对称比较模型)下的系统级故障诊断问题。通过引入蚂蚁寻找食物时所释放的“信息素”的概念评估了潜在症候与实际症候的相似度,并提出了针对一般的t-可诊断系统的群体智能诊断算法。大量仿真实验的结果证明了该算法能够在较短的时间内正确地识别出系统中的故障结点,具有一定的实用价值。4.在MM*模型下分别针对局部扭曲立方体和M?bius立方体提出了两个快速故障诊断算法MM*模型是一种非常实用的比较模型,自被提出以来受到了学者们的极大关注。局部扭曲立方体和M?bius立方体是两类常用的超立方体变形结构,具有许多优良的拓扑性质。在MM*模型下,人们已经知道n维局部扭曲立方体和M?bius立方体的诊断度为n,然而,还没有针对这两类特殊结构的高效率故障诊断算法。本文中,我们提出了局部扭曲立方体和M?bius立方体在MM*模型下的快速故障诊断算法,其时间复杂度均为O(N log 22N)。就时间复杂度而言,该算法与经典的Sengupta-Dahbura算法(其时间复杂度为O(N5) )相比具有显著的优越性。综上所述,本文研究了多计算机系统的系统级故障诊断问题,并提出了若干高效率的故障诊断算法。理论分析和大量计算机仿真实验证实了这些算法的正确性和有效性。