摘要：条件诊断性综述

2021-05-17

西华大学学报（自然科学版） 2021年3期

（西华大学计算机与软件工程学院，四川成都 610039）

1 研究意义

2019 年6 月在德国法兰克福举行的第34 届国际超级计算大会上，国际组织“TOP500”公布了最新一期全球超级计算机500 强榜单，中国的神威·太湖之光和天河二号继续名列第三和第四位，中国共有219 台超级计算机上榜，上榜数量位列第一，美国和日本分别以116 台和29 台超级计算机上榜，上榜数量分别位列第二、第三，这意味着中国超级计算机的发展已处于世界领先水平[1]。超级计算机能为能源、医药、飞机制造、航空航天、国家安全、娱乐业等广泛领域提供高性能计算服务，从而提升国家的科研实力和综合国力，增强国家的竞争力，对国家安全、高科技发展、经济和社会发展具有举足轻重的意义。

《国家中长期科技发展规划纲要（2006—2020）》明确把“高效能可信计算机”和“下一代网络关键技术与服务”列为重点领域“信息产业及现代服务业”的优先主题，把研制高性能、高可信计算机和高性能的核心网络设备与传输设备、接入设备作为信息产业的战略重点。超级计算是在超级计算机上实现的并行计算，通常超级计算、高性能计算、并行计算三者不加区分。并行计算是提高计算机系统计算速度和处理能力的一种有效手段，其基本思想是将较大规模的任务分解为多个较小规模的子任务，并分配给不同的处理器，各个处理器之间相互协同、并行地执行子任务，从而达到加快求解问题的目的。在并行计算机的计算过程中，各个子任务会分配给不同处理器进行处理，处理器之间需要相互通信来进行数据交换，所需的通信时间与处理时间不可忽视。因此，各处理器之间按照一定方式相互连接所形成的互连网络的容错性和诊断性成为衡量并行计算机系统性能的重要指标。网络的结构性质直接反映了系统的性质，对网络结构深层次地进行故障诊断性分析，不断获得新的诊断性理论与方法，有利于“高效能可信计算”的实现和“下一代网络关键技术与服务”的突破。

在高性能计算机的发展中，超大规模并行处理已成为主流体系结构。随着超大规模集成技术和微电子技术的飞速发展，单个处理器的性能不断提高、体积不断缩小，超大规模并行处理系统可以集成成千上万个处理器，同时为了满足用户的高可用性需求，系统的内部结构也变得越来越复杂，因此，系统呈现出大规模性、极度复杂性、异构性等特点。

互连网络有效地实现了处理器之间的通信，它已渗透到社会生活的各个领域。随着系统中处理器数目的急剧增加，处理器出现故障的概率不断增大。当具有大量处理器的系统（多计算机系统）发生故障时，系统难以判断处理器故障类型、位置和原因，易出现诊断精度和诊断速度低下、误诊、漏诊等现象，降低了系统的服务质量。金融、证券、军事、航空航天等国家级重点行业，对系统的可靠性和可用性要求极高，一旦系统出现故障，势必会带来不可估量的损失。因此，对网络进行多故障诊断性分析，并构建高效的多故障诊断算法迫在眉睫。由于网络中大量故障结点呈随机分布特性，因此本文从子网络性质、条件故障诊断度和条件故障诊断策略设计3 方面研究网络的多故障诊断性。

2 互连网络的故障诊断性的研究现状

当多计算机系统出现故障处理器时，计算机在进行信息存储、信息处理、信息传输过程中出错的可能性增大。为了保证系统的高可用性，一种诊断故障处理器或故障部件（结点）的有效方式是借助多计算机系统强大的计算能力和通信能力，获取结点有无故障的状态信息，即症候，然后再对其进行分析，确定故障结点。研究者们基于测试途径和比较途径这2 种获取症候的有效方式，提出了许多不同的诊断模型，其中基于测试途径的诊断模型有PMC 模型、BGM 模型等，基于比较途径的诊断模型有Malek 模型、Chwa-Hakimi 模型、Maeng-Malek模型、比较模型等。在这些诊断模型中，PMC 模型和比较模型是2 类经典的诊断模型。基于这2 类模型，学者们对不同互连网络的故障诊断性进行了研究，获得了大量的研究成果。下面从（强）诊断度、条件诊断度、g-好邻居条件诊断度、g-额外条件诊断度、诊断算法和二进制递归网络6 方面介绍网络故障诊断性领域的研究现状和存在的问题。

