随着信息技术的高速发展,为了解决宇宙学、气象、流体力学、材料等重大科学应用领域的计算问题,大规模并行处理机向着高性能、大规模、多样性、多功能的方向发展。随之而来的一个问题就是系统的容错性和维护问题,特别是在应用于某些重要部门（如军事和金融）的多机系统中,故障的危害不仅可能涉及个人和生命财产,甚至可能关系国家和民族的安危。由于系统的规模越来越大,从中发现故障结点的工作也越来越繁重,花费也越来越高。随着芯片集成技术的提高,目前的处理结点一般都具备了一定的通信和处理能力,那么一个很自然的想法就是充分利用结点这些能力,让它们相互测试,然后再根据测试结果和拓扑结构等条件,最终得出正确的诊断结果,这就是系统级故障诊断的基本思想。这种方法不必使用专用设备测试,在不增加系统额外成本的情况下就可实现系统的快速自诊断。本文的工作就是研究如何采用系统级故障诊断的方法解决多机系统的故障诊断问题,主要围绕着增强超立方体的t/k-诊断度及诊断算法,局部扭立方体的t/k-诊断度,BC图的t/k-诊断算法,t-可诊断系统的遗传诊断算法等四方面展开,并分别得出了相应的结论。1.增强超立方体的t/k-诊断度（k≤2）及诊断算法。为了提高系统级故障诊断中的诊断度,人们以牺牲很小一部分结点不能正确诊断为代价,提出以t/k-诊断策略。增强超立方体是超立方体的一种变体,它在如直径、平均结点间距离、通信密度等方面均具有较好的性能。为了确认其诊断度,我们首先证明了当故障结点集|F| < 2n时,增强超立方体的最大连通分图的结点数≥2ⁿ– |F|– 1;当故障结点集|F| < 3n– 2时,增强超立方体的最大连通分图的结点数≥2ⁿ– |F|– 2。然后基于以上结论,证明了其t/2-诊断度为3n– 2,并给出了一个O（N log₂N）的t/k-诊断算法（k≤2）。目前,上述成果尚未文献报导。2.局部扭曲立方体的t/k-诊断度。局部扭曲立方体是一种新的的变形立方体结构,它具有很多很好拓扑特性。我们证明局部扭曲立方体与超立方体有相同的t/k-诊断度。该个结论也在最近的一篇文章中被得出,但是我们的采用的证明方法与其是完全不同的,从另一个侧面证明了这个重要的结论。3.BC图的t/k-诊断算法。BC图是包括了超立方体和交叉立方体、M?bius立方体、扭曲立方体、局部扭曲立方体等多种变形立方体的一类图。人们证明了BC图的t/k-诊断度,但是未给出相应的t/k-诊断算法。对于结点总数为N的n维BC图,本文首先证明了当故障结点集|F| < （n + 1）n– （n + 1）（ n + 2）/2 + 1时,BC图的最