研究背景 随着计算机通讯技术的繁荣发展，多处理器系统的规模（处理器数量）也在不断增长，不可避免地会有一些处理器发生故障，因此，处理器的故障诊断问题对系统运行的可靠性尤为重要。系统级故障诊断分为两类：确定性故障诊断和不确定性故障诊断。确定性故障诊断总是可以正确并且完全的执行诊断任务，也就是说，无故障处理器通过系统测试可以完全诊断出被测试者的状态。作为不确定性诊断的一种，本文所研究的概率性故障诊断，是假定系统中的每个处理器都有一定概率发生故障，因而只需保证诊断任务高概率地被完全正确的执行即可，这极大地减少了系统的损失，也更符合现实环境。因此，用概率的方法来解决大规模多处理器系统的故障诊断问题对分析系统可靠性有一定价值。

目的 我们以具有一般性的d-正则d-连通图G为研究对象，旨在解决这类图的概率故障诊断问题。具体地，根据系统中任意结点发生故障概率的离散性与连续性，分别研究了此类图的局部概率故障诊断与全局概率故障诊断。此问题的研究动机：2019年，文献¹(1 Probabilistic diagnosis of clustered faults for hypercube-based multiprocessor system. Theor. Comput. Sci., 2019, 793: 113-131.) 针对围长为4的特殊图超立方体给出了阈值为3的概率故障诊断研究。然而，对于一般正则图在阈值为3的概率故障诊断方面还未有人涉及，我们考虑在围长大于等于6的一般正则图上建立阈值为3的概率故障诊断算法，这种方法适用于一类图，如星图、煎饼图及燃烧煎饼图等，结果更具一般性。

方法 首先，针对图G给出了阈值为3的局部故障诊断算法，该算法的主要思想是采用广度优先搜索策略，结合断片（faction）的定义及性质，以确定能够正确诊断出断片中所有结点的状态。进一步，通过反证法证明了该算法的正确性并证明了其时间复杂度是多项式级别的。基于此算法，结合概率PMC模型，我们按照结点的状态及与其关联的匹配边数分为8类进行讨论，证明了在离散状态下图G中任意结点故障的概率为常数时，此类正则图中结点被正确诊断的概率。其次，运用拉普拉斯变换，将离散状态下单个结点故障的概率转换为连续随机变量，并基于韦伯故障分布和卡方故障分布证明了此类正则图在连续随机状态下所有结点都能够被正确诊断的概率。

结果 （1）对于d-正则d-连通图的局部故障诊断方面，假设任意结点无故障的概率为常数p，按照与结点a相邻的匹配边数不同分以下8种情况，那么无故障结点a被正确诊断的概率为P_c(a^ + ) = 1 - \sum\nolimits_i = 1^8 P_w^i (a^ + ) （如下表1），故障结点a被正确诊断的概率为P_c(a^ - ) = \sum\nolimits_i = 1^8 P_c^i (a^ - ) （如下表2）。

表1 八种不同故障机群模式下无故障结点a被误诊的概率
故障机群模式	a 无故障结点被误诊的概率
Fig. 2(a)	P_w^1(a^ + )\text = (1 - p)^d\gamma ^d
Fig. 3(a)	P_w^2(a^ + )\text = dp(1 - p)^2d - 2\gamma ^2d - 2
Fig. 4(a)	P_w^3(a^ + )\text = d(1 - \gamma )\gamma ^d - 1\theta ^d - 1(1 - p)^d
Fig. 5(a)	P_w^4(a^ + ) \text = d(d - 1)p(1 -p)^2d - 2\gamma ^2d - 3 p(1 -p)^d - 2 \gamma ^d - 1 +\theta ^d - 1(1 - \gamma )
Fig. 6(a)	P_w^5(a^ + )\text = d(d\; -1)(1\; - \gamma )\gamma ^d - 1\theta ^d - 2(1 - p)^d\text + 1 p(1 - p)^d - 2 (1 - \gamma )\gamma ^d - 1 + \theta ^d - 1\beta
Fig. 7(a)	P_w^6(a^ + )\text = \left( \begingathered d \\ 2 \\ \endgathered \right)p^2(1 - p)^3d - 4\gamma ^3d - 4
Fig.8(a)	P_w^7(a^ + )\text = \left( \begingathered d \\ 2 \\ \endgathered \right)p(1 - \gamma )(1 - p)^2d - 2\gamma ^2d - 3\theta ^d - 1
Fig. 9(a)	P_w^8(a^ + )\text = \left( \begingathered d \\ 2 \\ \endgathered \right)\gamma ^d - 2(1 - \gamma )^2(1 - p)^d\theta ^2d - 2