2.1 （强）诊断度和条件诊断度研究现状

基于PMC 模型和比较模型，研究者们假设系统中处理器相邻结点可以同时出现故障，对系统的诊断度进行了大量的研究。Song 等[2]运用图分层的方法，研究了煎饼网络的诊断度。Lin 等[3]通过对无三角形网络的拓扑结构性质的研究，获得了它的诊断度。Li 等[4]研究了多网格超立方体网络的诊断度。可见，对于网络诊断度的研究主要针对的是规则网络，不规则网络结构的诊断度还未形成统一的研究方法。

这些系统诊断度都不会超过系统的最小顶点度，系统诊断能力极其有限，究其原因在于这种诊断度研究的前提假设是未考虑系统中处理器故障出现具有不同概率的情况。在多计算机系统中，处理器出现故障的概率是相对独立的，而且各处理器出现故障的概率也不相同。因此，对于系统中每个处理器而言，它的所有邻接处理器都出现故障的概率相当小，几乎可以忽略不计。基于这样的考虑，Lai 等[5]提出了系统的强诊断和条件故障诊断的概念，并运用图论方法在PMC 模型下确定了匹配符合网络和超立方体的条件故障诊断度，这种条件诊断度的提出增强了多处理器系统的诊断能力。强诊断度和条件诊断度的提出，提升了系统的故障诊断能力，开启了大量其他网络的强诊断度和条件诊断度研究。

随后，在PMC 模型和比较模型下，Hsieh 等[6]和Chang 等[7]确定了k元n立方体的条件诊断度；Yang[8 − 9]确定了平衡超立方体的条件诊断度；Li 等[10]和Li[11]研究了多网格超立方体光网络的条件故障诊断，获得了其强诊断度和条件诊断度；Lin 等[12]和Zhou 等[13]研究了洗牌立方体和分层立方体的强诊断度和条件诊断度；Guo 等[14]研究了环绕匹配符合网络的条件诊断度，运用该结果获得了k元n维立方体和递归循环图的条件诊断度。在PMC模型下，Lin 等[15]建立了正则图的3-额外连通度与条件诊断度之间的关系。在比较模型下，Lin 等[16]和Hao 等[17]利用额外连通度分析确定了正则图和对称差图网络的条件诊断度；Xu 等[18]研究了匹配符合网络的条件诊断度。这些条件诊断度的研究依然是针对规则网络结构，利用图结构性质获得的，未研究的规则网络和一般网络的条件诊断度仍然值得探索。

对于一般网络结构，在PMC 模型下，Cheng 等[19]获得了任意图的条件诊断度的一个紧的上界，并应用这个结果推导出了星图的条件诊断度；Stewart[20]提出了确定一类互连网络条件诊断度的方法，运用该方法可以直接确定超立方体、折叠立方体等立方体网络的条件诊断度。在比较模型和PMC 模型下，Zhu 等[21]研究了一类互连网路，包括BC 网络、折叠立方体、置换星图、超网格等的故障诊断性，建立了该网络的诊断度、强诊断度和条件诊断度之间的关系。科研者不仅研究规则网络结构的强诊断性和条件诊断性，还研究一般网络的强诊断性和条件诊断性，并试图用一种通用的模式来解决不同网络的故障诊断性；但是所提出的模式仅仅适用于带有限定条件的一般网络或者一类网络：因此，具有不同条件的一般网络和不同网络组成的一类网络的强诊断性和条件诊断性依然值得研究。

