基于比较诊断模型的超立方网络诊断算法

一个有效的诊断算法对多处理器系统而言极其重要。在多处理器系统中,识别所有故障节点的能力称为诊断系统的诊断度。在比较模型下,诊断 的执行是通过一个比较器处理器,给与之相邻的一对处理器发送相同的输入信号,并比较两者间的响应状态。为了提高超立方网络的诊断度,提出了一种新型的基于比较模型的超立方故障诊断算法,其利用超立方网络节点连接的特性生成一个拓扑图ES(k;n),最终得出一个3位二进制的诊断症候集,从而确定系统故障节点。该算法的诊断度最优能达到4n,大于传统超立方的诊断度n。     

PMC模型下网络故障的节点可诊断研究

传统故障诊断研究大多忽略了系统局部特征。PMC模型下,针对于这一问题,引入了节点可诊断的概念,并通过节点可诊断方法的研究得到了节点可诊断度的充分条件和◢t◣-可诊断新算法STFDA。最后,对◢n◣维超立方网络和◢n◣维星状网络从节点可诊断的角度进行了分析,验证了所得充分条件的正确性,并将算法应用到这两种网络中进行故障诊断。其中,充分条件和STFDA算法的实现借助了新的结构ST。STFDA算法的时间复杂度为◢O（Nδ）,δ◣为网络中节点的最大度。相比于其他算法,算法的时间复杂度得到显著降低。     

交换交叉立方网络的g正确邻结点条件诊断度研究

系统级故障诊断是保障多处理器计算机系统运行可靠性的一种重要手段。为了提高系统的诊断能力,增强系统的可靠性,在条件诊断度的基础上Peng等人进一步提出了[g]正确邻结点条件诊断度,[g]正确邻结点条件诊断度是一种更加适用于大规模多处理器计算机系统的故障诊断方式。以新型互连网络拓扑结构研究的最新成果--交换交叉立方网络为研究对象,在得到交换交叉立方网络的[Rg]点连通度的基础上,首次证得交换交叉立方网络[(ECQ(s,t))]在PMC模型下的[g]正确邻结点条件诊断度为[2g(s+2－g)－1],其中[t≥s>g],进而通过模拟实验验证了结论的正确性和有效性。该研究对于理清交换交叉立方网络的可靠性能并有效推动交换交叉立方网络的应用和推广,有着非常重要的理论价值和现实意义。     

增广立方体网络的t/k诊断度研究*

在多处理器系统,传统的t-可诊断算法在处理大规模故障集时有明显的局限性。针对增广立方体诊断度提升的问题,提出了一种t-可诊断的变形算法,即t/k可诊断。在该新算法下,可明显提高增广立方体的诊断度。算法核心思想是,在故障节点个数不大于t的情况下,允许故障集中出现k个非故障节点。从而在牺牲少数非故障节点的情况下,达到提高网络诊断度的目的。最终证明了,增广立方体在t/k诊断算法下的诊断度明显优于传统诊断度和条件诊断度。     

3元◢n◣立方体网络的◢t/k◣可诊断度研究

可诊断度是评估多处理器系统可靠性的一个关键指标.t/k诊断策略通过允许至多k个无故障处理器被误诊为故障处理器,从而极大提高了系统的可诊断度.与t可诊断度和t1/t1可诊断度相比,t/k可诊断度可以更好地反映实际系统的故障模式.3元n立方是一种性质优良并且应用广泛的网络拓扑,在许多分布式多处理器的构建中被用做底层网络.根据一些引理以及确定系统为t/k可诊断的充分条件,研究得出当n≥3及0≤k≤n,3元n立方是tk,n/k-可诊断的,其中tk,n=2(k+1)n-(k+1)(k+2).这个结果显示,在选择恰当的k值时,3元n立方的t/k可诊断度tk,n远大于其t可诊断度2n和t1/t1可诊断度4n-3.     

超立方体网络环诊断策略的研究

多处理器系统的传统故障诊断策略和条件可诊断策略已经被广泛研究,然而并未解决系统中存在的大量故障结点问题。提出一种新的策略--环诊断策略,即通过环分割方法对汉密尔顿环进行诊断,从而找出系统中存在的所有故障结点,并给出了超立方体网络的环诊断策略及一些重要性质。与此同时,提出了超立方体网络的环快速诊断算法,快速定位系统中的所有故障结点。基于以上策略,得到了在PMC模型下,n-维超立方体网络的环诊断度为(n2+n)/2,时间复杂度为O(n),其中n表示多处理器系统中处理器的个数。与超立方体网络的传统故障诊断策略和条件诊断策略相比较, 本文提出的环诊断策略具有诊断度大、时间复杂度小的优点。     

交换超立方网中的最短路径路由算法

