论文部分内容阅读
连通度和诊断度是度量多处理器系统故障诊断的重要参数.为了保证计算机系统的可靠性,系统中的故障处理器应该被诊断出来并被非故障处理器替换.识别故障处理器的过程称为系统的诊断.诊断度被定义为系统能够被诊断出的故障处理器的最大数目,它在衡量互连网络的可靠性和故障容错方面起着重要的作用.在经典的系统级故障诊断方法中,网络通常被假定为任一处理器的邻集可能同时故障.但是,在大型多处理器系统中这种故障出现的概率极小.因此,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.