点边混合故障情形下多处理器系统的可靠性分析和故障诊断

Reliability analysis and fault diagnosis for high performance fault tolerant systems are important research areas in the study of high performance computing. Among them, the reliability, fault diagnosis capability analysis and diagnosis algorithm design for multiprocessor systems is a hot zone. In the past studies, it is assumed that only node failures or link failures exist in the system. But in practice, node failures and link failures may co-exist. In this project, we will study the reliability and fault diagnosis problem for multiprocessor systems under hybrid failure assumptions. In the reliability analysis study: Based on the probability analysis, we will introduce a better measure for the reliability of multiprocessor systems: the reliability number function. Then we will investigate the reliability number function for some well-known interconnection networks and general graphs. For the fault diagnosis study: we will generalize the traditional PMC and comparson model to adapt hybrid failure circumstances. Then the fault diagnosis capability of several networks will be explored. Also, we will design diagnosis algorithm for these networks. Finally, the diagnosis algorithm design for general graphs under hybrid failures will be studied.

高性能容错计算系统的可靠性分析和故障诊断是高性能计算的重要研究领域，其中针对多处理器系统的可靠性、故障诊断能力参数的确定及其诊断算法的设计是可靠性和故障诊断研究的一个热点。然而以往的研究中，往往假设系统只存在节点故障或者只存在线路故障。而在实际中，节点故障和线路故障是可能同时并存的。在本项目中，我们要研究点边混合故障下的多处理器系统的可靠性分析和故障诊断问题。在可靠性度量方面：我们通过概率分析引入多处理器系统可靠性的更好的度量参数：可靠度。然后我们将研究一些著名互连网络和一般图的的可靠度确定问题。在故障诊断研究方面：我们将首先推广经典的PMC模型和比较模型以适应点边混合故障的情形。然后研究确定几个著名网络拓扑结构的故障诊断能力的指标并设计其点边混合故障诊断算法，最后我们将研究一般图的点边混合故障诊断算法。

在该面上项目的资助下，我们针对当前系统级诊断理论中存在的一些问题，取得了一些关键的科研进展。使得系统级诊断理论真正有可能应用于通讯网络的故障诊断。. 研究进展一：在点边混合故障情形下， 引入了 PMC模型下混合故障诊断参数并研究了立方体网络的该参数。该研究开创了在PMC模型的基础上研究网络混合故障情形下故障诊断能力的研究领域，该论文发表在理论计算机科学并已经得到了很多同行的认可，而且有很多的后续研究。. 研究进展二： 在PMC模型的基础上建立了混合故障诊断模型 HPMC模型，该模型克服了 PMC模型下仅可以处理网络中存在节点故障情形的缺点。 HPMC模型可以处理系统中同时存在节点故障和连线故障情形下的故障诊断问题。我们建立了 HPMC模型的基本理论并研究了立方体网络在HPMC模型下的故障诊断能力。 HPMC模型的引入以及后续故障诊断算法及相关研究能够真正使得系统级诊断理论有可能应用于通讯网络的故障诊断问题。. 研究进展三: 在PMC模型的基础上提出了对称PMC模型并研究了立方体网络在对称PMC模型下的可诊断数, 设计了对称PMC模型下的 t可诊断系统的多项式时间故障诊断算法。对比经典的PMC模型下的Dahbura-Mason算法，该算法可以处理更广泛情形下的故障诊断问题并有更高的效率。 . 研究进展四：将组合理论中等周问题与互连网络可靠性问题联系起来，利用等周问题的结果确定互连网络的额外连通度等可靠性参数。我们通过立方体网络的等周问题的结果，确定了立方体网络的额外连通度，我们的结果是已知关于立方体网络额外联通度的最好的结果，而且我们的方法将组合理论和网络的可靠性评估问题联系了起来，有可能利用组合理论中等周问题的其他结果来得到网络可靠性研究的新的突破。. 研究进展五：引入了概率连通度、混合连通度的概念并研究了立方体网络的概率连通度和混合连通度。概率连通度是传统连通度的推广，比起目前主流研究的各种条件连通度，可以更好的衡量网络的可靠性。混合连通度可以衡量网络在混合故障情形下的可靠性，开辟了一个新的研究领域。