【摘要】：連通度和診斷度是度量多處理器系統(tǒng)故障診斷的重要參數(shù).為了保證計(jì)算機(jī)系統(tǒng)的可靠性,系統(tǒng)中的故障處理器應(yīng)該被診斷出來(lái)并被非故障處理器替換.識(shí)別故障處理器的過(guò)程稱(chēng)為系統(tǒng)的診斷.診斷度被定義為系統(tǒng)能夠被診斷出的故障處理器的最大數(shù)目,它在衡量互連網(wǎng)絡(luò)的可靠性和故障容錯(cuò)方面起著重要的作用.在經(jīng)典的系統(tǒng)級(jí)故障診斷方法中,網(wǎng)絡(luò)通常被假定為任一處理器的鄰集可能同時(shí)故障.但是,在大型多處理器系統(tǒng)中這種故障出現(xiàn)的概率極小.因此,Lai等提出了網(wǎng)絡(luò)的條件診斷度,它限制在系統(tǒng)中任意故障集不包含任意頂點(diǎn)的所有鄰點(diǎn).2012年,Peng等提出了g-好鄰診斷度,它限制每個(gè)非故障頂點(diǎn)至少有g(shù)個(gè)非故障鄰點(diǎn).2016年,Zhang等提出了g-限制診斷度,它要求每個(gè)非故障分支至少有g(shù)+1個(gè)非故障頂點(diǎn). 1996年,J. Fabrega和M.A. Fiol提出了g-限制連通度,記作κ(g)(G). n維交叉立方體是超立方體的一個(gè)重要變形.Preparata等首次提出了系統(tǒng)級(jí)故障診斷模型,稱(chēng)為PMC模型.它是通過(guò)兩個(gè)相鄰的處理器之間相互測(cè)試來(lái)完成系統(tǒng)的診斷.Maeng和Malek提出了MM模型.在這個(gè)模型下,一個(gè)頂點(diǎn)向它的兩鄰點(diǎn)發(fā)出相同的任務(wù),然后比較它們反饋的結(jié)果.Sengupta和Dahbura提出了一個(gè)特殊的MM模型,也就是MM*模型,并且在MM*模型中每個(gè)頂點(diǎn)必須測(cè)試它的任意一對(duì)相鄰的頂點(diǎn).如果系統(tǒng)是可診斷的,為了識(shí)別系統(tǒng)中的錯(cuò)誤節(jié)點(diǎn),他們還在MM*模型下提出了一個(gè)多項(xiàng)式算法.下面是本文的主要內(nèi)容:第一章,簡(jiǎn)單介紹一下本文的研究背景和研究現(xiàn)狀,圖論中的一些基本概念,n維交叉立方體CQn的定義,以及兩個(gè)著名的故障診斷模型,即,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 鈮，

本文編號(hào)：2194394