针对交换超立方网络的最短路由问题,提出一个交换超立方网中的最短路径路由算法.利用图论的方法,通过引进子网的概念,研究交换超立方网的拓扑性质,给出节点各边可进行最短路径路由的充要条件,得到其时间复杂度为O(s+t)2).理论分析和仿真结果表明,该算法可输出交换超立方网中任意两节点间的一条最短路径.     

k元n立方网络的k圈排除问题的递归算法

为了度量以k元n立方网络为底层网络拓扑的并行计算机系统的容错能力,通过构造k元n立方网络中使得所有的k元1立方子网都发生故障的最小节点集合的方法,提出求解其k元1立方子网排除点割集的一种递归算法;证明了要使k元n立方网络中所有k元1立方子网都发生故障至少需要破坏掉kn-1个节点。结果表明,在不超过kn-1-1个节点被破坏的情况下,以k元n立方网络为底层拓扑构建的并行计算机系统中依然存在无故障的k元1立方子网。     

BCube在2-限制连通度下的容错路由算法

BCube是具有良好性能的数据中心网络.相比传统的树形数据中心网络,BCube在扩展和容错性能方面都表现出很大的优势.目前,对于BCube的研究可以归结为对其逻辑图BCn,k(广义超立方体的一种特例)的研究,其中交换机被视为透明设备.在实际应用中,随着网络规模的不断增加,顶点发生故障已经成为一种常态.因此,研究网络的容错路由很有意义.目前,有不少关于BCn,k容错路由的研究,但其2-限制连通度下的容错路由目前还没有被研究.在提出容错路由算法之前,首先证明了BCn,k的2-限制连通度为3(k+1)(n-1)-2n,其中k≥3且n≥3.然后在此基础上提出了一个时间复杂度为O(κ(BCn,k)3)的容错路由算法,其中κ(BCn,k)=(k+1)(n-1)是BCn,k的连通度.该算法可以在故障顶点个数小于3(k+1)(n-1)-2n且每个无故障顶点至少有两个无故障邻居时找到任意两个不同的无故障顶点之间的一条无故障路径.     

无线传感网络中覆盖保持的K-连通子集构造算法

构造无线传感网络中具有连通覆盖特性的节点子集是实现网络休眠调度、延长网络生命周期的关键技术之一,具有重要的研究意义.已有的研究大多侧重于k覆盖节点子集构造问题,由于k覆盖子集在一定条件下便满足k连通,故人们对k连通子集的构造问题研究较少,但通过构造k覆盖节点子集来实现k连通会耗费过多的节点,代价较大.因此,本文提出一个直接构造k连通1覆盖节点子集的算法-CPC,能够用较少的节点构造出一个既能满足网络的覆盖特性又能够满足k-连通特性的节点子集,使得在任意k-1个节点发生故障时,网络能够仍然保持连通.本文还对算法的正确性进行了严格证明,并通过仿真实验与相关算法进行了性能比较.结果表明,与已有的k覆盖算法相比,CPC算法能够节省约55%的节点数.     

A Local Diagnosability Measure for Multiprocessor Systems

The problem of fault diagnosis has been discussed widely and the diagnosability of many well-known networks has been explored. Under the PMC model, we introduce a new measure of diagnosability, called local diagnosability, and derive some structures for determining whether a vertex of a system is locally t-diagnosable. For a hypercube, we prove that the local diagnosability of each vertex is equal to its degree under the PMC model. Then, we propose a concept for system diagnosis, called the strong local diagnosability property. A system G(V, E) is said to have a strong local diagnosability property if the local diagnosability of each vertex is equal to its degree. We show that an n-dimensional hypercube Q_n has this strong property, nges3. Next, we study the local diagnosability of a faulty hypercube. We prove that Q_n keeps this strong property even if it has up to n-2 faulty edges. Assuming that each vertex of a faulty hypercube Q_n is incident with at least two fault-free edges, we prove Q_n keeps this strong property even if it has up to 3(n-2)-1 faulty edges. Furthermore, we prove that Q_n keeps this strong property no matter how many edges are faulty, provided that each vertex of a faulty hypercube Q_n is incident with at least three fault-free edges. Our bounds on the number of faulty edges are all tight     

Conditional fault diagnosis of hierarchical hypercubes

The design of large dependable multiprocessor systems requires quick and precise mechanisms for detecting the faulty nodes. The system-level fault diagnosis is the process of identifying faulty processors in a system through testing. This paper shows that the largest connected component of the survival graph contains almost all remaining vertices in the hierarchical hypercube HHC _n when the number of faulty vertices is up to two or three times of the traditional connectivity. Based on this fault resiliency, we establish that the conditional diagnosability of HHC _n (n=2 ^m +m, m≥2) under the comparison model is 3m?2, which is about three times of the traditional diagnosability.     

A fast diagnosis algorithm for interconnection network in high performance computers

