互连网络的非精确故障诊断与顺序故障诊断研究

It is well known that interconnection network is an important part of multiprocessor parallel computers and is the cooperation mechanism and the main mean of communication. Considering the low diagnostic capability of precise diagnosis, prerequisite conditions for conditional diagnosis and limited improvement in diagnostic capability, in order to improve the diagnostic capability of multiprocessor parallel computers greatly, and guarantee the system reliability, in this project, we try to study the imprecise diagnosis and sequential diagnosis of interconnection networks. By introducing the logical thinking of multi-objective optimization evolutionary algorithm, we design and optimize a traversal algorithm of interconnection networks topologies. After statistical analysis of calculating data, we dig up and prove some important related topological properties, and calculate a series of specific functions. Then, based on topological properties, combined with the characteristics of fault sets and so on, we construct the key characteristics of imprecise diagnosis and sequential diagnosis of interconnection networks. And then, study the diagnosabilities of imprecise diagnosis and sequential diagnosis of interconnection networks and extended the theory of sequence diagnosis. Finally, combining a variety of factors such as cost, topological properties, fault tolerance and various diagnosabilities, we map out an emergency diagnosis strategy for interconnect networks and carry out quantitative evaluation. The research results of this project will promote the application and popularization of interconnect networks in multiprocessor parallel computers.

互连网络作为系统内部的协同机制和主要的通信手段，是多处理器并行计算机的重要组成部分。为了进一步提高多处理器并行计算机的诊断能力，保障系统的可靠运行。针对互连网络精确故障诊断能力不足、条件故障诊断需要前提条件且诊断能力提高有限的现状。本项目以互连网络为研究对象，引入多目标优化进化算法的逻辑思维对互连网络拓扑结构遍历算法进行设计和优化，通过对遍历计算数据的统计分析，挖掘并证明相关拓扑性质，计算系列特定函数。进而，以拓扑性质为支撑，结合故障集合的性质特征等，构建起非精确故障诊断与顺序故障诊断的关键性特征，并展开互连网络的非精确故障诊断度与顺序故障诊断度研究和顺序故障诊断理论的拓展研究。最后，结合成本、拓扑性质、容错能力和各种诊断度等因素制定出互连网络的应急诊断策略，并进行定量评价。从而促进互连网络在多处理器并行计算机的应用和推广。

互连网络作为系统内部的协同机制和主要的通信手段，是多处理器并行计算机的重要组成部分。为了进一步提高多处理器并行计算机的诊断能力，保障系统的可靠运行。针对互连网络精确故障诊断能力不足、条件故障诊断需要前提条件且诊断能力提高有限的现状。本项目以互连网络为研究对象，引入多目标优化进化算法的逻辑思维对互连网络拓扑结构遍历算法进行设计和优化，通过对遍历计算数据的统计分析，挖掘并证明了相关拓扑性质，计算系列特定函数。进而，对互连网络连通度、诊断度以及它们之间的关联关系进行了综述研究，探索了互连网络的拓扑规则、连通性质、非精确故障诊断和顺序故障诊断研究的方法和理论。以拓扑性质为支撑，结合故障集合的性质特征，刻画出非精确故障诊断与顺序故障诊断的关键性特征，通过构建连通度与诊断度的关联关系的方式，度量出类超立方网络的t/k-诊断度和交换交叉立方网络的(t,k)-诊断度。提出了一种新的广义匹配组合网络，明晰了广义匹配组合网络的超连通度与条件诊断度之间的关系，利用这个关联关系，确定了系列互连网络的条件诊断度。结合交换超立方网络的连通度性质，确定了交换超立方网络在MM*模型下的条件诊断度。研究了同时出现边故障和结点故障的混合故障情况，确定了系列互连网络在混合故障情况下的诊断度，包括BC网络、星形图、折叠超立方网络等。提出了一种全新的Rg条件诊断度理论，度量出PMC模型下超立方网络的Rg条件诊断度，Rg条件诊断度扩展了条件诊断度的广度。最后，对互连网络的非精确故障诊断与顺序故障诊断结论进行了实验验证。本项目的研究有助于推进互连网络在多处理器并行计算机系统的广泛应用，保障并行计算机的可靠运行。