王 喜，张书奎

(1.苏州工业职业技术学院,江苏 苏州 215004；2.苏州大学计算机科学与技术学院,江苏 苏州 215006)

1 引言

多处理器互连网络(简称互连网络)是指由多个处理器按照一定规则相互连接而成的网络，目前越来越广泛地出现在计算机技术的相关研究与应用领域中。作为并行系统的基础，互连网络的性质直接决定了系统的性能。近年来，我国在基于并行系统的超级计算机领域有一系列的重大突破，特别地，由国防科技大学牵头研制，安装在国家超级计算天津中心的超级计算机——“天河三号”E级原型机，在最新的全球超级计算机TOP500榜单中蝉联冠军[1]。

由于大规模互连网络中有很多处理器，这就很难避免某些处理器出现故障，而这些故障处理器可能影响到整个互连网络的稳定性，从而导致整个网络瘫痪，造成极大的经济损失。一个互连网络的拓扑结构可用一个图来表示，其中处理器与处理器之间的通信链路可分别用顶点集和边集表示。为了确保互连网络可以正常运行，那么在顶点出现故障时，就应及时、准确地找出故障顶点并进行替换。系统能够找出故障顶点并进行替换的能力，称为系统的诊断性。系统的诊断度是一个系统中能够准确找出所有故障顶点的最大个数。若系统中出现的故障顶点的个数不超过其诊断度t时，则该系统能够确保所有的故障顶点都可被正确地诊断出来，那么系统是t-可诊断的[2]。

Preparata等[2]在给出系统级故障诊断概念的同时提出了一个经典诊断模型——PMC诊断模型，该模型是用3位作者姓名的首字母来命名的。……