论文部分内容阅读
诊断度被定义为系统能够诊断出的故障处理器的最大数目.它是多处理器系统故障分析的重要参数,且在衡量互联网络可靠性方面有着重要作用.在1997年,Preparata等首次提出了系统诊断理论.它的优点在于能够自动地检测系统中的处理器.系统级故障理论的研究依赖于模型的建立,因此,许多模型被提出.在这些模型中,两个最重要的模型是由Preparat等提出的PMC模型和由Maeng和Malek提出的MM*模型.PMC模型下的测试主要是通过两个相邻处理器之间相互测试来完成的.MM*模型的测试方式是通过一个顶点向它的两个邻点同时发出一个相同的任务,然后比较它们反馈的结果.传统诊断度认为任一处理器的邻集都可能同时发生故障,然而这种可能性在实际情况中很难出现.在2005年,Lai等对传统诊断理论做了改进,提出了条件诊断度,它要求系统中每个处理器至少与一个非故障处理器相连.在2012年,Peng在条件诊断度的基础上,进一步提出g-好邻条件诊断度.它要求每个非故障处理器至少与g个非故障处理器相邻.连通度在研究故障诊断过程中起着重要作用,它是测量系统容错的重要指标.一个系统的连通度必然不超过它的最小度.随着计算机系统规模的增加,处理器发生故障的可能性必然会增加.为了更好地研究系统的容错性,许多学者就系统连通度问题做了广泛研究.本文研究的g-好邻连通度是传统连通度的一种推广.它是最小的g-好邻割的基数. 本文主要有四个部分.在第一部分中,主要介绍了本文的研究背景及研究现状,图论中的一些基本概念,扩展3元n立方网络AQn,3的定义,以及两种诊断模型,即PMC模型和MM*模型;在第二部分中,我们证明了在n≥4时,扩展3元n立方网络AQn,3在PMC模型和MM*模型下的1-好邻条件诊断度均为8n-lO;在第三部分中,我们证明了在n≥4时,扩展3元n立方网络AQn,3的2-好邻连通度是12n-24,扩展3元n立方网络AQn,3在PMC模型和MM*模型下的2-好邻条件诊断度均为12n-22;在第四部分中,我们对本文的相关结论做了总结.