论文部分内容阅读
并行多处理器系统的容错计算一直是研究者关注的问题,识别故障处理器节点的过程称为系统故障诊断。系统的故障诊断,主要分为两种方式,一种是电路级诊断,一种是系统级诊断。在电路级诊断中,处理器必须在实验环境中一一进行检测,这将会使得诊断变得异常复杂且不准确;而系统级诊断则能够由系统自动执行。因此,在大规模处理器系统中,系统级诊断代替电路级诊断成为最常使用的诊断策略。 在目前系统级诊断研究中,常用的诊断模型有两种,分别为PMC模型和MM*模型。在故障识别研究中,除诊断模型外,系统的网络拓扑结构同时也是必须要考虑的关键之一。众所周知,超立方网络结构、交换超立方网络,星型图的诊断度等已被广泛研究。在众多的多处理器网络系统的拓扑结构中,规则互连网络结构无疑是极为重要的一种。究其原因,其一是超立方体网络具有良好的递归性,正则性,对称性,哈密尔顿性,路由算法简单,容错性强等诸多优点。其二是,超立方体网络在商业民用领域已得到广泛应用,如在Intel iPSC/1、iPSC/2和nCUBE机等系统中都采用了超立方体网络结构,甚至其有可能成为未来纳米计算机网络的基本结构。然而,超立方体网络有其缺陷性,其网络规模会随着维度的增大而节点数呈指数级增长。这将极大消耗计算机的硬件成本。 针对常规立方体网络的缺陷,本文分别研究了扩展立方体网络在t/k-可诊断、(t,k)-可诊断和2-good-neighbor可诊断策略下的网络诊断度。在t/k-可诊断策略中,通过对扩展立方体网络的网络特性,根据策略特性对邻接节点的分布进行分析,计算得到测试子集基数的最小下限,从而得到系统的t/k-诊断度。在(t,k)-故障诊断策略中,首先通过图论的方法研究n维扩展立方体网络的重要拓扑性质,依据这些性质设计了一个基于比较模型的算法来寻找该扩展立方体网络的最大非故障组件,然后利用所得的最大非故障组件来确定该网络系统的(t,k)-故障诊断度。最后,提出并证明了刀维扩展立方体网络是(t,2n-1)-可诊断的。而在2-good-neighbor可诊断策略中,条件限定为对于任意的节点,其至少有2个非故障节点,即每一个节点的所有邻接节点均不能同时为故障处理器节点,在该条件限制下,系统的故障诊断度得到了极大极高。最终本文证明了扩展立方体网络的2-good-neighbor诊断度为8n-18。