In high performance computers, a popular interconnection network, the folded hypercube (FHC), possesses smaller diameter, larger connectivity, better reliability and fault tolerance capability as compared with a hypercube counterpart. This paper addresses the fault identification of FHC multiprocessor interconncection systems under the MM^* model. The pessimistic one-step diagnosability of FHC networks is first determined. On the basis, a pessimistic one-step diagnosis algorithm tailored for FHC multiprocessor systems is proposed. The presented algorithm can isolate all faulty nodes to within a set which has at most one fault-free node, and can run in linear time.     

The conditional diagnosability of crossed cubes under the comparison model

The growing size of the multiprocessor systems increases their vulnerability to component failures. It is crucial to locate and replace the faulty processors to maintain the system's high reliability. The fault diagnosis is the process of identifying faulty processors in a system through testing. The conditional diagnosis requires that for each processor v in a system, all the processors that are directly connected to v do not fail simultaneously. In this paper, we show that the conditional diagnosability of the crossed cubes CQ _n under the comparison diagnosis model is 3n?5 when n≥7. Hence, the conditional diagnosability of CQ _n is three times larger than its classical diagnosability.     

On the maximal connected component of hypercube with faulty vertices (II)

In evaluating the fault tolerance of an interconnection network, it is essential to estimate the size of a maximal connected component of the network at the presence of faulty processors. Hypercube is one of the most popular interconnection networks. In this paper, we prove that for n?≥?6, an n-dimensional cube with a set F of at most (4n???10) failing processors has a component of size ≥2″???|F|???3. This result demonstrates the superiority of hypercube in terms of the fault tolerance.     

Conditional diagnosability and strong diagnosability of shuffle-cubes under the comparison model

The growing size of multiprocessor systems increases the vulnerability to component failures. It is crucial to locate and replace faulty processors to maintain the system's high reliability. Processor fault diagnosis is essential to the reliability of a multiprocessor system and the diagnosabilities of many well-known networks (such as hierarchical hypercubes and crossed cubes [S. Zhou, L. Lin and J.-M. Xu, Conditional fault diagnosis of hierarchical hypercubes, Int. J. Comput. Math. 89(16) (2012), pp. 2152–2164 and S. Zhou, The conditional diagnosability of crossed cubes under the comparison model, Int. J. Comput. Math. 87(15) (2010), pp. 3387–3396]) have been investigated in the literature. A system is t-diagnosable if all faulty nodes can be identified without replacement when the number of faults does not exceed t, where t is some positive integer. Furthermore, a system is strongly t-diagnosable if it is t-diagnosable and can achieve (t+1)-diagnosability except for the case where a node's neighbours are all faulty. In addition, conditional diagnosability has been widely accepted as a new measure of diagnosability by assuming that any fault-set cannot contain all neighbours of any node in a multiprocessor system. In this paper, we determine the conditional diagnosability and strong diagnosability of an n-dimensional shuffle-cube SQ_n, a variant of hypercube for multiprocessor systems, under the comparison model. We show that the conditional diagnosability of shuffle-cube SQ_n (n=4k+2 and k≥2) is 3n?9, and SQ_n is strongly n-diagnosable under the comparison model.     

A Low-Cost Fault-Tolerant Structure for the Hypercube

We propose a new, low-cost fault-tolerant structure for the hypercube that employs spare processors and extra links. The target of the proposed structure is to fully tolerate the first faulty node, no matter where it occurs, and almost fully tolerate the second, meaning that the underlying hypercube topology can be resumed if the second faulty node occurs at most locations—expectantly 92% of locations. The unique features of our structure are that (1) it utilizes the unused extra link-ports in the processor nodes of the hypercube to obtain the proposed topology, so that minimum extra hardware is needed in constructing the fault-tolerant structure and (2) the structure's node-degrees are low as desired—the primary and spare nodes all have node-degrees of n + 2 for an n-dimensional hypercube. The number of spare nodes is one fourth of primary nodes. The reconfiguration algorithm in the presence of faults is elegant and efficient. The proposed structure also effectively enhances the diagnosability of the hypercube system. It is shown that the diagnosability of the structure is increased to n + 2, whereas an ordinary n-dimensional hypercube has diagnosability n.     

在PMC模型下单向k元n立方体的诊断度

图的连通度和诊断度是与互连网络的可靠性密切相关的两个参数,而[g]好邻连通度和[g]好邻诊断度是比连通度和诊断度更精确的指标。[k]元[n]立方体是多处理机系统的最常用网络之一,而单向[k]元[n]立方体是指具有单向边的[k]元[n]立方体。证明了当[k≥3,n≥3]时,单向[k]元[n]立方体在PMC模型下的[1]好邻连通度是[k(n-1)],诊断度是[n]且[1]好邻诊断度是[kn-1]。