2.2 g-好邻居条件诊断度和g-额外条件诊断度研究现状

在多计算机系统中无故障结点的部分相邻结点同时出现故障的概率非常小，几乎可以忽略，基于这样的考虑，Peng 等[22]进一步延伸了条件诊断理论，假定任何无故障结点至少有g个无故障结点与之相邻，提出了g-好邻居条件诊断，并研究了超立方体在PMC 模型下的g-好邻居条件诊断度。g-好邻居条件诊断度极大地丰富了条件故障诊断的内容，在一定程度上提高了对给定系统的故障诊断能力。Wang 等[23]进一步研究了超立方体在比较模型下的g-好邻居条件诊断度。在PMC 模型和比较模型下，Yuan 等[24]和Yuan 等[25]通过对三元n维立方体和k元n维立方体的Rg-连通性[26]的研究，确定了它们的g-好邻居条件诊断度；Ren 等[27]确定了t-可诊断系统和完全图的g-好邻居条件诊断度；Ren 等[28]推导出了局部扭曲立方体的g-好邻居条件诊断度。Li 等[29]获得了星图网络的g-好邻居条件诊断度；对于(n,k)-星图网络，当1≤k≤n–1，1≤g≤n–k时，Xu 等[30]确定了该网络的g-好邻居条件诊断度。对于数据中心网络Dcell，Li 等[31]研究了该网络的g-好邻居条件诊断度。对于传递树生成的凯莱图，Wang 等[32]和Wang 等[33]确定了它的1-和2-好邻居条件诊断度。Wang 等[34]研究了交错群图的2-好邻居条件诊断度。可见，g-好邻居条件诊断度的研究主要是针对规则网络，对于一般网络和网络簇的研究极少。g-好邻居条件诊断度的研究还处在发展阶段，研究方法还有待完善，大量互连网络，如增广立方体、分层立方体、多网格超立方体等的g-好邻居条件诊断度亟待解决。因此，特定互连网络、一般网络和网络簇的g-好邻居条件诊断度是值得研究的问题。

考虑到多处理器中某个处理器的所有邻居结点都出现故障的可能性极小，Zhang 等[35]推广了条件诊断策略，假定系统出现故障后每个连通分支的结点数超过g，提出了g-额外条件诊断策略，并研究了超立方体的g-额外条件诊断度。随后，Xu 等[36]利用这一新的诊断策略研究了排列图网络的故障诊断，获得了排列图网络的1-、2-和3-额外条件诊断度；Wang 等[37]获得了冒泡排序星图网络的2-额外条件诊断度；Wang 等[34]研究了交错群图的2-额外条件诊断度。Ren 等[27]确定了t-可诊断系统和完全图的g-额外条件诊断度。Liu 等[38]在比较模型下，推导了超立方体和折叠立方体的g-额外条件诊断度。当前，g-额外条件诊断度的研究还处于发展阶段，未形成普遍适用的方法，大量网络结构的g-额外条件诊断度还有待确定。因此，特定互连网络、一般网络和网络簇的g-额外条件诊断度也是值得研究的问题。

2.3 诊断算法研究现状

近年来，研究人员针对常见的互连网络设计了大量的诊断算法。在PMC 模型下，Tsai[39]对N个结点的类立方体提出了时间复杂度为O(N)的悲观诊断算法；Zhu 等[40]运用图着色的方法，设计了一类适合于任何多处理器系统的故障诊断算法；Hsu 等[41]针对超网格结构提出了一个线性时间诊断算法，至多能够识别2n(k−1)−1个故障结点。在比较模型下，针对N个结点的类立方体，Ye 等[42]运用圈分解性质，提出了时间复杂度为O(N(log2N)2)的故障诊断算法，后来，Ye 等[43]运用深度优先算法找到最大分支，基于最大分支设计了一类时间复杂度为O(Nlog2N)的故障诊断算法；Liu 等[44]针对煎饼网络利用扩展星图和哈密尔顿路结构设计了一类线性时间算法。

