二进制递归网络的随机多故障条件诊断性分析

With the increasing size of multicomputers, the possibility of the presence of faulty processors in such systems is becoming increasingly large, leading to a dramatic drop in their reliability. For the purpose of ensuring that such a system can work properly in the presence of failures, it is essential to investigate the conditional diagnosability of the interconnection network. As an important generalization of hypercube, the Binary Recursive Network (BR network) is regular in structure and easy to be split, which has become a popular network topology both in theoretical research and practical application. This project addresses the conditional diagnosability of the BR network under the random multi-fault mode that the number of faulty nodes is larger than the connectivity of the network. The major research contents include: (1) establishing the analytic expressions of the g-good-neighbor conditional diagnosability and g-extra conditional diagnosability respectively; (2) proposing the g-conditional diagnosis strategy, and building the analytic expression of the g-conditional diagnosability; (3) bringing up the step conditional diagnosis strategy based on the network communication mode, and deriving the analytic expressions of the diverse step conditional diagnosabilities; (4) designing different efficient multi-fault diagnosis algorithms according to topological structure properties and different multi-fault conditional diagnosability. The expected results will greatly enrich and develop the fault diagnosis theories and algorithms, as well as provide theoretical guidelines and technical supports for the development of trusted high-performance computer in China.

随着并行计算系统中处理器数目的快速增加，系统中出现故障处理器的可能性也在急剧增大，这极大地降低了系统的可靠性。为了保证系统在某些结点出现故障时仍然能够正常工作，非常有必要研究互连网络的条件诊断性。二进制递归网络（BR网络）具有结构规则、易于分割等优点，是理论研究和实际应用中颇受欢迎的网络结构。本项目在BR网络的故障结点数大于连通度的随机多故障模式下研究BR网络的条件诊断性，主要研究内容包括：（1）建立BR网络的g-好邻居条件诊断度和g-额外条件诊断度的解析表达式；（2）提出g-条件诊断策略，建立g-条件诊断度的解析表达式；（3）基于网络通信模式，提出跨步条件诊断策略，建立不同跨步条件诊断度的解析表达式；（4）基于拓扑结构性质和不同多故障条件诊断度,设计高效的多故障诊断算法。预期研究成果能够丰富和发展互连网络故障诊断理论与算法，为我国高性能可信计算机的发展提供理论依据和技术支持。

随着并行计算系统中处理器数目的快速增加，系统中出现故障处理器的可能性也在急剧增大。为了保证二进制递归网络（BR网络）在某些结点出现故障时仍然能够正常工作，本项目在BR网络的故障结点数大于连通度的随机多故障模式下研究BR网络的条件诊断性，主要研究内容包括：（1）建立BR网络的g-好邻居条件诊断度和g-额外条件诊断度的解析表达式；（2）提出g-条件诊断策略，建立g-条件诊断度的解析表达式；（3）基于网络通信模式，提出跨步条件诊断策略，建立不同跨步条件诊断度的解析表达式；（4）基于拓扑结构性质和不同多故障条件诊断度,设计高效的多故障诊断算法。.重要结果体现在：.(1) 建立了典型二进制递归网络在PMC模型下的g-好邻居条件诊断度的解析表达式。对于超网格光互连网络，利用超网格光互连网络的g-好邻居条件故障点割集和顶点度至少为g的子图顶点集的规模，构造性地证明了超网格光互连网络在PMC模型下的g-好邻居条件诊断度。.(2)建立了典型二进制递归网络在比较模型下的g-好邻居条件诊断度的解析表达式。通过探讨超网格光互连网络不同结点的邻居结点规模、特殊顶点集的规模估计和拓扑结构性质，构造性地证明了超网格光互连网络在比较模型下的g-好邻居条件诊断度。.(3)提出了r-跨步诊断策略，提升了二进制递归网络的诊断能力。对于超立方体网络，相邻处理器之间通信扩展成了Hamming距离不超过r的处理器之间可以实现通信，相互进行测试，传统的相互测试扩展成了“跨步”测试，这种测试方式能够在光网络的通信模式中实现。定义了r-通信图、r-直径、r-连通度等概念，研究了超立方体网络的这些新的拓扑结构性质，从而获得超立方体网络的r-跨步诊断性。.(4)基于典型二进制递归网络的拓扑结构性质和不同多故障诊断度，设计了不同的多故障诊断算法。.(5)项目共计发表学术论文23篇，其中SCI检索15篇，EI检索5篇，申请专利4项(已公开)，软件著作权1项。