許多多重處理器系統(tǒng)用互連網(wǎng)絡(luò)(簡稱網(wǎng)絡(luò))作為它的基礎(chǔ)拓?fù)洳⑶揖W(wǎng)絡(luò)通常用圖表示,其中頂點表示處理器,邊表示處理器之間的通信鏈路.我們交替使用圖和網(wǎng)絡(luò).連通度是衡量互連網(wǎng)絡(luò)容錯性的重要參數(shù).由于一個大規(guī)模的計算機(jī)系統(tǒng)是由成千上萬個計算機(jī)處理器組成,因此在這種復(fù)雜的操作環(huán)境下會有更多的處理器可能發(fā)生故障.為了更好的研究系統(tǒng)的容錯性,1996年,J.Fabreg和M.A.Fiol提出了互聯(lián)網(wǎng)絡(luò)的k-限制連通度.診斷度是度量多重處理器系統(tǒng)故障診斷能力的重要參數(shù).然而,在系統(tǒng)中一些處理器可能是故障的.所以,為了保證計算機(jī)系統(tǒng)的可靠性,系統(tǒng)中的故障處理器應(yīng)該被診斷出來并被非故障處理器替換.識別故障處理器的過程被稱為系統(tǒng)診斷.診斷度被定義為系統(tǒng)能夠被診斷出的故障處理器的最大數(shù)目.傳統(tǒng)的診斷度允許點的鄰點全為故障點.但是在大型多重處理器系統(tǒng)中這種故障出現(xiàn)的概率極小.因此,2015年,Lai等提出了系統(tǒng)的條件診斷度,它限制系統(tǒng)中任意一個處理器至少與一個非故障處理器相鄰.2012年,Peng等提出了系統(tǒng)的g-好鄰診斷度,它限制每個非故障頂點都至少有9個非故障點與之相鄰.并且研究了超立方體在PMC模型下的g-好鄰診斷度.為了測量多重處理器系統(tǒng)的診斷度,很多診斷模型已經(jīng)被提出.尤其是PMC模型和MM*模型,這兩個模型被廣泛使用.在PMC模型和MM*模型下已經(jīng)有許多的研究成果.下面是本文的主要內(nèi)容:第一章:簡單介紹一下本文的研究背景和研究現(xiàn)狀,給出圖論中的一些基本概念,擴(kuò)展k元n立方體AQn,k和交換交叉立方體ECQ(s,t)的定義,以及兩個著名的故障診斷模型(PMC模型和MM*模型).第二章:證明了擴(kuò)展k元n立方體在PMC模型和MM*模型下的1-好鄰診斷度是8n-9(n≥ 4,k≥ 4).第三章:證明了交換交叉立方體ECQ(s,t)的2-限制連通度是3s-2(2 ≤ s ≤第四章:工作總結(jié).
【學(xué)位單位】：河南師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2018
【中圖分類】：O157.5
【部分圖文】：

第一章緒論｝．逡逑Ｇ邋Ｖ（Ｇ）邋－邋Ｆ，邋ｒ；邋Ｇ邋兄則邋ａ（ｕ？）邋＝邋１；逡逑ｅ邋Ｖ（Ｇ）邋－邋Ｆ，則邋＝邋０．逡逑）中任意兩個不同的頂點子集巧和ｆ２，若（Ｔ＾）邋ｎ，記（N銑В玻┦強(qiáng)汕侄裕簦幔ǎ

本文編號：2827961