论文部分内容阅读
超级计算机系统，也称多处理器并行系统，是衡量一个国家综合科技水平的重要指标，是一个国家的未来高科技发展的基础性平台，在航空航天、地球物理、生命信息、人工智能、工程计算等领域发挥着越来越重要的作用。在超级计算机系统中，处理器与处理器之间的相互连接关系可以用一个图来表示，顶点代表处理器，边代表处理器之间的连接，这样的图被称为是互连网络。互连网络是超级计算机系统中的一个重要组成部分，互连网络性能上的优劣在相当程度上会影响到整个超级计算机系统最终所能达到的性能极限。
随着超级计算机系统的快速发展，系统的规模在不断扩大，不可避免地要面对系统中的处理器或处理器之间的链路出现故障的情况，这就带来了如何确保系统高可靠性和高利用率的问题。互连网络故障诊断是解决这一问题的关键性容错技术之一。互连网络故障诊断技术无需对系统进行停机拆解操作，并在不额外增加系统硬件成本的条件下，利用处理器的计算能力及系统中的互连网络进行系统内部的故障自诊断，从而实现对系统内部故障点的识别，从而提高了系统的可靠性和利用率。因此，互连网络故障诊断研究是一个很有价值的课题。
本文将从精确故障诊断的角度对折叠超立方网络(F Qn，Folded Hypercube)、超彼得松网络(HP n, Hyper Petersen Network)、星型网络(Sn, Star Graph)、平衡超立方网络(BHn，Balanced Hypercube)、BC互连网络族(Ln, Bijection-Connected(BC)Networks)及匹配组合网络族(M C N s, Matching Composition Networks)等互连网络开展研究，分别研究了局部故障诊断策略、间歇性故障诊断策略、g-扩展条件诊断策略在相应互连网络上的故障诊断问题。本文的主要工作分成三个部分：
1.本文证明了折叠超立方网络、匹配组合网络族都具有很好的局部诊断能力，并基于互测策略提出了一种局部故障诊断方法，主要结论如下：
(1)分析了折叠超立方网络中一个顶点v与不同数量可用边相关联时，顶点v具有的局部故障诊断性，并证明了当FQn?S中每一个顶点至少与两条可用边相连，FQn?S中的每个顶点v的局部可诊断度等于顶点v在图FQn?S中的度，FQn?S具有强局部诊断性质。
(2)分析了所有相关联的边都为可用边的情况下，匹配组合网络族具有强局部诊断性质。此外，提供了一个充分条件用以验证存在不可用边条件下，匹配组合网络族在PMC模型下的强局部可诊断度，并将该方法推广到了n维BC互连网络Xn和超彼得森网络HPn。
(3)对类型I结构下的双向互测策略进行了详细的分析和理论证明，提出了基于类型I结构对顶点状态进行故障诊断的方法。
2.本文研究了超彼得松网络、BC互连网络族和星型网络的间歇性故障诊断度，主要结论如下：
(1)证明了在不存在不可用边条件下，n维超彼得森网络在PMC诊断模型下的间歇故障诊断性为n?1，且当min{deg(v)|v∈V(HPn)}=r，2≤r≤n时，一个n维的超彼得森网络HPn(n≥3)是(r?1)i可诊断。此外，还证明了n维的超彼得森网络在MM*比较诊断模型下的间歇故障诊断度为n?2。
(2)证明了当网络中存在不可用边条件下，BC互连网络族在PMC诊断模型下是(r?1)i可诊断，BC互连网络族在MM*比较诊断模型的间歇故障诊断度分别为n?2。
(3)利用最小邻居数的概念证明了星型网络在PMC诊断模型下的间歇故障诊断度为n?1。
3.本文研究了平衡超立方网络BHn在PMC诊断模型下的g-扩展条件诊断度，以及BC互连网络族在MM*比较诊断模型下的g-扩展条件诊断性质，得到了如下结论：
(1)当n≥3时，平衡超立方网络BHn在PMC诊断模型下的4-扩展条件诊断度为6n?4，5-扩展条件诊断度为6n?3。
(2)当n≥33，3≤g≤(n?1)/4时，F是Xn的一个g-扩展顶点子集，如果Xn?F中最多存在(n?1)/2个deg(v)=1的顶点，则BC互连网络族在MM*诊断模型下的g-扩展条件诊断度为etg(G)=(g+1)n?g?C2g。
随着超级计算机系统的快速发展，系统的规模在不断扩大，不可避免地要面对系统中的处理器或处理器之间的链路出现故障的情况，这就带来了如何确保系统高可靠性和高利用率的问题。互连网络故障诊断是解决这一问题的关键性容错技术之一。互连网络故障诊断技术无需对系统进行停机拆解操作，并在不额外增加系统硬件成本的条件下，利用处理器的计算能力及系统中的互连网络进行系统内部的故障自诊断，从而实现对系统内部故障点的识别，从而提高了系统的可靠性和利用率。因此，互连网络故障诊断研究是一个很有价值的课题。
本文将从精确故障诊断的角度对折叠超立方网络(F Qn，Folded Hypercube)、超彼得松网络(HP n, Hyper Petersen Network)、星型网络(Sn, Star Graph)、平衡超立方网络(BHn，Balanced Hypercube)、BC互连网络族(Ln, Bijection-Connected(BC)Networks)及匹配组合网络族(M C N s, Matching Composition Networks)等互连网络开展研究，分别研究了局部故障诊断策略、间歇性故障诊断策略、g-扩展条件诊断策略在相应互连网络上的故障诊断问题。本文的主要工作分成三个部分：
1.本文证明了折叠超立方网络、匹配组合网络族都具有很好的局部诊断能力，并基于互测策略提出了一种局部故障诊断方法，主要结论如下：
(1)分析了折叠超立方网络中一个顶点v与不同数量可用边相关联时，顶点v具有的局部故障诊断性，并证明了当FQn?S中每一个顶点至少与两条可用边相连，FQn?S中的每个顶点v的局部可诊断度等于顶点v在图FQn?S中的度，FQn?S具有强局部诊断性质。
(2)分析了所有相关联的边都为可用边的情况下，匹配组合网络族具有强局部诊断性质。此外，提供了一个充分条件用以验证存在不可用边条件下，匹配组合网络族在PMC模型下的强局部可诊断度，并将该方法推广到了n维BC互连网络Xn和超彼得森网络HPn。
(3)对类型I结构下的双向互测策略进行了详细的分析和理论证明，提出了基于类型I结构对顶点状态进行故障诊断的方法。
2.本文研究了超彼得松网络、BC互连网络族和星型网络的间歇性故障诊断度，主要结论如下：
(1)证明了在不存在不可用边条件下，n维超彼得森网络在PMC诊断模型下的间歇故障诊断性为n?1，且当min{deg(v)|v∈V(HPn)}=r，2≤r≤n时，一个n维的超彼得森网络HPn(n≥3)是(r?1)i可诊断。此外，还证明了n维的超彼得森网络在MM*比较诊断模型下的间歇故障诊断度为n?2。
(2)证明了当网络中存在不可用边条件下，BC互连网络族在PMC诊断模型下是(r?1)i可诊断，BC互连网络族在MM*比较诊断模型的间歇故障诊断度分别为n?2。
(3)利用最小邻居数的概念证明了星型网络在PMC诊断模型下的间歇故障诊断度为n?1。
3.本文研究了平衡超立方网络BHn在PMC诊断模型下的g-扩展条件诊断度，以及BC互连网络族在MM*比较诊断模型下的g-扩展条件诊断性质，得到了如下结论：
(1)当n≥3时，平衡超立方网络BHn在PMC诊断模型下的4-扩展条件诊断度为6n?4，5-扩展条件诊断度为6n?3。
(2)当n≥33，3≤g≤(n?1)/4时，F是Xn的一个g-扩展顶点子集，如果Xn?F中最多存在(n?1)/2个deg(v)=1的顶点，则BC互连网络族在MM*诊断模型下的g-扩展条件诊断度为etg(G)=(g+1)n?g?C2g。