当前，在比较模型下的故障诊断算法比在PMC 模型下的故障诊断算法少得多，原因在于前者要比后者故障诊断复杂得多，需要借助的图结构性质也较多。因此，在比较模型下设计高效的故障诊断算法还有待突破，同时针对特定互连网络或网络簇设计特定的故障诊断算法仍然是当前的研究热点。

2.4 二进制递归网络研究现状

互连网络是由若干处理器按照一定互连方式相互连接形成的网络结构。在并行处理器系统中，互连网络作为其主干网络，它的性能直接决定着整个系统性能的好坏。互连网络的拓扑结构性质和多故障诊断性是决定互连网络性能的2 个重要因素。二进制递归网络作为一类具有良好拓扑性质和网络参数的互连网络模型，包含了超立方体、交叉立方体、扭曲立方体等，是一类具有广阔应用前景的超级计算机网络和数据中心网络结构。超立方体因其具有正则性、对称性、较小的网络直径、强连通性、对称性以及结构递归性等众多优良的网络特性，成为实际应用最广泛、理论研究最多的一种网络拓扑。许多商业公司的科研人员基于超立方体结构，先后研制了CM-2、nCube、Cosmic Cube、SGI Origin 2000 等并行计算机系统，并在神经网络、P2P 网络、覆盖网络等领域进行了深入的应用研究。为既能保持超立方体这些良好特性，又能减小网络的通信延迟(即降低网络直径)，人们对超立方体进行了各种改造，得到了许多变体。在分析比较了大量超立方体的变体之后，发现某些变体和超立方体一样，都具有相同顶点数、相同的边数、相同的正则性和严格的递归性，即每个n维的网络都是由2 个n–1 维的网络按照某种特定关系组合而成的。Sun 等[45]将超立方体的这类变体归纳为一类二进制递归网络（binary recursive network,BR），用0 和1 组成的二进制字符串对结点进行标记，并使用互连代数对其进行了递归定义。

这样，超立方体的不同变体，如扭曲立方体、局部扭曲立方体、折叠立方体、交叉立方体、Möbius 立方体、增广立方体、加强立方体等二进制立方形递归网络实质上是二进制递归网络的一个特殊子类，因此对二进制递归网络成立的拓扑性质对二进制立方形递归网络同样成立，但反之不然。一些文献中提到的类超立方体网络、BC 网络、匹配符合网络等也可看成是二进制递归网络的一些特殊形式。二进制递归网络子类的不同故障诊断度和诊断算法已经有大量研究成果[45 − 46]，但二进制递归网络在直径、泛圈性、哈密尔顿性等方面的研究成果较少。因此，二进制递归网络的（强）诊断度、条件诊断度、g-好邻居条件诊断度、g-额外条件诊断度、条件诊断策略和诊断算法的研究仍然是当前的热点研究问题。

3 摘要：条件诊断

二进制递归网络作为一类新型的网络族，包含了立方形递归网络，如超立方体、交叉立方体、扭曲立方体等。本文将二进制递归网络中故障结点数量小于连通度的故障模式称为少故障模式，故障结点数量大于连通度的故障模式称为随机多故障模式。立方形递归网络作为二进制递归网络的特殊子类，不等同于二进制递归网络。于是，二进制递归网络的多故障条件诊断性理论与方法可以直接应用于立方体递归网络的多故障条件诊断性分析，极大地减少了分别研究每个立方体递归网络的结构性质和多故障条件诊断性的代价。本文对摘要：条件诊断的阐述将从多故障条件诊断度研究、多故障条件诊断策略构建和多故障条件诊断算法设计3 方面展开，各部分的研究内容及相互关系如图1 所示。

图 1 主要研究内容及相互关系

3.1 研究多故障条件诊断度

1）g-好邻居条件诊断度。与诊断度、强诊断度和条件诊断度相比，g-好邻居条件诊断度丰富了网络故障诊断的内容，提高了系统多故障诊断能力。通过研究二进制递归网络的g-好邻居条件故障点割集规模和带条件子图规模，建立分析二进制递归网络的g-好邻居条件诊断度的解析表达式，可为在二进制递归网络上设计自主高效的g-好邻居条件诊断算法做必要的理论准备。

