n维交叉立方体的连通度和诊断度
发布时间：2018-08-20 17:14
【摘要】：连通度和诊断度是度量多处理器系统故障诊断的重要参数.为了保证计算机系统的可靠性,系统中的故障处理器应该被诊断出来并被非故障处理器替换.识别故障处理器的过程称为系统的诊断.诊断度被定义为系统能够被诊断出的故障处理器的最大数目,它在衡量互连网络的可靠性和故障容错方面起着重要的作用.在经典的系统级故障诊断方法中,网络通常被假定为任一处理器的邻集可能同时故障.但是,在大型多处理器系统中这种故障出现的概率极小.因此,Lai等提出了网络的条件诊断度,它限制在系统中任意故障集不包含任意顶点的所有邻点.2012年,Peng等提出了g-好邻诊断度,它限制每个非故障顶点至少有g个非故障邻点.2016年,Zhang等提出了g-限制诊断度,它要求每个非故障分支至少有g+1个非故障顶点. 1996年,J. Fabrega和M.A. Fiol提出了g-限制连通度,记作κ(g)(G). n维交叉立方体是超立方体的一个重要变形.Preparata等首次提出了系统级故障诊断模型,称为PMC模型.它是通过两个相邻的处理器之间相互测试来完成系统的诊断.Maeng和Malek提出了MM模型.在这个模型下,一个顶点向它的两邻点发出相同的任务,然后比较它们反馈的结果.Sengupta和Dahbura提出了一个特殊的MM模型,也就是MM*模型,并且在MM*模型中每个顶点必须测试它的任意一对相邻的顶点.如果系统是可诊断的,为了识别系统中的错误节点,他们还在MM*模型下提出了一个多项式算法.下面是本文的主要内容:第一章,简单介绍一下本文的研究背景和研究现状,图论中的一些基本概念,n维交叉立方体CQn的定义,以及两个著名的故障诊断模型,即,PMC模型和MM*模型.第二章,我们首先证明了n维交叉立方体CQn的1-好邻连通度是2n-2 (n≥4).然后,我们又证明了n维交叉立方体CQn在PMC模型(n ≥ 4)和MM*模型(n ≥ 5)下的1-好邻诊断度是2n-1.第三章,我们首先证明了n维交叉立方体CQn的2-限制连通度是3n-5 (n ≥ 5)以及n维交叉立方体CQn (n ≥ 5)是(3n-5)紧超2-限制连通的.然后,我们又证明了n维交叉立方体CQn 在PMC模型(n≥5)和MM*模型(n≥6)下的 -限制诊断度是3n 3.第四章,我们首先证明了n维交叉立方体CQn的2-好邻连通度是4n - 8 (n ≥ 5)以及n维交叉立方体CQn(n≥ 6)是(4n-8)紧超2-好邻连通的.然后,我们又证明了n维交叉立方体CQn 在PMC模(n≥ 5)和MM* 模型(n 5) 下的2-好邻诊断度是4n - 5.第五章,我们首先证明了n维交叉立方体CQn的3-限制连通度是4n-9(n≥5)以及n维交叉立方体CQ(n ≥ 7)是(4n-9)紧超3-限制连通的.然后,我们又证明了n维交叉立方体CQn在PMC模型(n≥5)和MM*模型(n ≥ 7)下的3-限制诊断度是4n - 6.
[Abstract]:Connectivity and diagnosis are important parameters to measure fault diagnosis of multiprocessor systems. In order to ensure the reliability of the computer system, the fault processor in the system should be diagnosed and replaced by the non-fault processor. The process of identifying a fault processor is called system diagnosis. Diagnostic degree is defined as the maximum number of fault processors the system can be diagnosed. It plays an important role in measuring the reliability and fault tolerance of interconnection networks. In the classical system level fault diagnosis method, the network is usually assumed to be the neighbor set of any processor may fail at the same time. However, in large multiprocessor systems, the probability of this failure is minimal. Therefore, Lai et al proposed the conditional diagnostic degree of the network, which is limited to all adjacent points in any fault set of the system without any vertex. In 2012, Peng et al proposed the g- good neighbor diagnostic degree. It limits every non-fault vertex to have at least g non-fault adjacent points. In 2016, Zhang et al proposed g- restricted diagnostic degree, which requires every non-fault branch to have at least one non-fault vertex. In 1996, J. Fabrega and M. A. Fiol proposed g- restricted connectivity, which is described as 魏 (g) (G). N dimensional cross cube, which is an important deformation of hypercube. The system-level fault diagnosis model, called PMC model, is proposed for the first time. It uses two adjacent processors to test each other to complete the diagnosis of the system. Maeng and Malek put forward the MM model. In this model, a vertex sends the same task to its two neighboring points, and then compares their feedback results. Sengupta and Dahbura propose a special MM model, which is called MM* model. And in the MM* model, each vertex must be tested for any pair of adjacent vertices. If the system is diagnosable, in order to identify the wrong nodes in the system, they also propose a polynomial algorithm based on the MM* model. The following are the main contents of this paper: in Chapter 1, the research background and present situation of this paper, the definition of some basic concepts in graph theory, CQn, and two famous fault diagnosis models are briefly introduced. PMC model and MM* model. In chapter 2, we first prove that the 1-good neighbor connectivity of n-dimensional crossed cube CQn is 2n-2 (n 鈮，
本文编号：2194394
[Abstract]:Connectivity and diagnosis are important parameters to measure fault diagnosis of multiprocessor systems. In order to ensure the reliability of the computer system, the fault processor in the system should be diagnosed and replaced by the non-fault processor. The process of identifying a fault processor is called system diagnosis. Diagnostic degree is defined as the maximum number of fault processors the system can be diagnosed. It plays an important role in measuring the reliability and fault tolerance of interconnection networks. In the classical system level fault diagnosis method, the network is usually assumed to be the neighbor set of any processor may fail at the same time. However, in large multiprocessor systems, the probability of this failure is minimal. Therefore, Lai et al proposed the conditional diagnostic degree of the network, which is limited to all adjacent points in any fault set of the system without any vertex. In 2012, Peng et al proposed the g- good neighbor diagnostic degree. It limits every non-fault vertex to have at least g non-fault adjacent points. In 2016, Zhang et al proposed g- restricted diagnostic degree, which requires every non-fault branch to have at least one non-fault vertex. In 1996, J. Fabrega and M. A. Fiol proposed g- restricted connectivity, which is described as 魏 (g) (G). N dimensional cross cube, which is an important deformation of hypercube. The system-level fault diagnosis model, called PMC model, is proposed for the first time. It uses two adjacent processors to test each other to complete the diagnosis of the system. Maeng and Malek put forward the MM model. In this model, a vertex sends the same task to its two neighboring points, and then compares their feedback results. Sengupta and Dahbura propose a special MM model, which is called MM* model. And in the MM* model, each vertex must be tested for any pair of adjacent vertices. If the system is diagnosable, in order to identify the wrong nodes in the system, they also propose a polynomial algorithm based on the MM* model. The following are the main contents of this paper: in Chapter 1, the research background and present situation of this paper, the definition of some basic concepts in graph theory, CQn, and two famous fault diagnosis models are briefly introduced. PMC model and MM* model. In chapter 2, we first prove that the 1-good neighbor connectivity of n-dimensional crossed cube CQn is 2n-2 (n 鈮，
本文编号：2194394
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/2194394.html