表2 八种不同故障机群模式下故障结点a被正确诊断的概率
故障机群模式	故障结点a被正确诊断的概率
Fig. 2(b)	P_c^1(a^ - )\text = \theta ^d
Fig. 3(b)	P_c^2(a^ - )\text = d(1 - \gamma )\gamma ^d - 1p(1 - p)^d - 1\theta ^d - 1
Fig. 4(b)	P_c^3(a^ - )\text = d(1 - p)\beta \theta ^2d - 2
Fig. 5(b)	P_c^4(a^ - )\text = d(d - 1)p(1 - p)^d - 1(1 \;-\; \gamma )\gamma ^d - 2\theta ^d - 1p(1 - p)^d - 2\gamma ^d - 1 + (1 - \gamma )\theta ^d - 1
Fig. 6(b)	P_c^5(a^ - )\text = \;d(d\; - 1)(1 - \;p)^2\beta \theta ^2d - 3p(1 - p)^d - 2 (1 - \gamma ) \gamma ^d - 1 + \theta ^d - 1
Fig. 7(b)	P_c^6(a^ - )\text = \left( \begingathered d \\ 2 \\ \endgathered \right)\gamma ^2d - 2(1 - \gamma )^2p^2(1 - p)^2d - 2\theta ^d - 2
Fig. 8(b)	P_c^7(a^ - )\text = \left( \begingathered d \\ 2 \\ \endgathered \right)\beta \gamma ^d - 1(1 - \gamma )p(1 - p)^d\theta ^2d - 3
Fig. 9(b)	P_c^8(a^ - )\text = \left( \begingathered d \\ 2 \\ \endgathered \right)\beta ^2(1 - p)^2\theta ^3d - 4

（2）对于d-正则d-连通图的全局故障诊断方面，假设任意结点无故障的概率p为随机变量，表示为 p = e^ - m 。运用拉普拉斯变换L(s)=\int_0^\infty e^ - smf(m) dm (s \geqslant 0 )可得：Y = E(p) = \int_0^\infty e^ - mf(m) dm\text = L(1) ，Y=1–F。其中，Y表示G中所有被诊断为无故障结点的数学期望，F表示G中所有被诊断为故障结点的数学期望。另外，Y_c 表示无故障结点被正确诊断的数学期望，F_c 表示故障结点被正确诊断的数学期望。（2.1）在韦伯分布下，d-正则d-连通图G中的所有结点被正确诊断的概率为：\fracY_cY = 1 + \sum\limits_i = 0^3d - 2 w_i\frac\mu + 1\mu + i + 1, \fracF_cF = \frac(1 - k)\mu + 11 + \mu \Bigg\hat w_0 + \sum\limits_i = 1^3d - 2 (\hat w_i - \hat w_i + 1)\frack\mu \mu + i -\hat w_3d - 2\frack\mu \mu + 3d - 1\Bigg , 其中， \lambda 为韦伯分布的规模系数，m为韦伯分布的随机变量， \mu \text = m^k - 1/\lambda ^k 。当参数 k\to 0 ， \hat w_0 \to 1 ，d \to \infty 时，\dfracY_cY \to 1 ，dfracF_cF \to 1 。（2.2）在卡方分布下，d-正则d-连通图G中的所有结点被正确诊断的概率为：\fracY_cY = 1 + \sum\limits_i = 0^3d - 2 w_i\Bigg\frac1\text + \lambda \text/\sigma 1\text + (i + 1)\lambda \text/\sigma \Bigg^ - \sigma , \fracF_cF = \frac11 - (1\text + \lambda \text/\sigma )^ - \sigma \Bigg\hat w_0 + \sum\limits_i = 1^3d - 2 (\hat w_i - \hat w_i + 1)(1 + i\lambda /\sigma )^ - \sigma - \hat w_3d - 2(1 + (3d - 1)\lambda /\sigma )^ - \sigma \Bigg 其中，\sigma \text=k/2 为卡方分布的机群系数，k为卡方分布的自由度， \lambda \text=2\sigma 为随机变量m的平均值。当参数 \widehatw_0\to 1 ，d\to \infty 时，\fracY_cY \to 1 ，\fracF_cF \to 1 。综上，在韦伯故障分布与卡方故障分布下，此类d-正则d-连通图中的所有结点的状态都能被正确诊断的概率趋于1。

结论 概率性故障诊断由于其花费少、更贴近实际而受到大家的关注。本文将基于一般正则图的多处理器系统作为研究对象，建立了阈值为3的局部故障诊断算法，并通过反证法证明了此算法的正确性。在概率PMC模型下，使用此局部故障诊断算法评估了围长大于等于6（围长限制表明断片中任意两个不相邻结点之间的公共点数至多为1）的一般正则图中任意结点被正确诊断的概率。然而，关于阈值为3且围长小于6的网络，如类超立方网络、交错群网络、复合网络等，在概率故障诊断方面的研究还鲜少有人涉及，未来可考虑研究符合此特性的网络在概率故障诊断方面的研究，从而提供不同的角度分析网络的可靠性。此外，不同的阈值对故障诊断有一定影响（.若断片大小大于等于阈值，则此断片被诊断为一个真正的无故障分支，否则，此断片被诊断为故障），目前仅对较小的阈值进行研究，而更大阈值的意义在于断片中更多结点的状态将能够被确定性地诊断，因此，研究阈值的峰值也是值得思考的问题。