2）g-额外条件故障诊断度。g-额外条件故障诊断是一类相当新的故障诊断策略。它充分考虑了无故障分支的拓扑性质，丰富了网络故障诊断的内容。与（强）诊断度、条件诊断度和g-好邻居条件诊断度相比，它提高了系统多故障诊断能力。通过研究二进制递归网络的g-额外条件故障点割集规模、无故障分支规模等，建立确定g-额外条件诊断度的解析表达式，可为在二进制递归网络上设计自主高效的g-额外条件故障诊断算法做必要的理论准备。

3.2 构建多故障条件诊断策略

1）g-条件诊断策略构建。在g-好邻居条件诊断策略中，系统中的每个无故障结点至少有g个好邻居结点，在条件诊断策略中，系统中的每个处理器的邻居结点不会同时出现故障，但在实际系统中，故障结点也可能至少存在g个无故障邻居结点。为了保证系统的高性能，这就需要系统具有更高的可诊断性，因此可以基于g-好邻居条件诊断策略和条件诊断策略，假定每个结点至少有g个好邻居结点，提出g-条件诊断策略。由于系统中每个结点出现故障的概率是不同的，每个结点的邻居结点都出现故障的概率非常小，几乎可以忽略，因此每个点至少有g个好邻居结点的假设是合理的。可见，g-条件诊断是g-好邻居条件诊断和条件诊断的扩展，当g=1 时，1-条件诊断度即为条件诊断度。通过对g-条件故障点割集规模和带条件子图规模的研究，确定二进制递归网络的g-条件诊断度的一般方法，可为在二进制递归网络上设计自主高效的g-条件诊断算法做必要的理论准备。

2）跨步条件诊断策略构建。在二进制递归网络中，超立方体网络结构规则、简单易于实现，但网络直径较大、连通度较小，随着网络规模增长，其诊断性减弱。虽然可用扭曲立方体、折叠立方体、交叉立方体、Möbius 立方体、增广立方体、加强立方体等二进制立方形递归网络来克服超立方体的缺点，但是传统故障诊断都是基于网络结构直接建立的；因此，不同故障诊断能力有限，诊断性能提升不够明显，改进网络结构来提升网络的故障诊断能力，其性价比也不高。为此，可结合网络结构和网络通信模式提出新的故障诊断策略来提升网络的故障诊断能力。

网络模型结构中的每个处理器由任务处理器和通信处理器2 部分组成。通常任务处理器比通信处理器发生故障的可能性大得多，因此可以假设：网络中通信处理器故障不会出现，处理器故障是由任务处理器出现故障造成的；网络拓扑结构中不相邻的2 个处理器之间也能进行通信，相互进行测试。与传统诊断策略相比，网络拓扑结构中处理器之间的相互测试实现了“跨步”，本文称为跨步诊断策略。在这种策略下，可以假设网络中处理器故障或无故障状态满足某些条件，便可定义不同的跨步条件诊断策略。为了便于度量跨步条件诊断性，可以基于Hamming 距离在二进制递归网络结点间通过添加新边的方式建立二进制递归网络的通信图，基于二进制递归网络的通信图研究二进制递归网络的跨步条件诊断性。

3.3 设计多故障诊断算法

根据二进制递归网络的最小g-好邻居条件点割集规模、g-额外条件点割集规模、子图规模等拓扑结构性质，以及g-好邻居、g-额外和g-条件诊断度，设计g-好邻居条件诊断算法、g-额外条件诊断算法和g-条件诊断算法；基于二进制递归网络的通信图，运用以上条件诊断算法的设计方法设计跨步条件诊断算法，实现二进制递归网络在多故障模式下的故障结点定位。分析这些诊断算法的复杂性与正确性，保证算法的可行性与高效性。